关键词：通讯；最优算法；程序；最小通信；矩阵乘法
摘 要：Communication, i.e., moving data, between levels of a memory hierarchy or between parallel processors on a network, can greatly dominate the cost of computation, so algorithms that minimize communication can run much faster (and use less energy) than algorithms that do not. Motivated by this, attainable communication lower bounds were established in [12, 13, 4] for a variety of algorithms including matrix computations.The resultapplies to recursive programs, irregular iteration spaces, sparse matrices, and other data structures as long asthe computation can be logically mapped to loops and indexed data structure accesses. We also discuss whenoptimal algorithms exist that attain the lower bounds; this leads to new asymptotically faster algorithms forseveral problems.