Communication Avoiding Algorithms: Analysis and Code Generation for Parallel Systems
Communication Avoiding Algorithms: Analysis and Code Generation for Parallel Systems
复制标题
通信避免算法：并行系统的分析和代码生成
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
J. Mellor
中科院分区：
文献类型：
--
作者：
K. Murthy;J. Mellor
对于子孙后代，数据移动是一个关键的瓶颈。开发了.5D避免通信的算法的类别来解决此瓶颈。这些算法减少了交流，并在时间和能量上提供了强大的缩放。作为自动开发避免通信效果的第一步，我们开发了Maunam编译器。 Maunam从使用符号数据大小和处理器数量表示的.5D算法的高级全局视图草图中生成有效的并行代码。它支持数据流动和通信的表达，直到最高级别的全局操作，例如倾斜和cshift以及通过元素副本操作。使用后者，也可以使用基于Modulo操作的下标进行围绕通信模式。 Maunam采用多面体分析来推理.5D算法中存在的通信和计算。在分区数据和计算之后，它根据需要插入点对点和集体通信。 Maunam还分析了数据依赖模式和数据布局，以确定对处理器子集的减少。 Maunam生成的FORTRAN+MPI代码，用于2.5D矩阵乘法在4096个芯上运行的Cray XC30超级计算机的核心，可实现59 Tflops/s（占机器峰的76％）。我们生成的并行代码可实现手工编码版本的性能的91％。
Data movement is a critical bottleneck for future generations of parallel systems. The class of .5D communication-avoiding algorithms were developed to address this bottleneck. These algorithms reduce communication and provide strong scaling in both time and energy. As a firststep towards automating the development of communication-avoiding-libraries, we developed the Maunam compiler. Maunam generates efficient parallel code from a high-level, global view sketch of .5D algorithms that are expressed using symbolic data sizes and numbers of processors. It supports the expression of data movement and communication through-high-level global operations such as TILT and CSHIFT as well as through element-wise copy operations. With the latter, wrap around communication patterns can also be achieved using subscripts based on modulo operations. Maunam employs polyhedral analysis to reason about communication and computation present in a .5D algorithm. After partitioning data and computation, it inserts point-to-point-and collective communication as needed. Maunam also analyzes data dependence patterns and data layouts to identify reductions over processor subsets. Maunam-generated Fortran+MPI code for 2.5D matrix multiplication running on 4096 cores of a Cray XC30 super computer achieves 59 TFlops/s (76% of the machine peak). Our generated parallel code achieves 91% of the performance of a hand-coded version.