基于相关性分析的障碍同步消除算法

AN ALGORITHM FOR BARRIER SYNCHRONIZATION REMOVAL BASED ON DEPENDENCE ANALYSIS

同步控制是并行执行中的主要开销源之一．本文以Fortran77串行程序自动转换为MPPFortran并行程序为背景，提出了一种减少数据并行程序中障碍同步开销的优化算法．根据数据并行程序中显式的数据分布与工作划分，处理机间的相关性分析可用于消除程序中不必要的障碍同步，改善程序的并行性能．我们使用一组标准测试程序对算法的有效性进行了测试，测试结果表明平均26％的障碍同步可消除．算法的基本思想同样适用于其它数据并行语言程序的障碍同步优化．

Barrier synchronization is one of the main sources of overhead in parallel execution. Thispaper introduces an optimization algorithm for reducing barrier synchronization overhead in dataparallel programs. According to data distribution and workload partition explicitly specified in dataparallel programs, inter--processor data dependence analysis can remove unnecessary barriersynchronization and improve parallel program performance. The authors evaluated the algorithm usingstandard benchmark suite. Experimental results show that barrier synchronization is removed 26%on average. Although this study is conducted on the basis of automatically translating Fortran 77serial codes to MPP Fortran parallel form, the algorithm can also be applied to barriersynchronization optimization in other data parallel language programs.