利用U模变换增加并行粒度与改善数据访问局部性的方法  

Increase Parallel Granularity and Data Locality by Unimodular Metrics

作　　者：马国凯[1] 王欣孃[1] 王鹏[1] 臧斌宇[1] 朱传琪[1] 

机构地区：[1]复旦大学并行处理研究所,上海200433

出　　处：《计算机学报》2004年第4期516-523,共8页Chinese Journal of Computers

基　　金：到国家自然科学基金 ( 60 2 73 0 46);上海市科学技术委员会重点基础项目基金( 0 2JC14 0 13 )资助

摘　　要：提出了一种利用循环变换增加循环并行粒度 ,改善循环数据访问局部性的方法 .该方法利用了给定二重循环的相关向量集的某些性质 ,将外层循环变量不同而内层循环变量相等的若干次迭代合并 ,成为折叠后迭代空间的一个结点 ,并且保持内层循环的并行性不变 ,从而达到增加循环并行粒度的目的 .对于更普遍的情况 ,该文讨论了如何根据给定循环的循环向量集 ,确定一个U模变换对迭代空间进行变换 ,达到内层循环可并行和扩大循环粒度两个目的 .针对循环变换中数据访问局部性可能变差的问题 ,该文提出了对内层循环先合并 ,根据合并后的相关向量集变换迭代空间 ,以及折叠迭代空间的方法 .该文的方法是wavefront循环并行化方法的一种扩展 .We discusses a loop transformation method which would increase the granularity of the loop body and improve the data locality of the transformed loop. By analyzing the dependence vector set of the given nested double-loop, we could merge several nodes in the iteration space, which have same outer loop variable value and different inner loop variable value into one node in the folded iteration space, while preserving the parallelism of inner loop at the same time. Thus, we increased the granularity of the parallel loop body. Furthermore, we discussed how to find a unimodular metrics to transform the given iteration space with the given dependence into an iteration space in which iteration nodes could be merged using our methods given above. We also present a method to preserve the locality of the original loop while doing our loop transformation and iteration space folding. Our method discussed in this article is the generalization of the wavefront method. Compared with the wavefront method, our method can achieve higher performance due to larger granularity and better data locality. We apply our method to ygx, a program of the IAPCM Benchmark, to evaluate the effect of the technique. The experiment data show that our method can spare the execution time by 22% compared with the wavefront method when the program is parallel processed by 4 CPU's on SGI origin 200 system which is a typical 4 CPU's SMP architecture.

关 键 词：循环变换 并行化编译 U模变换 迭代空间折叠 数据访问局部性 wavefront方法 

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