（计算机系统结构专业论文）分布式主存系统上自动数据和计算分解和相关研究.pdf

摘簧 数据稿计算分解楚黄行化懿蓥础，对成游数据分布瑚计算划分是薨行化编译的重骤 缓成都分。 自动数耀分布需要同时鸯璐程序的并行性、局部性、刚示机器特憔、后端编译器优 化等一系列问麒。这大大增加了自动数据分布的复杂性和难度。采用整数线性规划方法 鹣塞动数据分毒框粱可以揭枣鬟好的嚣标程黪逶应性，不过戆入豹方案存在复杂麦熹， 馁能模型不够精确的缺点。针对这些阉鼹，我们提南了羊孛蓊的蠢安磷彀抟鸯萄数据分 布框架。该橙架提供了对多维分布、多分割分布方式、多壤流水并行的缴掘以及动态融 分布的支持，嶷有懿性能，可扩展性和低开销等特点，豳瓤有比较蕊的嶷用性 嫠分重复谤箕翻分是诗棼划分陵段送行戆重要臻纯，可以有效数馥少苇点阀蘧信秘 阊步，从而掇谳程序的性能和可扩展性。前入的研究工作局陵于一个德环套的范围，并 凰没有性能模溅的支持。我们扩展了原夺部分重复计簿划分的优化范围，给出了显式的 髓能模型帮求辫方法。 本文主要贾献如下： l - 摁融鏊予并行性萃弱数锯依赖关系的树形程序分解方法，提离了大范醚统一数 据分布憾况下的蛙能饿计糖瘦，在镁遗产生算法中，对每一。个程序片断只产生r + 个简帮簸傀的鼗攒分布方式，飙面大大降低了舞泫黪复杂蛀。毒瘸辫疆除段蔷方 法，遗波实际应用中常见的一些特色，降低了问题复杂瘦。 2 掇出自动进行熬于糖丁方格的秘分割数据分布方式，对多维的流水并行性掇 供了雯好姻支持，能够叁动搜索捷纯躲处理器空间聚嚣。 3 绘磁其有戳上特魏的求懈垒墒爨穑数据分布的整数线经藏划求解挺粲。 4 给出广义的部分麓复计算的概念，扩展了部分藿复计算划分的优化范围。从 全局范豳的部分重复计算划分、利用可用数组区域的部分重复计算划分、多联次 帮分熏囊诗募翅分等方蠢，说明毅定义联鬟筷灏旋纯瓤会。 5 提蹈了相应静线憔惶能模型，漾嗣基，丁定义点的冗余通信检测方法来馈计避 信优化姻作用。此方法在自动数据分布和部分重复计算划分中都谢所应用。 6 给蹬了一神解次此离题髓扁发式框架，能够0 鞍有效鑫专解凌一大类应用程膨 秘帮分溪复诗舞裁分逮戆。 7 绘出一种基予熬数线性规戈方法解决全局部分夔复计算戈分瓣趣款框架。简 化了问越的求解过程，并且降低了澎维分布情况下的复杂度。实骏结果表嘴耨的 全褥部分霞复计算划分，在过去的部分重复计算划分基础上，对性能_ 手n 扩震性有 显著爨薅。 l 分布式书存系统t 目动数据和计算分解和相关研究：摘要 关键谢：分布式并行系统，共行化编译，蛊动数据分布，计算划分。 l i r e s e a r c ho na u t o m a t i cd a t aa n dc o m p u t a t i o nd e c o m p o s i t i o n o nd i s t r i b u t e d - m e m o r ys y s t e m s w a n gy i r a n ( c o m p u t e r a r c h i t e c t u r e ) d i r e c t e db yz h a n gz h a o q i n g d a t aa n dc o m p u t a t i o nd e c o m p o s i t i o ni st h eb a s i so fp a r a l l e lp r o g r a m s t oa c h i e v eh i g h p e r f o r m a n c e ，l o c a l i t yo fd a t aa c c e s sa n da v a i l a b l ep a r a l l e l i s mm u s tb ec o n s i d e r e da tt h es a m e t i m e t h ec o m p l e x i t yc o m e sf r o mb o t ht h ep r o g r a ma n dt h et a r g e tm a c h i n e a u t o m a t i cd a t a a n dc o m p u t a t i o np a r t i t i o n i n ga r eo f g r e a tc h a l l e n g ei np a r a l l e l i z i n gc o m p i l e r s a u t o m a t i cd a t al a y o u ti st h eb a s i sf o ra u t o m a t i cp a r a l l e t i z a t i o n t of i n dag o o dd a t a l a y o u t ，t h ec o m p i l e rm u s tc o n s i d e rt h ec h a r a c t e r i s t i co f t h ep r o g r a ma n dt h et a r g e tm a c h i n ea t t h es a m et i m e s u p p o r t i n go fd y n a m i cd a t al a y o u tf u r t h e rc o m p l i c a t e dt h ep r o b l e m t h e r ea r e s e v e r a ls t a t e o f - a r tf o r m e rr e s e a r c h e sa n de m p l o y i n gi l p ( i n t e g e rl i n e a rp r o g r a m m i n g ) f r a m e w o r kt os o l v et h ea u t o m a t i cd a t al a y o u tp r o b l e mi sap r o m i s i n gm e t h o d w ep r o p o s e da n o v e lf r a m e w o r kf o ra u t o m a t i cd a t al a y o u tt o o l s c o m p a r e dt op r e v i o u sw o r k s ，t h i sf r a m e w o r k l o w e r st h ea n a l y s i sc o s tc o n s i d e r a b l ya n di n c r e a s e st h ep r e c i s i o no fp e r f o r m a n c em o d e l ，t o a c h i e v et h e s eg o a l s ，w ee m p l o ys e v e r a lt e c h n i q u e s f i r s t ，w ei n t r o d u c et r e es h a p e dp r o g r a m p a r t i t i o n i n gd i r e c t e db yp a r a l l e l i s ma n dl o c a l i t yc h a r a c t e r i s t i c s s u c h ap r o g r a mp a r t i t i o n i n g m e t h o dr e d u c e st h ea n a l y z i n gc o s ta n de n a b l e sm o r ep r e c i s ep e r f o r m a n c ep r e d i c t i o n s e c o n d ， t h i sf r a m e w o r km o d e l st h e e f f e c to fc o m m u n i c a t i o no p t i m i z a t i o nf o rs h i f tc o m m u n i c a t i o n s ， w h i c hi n c r e a s et h ep r e c i s i o no f p r o b l e mf o r m u l a t i o n t h e r ea r ea l s os o m eo t h e ri m p r o v e m e n t s ， s u c ha sa u t o m a t i cm u l t i p a r t i t i o n i n gs u p p o 【f o rt h ef i r s tt i m ea n dc o n s i d e r a t i o nf o re x a c ts h a p e a n ds i z eo fp r o c e s s o rg r i d e x p e r i m e n t a lr e s u l t ss h o wt h a to u rf r a m e w o r kg e n e r a t ed a t al a y o u t f o re x a m p l ep r o g r a m se q u a lt oo rb e a e rt h a np r e y i o u sw o r k s p a r t i a lr e p l i c a t i o ni sa ni m p o r t a n to p t i m i z a t i o nt h a tr e d u c e sn e a r - n e i g h b o rc o m m u n i c a t i o n a tt h ec o s to fs o m er e p e a t e dc o m p u t a t i o n i tc a nc o n s i d e r a b l yi m p r o v et h ep e r f o r m a n c ea n d s c a l a b i l i t y o fp a r a l l e l p r o g r a m s f o r m e re x p l o r a t i o n o fp a r t i a l r e p l i c a t ec o m p u t a t i o n p a r t i t i o n i n gi sl i m i t e dw i t h i nas i n g l el o o pn e s t , a n dn oe x p l i c i tc o s tm o d e li su s e d + i nt h i s p a p e r , w ep r e s e n taf o r m a ld e s c r i p t i o no fm o r eg e n e r a lp a r t i a lr e p l i c a t ec o m p u t a t i o n p a r t i t i o n i n gp r o b l e m s ，w h i c hi sc a l l e dg l o b a lp a a i a lr e p l i c a t ec o m p u t a t i o np a r t i t i o n i n g a s r e d u n d a n tm e s s a g ee l i m i n a t i o ne x e r t sg r e a te f f l u e n c eo nt h ee f f e c to fs u c ho p t i m i z a t i o n s ，w e i n t r o d u c e dal i n e a rc o s tm o d e lw h i c hc o n s i d e r si t se f f e c t w ea l s od e v e l o p e daf r a m e w c i r k w h i c he m p l o y st h ei n t e g e rl i n e a rp r o g r a m m i n gm e t h o d e x p e r i m e n t a lr e s u l t ss h o wt h a tt h e s o l u t i o ni ss u p e r i o rt ol o c a la p p r o a c h e s c o m p a r e dt oh e u r i s t i cm e t h o d ，t h en e w a p p r o a c hc a l l d e a lw i t hm o r eg e n e r a lc a s e sa n di se a s i e rt ob ea d a p t e dt od i f f e r e n td a t ad i s t r i b u t i o n k e y w o r d s ：d i s t r i b u t e dm e m o r yp a r a l l e ls y s t e m s ，p a r a l l e l i z i n gc o m p i l e r , a u t o m a t i cd a t a d i s t r i b u t i o n ，c o m p u t a t i o np a r t i t i o n i n g 1 1 1 图目录 图2 - 1a u t o p a r 势行化编译嚣的主要结构8 图3 - 1h p f 的对准和分布一1 3 图3 - 2 a d i 核一t l , 程序的通信图。1 5 图3 - 3 ( a ) p h a s e 分解前后的通信图，( b ) a d i l 趵p h a s e 转换图1 6 醋3 4 二维a d i 核心的p h a s e 分解 i j p c f g 17 图3 - 5r i c e 的方案中，二维a d i 核心的p h a s e 控制流图以及数据分布圈l 8 图3 - 6 访问模式，并行化超边和通信边2 1 图3 7a d i 侈o 予的一个合法鳃2 1 图4 - 1 一个流水循环的例子，来1 2 t n p b2 3s e r i a ls p 2 6 图4 - 2 多维流水的例子，来自n p bl u 2 8 圈4 - 39 个处理器情况下2 维和1 维流水计算的区_ 5 j i j 2 8 图4 - 4 多分割盼数据分布和超级流水的计算划分2 9 图耷5 广义多分割3 0 图4 - 6 重分杰的只读副本优化3 2 图4 7 ( a ) ，( b ) ，和( c ) 三个循环分别是弗行，流水和串行计冀。( c ) 中数组m 和n 的瞌编译时 刻未知3 5 图4 - 8 具有多重并行性的计算耦台和非耦合的流水计算3 6 国4 - 9 一个边界计算的例子，来i 刍n p b 2 3s e r i a ls p 的c o m p u t e r h s 子过程4 0 图4 - 1 0 初始化计算扮洌子，来自n p b 2 3s e r i a ls p 。4 0 图4 1 1n p b 2 3s e r i a ls p 的篱略程序分解圈的一帮分。4 1 图4 - 1 3l u 的程序分鳃4 2 图4 一1 4 不同分布参数的二维块状分布的性能b t 和s p 是n p b 2 3 的例j 于，而a 和b 分 别代表“a ”和b 规模( c l a s s a a n d b ) 4 2 l x 图4 15 个两个送信构成的冗余通信组4 9 图4 - t 6 鸯动数据分枣实蕊挺架。5 1 图4 - 1 7s p 的数撼分布产生5 6 图5 1 卡日对冗条关系图。6 3 霆5 - 2 爨对一个搪环襄瓣薅努重复毒手冀裂分秘 图5 - 3 通过用户添加制露实现一蹙垒局部分重复计算划分的例子，寐f l n p b 2 3s e 。6 5 圈采t 个全稀部分囊鬣计葬划分的例子，来自黼b 2 3s p , 6 7 鼹6 - 2 一个全盛部分蘩笈计篓划分的铡予，来鲤雌8 2 3s r 6 8 图6 3 。基于可劂数组区域的部分攫复计弊划分方案6 8 图6 _ 4 多瑟次帮分重复 箕黧努穷寨，慕盘n 陷2 3s e r i a ls p 。6 9 图6 - 5 多维部分匿复计冀划分方案，来自n p 8 2 3s e r i a lb t ，我们忽略了不相关疑代鹦， 后面的对于q s $ 1 ：i s q u a r e 的使用语句分别属予三个三臌的循环套，索引变量也郄怒k ，j ，i ，迭 代空阕露第一个簇嚣套瓣只寿擞，l 、差梨。 图6 - 6 算法2 ，斌隧进行个部分重复计算划分调整7 5 闰舀7 全弱部分震菱计算划分算法7 7 图6 - 8 阀题的袒始解7 8 图6 - 9 问题的初始解7 9 两6 - 1 0 一个中润狡态。7 9 闰6 - 1 1 最终状惫舄一个中问状态。8 0 甾6 - 1 2 最终状态。s o 凰6 一1 3 全舄算法。；8 2 图6 - 1 4 避信量的改进，友露一维炔状分帮，右图二维块状分布。8 3 萄6 - 】s 全露最饶部分重复诗簿分翁褐对瓣蘧毙，维块状分布的情况。8 3 图6 - 1 6 全局部分重复计算划分和局部部分燕复诗冀划分的性能毖较，n p b 2 。3s p a 缴、 b 级和c 级。8 4 x 图6 1 7 全局部分重复计算划分和局部部分熏复计算划分的性能比较，n p b 2 ，3b t a 级、 b 级和c 级8 5 图6 - 1 8 全局部分重复计算划分和局部部分煎复计算划分的性能比较，n p b 2 3l ua 级、 b 级和c 级。8 6 图6 1 9 全局部分重复计算划分相对于局部部分重复计算划分的加速比8 6 图6 - 2 0 部分重复计算划分和数组收缩的关系8 8 表目录 表4 - 1 并行模板的简要信息，并行维都按照统一的对准顺序排列一4 1 表4 也各个例子程序的基本特性5 3 表4 - 3 不同自动数据分布方案对例子b t 的阶段、数据分布候选、数据分布搜索空间比 毫5 4 表4 - 4 不同自动数据分布方案对饲予s p 的阶段、数据分布候选、数据分布搜索空间比较 - 一- - - - - - - ，5 4 表冬5 不同自动数据分布方案对例予l u 的阶段、数据分布候选、数据分布接索空间毖 较5 4 表4 - 6 自动数据分布的结果比较。用黑色字体表示其中相对最优的数据分布方案5 5 表4 7s p 的不同数据分布下，运行加速比。5 5 表4 - 8b t 的不同数据分布下，运行加速比5 6 表4 - 9l u 的不同数据分布下，运行加速比。5 7 表4 - 1 0 a d i ，e f l u x 。s w i m ，t o m c a t v 在不同数据分布，处理器数磊下的运行加速比5 8 表4 - l la d i5 1 2 4 5 t 2 阚格和1 0 2 4 + 1 0 2 4 网格的各种数据分布模式比较5 9 声明 我声明本论文是我本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，本论文中不包含 其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：乏牟尖雪鸡 论文版权使用授权书 隰2 9 饼锎 本人授权中国科学院计算技术研究所可以保留并向国家有关部门或机 构送交本论文的复印件和电子文档，允许本论文被查阅和借阅，可以将本 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编本论文。 ( 保密论文在解密后适用本授权书。) 作者签名：碱导师签名：f 缸此天日期加苦毕鳃 1 1 背景知识 第1 章引言 传统的高性能计算应用比较多的领域包括科学研究领域的全球气象、天体物理、基 因学，蛋白质折叠、药物设计、计算化学、材料科学，工程领域的碰撞模拟、集成电路 设计、地震和结构模拟、流体力学，商业领域如经济和财务模拟、交易处理，搜索引擎， 国防领域如核爆破、密码学。随着越来越多的应用的涌现，高性能计算的应用范围将日 益广泛，而且会逐步深入到人们日常生活的范围。对更高性能，更高的可扩展性，更合 理的价格的需求也日益增长。 分布式主存并行系统( d i s t r i b u t e dm u l t i p r o c e s s o r s ) 这样应用需求提供了必要的的 性能、扩展性和性能价格比。这样的系统需要显示的对数据和计算进行分割，而数据的 迁移需要显示的进行，这大大增加了应用开发的难度，尤其是在保证正确性的基础上获 得满意的性能。调查表明九十年代在向量g _ k 典型的应用可获得计算峰值的4 0 5 0 ，而 现今的并行系统上，多数应用仅获得5 - 1 0 或更低的性能。 另外提供快速的远程内存访问和高可扩展性具有根本的矛盾，所以即使系统提供了 一定的远程内存访问机制，要利用这些机制而保持高性能非常困难。在这样的系统上， 分布式的编程模型也广泛的被采用。 所以在这样的背景下，并行编程模型和开发工具面临巨大的机遇和挑战。 最具代表性的是，由开发人员直接编写并行程序，而编程环境只提供基本的底层支 持，其中最具代表性的是m p i 。这样的开发方法可以提供较高的性能和可移植性，也保 证一定的性能可移植性。然而开发人员的负担很重，程序的编写，调试工作都很沉重。 而基于并行化编译的自动半自动开发方法，可以帮助用户承担大量繁重机械的工 作，而只负责串行程序和关键性的制导，无疑可以大大提高开发效率。在并行形识别、 数据和计算分解、通信优化等方面编译器都承担了大量的工作。然而很多方面的技术都 缺乏足够的实用性，尤其是自动的数据和计算分解方面。 自动的数据和计算分解面临的问题来自两大方面，并行性和局部性。从体系结构的 角度考虑高性能计算的问题，这也是两个对性能产生根本影响的因素。并行性提供了性 能改进的可能性，而过差的局部性则可以抵消大部分的性能提高。 应用程序中存在的一定的固有并行性，而在一定的数据存储模式下，可以被有效利 用的并行性我们称之为可用并行性所以数据和计算分解的目标是要发掘充分的可用并 行性。同时在不同的计算阶段避免过多的数据移动和同步。 局部性问题又表现为多重层次。人们比较早注意的例如不同计算节点之间的数据移 动。后来在多处理器节点内部的处理器缓存之问的移动也成为一大问题。随着处理器计 l 中国科学院博士学位论文 算速度和存储器访问速度的差距口渐扩大，并行模式对单个处理器的存储访问局部性的 影响造成的性能区别也对整体性能产生很大影响。 数据和计算分解需要在可利用的并行性和局部性之问取得合理的平衡。单纯强调可 用并行性。经常会造成大量的数据移动，而过度避免数据移动，将严重限制可用并行性。 在自动并行编译过程中，并行性识别主要是分析程序存在的并行性，以及要利用特 定并行性需要满足的条件，而通信优化主要考虑的是如何取得多大的局部性。这两个阶 段面临的问题都相对单纯一些，而自动的数据和计算分解需同时面临着两个问题，所以 也是其中最困难和关键的一步 1 2 本文的贡献 本文讨论了数据并行模型中，对基于规则的数据结构的程序的自动数据和计算分解 问题。主要贡献如下： 在自动数据分布方面，提出一种新的数据分布问题解决框架，该框架提供了对多维 分布、多分割分布方式、多层流水并行的发掘以及动态重分布的支持。综合起来，新的 自动数据分布框架具有高性能，可扩展性和低开销等特点，因而有比较高的实用性。 1 基于并行性和数据依赖关系的树形程序分解方法。提商了打范围统一数据分布情 况下的性能估计精度，在候选产生算法中，对每一个程序片断只产生一个局部最 优的数据分布方式，从而大大降低了算法的复杂性。 2 利用附属阶段等方法，适应实际应用中常见的一些特色，降低了问题复杂度。 3 在全局数据分布的描述和性能模型中。通过基于定义点的冗余通信检测方法，来 估计通信优化的效果，从而更精确的评估通信性能。 4 对多维的流水并行性提供了更好的支持，能够自动搜索优化的处理器空间配置， 并第一次自动支持给予拉丁方格的多分割数据分布方式。 5 具有以上特色的整数线性规划框架求解全局自动数据分布。 在全局部分重复计算划分方面的贡献包括z 1 给出了广义的部分重复计算的概念，从非循环范围的部分重复计算划分、利用可 用数组区域的部分重复计算划分、多层次部分重复计算划分几个方面说明了新的 定义所提供的优化机会。 1 ) 在形式化定义的基础上提出了一个相应的线性性能模型，尤其是采用基于定 义点的冗余通信检测方法来估计通信优化的作用。 2 ) 提出了一种解决此类问题的启发式框架，能够比较有效的解决一大类比较典 型的应用程序对应的部分重复计算划分问题。 3 ) 提出了一种基于整数线性规划方法解决全局部分重复计算划分问题的框架。 这样一个框架，简化了问题的求解过程，并且降低了多维分布情况下的复杂 度。 2 第一章引言 本文主要探讨了并行化编译器中的自动计算和数据分解，这个问题和程序的并行性、 局部性紧密相关。数据分布通过采用适合的数据分布方式以及适当的重分布来减少数据 移动同时保证可利用的并行性。而部分重复计算划分在此基础上，对计算划分进行优化， 以进一步减少非本地数据的引用，提高并行程序的局部性。测试结果表明，我们的自动 数据分布方法相比国内外最新研究，具有更低的复杂度，支持广泛的择优的数据分布模 式。而部分重复计算划分方法，相比以前的研究工作，扩展了优化的范围，提供了完全 自动地分析能力，最终提高了并行程序的性能和可扩展性。 1 3 论文的组织 论文从高性能并行计算硬件和编程环境的发展出发。首先介绍了并行化编译及相关 的背景知识。 在第三章中，介绍了当今自动数据分布的最新研究进展和趋势。以上一章为铺垫， 第四章详细描述了我们的自动数据分布框架及试验结果。 第五章随后介绍了部分重复计算划分的研究和特点。在第六章介绍了我们对部分重 复计算划分的定义，性能模型，以及两种新的实现框架。 第七章对全文进行了总结，并展望将来可能的研究工作。 第2 章背景知识 高性能并行计算领域的涵盖范围很广，面临的问题也多种多样 h e n n 0 2 。而这句话 对并行编译系统尤其适用。 并行编译技术对于提高并行系统，尤其是分布式主存的并行系统的易用性有重要作 用。然而既保证不需要过多的用户干预又要取得近似于手写并行化的效率是极大的挑战， 也十分艰巨，完全自动的并行编译仍然比较局限于规则的基于数组表示的科学计算程序， 而这些自动编译器能够取得的性能仍然和手工优化的并行程序有相当的差距 2 1 高性能并行体系结构 无论单处理器的计算能力取得怎样的提高，以之为基础，利用多处理器进行并行计 算总是获得高性能的重要方法。这类并行计算机按照其体系结构的内存访问和编址特征， 可以分为s n i p , c c n u m a , 和分布式主存系统。 提供多处理器对称的访存能力，或者多个存储结构之间的一致性支持，都相应的限 制系统的扩展能力。另外在非一致内存访i h ( n v m a ) 上，要保证并行应用的性能，必然 需要考虑到不同内存地址的访问延迟和带宽差别。所以大规模的并行系统必然具有明显 的分布式特征，而采用与之对应的消息传递模型的编程模型，也在这样的系统上占统治 地位 2 2 程序设计模型 m p i 是当今并行程序开发的事实上的标准，通过手工编写基于m p i 的并行程序，可 以保证一定的可移植性，获取租粒度的并行。在开发过程中，开发人员需要全程参与并 行化过程，包括数据和计算的分解，通信的优化尽管存在一系列的缺点，基于m p i 的 开发模型，有丰富经验的开发人员经过充分的开发和调试，可以在分布式并行系统上取 得不错的性能，至少足优于其他开发方法。 m p i 仅负责对目标机器的通信机制作有限的抽象和包装，这样一个开发模型缺乏更 高层次的抽象，是一个比较低级的开发模型。这就导致了一些弊端：首先程序员需要处 理大量的复杂问题，其中相当一部分又比较机械和重复；再者，通信优化过程比较繁琐， 尤其是对不规则应用；另外，m p i 程序不适合自动的性能优化，而随着问题规模的增长， 手工的优化又太困难。总结起来，利用这样的开发模型进行并行应用的开发，开发人员 的负担很重，又涉及很多比较繁琐重复的工作。 所以，人们一直希望利用各种工具来辅助并行程序的开发，尤其是对于其中比较机 械和重复的部分，而程序员可以专注f 并行程序开发的“核心、本质”的问题和优化。 中用科学院博士学位论文 人们对并行程序开发模型和编译环境的期望有菪干个方面：首先可以替代程序员承 担大量重复性的开发工作，这样大大开发过程的人工工作量；然后是在开发人员少量参 与的情况下，取得接近于x _ - 1 2 开发的程序的性能：最后，能够提供一个优秀的开发接口， 使得开发人员可以有效的参与开发，在此基础上，如果开发人员投入相当的精力可以 进一步对性能进行优化。 比较早的并行开发语言是h p f ，作为对f o r t r a n 语言的一个扩展，h p f 提供了一系 列的制导。开发人员可以利用这些制导来说明稗序中的数据分布和并行性。o p c r t m p 是 个比较成功的共享内存多处理开发模型，人们在此基础上。提出了增加一些数据分布 制导，来适应分布式的开发环境，这种扩展一般被称为分布的o p c n m p 。 经过业界、学术界多年的探索和实验，人们发现，基于分布共享存储的程序设计模 型，有望在近期提供一个同时具有高性能、可适应性和高牛产率的解决方案。这就是分 割的全局地址空间模型( p a r t r i o n e d g l o b a l a d d r e s ss p a c e m o d e l ，简称p g a s 模型) ，这 种显式并行模型，通过对串行语言的制导扩展，提供局部性和并行性的充分描述，并把 复杂的通信处理转化成对共享变量的访问。此外，该模型同时支持粗、细两种编程模式， 允许用户程序的增量式开发。该模型能适合共享存储、消息传递机器、混合存储体系、 p i m 等多种并行体系结构。 p g a s 模犁分为基于库、基于语言扩展两大类。基于库的模式有三类实现：m p i - 2 ( a r g o n n e 实验室) 、s h m e m ( a m e s 实验室和c r a y ) 和g l o b a la r r a y s ( p n n l 即太平 洋西北国家实验室) ：基于语言扩展的模式也有三个：c o - a r r a yf o r t r a n n u m 9 8 、u n i f i e d p a r a l l e lc e 1 9 0 4 l 、t i t a n i u m y e l 9 8 】( j a v a 的并行扩展) 。 对于p g a s 语言的潜力、及其对丁编译技术的挑战，很多的实验和文章进行了论 述 w a l l 0 2 , b e r 0 3 ，r a b 0 3 ，c a n 0 3 ，e 1 9 0 2 ，c o a 0 3 ，a n dc h e n 0 3 ，普遍认为，p g a s 语言有希 望成为兼具有可编程性和高性能的程序设计语言。对于r i c e 的c a f 编译器( c o - a r m y f o r t r a n ) 、u cb e r k e l e y 与h p 的u 1 ) c 编译器的初步试验 c o a 0 3 ，c h e n 0 3 ，c o m p 表明， p g a s 语言编写的粗粒度并行程序与m p i 程序性能相当。这是个令人鼓舞的进展。 u p c 语言获得普遍的厚望，凝结了政府、企业和学术界各方的努力的u p c 语言规 范v i 0 于2 0 0 1 年2 月发布。语言规范的参与者包括g w u , i d a , d o d ，a r s c 。c o m p a q , c s c ，c r a y , e m u s 。l i p , i b m , i n t r e p i dt e c h n o l o g i e s ，l b n l , l l n l ，删。s g ls u n m i c r o s y s t e m s ，u cb e r k e l e y , a n du sd o e 等等。u p c 有库函数、i o 和语言规范三个工作 组在推进语言的发展。 目前，在u p c 语言的支持方面：e t n u s 的t o t a l v i e w 6 4 已经支持对u p c 的调试。已 经开发或者发布的u p c 编译器有：h pu p c i c o m p 、c r a yu p c i c m y 、基于g c c 的i n t r e p i d 编译器 g c c 、b l u e g e n e l 的u p c 、u cb e r k e l e yu i ) c 瞰i l f 0 1 等。m i c h i g a n 技术大学正在 针对集群系统，研究第一代的运行时系统m u p c i s a v 0 2 。 在c o - a r r a yf o r t r a n 的支持方面：s g i 公司、r i c e 大学分别开发了自己的c o - a r r a y 6 第二章背景知识 f o r t r a n 编译器，m i n n e s o t a 大学、u i u c & n c s a ( p a n d a h d f 的对于并行i o 的研究) 也 在开t tc a f 相关的研究。而t i t a n i u m 的编译平台已经在u cb e r k e l e y 等开展【s u 0 4 】。 2 3 并行化编译 并行化编译是解决并行程序开发的一种重要方法。并行化编译系统的作用足自动或 半自动地把串行程序转换成并行程序。其优点是：自动的并行性发掘。数据分布使降低 了开发人员的负担；针对特定的目标体系结构作相应的优化，带来一定的性能可移植性； 在这种开发模型中，开发人员只需要保证串行输入的正确性，所以降低了调试难度；另 外遗留的串行程序的重用变得容易。这些特点都使得开发人员可以不需要对于应用程序、 目标机器的特点作深入地了解，避免了大量的重复劳动。然而这也使得编译器承担了艰 巨的工作，这也是至今仍没有达到实用程度的商用系统，自动并行化编程模型难以得到 广泛应用的一个重要原因。 d h p f 、p a r a f r a s e 、p f c 、s u i f 、p o l a r i s 等都是国际上著名的自动并行化编译系统。 虽然有着广泛的应用前景，迄今为止，全自动并行化系统还远没有达到实用的程度，特 别是对丁二分布内存的并行处理系统，自动并行的性能不够理想。 造成这种现象的原因在于体系结构的分布式特征和应用问题的复杂性。 体系结构中的分布式内存访问，缓存之间的一致性开销，编译器必须对此类特征给 予充分考虑，并进行相应的优化。所以必须同时保证一定的并行性和局部性，同时解决 紧密耦合的这两个复杂问题，足并行编程的主要问题。而这个问题对于并行化编译器则 尤其困难。 应用程序的并行性和局部性特征的复杂性。实际的应用程序具有多种表现形式的并 行性和局部性，这给编译程序的分析和表示造成了巨大的困难。现实世界中的物理现象 具有很多非规则特征，离散的粒子系统，不同成分和相的物质、连续的但是物理特征差 异很大非常不对称。其特征是，不具有广泛的空间对称性，并随着时问的推进，其结构 可动态演化。要有效模拟这样系统，并取得满意的性能，就需要采用与之对应的数据结 构，例如基于稀疏矩阵和指针的非规则数据结构。 并行化编译中适当地引入程序员的干预，会使并行化的效果显著提高。向源程序添 加用户制导以提供辅助信息和交互式编译是两种典型的方式。采用这样的方式，编译器 和开发人员之间的信息表示方式决定最终的开发效率。这个问题并不简单，解决它也具 有相当的使用价值，前人提出了各种方法，不过大多数仍然是比较简单和初步的。 一个并行化编译过程一般要进行并行性分析、数据和计算的分解，以及通信优化等 工作。与之配合的，还需要进行很多的辅助分析、变换和优化。其中的各个阶段都可以 采取半自动的方式，a g 年, j 用一定的用户输入辅助信息来进行 中田科学院博士学位论文 圈2 - 1a u t o p a r 并行化编译器的主要结构 图2 一l 所示为a u t o p a r 并行化编译器的简略结构。其中并行化编译部分包括四个主要部 分。并行分析发现程序中的并行性。数据分布同时考虑并行性和局部性来进行程序的计 算和数据分解。计算划分阶段决定各个语句的计算划分，同时进行数据分布的微调，根 据数据分布和计算划分进行一定的性能优化程序变换。而通信优化则对远程的数据访问 进行优化。可以看至其基本思想始终是围绕着并行性和局部性进行优化，又表现为由粗 到细的若干步骤。 2 4 自动数据和计算分解 在数据并行模型中，数据分布和计算划分是并行化的基础，其方案的优劣对并行性 能有根本的影响。数据分布需要解决的问题是同时保证程序的局部性的和可利用的并行 性。 在用户手写的数据并行程序中，数据分布和计算划分是很重要的问题，同时也是一 个繁琐的问题。h p f 的提出就是为了减轻这些负担，用户通过标准的制导可以比较简单 的表达数据分布，然后用一些规则由数据分布推导出计算划分呻f 9 3 。在h p f 中能够 支持的数据分布模式限于b l o c k - c y c l i c 方式，然而即使对于规则的科学计算程序，这些分 布模式仍然是不充分的，近年来提出了一些新的数据分布方式 b r u 8 8 ，l e n 8 7 ，n a i k 9 3 ， n a v 0 3 。 h p f 减少了用户的机械的工作，然而用户仍然要确定数据分布的基本方式，编译程 序只负责数据分布的细化工作，例如由关键数组的数据分布推导其他数组的数据分布， 以及具体的参数的确定。然而对于用户提供关键制导需要对应用程序和目标机器的深入 了解，而且 玎) f 不能很好的保证性能的可移植性。 所以人们提出了自动的数据分布，编译器根据输入程序的分析结累和机器参数，自 动产生数据分布。这方面有很多代表性的工作 a y 9 9 8 ，g a r 0 1 ，a n d 9 7 , p a l 9 5 ，p a l 9 6 , r a m 9 5 ， k r e 9 6 ，g u p 9 2 ，n a y 0 3 ，l e e 9 7 。大部分的工作都采用一定的对准和分布方法，并主要考虑 分布问题，具体的方案有进行全局的对准和进行局部的对准的区别。按照特征，这些方 案可以按照是否支持动态数据分布分为两类。支持动态数据分布的这类又可以按照是 否显式的构造数据分布搜索空间进一步分为两类。 目前为止，这些方案仅局限于规则的程序，然而仍不能取得和手写代码相比的性能， 而且在多维分布上面有较多的局限。 8 第二章背景知识 2 5 整数线性规划 整数规划可以用来解决一大类实际问题，这些问题关系到稀缺、非连续资源的管理 和使用，通过这种方法可以有效的提高资源的使用效率。一些实际的例子例如超大规模 集成电路的设计，通信、交通网络的设计和使用，大规模人员管理。此类的经典形式化 问题包括背包问题( k n a p s a c kp r o b l e