自动并行化中不规则循环的通信代码生成

Communication code generation for automatic parallelization of irregular loops

不规则计算在大规模并行应用中广泛存在。在面向分布存储结构的自动并行化过程中,较难在编译时为不规则循环生成并行代码。并行代码中的通信代码对程序运行结果的正确性以及加速效果有着严重的影响。通过分析程序的数组重分布图,使用部分冗余的通信方式来维持不规则数组访问的生产者-消费者关系,可以在编译时为一类常见的不规则循环自动生成有效的通信代码。该方法使用计算分解和数组引用的访问表达式求解不规则数组在各处理器的本地定义集作为通信的数据集,分析针对此类不规则循环划分的通信策略,继而生成相应的通信代码。实验测试的结果取得了预期的加速效果,验证了方法的有效性。

Irregular computing exists in large scale parallel application widely and the automatic parallelization on distributed memory is hardly to generate parallel code for irregular loops at compile-time.The communication code of the parallel code influences the correctness and the efficiency to the runout of the program.It could automatically generate useful communication code for a common class of irregular loops at compile-time by using the approach of partial communication redundancy,that needed analyzing the array redistribution graph of the program to maintain the producer-consumer relation of irregular array references.The approach searched the local definition set of the irregular array on each processor by computation decomposition and accessed expression of array references as the communication data set,then analyzed the communication strategies for such irregular loops and generated the corresponding communication code.The experimental results show the validity of the approach and the expectant speedup of test applications.