Communication-avoiding algorithm

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Communication-avoiding algorithms minimize movement of data within a memory hierarchy for improving its running-time and energy consumption. These minimize the total of two costs (in terms of time and energy): arithmetic and communication. Communication, in this context refers to moving data, either between levels of memory or between multiple processors over a network. It is much more expensive than arithmetic.

Communication-avoiding algorithms minimize movement of data within a memory hierarchy for improving its running-time and energy consumption. These minimize the total of two costs (in terms of time and energy): arithmetic and communication. Communication, in this context refers to moving data, either between levels of memory or between multiple processors over a network. It is much more expensive than arithmetic. {{Math proof|title=Proof|proof= We can draw the computation graph of D = AB + C as a cube of lattice points, each point is of form (i,j,k) .

Since D[i,k] = \sum_j A[i,j]B[j,k] + C[i,k] , computing AB+C requires the processor to have access to each point within the cube at least once. So the problem becomes covering the mnk lattice points with a minimal amount of communication. If M is large, then we can simply load all mn+nk+mk entries then write nk entries. This is uninteresting. If M is small, then we can divide the minimal-communication algorithm into separate segments. During each segment, it performs exactly M reads to cache, and any number of writes from cache.

During each segment, the processor has access to at most 2M different points from A, B, C . Let E be the set of lattice points covered during this segment. Then by the Loomis–Whitney inequality, |E| \leq \sqrt with constraint \sum_i |\pi_i(E)| \leq 2M . By the inequality of arithmetic and geometric means, we have |E| \leq \left(\frac 23 M\right)^{3/2} , with extremum reached when \pi_i(E) = \frac 23 M . Thus the arithmetic intensity is bounded above by CM^{1/2} where C = (2/3)^{3/2} , and so the communication is bounded below by \frac{nmk}{CM^{1/2}} .

Direct computation verifies that the tiling matrix multiplication algorithm reaches the lower bound. }} Measure of computation = Time per FLOP = γ Measure of communication = No. of words of data moved = β ⇒ Total running time = γ·(no. of FLOPs) + β·(no. of words) From the fact that β >> γ as measured in time and energy, communication cost dominates computation cost. Technological trends indicate that the relative cost of communication is increasing on a variety of platforms, from cloud computing to supercomputers to mobile devices.

The report also predicts that gap between DRAM access time and FLOPs will increase 100× over coming decade to balance power usage between processors and DRAM. Energy consumption increases by orders of magnitude as we go higher in the memory hierarchy. United States president Barack Obama cited communication-avoiding algorithms in the FY 2012 Department of Energy budget request to Congress: Let A, B and C be square matrices of order n × n.

The following naive algorithm implements C = C + A * B: for i = 1 to n for j = 1 to n for k = 1 to n C(i,j) = C(i,j) + A(i,k) * B(k,j) Arithmetic cost (time-complexity): n 2 (2n − 1) for sufficiently large n or O(n 3 ).

Rewriting this algorithm with communication cost labelled at each step for i = 1 to n {read row i of A into fast memory} - n 2 reads for j = 1 to n {read C(i,j) into fast memory} - n 2 reads {read column j of B into fast memory} - n 3 reads for k = 1 to n C(i,j) = C(i,j) + A(i,k) * B(k,j) {write C(i,j) back to slow memory} - n 2 writes Fast memory may be defined as the local processor memory (CPU cache) of size M and slow memory may be defined as the DRAM.

Communication cost (reads/writes): n 3 + 3n 2 or O(n 3 ) Since total running time = γ·O(n 3 ) + β·O(n 3 ) and β >> γ the communication cost is dominant.

The blocked (tiled) matrix multiplication algorithm reduces this dominant term: for i = 1 to n/b for j = 1 to n/b {read block C(i,j) into fast memory} - b 2 × (n/b) 2 = n 2 reads for k = 1 to n/b {read block A(i,k) into fast memory} - b 2 × (n/b) 3 = n 3 /b reads {read block B(k,j) into fast memory} - b 2 × (n/b) 3 = n 3 /b reads C(i,j) = C(i,j) + A(i,k) * B(k,j) - {do a matrix multiply on blocks} {write block C(i,j) back to slow memory} - b 2 × (n/b) 2 = n 2 writes Communication cost: 2n 3 /b + 2n 2 reads/writes 3 arithmetic cost Making b as large possible: 3b 2 ≤ M we achieve the following communication lower bound: 3 1/2 n 3 /M 1/2 + 2n 2 or Ω (no. of FLOPs / M 1/2 )

See also

Data locality

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378729510 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001378729510 · captured 1791233392.0 · version history

Cite this page as: encyclopegia.org, “Communication-avoiding algorithm”, snapshot enwiki-001378729510. https://encyclopegia.org/a/communication-avoiding-algorithm

Sources cited in this revision

6 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.