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

摘要

提出了一种面向SIMD机器的全局数据自动分割算法,该算法能处理多个非紧嵌的循环嵌套,并且数组下标存取式为循环变量的线性式.首先通过数据与迭代映射抽象出计算中的通信方式,然后提出识别规则模式通信模式的形式化条件.接着建立包含对准信息和相应通信开销的数据迭代图,并在数据迭代图的基础上提出一个启发式算法来计算较优的数据分布和迭代分布,以优化处理单元之间的通信开销.通过分析多个循环嵌套所涉及的多个数组映射和迭代映射之间复杂的相互制约关系,从全局的角度求得一个较优的数据迭代分布方案.该算法已经用于面向SIMD机器的自动并行编译器的设计和实现中.实验结果表明,它在减少通信开销上有着显著的成效.