自动并行编译新技术

《自动并行编译新技术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、!""#$%%%&’()*+,-./01,2",2340.5软件学报)%%%7$$8’9:$);(<$)=*66666666666666666666666666666666666666666666666666666666666自动并行编译新技术>阳雪林于勐陈道蓄谢立8南京大学计算机软件新技术国家重点实验室南京)$%%’?98南京大学计算机科学与技术系南京)$%%’?9@&A0B1:CD1EFBG10HI/J-I5F-IK/摘要自动并行编译为并行化现有的串行程序及编写新的并行程序提供了重要的支持7因此)%多年来一直受到重视

2、I近几年来7自动并行编译技术的研究进展7包括在依赖关系分析L程序变换L数据分布和重分布及调度等方面的进展7将自动并行编译进一步推向了实用化I该文介绍了自动并行编译技术的最新进展7并提出了进一步的研究所要解决的问题I关键词自动并行编译7依赖分析7程序变换7数据分布7调度I中图法分类号MN?$O自动并行编译为充分发挥并行计算环境不断增强的计算能力提供了一条重要的途径I它有以下优点:8$9在缺乏被普遍接受的并行程序设计语言的情况下7自动并行化工具能有效地解决代码的可重用和可移植问题P8)9解决了用一种语言难以显式地表达从指令层

3、到任务层各个层次的并行性7并进行基于体系结构的优化问题P8?9自动并行化工具为大量存在于应用领域的7并经过长时间的设计L使用和测试的成熟大型串行应用程序的并行化提供了唯一可行的选择I但设计自动并行化系统十分复杂I自动并行编译牵涉到数据依赖关系分析L程序变换L数据分布及调度等许多技术I如果说基于共享内存的自动并行编译技术已具有一定程度的实用性7基于分布内存的技术则由于数据分布的困难而离实用化还有相当一段距离I自’%年代以来7对自动并行编译技术的研究有了很大的进展7产生了一批有代表性的自动并行化系统7国外的有"Q!R8"30

4、/2,.F-/BS5.GB3CB/35.A5FB0352,.A0397N,10.BGP国内的有Y$ZY)Z和+VN"Y?ZTU&NVWNWX7RVM7V-3,[0.I通过对这些系统的开发7人们提出了很多实用技术7涵盖了数据依赖关系分析L程序变换L数据分布及调度等方面的内容I下面依次对这些技术作简要的介绍I依赖关系分析循环体中的依赖关系分析和过程间依赖关系分析的质量决定了数据并行性和任务并行性的开发程度7多年来7它们一直是研究的热点I近几年的研究成果更是进一步地推动了自动并行的实用化I指针分析是对]7]^^程序并行化不可

5、缺少的工作II循环体中的依赖关系分析循环占用了串行程序的绝大部分执行时间7因此7对循环体的依赖关系分析一直是最受关注的YO7*ZI早期的>本文研究得到国家(;?高科技项目基金8#,I(;?&?%;&_M%)&%?%$9资助I作者阳雪林7$’;=年生7博士生7助教7主要研究领域为并行与分布式计算I于勐7$’=)年生7博士生7助教7主要研究领域为并行与分布式计算I陈道蓄7$’O=年生7教授7博士生导师7主要研究领域为并行与分布式计算I谢立7$’O)年生7教授7博士生导师7主要研究领域为并行与分布式计算7计算机网络I本文通

6、讯联系人:阳雪林7南京)$%%’?7南京大学计算机科学与技术系本文)%%%&%$&);收到原稿7)%%%&%;&$)收到修改稿阳雪林等D自动并行编译新技术aCT,ba工作主要集中于数组是线性下标的精确方法和运行速度足够快的近似方法!分析也都是静态的"因此!在大多数情况下只能得到保守的结果"#$%&’(%)*+,-使用整数规划!综合得到了速度快且精确的结果".’/&%(%)*+0-突破了线性下标的限制".1234%567*89/:48;’*8<8/&59’==>(%)*和?.123=’<@4%567*89/:48;’*8<

7、8/&59’==>(%)*+A-对依赖于输入B静态所不能确定依赖关系的循环进行了动态并行化"C"C"C#$%&’(%)*#$%&’(%)*的原理是D依赖关系分析可以归结为求解一组任意的线性等式和不等式集合的整数解!即整数规划的问题"传统上认为用整数规划来求解依赖关系代价过高!#$%&’(%)*的速度则表明这种看法是不正确的"#$%&’(%)*由一种消去整数约束的新方法和E9648%4FG9*

8、PC!定义R为变量的JKLKMJKLKM索引集合"它的工作步骤可分为S步D3C>将约束标准化"标准化的约束是指所有的系数是整数且所有系数的最大公约数3不包括NJ>是C的等式和不等式"3T>消减等式约束"为消减等式INLOLPJ!首先检查是否存在UVJ使得WNUWPC"如果存在!我们解出OU并JKLKM代入其他约束以消