Communication-Optimal Loop Nests
Communication-Optimal Loop Nests
复制标题
通信最佳循环嵌套
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Nicholas Knight
中科院分区：
文献类型：
--
作者：
Nicholas Knight
通信(数据移动)通常主导计算的运行时间和能源成本，促使组织算法的操作以最大限度地减少通信。我们研究了一类算法的通信开销，这些算法包括多体计算和矩阵/张量计算，更一般地，循环嵌套操作于由循环迭代向量的线性函数下标的数组变量上。我们使用变量和运算之间的这种代数关系来推导出这些算法的通信下界。我们还讨论了达到这些界限的通信优化实现。
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.