基于投影分层技术的嵌套循环空间局部性优化方法.pdf

《基于投影分层技术的嵌套循环空间局部性优化方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第26卷第5期计算机学报VoI.26No.52003年5月CHINESEJOURNALOfCOMPUTERSMay2003基于投影分层技术的嵌套循环空间局部性优化方法夏军杨学军曾丽芳周海芳（国防科学技术大学计算机学院长沙410073）摘要从数据访问轨迹入手，探讨了利用数据变换来改善数据访问局部性的本质，提出了一种新的优化数据访问的投影分层技术以及基于它的数据变换框架.该框架主要利用投影技术来优化数据访问的空间局部性，并同时利用数据分层技术来解决因投影而带来的数据重叠问题.该数据变换框架不仅能处理仿射数组下标，而且还能处理许

2、多非仿射的更复杂的数组下标，同时它还能简单直接地确定数据元素的最优存储布局以及优化数据访问的数据变换矩阵，并能使访问间距尽量小.实验结果表明它是有效的.关键词并行编译优化；数据访问轨迹；数据变换；空间局部性中图法分类号TP311AProjection-delaminationBasedApproachtoOptimizingSpatialLocalityinLoopNestsXIAJunYANGXue-JunZENGLi-fangZHOUHai-fang（InstituteofComputer，NationalUniuer

3、sityofDefenseTechnology，Changsha410073）AbstractBasedonanaIysisforthedataaccesstracktheessenceofdatatransformationispointedout.Thenanewprojection-deIaminationtechnigueforoptimizingspatiaIIocaIityispresented，andadatatransformationframeworkbasedonthistechnigueisbroug

4、htforward.Anarray’ssubscriptexpressionsareinfactrepresenta-tivesofitsparameterizeddataaccesstrack，accordingtowhichthespatiaIanaIyticeguationofitsdataaccesstrackcanbegot.Theprojection-deIaminationtechniguecanbeusedtomakethedataaccesstrackconsistentwiththedefauItdat

5、aIayoutdefinedbycompiIer，whichcanimprovethespatiaIIocaIityofthedataaccesstrack.Intheaboveframework，projectiontechnigueisadoptedtooptimizethespatiaIIocaIityofdataaccessandde-IaminationtechnigueisusedtosoIvetheprobIemofdataoverIappingcausedbyprojection.Theframeworkc

6、andeaIwithnotonIyarrayswithaffinesubscripts，butaIsoarrayswithmanycompIexnon-affinesubscripts.More-over，theframeworkcanmakeaccessstrideassmaIIaspossibIeanddeterminetheoptimaIstorageIayoutofdataanddatatransformationmatrixforoptimizingdataaccessdirectIyandeasiIy.Keyw

7、ordsparaIIeIcompiIingoptimization；dataaccesstrack；datatransformation；spatiaIIocaIity的局部性主要有两种方法，它们是程序变换和数据1引言变换.以前的研究主要集中在程序变换上，通过对迭代空间的变换和调度来提高数据访问的局部性，例在并行系统中，通过充分开发并行程序的局部如单模和非单模迭代空间变换［1］、循环分块［2］、循环合并［3，4］、循环分布［5，6］等.但与数据变换相比较，程性，可以改善并行程序的访问特性，从而提高并行程序的执行效率.因此，

8、提高数据访问的局部性问题是序变换有一定的局限性.首先，程序变换的合法性要受数据相关性的限制［5］，但数据变换不受其影响；其当今并行编译优化研究的重点之一.提高数据访问收稿日期：2001-04-05；修改稿收到日期：2003-01-13.本课题得到国家杰出青年科学基金（69825104）和国家自然科学基金