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

《循环变换增加并行粒度与改善数据访问局部性》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、复旦大学硕士学位论文循环变换增加并行粒度与改善数据访问局部性姓名：马国凯申请学位级别：硕士专业：计算机软件与理论指导教师：朱传琪2002.5.18摘要／／，ｆ在程序自动并行化的过程中，并行粒度和数据访问局部性是两个常常被关注的问题。实用的并行化算法必须考虑并行化后的循环有适当的并行粒度和良好的数据访问局部性，以降低处理机花费在进程同步和内存访问不命中上的开销。一些经典的循环并行化方法往往把注意力集中在挖掘循环的并行性上，这是出于简化问题的原因。然而在实用并行化编译器的研制中，应当充分考虑到一些次要问题对并行化结果的影响，对经典算法进行适当的补充和扩展，以满足实用性的需要。、一｝本文在迭代空

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

3、根据合并后的相关向量集变换迭代空间，以及折叠迭代空间的方法。这种方法能够在保持扩大循环粒度效果的基础上，达到保持原程序数据访问局部性的效果。本文从实际应用的角度出发，能够达到很好的循环并行化效果，而且是现有循环变换方法的一个推广。关键字循环变换，并行化霜诲，Ｕ模变换，迭代空伺折叠，数据访问局部性，Ｗａｖｅｆｒｏｎｔ方法０ＡｂｓｔｒａｃｔＩｎａｕｔｏｍａｔｉｃｐｒｏｇｒａｍｐａｒａｌｌｅｌｉｚｉｎｇ，ｇｒａｎｕｌａｒｉｔｙａｎｄｄａｔａｌｏｃａｌｉｔｙａｒｅｉｓｓｕｅｓｏｆｔｅｎｃｏｎｃｅｒｎｅｄ．Ｐｒａｃｔｉｃａｌｐａｒａｌｌｅｌｉｚｉｎｇａｌｇｏｒｉｔｈｍｍｕｓｔｋｅｅｐｇｏｏｄｇｒａ

4、ｎｕｌａｒｉｔｙａｎｄｄａｔａｌｏｃａｌｉｔｙｏｆｔｈｅｐａｒａｌｌｅｌｌｏｏｐｓｉｎｏｒｄｅｒｔｏｒｅｄｕｃｅｔｈｅｏｖｅｒｈｅａｄｏｆｐｒｏｃｅｓｓｓｙｎｃｈｒｏｎｉｚｉｎｇａｎｄａｃｃｅｓｓｍｉｓｓｉｎｍｅｍｏｒｙｓｙｓｔｅｍ．Ｍｏｓｔｐａｒａｌｌｅｌｉｚｉｎｇａｌｇｏｒｉｔｈｍｐｕｔｇｒｅａｔｅｆｆｏｒｔｓｉｎｈｏｗｔｏｇｅｔｍａｘｉｍａｌｐａｒａｌｌｅｌｉｚｅｄｌｏｏｐｓｆｒｏｍｔｈｅｐｒｏｇｒａｍ．Ｔｈｉｓｃｏｎｓｉｄｅｒａｔｉｏｎｗｉｌｌｓｉｍｐｌｉｆｙｔｈｅｐｒｏｂｌｅｍｉｎｔｏａｄｉｓｃｕｓｓａｂｌｅｄｅｇｒｅｅ．Ｂｕｔｉｎｔｈｅｄｅｖｅｌｏｐｍｅｎｔ

5、ｏｆｐｒａｃｔｉｃａｌｐａｒａｌｌｅｌｉｚｉｎｇｃｏｍｐｉｌｅｒ，ｗｅｍｕｓｔｃｏｎｓｉｄｅｒｔｈｅｓｅｍｉｎｏｒｆａｃｔｏｒｓｒｅｇａｒｄｉｎｇｔｈｅｅｆｆｅｃｔｓｏｆｐａｒａｌｌｅｌｉｚｅｄｐｒｏｇｒａｍ．Ｓｏｍｅａｌｇｏｒｉｔｈｍｓｈｏｕｌｄｂｅｅｘｔｅｎｄｅｄｍｏｄｉｆｉｅｄ．Ｉｎｔｈｉｓｔｈｅｓｉｓｗｅｄｉｓｃｕｓｓｅｄｔｏａｍｅｅｔｔｈｅｓｅｃｏｎｓｉｄｅｒａｔｉｏｎ，ｓｏｍｅｓｈｏｕｌｄｂｅｓｌｉｇｈｔｌｙｌｏｏｐｔｒａｎｓｆｏｒｍａｔｉｏｎｍｅｔｈｏｄｗｈｉｃｈｃｏｕｌｄｉｎｃｒｅａｓｅｔｈｅｇｒａｎｕｌａｒｉｔｙｏｆｔｈｅｌｏｏｐｂｏｄｙａｎｄｉｍｐｒｏｖｅｔｈｅｄ

6、ａｔａｌｏｃａｌｉｔｙｏｆｔｈｅｔｒａｎｓｆｏｒｍａｔｅｄｌｏｏｐ：Ｂｙａｎａｌｙｚｉｎｇｔｈｅｄｅｐｅｎｄｅｎｃｅｖｅｃｔｏｒｓｅｔｏｆｔｈｅｇｉｖｅｎｎｅｓｔｅｄｄｏｕｂｌｅ—ｌｏｏｐ，ｗｅｃｏｕｌｄｍｅｒｇｅｓｅｖｅｒａｌｎｏｄｅｓｉｎｔｈｅｉｔｅｒａｔｉｏｎｓｐａｃｅ，ｗｈｉｃｈｈａｖｅｓａｍｅｏｕｔｅｒｌｏｏｐｖａｒｉａｂｌｅｖａｌｕｅａｎｄｄｉｆｆｅｒｅｎｔｉｎｎｅｒｌｏｏｐｖａｒｉａｂｌｅｖａｌｕｅ，ｉｎｔｏｏｎｅｎｏｄｅｉｎｔｈｅｆｏｌｄｅｄｉｔｅｒａｔｉｏｎｓｐａｃｅ，ｗｈｉｌｅｐｒｅｓｅｒｖｉｎｇｔｈｅｐａｒａｌｌｅｌｉｓｍｏｆｔｈｅｉｎｎｅｒｌｏｏｐａｔｔｈｅｓａ

7、ｍｅｔｉｍｅ．Ｔｈｕｓ，ｗｅｉｎｃｒｅａｓｅｄｔｈｅｇｒａｎｕｌａｒｉｔｙｏｆｔｈｅｐａｒａｌｌｅｌｌｏｏｐｂｏｄｙ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｗｅｄｉｓｃｕｓｓｅｄｈｏｗｔｏｆｉｎｄａｕｎｉｍｏｄｕｌａｒｍｅｔｒｉｃｓｔｏｔｒａｎｓｆｏｒｍｔｈｅｇｉｖｅｎｉｔｅｒａｔｉｏｎｓｐａｃｅｗｉｔｈｔｈｅｇｉｖｅｎｄｅｐｅｎｄｅｎｃｅｉｎｔｏａｎｉｔｅｒａｔｉｏｎｓｐａｃｅｉｎｗｈｉ