（计算机应用技术专业论文）串行程序并行化及其在桌面网格中的应用.pdf

r 苏州大学学位论文使用授权声明 ! l l ll f ii i i iii ii i i r l li ii y 17 3 2 1 2 0 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属在年月解密后适用本规定。 非涉密论文口 论文作者签名：趣监垦聋 日 期：2 q l q ：啦：l 孑 导师签 _ 一 串行程序并行化及其在桌面网格中的应用摘要 摘要 随着计算机软、硬件技术的迅速发展，高性能计算逐渐在越来越多的行业中得 到应用。并行计算是实现高性能的一种重要的技术途径，其关键环节是并行程序设 计。串行程序并行化作为并行程序设计的一个有效手段，主要分为依赖关系分析、 别名分析、数据划分三个阶段。本文在研究串行程序并行化的基础上进行了如下工 作： 首先，依赖关系分析是串行程序并行化的一个难点。依赖关系分析作为串行程 序并行化的首要工作，是检测程序并行性的基础步骤。依赖关系分为控制依赖关系 和数据依赖关系两类。本文在控制依赖分析阶段，提出了一种改进的控制依赖分析 算法。该改进算法通过引入函数调用和返回引起的控制转移来计算函数间的控制依 赖关系。在数据依赖分析阶段，分别给出了语句问假依赖和迭代间假依赖的消除算 法描述，并将假依赖消除算法应用到一种并行划分算法以验证算法的正确性。 其次，别名分析也是串行程序并行化中的一个重要阶段。别名分析的好坏会影 响依赖关系的准确性，从而影响并行化程度。本文在别名分析阶段给出了一种流不 敏感的别名分析算法。该算法在现有别名分析的基础上，通过添加别名集更新操作 提高了别名分析的精度。 此外，本文分析了半导体集成工业中内存检测计算面临的问题以及现有的解决 方法。在此基础上，把桌面网格引入内存检测计算，给出基于桌面网格的数据划分 算法以实现数据的并行化，从而提高了内存检测计算的性能。 本文对串行程序并行化部分算法的研究和改进具有一定的现实意义。首先，它 对依赖关系分析和别名分析方法的研究以及部分程序并行化算法的改进具有一定的 参考价值，在一定程度上推动了串行程序并行化算法的研究。其次，它针对内存检 测计算所面临的问题，给出了基于桌面网格的数据划分的解决方案，为其它类似的 应用提供了借鉴。 关键词：程序并行化、控制依赖、数据依赖、别名分析、桌面网格 作者：姚辉萍 指导教师：杨季文 - _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 。 a b s t r a c t p a r a l l e l i z a t i o nf o rs e r i a lp r o g r a m sa n di t sa p p l i c a t i o no nd e s k t o pg r i d -_-_-_-_-_-_-。_-_-_-。-。_。-_-_。_。_-。-。-。_。i。_。_。一一 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rs o f t w a r ea n dh a r d w a r e ，h i g h - p e r f o r m a n c e c o m p u t i n gh a sb e e ng r a d u a l l ya p p l i e dt oa ni n c r e a s i n gn u m b e ro ff i e l d s p a r a l l e lc o m p u t i n g i sa ni m p o r t a n tt e c h n i c a lw a yt oa c h i e v eh i g hp e r f o r m a n c e p a r a l l e l i z a t i o nf o rs e r i a lp r o g r a m s ，as i g n i f i c a n tm e t h o do fp a r a l l e lc o m p u t i n g ，c a nb em a i n l yd i v i d e di n t ot h r e ep a r t s ： d e p e n d e n c ya n a l y s i s ，a l i a sa n a l y s i s ，a n dd a t ad e c o m p o s i t i o n b a s e do nt h er e s e a r c h e so n p a r a l l e l i z a t i o nf o rs e r i a lp r o g r a m s ，t h em a i n r e s e a r c hw o r ko ft h i sp a p e ri sa sf o l l o w s ： f i r s t l y , d e p e n d e n c ya n a l y s i si st h ef o r e m o s tt a s ko fp a r a l l e l i z a t i o n d e p e n d e n c yc a n b ed i v i d e di n t ot w oc a t e g o r i e s ：c o n t r o ld e p e n d e n c ya n dd a t ad e p e n d e n c y i nt h es t e po f c o n t r o ld e p e n d e n c ya n a l y s i s ，t h i sp a p e rp r e s e n t sa l li m p r o v e da l g o r i t h m ，w h i c ha n a l y z e s i n t e r - p r o c e d u r a lc o n t r o ld e p e n d e n c yb yt h ec o n c e p t i o no ft h ec o n t r o lt r a n s f e rc a u s e db y f u n c t i o nc a l l sa n dr e t u r n s i nt h ep h a s eo f d a t ad e p e n d e n c ya n a l y s i s ，w eg i v et h ea l g o r i t h m s f o rr e m o v i n gi n t e r - s t a t e m e n ta n di n t e r - i t e r a t i o nf a l s ed e p e n d e n c i e s l a t e r , w ea p p l yt h e a l g o r i t h m st oap a r a l l e ld i v i s i o nm o d e la l g o r i t h mt ov e r i f yt h ec o r r e c t n e s so ft h ea l g o r i t h m s s e c o n d l y , a l i a sa n a l y s i si sa ni m p o r t a n tp h a s e ，w h i c hi m p a c t st h ed e g r e e o fp a r a l l e l i z a - t i o n i nt h i sp a p e r , w ep r e s e n ta l la l g o r i t h mf o rf l o w i n s e n s i t i v ea l i a sa n a l y s i s ，w h i c ha d d s c e r t a i nr u l e so fu p d a t i n ga l i a ss e tt oi m p r o v et h ep r e c i s i o no fa l i a sa n a l y s i s t h i r d l y , t h ep a p e ra n a l y z e st h ei s s u e so fm e m o r yd e t e c t i o ni ns e m i c o n d u c t o ri n d u s t r y , a n dt h eu s u a ls o l u t i o n s o nt h i sb a s i s ，d e s k t o pg r i di si n t r o d u c e di n t om e m o r yd e t e c t i o n c o m p u t i n g t h e n ，t h ei d e ao fm e m o r y d e t e c t i o nb a s e do nd e s k t o pg r i di sp r o p o s e d ，a n da n a l g o r i t h m o fd a t ad e c o m p o s i t i o ni sg i v e nt oi m p r o v et h eo v e r a l le f f i c i e n c y t h er e s e a r c h e sa n di m p r o v e m e n t so nt h ea l g o r i t h m so fp a r a l l e l i z a t i o nh a v ec e r t a i n p r a c t i c a ls i g n i f i c a n c e f i r s t l y , i ti so fr e f e r e n t i a lv a l u ef o rd e p e n d e n c ya n da l i a sa n a l y s i s ， w h i c hp r o m o t e sf u r t h e rr e s e a r c ho fp a r a l l e l i z a t i o n s e c o n d l y , w eg i v ea na l t e r n a t i v es o l u t i o nt om e m o r yd e t e c t i o n ，w h i c hp r o v i d e sr e f e r e n c ef o ro t h e rs i m i l a ra p p l i c a t i o n s k e y w o r d s ：p a r a l l e l i z a t i o n ，c o n t r o ld e p e n d e n c y , d a t ad e p e n d e n c y , a l i a sa n a l y s i s ，d e s k t o p g r i d w r i t t e nb yy a oh u i p i n g s u p e r v i s e db yy a n gj i w e n 第一章 1 1 1 2 1 3 1 4 目录 绪论1 课题背景1 课题研究内容2 课题研究意义3 文章组织结构4 第二章相关知识及研究现状 2 1 串行程序并行化 2 1 1 串行程序并行化的基本概念 2 1 2串行程序并行化的研究概况 2 2 桌面网格技术 2 2 1桌面网格的基本概念和特点 2 2 2网格技术的研究概况 第三章 3 1 3 2 3 3 3 4 3 5 第四章 4 1 串行程序并行化的总体流程 串行程序并行化的整体框架 前端分析 依赖关系分析 3 3 1 控制依赖关系分析 3 3 2 数据依赖关系分析 别名分析 数据划分 依赖关系分析 控制依赖关系分析 4 1 1控制依赖关系分析算法 4 1 2函数调用控制依赖关系计算的常用方法 4 1 3改进的控制依赖分析算法的基本思想 5 5 5 8 1 1 l l 1 2 1 4 1 4 1 5 1 5 1 5 1 6 1 7 1 7 1 9 1 9 1 9 2 1 2 2 _ _ _ _ _ _ _ _ - _ - _ _ - 。_ _ 。1 。 4 1 4改进的控制依赖分析算法的实现方法2 2 4 1 5实例及其结果对比2 4 4 2 数据依赖关系分析- 2 7 4 2 1假依赖的相关概念2 7 4 2 2 假依赖消除的常用方法2 7 4 2 3重命名假依赖消除方法2 8 4 2 4图形变换依赖环路消除方法2 9 4 2 5假依赖消除的核心算法3 l 4 2 6 应用实例3 2 4 3 本章小结3 7 第五章 5 1 5 2 5 3 5 4 第六章 6 1 别名分析3 8 别名分析相关概念3 8 5 1 1别名的概念3 8 5 1 2 别名的分类3 9 5 1 3 别名的表示4 0 5 1 4 别名分析算法的分类比较4 l 流不敏感的别名分析4 4 5 2 1别名分析算法的提出4 4 5 2 2 别名的表示法4 5 5 2 3 别名集更新规则分析4 6 5 2 4 别名分析算法的实现4 7 5 2 5别名分析算法的实例4 9 实验5 0 5 3 1 实验代码选择5 0 5 3 2 实验环境5 1 5 3 3实验结果与分析5 l 本章小结5 2 基于b o i n c 桌面网格的数据划分5 3 问题描述5 3 6 2 基于b o i n c 桌面网格的解决方案5 3 6 2 1 b o i n c 桌面网格的选择5 4 6 2 2 w r a p p e r 技术5 6 6 2 3 数据划分算法5 7 6 3 实验6 0 6 3 1 实验环境6 0 6 3 2 参数说明6 0 6 3 3实验结果与性能分析6 0 6 4 本章小结6 2 第七章总结与展望6 3 7 1 总结6 3 7 2 展望6 4 参考文献6 5 攻读硕士学位期间发表的论文7 1 致谢7 2 串行程序并行化及其在桌面网格中的应用第一章绪论 第一章绪论 1 1 课题背景 随着计算机软、硬件技术的发展，高性能计算已逐渐渗透到了包括生物信息、 材料科学、计算机辅助工程、地理信息系统、数字化影视、医学影像、电子设计自 动化、石油勘探、金融保险、动漫渲染、大气气象、游戏等各个专业领域u i 。并行 处理或并行计算由于能够同时使用多种资源解决计算问题，已成为实现高性能计算 的一种重要的技术途径【2 】。当前，大量高性能计算机都是并行机。如果要充分发挥 这些机器的效用，则必需建立在并行处理的基础上【3 】。 并行程序设计是并行处理的一个重要环节。当前并行程序设计主要有两种途径： 使用并行程序设计语言编写程序和串行程序并行化。由于历史原因，很多领域的应 用程序往往是串行的，难于在并行机上发挥作用，而将这些程序使用并行程序设计 语言重新编写，转换为并行程序，又有着很高的技术门槛，普通的程序员难以完成， 往往需要并行程序设计的专家的参与。因此，用户希望存在一种可靠的软件，能够 将现存的串行程序自动转换为高效的并行程序，从而发挥并行机的处理优势，这样 不但能减轻程序员的负担，更可以充分利用已成熟的串行程序资源【4 】。 并行计算中，大型机和超级计算机扮演了重要的角色。但是由于其造价昂贵、 维护复杂、配置不便，普通企业和科研组织难以承受，从而限制了很多科学研究工 作的开展和并行计算的应用。随着计算机的普及，个人电脑已成为必备品。而大多 数个人电脑仅使用很少的资源，这意味着计算机资源的大量闲置。互联网的出现使 得连接调用这些闲置的计算机资源成为现实。于是，一种廉价的、高效的、易维护 的计算方式应运而生一网格计算。网格计算通过利用大量异构计算机( 通常为桌 面p c ) 的闲置资源，将其作为嵌入在分布式基础设施中的一个虚拟的计算机集群， 为解决大规模的计算问题提供了一种高性能计算、管理及服务的能力。目前，网格 计算主要被各大学和研究实验室用于高性能计算的项目。这些项目往往需要巨大的 计算能力，或需要访问大量的数据。 网格计算为用户处理复杂问题提供了新方法。通过使用网格实现并行处理，可 以用较低的成本获取高的计算性能，是发展的趋势【5 】。并行处理一般有功能并行和 数据并行两种方式【6 】。功能并行主要用于检测并分析串行程序本身的并行性，也是 第一章 绪论串行程序并行化及其在桌面网格中的应用 并行化技术研究的重要内容之一。而数据并行是指将数据划分为若干块，分别映射 到不同的处理机上，每个处理机对所分派的数据进行相同或不同的计算。如何分割 数据以达到较高的加速比和并行效率是数据并行中的关键问题，也是串行程序并行 化研究的重要内容之一。 1 2 课题研究内容 并行处理是计算机系统中能同时执行两个或更多个处理机的一种计算方法。利 用并行处理可以节省大型和复杂问题的解决时间。 本课题主要围绕着串行程序并行化的相关技术展开，研究的是串行程序并行化 几个阶段中的一些相关算法以及这些算法在内存检测计算中的应用。课题根据串行 程序并行化的三个主要阶段：依赖关系分析、别名分析、数据划分，分步研究每个 阶段具体采用的方法，分析方法的不足，并提出新的算法或给出相应的改进算法。 具体研究内容如下： ( 1 ) 研究了控制依赖计算方法，并给出了一种改进的控制依赖计算算法。控制依 赖分析是用来确定一条程序语句的语义变化是否会影响其它程序语句的执行，是程 序并行化的基础。本课题针对现有的控制依赖计算方法的不足，提出了一种改进的 算法。该改进算法通过引入函数调用和返回引起的控制依赖转移来计算函数问的控 制依赖关系，并通过实例验证了该改进算法比原算法更能准确地分析程序的控制依 赖关系。 ( 2 ) 研究了假依赖消除的相关算法。假依赖作为一种特殊的数据依赖关系，是由 对存储单元的多次访问引起的，而不是由语句间的数据流引起的。假依赖的存在会 影响程序并行化程度，所以如何消除假依赖是本课题研究的重点内容之一。本文针 对现有研究工作的不足，分别给出了语句间假依赖和迭代间假依赖的消除算法，并 将这两种假依赖消除算法应用到p d m a 【7 】算法，从而减少了程序的数据依赖关系， 提高了并行化程度。 ( 3 ) 研究了别名分析的相关算法，提出了一种流不敏感的别名分析算法。别名分 析对程序分析、程序自动并行化有着十分重要的作用。不进行别名分析或分析算法 选择不当，可能会影响分析结果的可信度，甚至会导致分析结果的完全不正确。本 文给出的别名分析算法在抽象语法树的基础上，通过添加别名集更新操作提高别名 分析的精度。 2 串行程序并行化及其在桌面网格中的应用第一章绪论 ( 4 ) 描述了半导体内存检测计算所面临的问题，提出了一个基于桌面网格的解决 方案。重点研究了网格平台的选取策略、针对该平台和问题本身特性的数据划分的 方法、以及如何提高加速比和并行效率。实验表明，基于桌面网格进行合理的数据 划分可以提高内存检测计算的性能。 1 3 课题研究意义 随着i n t e r n e t 的迅猛发展和计算机性能的不断提高，人类的应用需求正日益朝着 多样化、多功能、高性能方向发展。对于许多大规模科学与工程计算问题，仅一台 高性能计算机已不能满足需求，它们需要将地理上分布的、异构的多台计算机资源 通过高速网络连接起来，共同完成计算任务。利用网格进行并行计算所带来的高效 率已经得到社会的认可。然而国内外研究并行计算大多停留在理论上，或者利用网 格平台实现某个具体问题的并行应用的实例还是很少，所以如何利用网格来提高实 际生活、生产中应用程序的性能是研究人员普遍关心的问题。 本课题主要研究了串行程序并行化和桌面网格的相关技术，提出了新的算法或 给出部分改进算法。尽管这些算法并不一定是最优算法，还有待于进一步的研究与 完善，但是本课题所做的工作还是具有一定的理论价值和实践意义，具体体现在如 下方面： ( 1 ) 本文在依赖关系分析阶段给出的相关算法，对控制依赖分析和数据依赖分析 方法的研究和改进具有参考价值。比如将一种经典的控制依赖计算算法通过引入函 数调用和返回引起的控制转移来分析函数间的控制依赖关系，从而准确地计算实际 程序的控制依赖关系。此外，本文针对现有研究工作的不足，分别给出了语句间假 依赖和迭代间假依赖的消除算法描述，并将这两种假依赖消除算法应用到p d m a 算 法，从而提高了p d m a 算法的性能。 ( 2 ) 本文提出的别名分析算法对部分串行程序并行化算法的研究具有参考价值。 本文给出的流不敏感的别名分析算法，在已有研究工作的基础之上添加别名集更新 操作，提高了别名分析的精度。该算法在一定程度上推动了串行程序并行化算法的 研究。 ( 3 ) 本文提出基于b o i n c 桌面网格的内存检测并行计算，并根据平台的特征和问 题本身的特性给出合理的数据划分以获得较好的加速比和并行效率，为其它类似的 应用程序获得高性能提供了借鉴。 3 第一章绪论串行程序并行化及其在桌面网格中的应用 综上所述，课题研究的内容对于串行程序并行化及其在桌面网格的应用，具有 一定的现实意义和参考价值。 1 4 文章组织结构 全文的组织如下： 第一章简要介绍了课题提出的背景、课题的研究内容、课题的研究意义与文章 的组织结构。 第二章介绍了串行程序并行化和桌面网格的相关概念，主要说明了串行程序并 行化各个阶段中的基本概念和研究现状，桌面网格的基本特点及其研究概况。 第三章主要介绍了串行程序并行化的整体框架。针对串行程序并行化的前端分 析、依赖关系分析、别名分析与数据划分这四个主要阶段，介绍了其中的相关技术 与方法。 第四章介绍了依赖关系分析的相关概念和常用技术，在此基础上分析了现有方 法的缺陷，提出改进的控制依赖计算算法。此外，给出了语句间假依赖和迭代问假 依赖的消除算法，并将给出的假依赖消除算法应用于一种并行划分算法，从而在一 定程度上提高了并行化程度。 第五章介绍了别名分析的基本概念、常用方法，在此基础上给出了一种流不敏 感的别名分析算法。该算法以j a v a 语言为例，提出了相应的别名表示法和别名集更新 规则，同时给出了流不敏感的别名分析算法的实现，并通过实验验证了该算法的有 效性。 第六章针对半导体内存检测计算面临的问题，提出了基于桌面网格的数据并行 化的思想，并结合b o i n c 桌面网格平台特点和问题本身的性质给出了一种数据划分 算法，并通过实验验证了该想法的可行性和有效性。 第七章对所做的工作进行总结，并对未来工作进行展望。 4 串行程序并行化及其在桌面网格中的应用第二章 相关知识及研究现状 第二章相关知识及研究现状 串行程序并行化作为实现并行处理的重要手段，是获得高性能计算的有效途径。 然而由于大型机和超级计算机的使用成本高昂，通过网格进行并行处理来实现高性 能已成为发展趋势。本章首先介绍了串行程序并行化过程中的基本知识与研究发展， 然后介绍了桌面网格的相关概念、特点，并详细说明了网格技术的研究现状。 2 1 串行程序并行化 2 1 1串行程序并行化的基本概念 串行程序并行化是把串行程序进行分解，识别出其中可并行运行的部分。程序 并行化时关心的是正确率和效率，它要求在不破坏程序正确性的前提下改善程序的 性能。要对串行源程序进行并行化，就要理解源程序，找出可并行的部分进行并行 化。串行程序并行化的总体流程主要分为依赖关系分析、别名分析、数据划分三个 阶段。下面简要介绍上述三个阶段的相关知识。 1 依赖关系分析 一个程序的各部分之间总存在一定的依赖关系。并行化的任务就是在不破坏这 种依赖关系的前提下，把程序分解成多个任务来并行执行，从而缩短整个程序运行 所需的时间。因此，依赖关系分析的理论和技术是串行程序并行化的基础。只有作 出正确的依赖关系分析，才能保证并行化的正确性。只有找到尽可能多的不相关部 分，才能提高并行化的程度。 在一个程序中，若事件或动作b 发生前，事件或动作a 必须发生，则称b 依赖 于a ，称这种关系为依赖关系【2 】。依赖关系分为控制依赖关系和数据依赖关系。下 面我们简要介绍下这两类依赖关系的基本概念。 ( 1 ) 控制依赖关系 控制依赖是指后面执行的指令依赖于前面计算的结果【3 】。控制依赖会导致程序 流程的变化。对于控制依赖关系，相关的两个实体可以是基本块，也可以是语句。 结合控制依赖关系的相关知识，本文给出如下几个定义。 定义2 1 控制流图( c o n t r o lf l o wg r a p h ，缩写为c f g ) 是一个有向图g = ( v ，e ) ， 5 第二章相关知识及研究现状串行程序并行化及其在桌面网格中的应用 这里v 是节点的有穷非空集合，e 是边的集合。图中的节点表示语句，边“_ v 表示 从节点u 到v 可能的控制信息流向。g 增加了两个特殊的节点：进入节点s t a r t 和退出 节点s t o p 。其中，进入节点s t a r t 没有前驱，由它可以到达图中的每个节点；退出节 点s t o p 没有后继，从图中的每个节点都可以到达它。 定义2 2 节点u 是节点v 的后必经节点( p o s td o m i n a t o r ) ，当且仅当控制流图中的 每一条从v 至l j s t o p 的路径( 不包括v ) 包含u 。 定义2 3 节点u 是节点v 的直接后必经节点( i m m e d i a t ep o s td o m i n a t o r ) ，当且仅 当： 1 ) 节点u 是v 的后必经节点； 2 ) 不存在节点p ，使得p 是v 的后必经节点，g u 是p 的后必经节点。 定义2 4 后必经节点树( f o r w a r dd o m i n a n c et r e e ，缩写为f d t ) 是用来描述后必 经节点的一种辅助数据结构。在后必经节点树中，如果节点u 是v 的直接后必经节点， 则从节点u n v 之间存在边。 定义2 5 令p 是一个源程序，s 1 和s 2 是p 中的语句。s 2 控制依赖于s l ，当且仅当 在控制流图中： 1 ) s l 和s 2 之间存在一条路径； 2 ) 存在一条执行路径从s l 到程序结束但不经过s 2 。 定义2 6 控制依赖医 ( c o n t r o ld e p e n d e n c yg r a p h ，缩写为c d g ) 是一个有向图g = ( ve ) ，其中v 表示语句节点的有穷非空集合，e 表示边的集合。边u - v 表示从结 点u n v 的控制依赖。g 中有一个特殊的结点：起始结点，它没有前驱，由它可以到达 图中的每个结点。 从上面的定义可以看出，控制依赖在程序中的典型表现是条件语句和循环语句。 条件语句中，条件判断部分与真、假值对应的语句体之间存在控制依赖关系。循环 判断语句决定了循环体中语句将被执行的次数，即决定了是否进入循环体。因此循 环判断语句和对应的循环体之间存在控制依赖关系。 ( 2 ) 数据依赖关系 数据依赖是指后面的计算依赖于前面的计算结果，是由读写同一数据引起的。 直观地讲，数据依赖就是在运行多个执行过程时访问相同的数据。数据依赖分为三 6 r ( s 1 ) ：表示语句s 1 中的读变量集。 w ( s 2 ) ：表示语句s 2 中的写变量。 定义2 7 两个语句s 1 和s 2 ，若存在变量x w ( s 1 ) a x r ( s 2 ) ，且s l 和s 2 之间存在 一条执行路径，则称s 2 流依赖于s 1 ，记作：s 1 s 2 。 定义2 8 两个语句s i 和s 2 ，若存在变量x w ( s 1 ) a x w ( s 2 ) ，则称s 2 输出依赖 于s l ，记作：s l 口s 2 。 定义2 9 两个语句s 1 和s 2 ，若存在变量x r ( s 1 ) a x w ( s 2 ) ，r s l 和s 2 之问存在 一条执行路径，则称s 2 反依赖于s 1 ，记作：s l 。s 2 。 其中，输出依赖和反依赖是由对存储单元的多次访问引起的，而不是由语句间 的数据流引起的，因此它们不是真正的数据依赖。 2 别名分析 别名分析用于获得指向相同存储位置的指针或引用表达式，是提高依赖关系分 析精确度的有效途径，在串行程序并行化中具有重要的意义。别名分析用来判定可 能用两种或两种以上的方式来访问相同的存储位置的情况。分析程序中可能的别名 信息可以提高依赖关系分析的准确性，从而提高并行化的程度。 别名分析结果受许多因素的影响，我们根据这些冈素对别名分析进行分类，这 些因素包括： 流敏感的分析( f l o ws e n s i t i v ea n a l y s i s ) ：考虑程序控制流信息，如条件、循环 语句等，即在进行别名分析时，需要考虑程序语句的执行顺序，将程序作为一个语 句序列来处理。 流不敏感的分析( f l o wi n s e n s i t i v ea n a l y s i s ) ：不考虑程序控制流信息，将程序作 为一个语句集合来处理，即在进行别名分析时认为程序语句是无序的。 上下文敏感的分析( c o n t e x ts e n s i t i v ea n a l y s i s ) ：考虑相同函数在不同的调用点 的上下文信息。上下文敏感的分析方法可按一定的准则对同一函数不同的调用点的 调用上下文进行区别，从而针对不同的调用点产生不同的别名分析结果。 7 第二章 相关知识及研究现状串行程序并行化及其在桌面网格中的应用 上下文不敏感的分析( c o n t e x ti n s e n s i t i v ea n a l y s i s ) - 在不同的调用点合并相同 函数的调用上下文信息。即如果一个函数被多次调用，则此函数每个调用点的别名 信息被合并到一起。 流不敏感的别名分析算法不考虑函数内的控制流信息，因此其分析精度比流敏 感的别名分析算法要低，但时间和空间效率较高。上下文不敏感的别名分析由于返 回到各个调用点的别名信息综合了所有调用点函数调用的共同行为，所以其分析结 果相对于上下文敏感的别名分析而言并不准确，但是可以获得相对较快的分析速度。 综上所述，我们可以看出，流敏感、流不敏感、上下文敏感、上下文不敏感别名分 析算法各有优势，但都有各自的不足。 3 数据划分 由于多处理机和多计算机包含多个计算节点，因此存在计算在各个计算节点上 的分布问题。对于共享内存系统，需要考虑计算在多处理机间的划分，而数据则不 需要分割。对于分布内存系统，则需要同时考虑计算和数据在处理机间的分布问 题。 对基于分布内存的串行程序并行化系统而言，数据划分对程序性能的影响很 高。数据划分依赖于问题本身的性质、目标机器以及可用的处理器数量。一般情况 下，这是n p 难题。k e n n e d y 等人指出，利用最新的0 1 整数规划技术可以有效地求出 这些n p 难题的优化解【9 】。g u o 等人从无通信的角度入手，研究了线性数据划分的基 本问题【l o 】。为了避免分布内存系统的数据划分的复杂性，c o x 等人研究了将软件分 布式共享内存作为分布内存系统并行编译目标的可能性【1 1 】。 数据划分的一个研究热点是自动数据划分。自动数据划分的目标是在程序分析 的基础上，全盘考虑数据划分与计算分割的需要，推导出一个全局较优的数据划 分模式，从而在尽可能大地开发程序中的并行性的同时，减少程序通信、同步的开 销【1 2 。 2 1 2 串行程序并行化的研究概况 自从有了面向大型计算机的编译器，人们就开始对编译器的性能进行研究，也 就开始了对编译器的优化性能的研究。而对串行程序并行化技术的研究，最早可以 追溯至t 2 0 世纪6 0 年代，虽然当时还没有串行程序并行化方面的专门研究，但是，当 时的编译器研究人员就已提出了数据依赖这个概念，而数据依赖正是串行程序并行 8 串行程序并行化及其在桌面网格中的应用第二章 相关知识及研究现状 化的关键技术之一。 2 0 世纪8 0 年代中期，串行程序并行化随着并行计算机的发展而逐渐兴起。其前 身是始于7 0 年代的由l a m p o r t 【1 3 1 和k u c k 等人【1 4 ，1 5 】最早提出的程序向量化。程序 向量化是将串行程序转换为在向量机上运行的程序。n 8 0 年代后，向量化技术发 展成熟，并出现了有代表性的程序向量化系统，如i l l i n o i s 大学的p a r a f r a s e 【1 6 ，美 国r i c e 大学研制的f o r t r a n 转换器( p f c ) 【1 7 1 ，独立软件制造商的k a p 【1 8 1 和v a s t 【1 9 1 。 串行程序并行化技术以向量化为基础。因此，程序并行化和向量化有很大的共同之 处，其一是它们的优化对象是相同，二者均把源程序作为优化的对象；其二是它们 所依赖的基础技术相同，二者均把依赖关系分析技术作为优化的依据【2 0 1 。 自从9 0 年代以来，串行程序并行化技术取得了很大的进展，并涌现出很多自动 并行化系统，如g r e e n w i c h 大学的c a p t o o l s 【2 1 ，s t a n f o r d 的s u i f 【2 2 ，u i u c 的p o l a r i s 【2 3 。我国在串行程序并行化方面的研究也取得了较大的进展，比较有代表性的有复 旦大学的自动并行化系统a f t 2 4 ，清华大学的交互式并行化系统t i p s 2 5 ，南京大 学的基于j a v a 的程序自动并行化系统j a p s 【2 6 ，2 7 。此外，我国比较具有代表性的商 业化的自动并行软件是北京飞箭公司的有限元自动并行化软件。它能够根据提交的 满足要求的文件自动生成并行的有限元软件。 串行程序并行化软件可以作为一般的软件单独使用，也可以作为优化器嵌入到 并行编译器中。前一种是在程序的源代码级实现的，用户可以看到程序并行化后的 代码，并可以对其进行修改。因此，这种方式不仅可以为并行程序员提供参考，而 且具有良好的可移植性。而后一种是在并行编译中由编译器在中间代码一级实现并 行化。程序并行化工具与并行编译系统的关系如图2 1 所示： 串行程序并行化软件根据设计目的可分为专业性的和通用性的。专业性的并行 化软件通常是针对某一特定的应用领域，正如前面提到的飞箭公司的有限元并行化 软件，适用于有限元分析领域。而通用性的并行化软件不特定于某一具体领域，而 是试图寻找各种应用程序中的并行性，如南京大学的j a p s 。但就目前串行程序并行 化软件的发展来看，不管是通用性软件还是专业性软件，大都偏向于数值计算领域， 所使用的关键技术是依赖分析，包括数据依赖分析和控制依赖分析。在非数值计算 方面，串行程序并行化软件的能力还显得非常弱。一方面，这与程序并行化技术来 源于程序的优化编译技术有关，也与大型机最初主要用于科学计算有关；另一方面， 在非数值计算领域，还没有成熟的程序并行化理论产生。也许随着人工智能的发展， 9 第二章相关知识及研究现状串行程序并行化及其垄塞亘堕整皇塑查旦 图2 1 并行编译系统结构 串行程序并行化会在非数值计算领域取得重大进展。 串行程序并行化软件根据程序信息的获取方式，可分为人机交互式的和完全自 动并行化的两类软件。前者有些不需要读入程序，只需用户输入一定的信息就可实 现并行化，有些则需要读入源程序文件，并在分析过程中提示用户输入信息来实现 并行化。而完全自动并行化软件只需用户输入能够正确运行的串行源程序，所有其 它步骤则由并行化软件来完成。人机交互式的软件在实现上是相对容易些，在某些 具体的领域比如有限元分析、物理流场分析中已取得了良好的效果，并可以迅速投 入使用。完全自动并行化的实现有许多困难，对有些源程序并行化的效果还不是很 好，离实际应用还有一定的距离。但是从长远的观点来看，完全自动并行化是有很 大的潜力的，是串行程序并行化发展的方向。 串行程序并行化软件根据所输出的并行程序适合的体系结构，可分为面向共享 内存和面向分布式内存两类。面向共享内存的程序并行化软件已取得了很好的研究 成果。而基于分布式体系结构的并行化软件由于不能共享内存，造成了数据的远程 访问和通信时问的增加，其并行化后的加速比和并行效率要低于基于共享内存的并 行程序。然而，基于分布式体系结构的并行机是大型机发展的主要方向，随着大型 机内部网络技术的提高，基于分布式内存的程序并行化将有很大的应用前景。 1 0 串行程序并行化及其在桌面网格中的应用第二章相关知识及研究现状 2 2 桌面网格技术 2 2 1 桌面网格的基本概念和特点 网格是一个集成的计算与资源环境，或者说是一个计算资源池，它能够充分吸 纳各种计算资源，并将它们转化为一种随处可得的、可靠的和经济的计算能力。这 里的计算资源，除了各种类型的计算机外，还包括网络通信能力、数据资源等 2 8 。 桌面网格是网格中的一种，其计算资源主要是由桌面p c 机组成【2 9 1 。这种计算 模型能够把计算量大的应用划分为若干计算量较小的子任务，并通过网络传输把子 任务分配给各个p c 机处理。由于p c 机具有价格低廉、性能高效等特点，所以利用桌 面网格可以大大节省计算成本，提高效率。作为一项新兴的技术，桌面网格具有如 下基本特点【2 9 】： ( 1 ) 异构性 桌面网格的异构性主要表现在组成网格的每个工作节点可能有不同的处理器、 不同的内存容量、不同的数据表示、不同的操作系统以及不同的通信带宽等。将异 构资源映射成统一管理的逻辑资源，并实现资源的动态收集、计算与调度是桌面网 格资源管理系统的关键。 ( 2 ) 动态性 桌面网格中的资源不但是异构的，而且是动态变化的。桌面网格的动态性包括 资源的动态增加和动态减少。网格系统的规模总是不停地改变：有的资源出现了故 障，有些新资源要加入网格中。网格系统必须适应网格的这种动态性，不仅需要做 到对高层用户透明或尽量减少用户的损失，而且需要从可利用的资源中选取最佳资 源为用户提供服务。 ( 3 ) 分布性 分布性是桌面网格最主要的特点。桌面网格的分布性主要体现在其资源是分布 的。组成桌面网格的计算能力( 包括不同的计算机，各种类型的数据库，以及其他 资源) ，是分布在地理位置不相同的多个地方，而不是集中在一起。这些资源属于不 同的组织，他们之间有些建立了信任关系，有些则没有。所以如何管理没有信任的 网格资源是桌面网格系统中一个重大挑战。 ( 4 ) 自治性与管理的多重性 桌面网格资源的所有者对资源拥有最高级别的管理权限，网格应该允许资源拥 1 1 第二章相关知识及研究现状串行程序并行化及其在桌面网格中的应用 有者对他的资源有自主管理的能力，这称为自治性。但桌面网格资源也必须接受网 格的统一管理，否则就无法实现共享和互操作，因此桌面网格的管理具