循环变换增加并行粒度与改善数据访问局部性

摘要

该文在迭代空间变换的基础上,提出了一种利用循环变换增加循环并行粒度,改善循环数据访问局部性的方法.首先针对循环并行粒度的问题,该文利用了给定二重循环的相关向量集的某些性质,对迭代空间进行折叠,将外层循环变量不同,而内层循环变量相等的若干次迭代合并,成为折叠后迭代空间的一个结点,并且保持内层循环的并行性不变,从而达到增加循环并行粒度的目的.对于更普遍的情况,该文讨论了如何根据给定循环的循环向量集,确定一个循环变换对迭代空间进行变换,达到内层循环可并行和扩大循环粒度两个目的.其次针对循环变换中数据访问局部性可能变差的问题,该文从原程序的循环是局部性良好的循环这一前提假设出发,提出了对内层循环的不同迭代先合并,根据合并后的相关向量集变换迭代空间,以及折叠迭代空间的方法.这种方法能够在保持扩大循环粒度效果的基础上,达到保持原程序数据访问局部性的效果.该文从实际应用的角度出发,能够达到很好的循环并行化效果,而且是现有循环变换方法的一个推广.

目录

文摘

英文文摘

1.背景介绍

1.1.并行编译的有关背景

1.2.主要内容

1.3.相关的研究

1.4.前提假设、名词解释和记号

2.通过循环变换增加并行粒度

2.1.通过对迭代空间的变形增加并行粒度

2.2.结点可以合并的条件

2.3.一般的U模变换情况

2.4.对相关向量集D的讨论

2.5.非U模变换

3.通过迭代空间分块增加数据局部性

3.1.U模变换前通过结点合并增加数据局部性

4.整体实现与结论

4.1.一般的处理流程

4.2.实验数据

4.3.小结

致谢

参考文献

声明