Communication-Avoiding Algorithms

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.

Consider the following running-time model:

⇒ 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 100x 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:“New Algorithm Improves Performance and Accuracy on Extreme-Scale Computing Systems. On modern computer architectures, communication between processors takes longer than the performance of a floating point arithmetic operation by a given processor. ASCR researchers have developed a new method, derived from commonly used linear algebra methods, to minimize communications between processors and the memory hierarchy, by reformulating the communication patterns specified within the algorithm. This method has been implemented in the TRILINOS framework, a highly-regarded suite of software, which provides functionality for researchers around the world to solve large scale, complex multi-physics problems.”

Communication-Avoiding algorithms are designed with the following objectives:

The following simple example demonstrates how these are achieved.

Let A, B and C be square matrices of order n x n. The following naive algorithm implements C = C + A * B:

...
Wikipedia