Communication-avoiding algorithm

Communication-avoiding algorithms are a class of algorithms designed to minimize the movement of data through a memory hierarchy, rather than only minimizing the number of arithmetic operations performed. In this context, communication means moving data either between levels of a memory hierarchy or between multiple processors across a network, and it is markedly more costly in time and energy than the arithmetic itself. A communication-avoiding algorithm restructures a computation so that the combined cost of arithmetic and communication is minimized, which matters most on large-scale parallel and distributed systems where data movement, not computation, is the dominant bottleneck on running time and energy consumption.