面向SIMD机器的全局自动数据分割  

GLOBAL DATA AND LOOPS PARTITIONING FOR SIMD MACHINES

作　　者：林进[1] 朱宁宁[1] 张兆庆[1] 乔如良[1] 

机构地区：[1]中国科学院计算技术研究所,北京100080

出　　处：《计算机学报》1999年第6期596-602,共7页Chinese Journal of Computers

摘　　要：提出了一种面向ＳＩＭＤ机器的全局数据自动分割算法，该算法能处理多个非紧嵌的循环嵌套，并且数组下标存取式为循环变量的线性式．首先通过数据与迭代映射抽象出计算中的通信方式，然后提出识别规则模式通信模式的形式化条件．接着建立包含对准信息和相应通信开销的数据迭代图，并在数据迭代图的基础上提出一个启发式算法来计算较优的数据分布和迭代分布，以优化处理单元之间的通信开销．通过分析多个循环嵌套所涉及的多个数组映射和迭代映射之间复杂的相互制约关系，从全局的角度求得一个较优的数据迭代分布方案．该算法已经用于面向ＳＩＭＤ机器的自动并行编译器的设计和实现中．实验结果表明，它在减少通信开销上有着显著的成效．This paper describes a compiler algorithm for SIMD machines that automatically finds computation and data arrays distribution so optimize the communication between the processor elements of SIMD machines with distributed local memory. The algorithm can handle programs with general non perfect loop nests where the array accesses are affine functions of the loop indices.In this framework, matrices are used to represent the mapping of loops space and data space onto the processor space. The general communication in the computation is formulated first based on the mapping of the data and loops onto the processor elements. Then, the formal conditions for detecting the regular pattern communication are derived. The data and loops graph is built to model affine communication. Finally, a heuristic method based on data and loops graph is devised to derive an optimal loop and data partitioning for reusing the data across multiple loop nests and optimizing the communication. These ideas are adopted in the design and implementation of a parallelizing compiler targeted on the SIMD machines. This paper also demonstrates the efficiency of this approach with encouraging experimental results.

关 键 词：数据分布 并行编译器 数据分割 SIMD机器 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论] TP314[自动化与计算机技术—计算机科学与技术]