Communication-Optimal Loop Nests

Communication (data movement) often dominates a computation’s runtime and energy
costs, motivating organizing an algorithm’s operations to minimize communication. We
study communication costs of a class of algorithms including many-body and matrix/tensor
computations and, more generally, loop nests operating on array variables subscripted by
linear functions of the loop iteration vector. We use this algebraic relationship between
variables and operations to derive communication lower bounds for these algorithms. We
also discuss communication-optimal implementations that attain these bounds.

Technical Report

Author: Nicholas Knight
Publication Date: August 2015
Conference: Technical Report No. UCB/EECS-2015-185