（计算机应用技术专业论文）并行计算平台的建立及性能分析.pdf

摘要 摘要 传统的并行计算任务往往由大型的并行计算机来完成，因而并行机 的研究也就成为并行计算的主要研究方向，典型的并行计算机系统包括 阵列处理机、向量处理机、共享存储多处理机、分布式存储多计算机和 分布式共享存储多处理机，而进行并行研究的也大多为实力雄厚的科研 机构和企业。随着网络的快速发展，基于机群网络的并行计算也成为并 行计算研究的一个重要方向。 只是拥有机群网络是无法直接进行并行计算的，研究人员在机群网 络上实现了一系列的网络通信工具和辅助编程工具以支持基于机群网络 的并行计算。本文提出并实现了一个并行计算平台。以往并行计算平台 的研究主要集中在对并行程序通信的支持以及辅助并行程序的编写。本 文研究的重点是并行计算平台对并行计算资源的管理以及对并行程序的 管理。 机群网络易于构建，同时也经常发生交化。这种特点就要求在机群 网络上运行的程序有较好的移植性能。本文对并行计算和并行程序进行 分析，提出了一个具有普遍意义的并行程序模型；为了检验并行模型的 可用性，本文实现了一个基于该模型的算例程序。 机群网络结构松散，如何对机群网络中的计算节点进行管理也就成 了并行计算平台研究的一个重要问题。本文中提出的并行计算平台可以 对机群网络中提供并行计算服务的计算节点进行管理。用户需要进行并 行计算时，只要在本地机器通过并行计算平台的控制台就可以获得计算 节点的信息。控制台还支持对并行程序进行管理，因此用户在提供并行 程序后，通过进行简单的操作就可以实现并行程序的任务分配和并行程 序任务的运行。 本文首先对并行计算进行介绍和分析，对并行程序模型以及并行程 序各个任务之间的通信进行分析，给出了一个并行程序的实际例子；然 后重点对现有的并行计算平台进行分析，提出并行计算平台的设计方案； 变三些奎兰堡圭兰堡兰兰 接下来根据设计实现并行计算平台，运行算例程序：最后根据算例程序 的运行数据对平台的性能进行量化分析。 在实现并行计算平台的过程中，主要的研究内容有网络的消息通信， 消息队列的实现，机器间文件的传输以及并行程序通信的实现。 关键宇：并行计算；并行程序模型；机群网络；并行计算平台；加速比 n a b s t r a c t t r a d i t i o n a lp a r a l l e lc o m p u t i n gt a s k sa r eo f t e nal a r g ep a r a l l e l c o m p u t e rt oc o m p l e t e ，t h u sp a r a l l e lr e s e a r c ho np a r a l l e lc o m p u t e r h a sb e c o m et h em a i nd i r e c t i o no fr e s e a r c h w i t ht h e r a p i d d e v e l o p m c o m p u ti n c l u s t e r e n to ft h en e t w o r k ，n e t w o r k b a s e dc l u s t e ro fp a r a l l e l gh a sb e c o m ea ni m p o r t a n tr e s e a r c hd i r e c t i o n n e t w o r ki sn o td i r e c t l yu s e d f o rp a r a l l e lc o m p u t i n g c l u s t e rr e s e a r c hi nt h en e t w o r kt oa c h i e v eas e r i e so fn e t w o r k c o m m u n i c a t i o nt o o l sa n dp r o g r a m m i n gt o o l st os u p p o r tc l u s t e r b a s e dp a r a l l e lc o m p u t i n g i nt h i sp a p e r ，ap a r a l l e lc o m p u t i n g p l a t f o r mi sb u i l t p r e v i o u ss t u d yo fp a r a l l e lc o m p u t i n gp l a t f o r m f o c u s e do nc o m m u n i c a t i o n ss u p p o r t ，a n ds u p p o r t i n gt h ep r e p a r a t i o n o fp a r a l l e lp r o g r a m m i n g t h i sp a p e rf o c u s e so np a r a l l e lc o m p u t i n g p l a t f o r mf o rp a r a l l e lc o m p u t i n gr e s o u r c e sm a n a g e m e n ta n d t h e p a r a ll e lp r o g r a mm a n a g e m e n t c l u s t e re a s yt ob u i l dn e t w o r k s ，b u ta l s of r e q u e n tc h a n g e s t h i s f e a t u r er e q u i r e st h a tt h ep a r a l l e lp r o g r a mo nc l u s t e rn e t w o r kh a v e b e t t e rp e r f o r m a n c eo nt r a n s p l a n t a ti o n h o wt om a n a g et h en e t w o r kn o d e w i l lb ea n i m p o r t a n ti s s u eo f p a r a l l e lc o m p u t i n gp l a t f o r m t h i sp a p e rp r e s e n t s a p a r a l l e l c o m p u t i n gp l a t f o r mo nc l u s t e rn e t w o r kf o rp a r a l l e lc o m p u t i n g s e r vic e sa n dt h em a n a g e m e n to fn e t w o r kn o d e t h i sp a p e rf i r s ti n t r o d u c e dp a r a l l e lc o m p u t a t i o na n da n a l y s i s p a r a l l e l p r o c e d u r e s f o r p a r a l l e lp r o g r a m m i n g m o d e la n d c o m m u n i c a t i o n sb e t w e e nt h et a s k s ：t h e nf o c u so nt h ee x is t i n g p a r a l l e lc o m p u t i n gp l a t f o r m ，ap a r a l l e lc o m p u t i n gp l a t f o r mi s p r o p o s e da n dd e s i g n e d ：n e x t ，t h ep a r a l l e lc o m p u t i n gp l a t f o r mi s h i 广东1 = 业大学硕士学位论文 b u i i t ：f i n a l l yp r o c e s st h er u n n i n gd a t ao ft h ep a r a l l e lp r o g r a m r u no nt h i sp l a t f o r mf o rq u a n t i t a t i v ea n a l y s i s k e yw o r d ：p a r a l l e lc o m p u t i n g ： n e t w o r k ：p a r a l l e lc o m p u t i n g p a r a l l e lp r o g r a m m i n gm o d e l ：c 1 u s t e r p 1 a t f o r m ：s p e e d u p 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是 我个人在导师的指导下进行的研究工作及取得的研究成果。尽我所知， 除了文中特别加以标注和致谢的地方外，论文中不包括其他人已经发表 或撰写过的研究成果，不包含本人或其他用途使用过得成果。与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的声明，并 表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取 得的，论文成果归广东工业大学所有 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此 声明。 1 0 1 指导教师签 论文作者签 2 0 0 7 年岁月动日 ， 。 1 1 研究背景及意义 第一章绪论 人们认识并行计算对于加速计算单元的作用已经几十年了。并行计 算在科学及工程应用的计算模拟、商业应用的数据挖掘及事务处理等许 多领域产生了巨大的影响。并行化的成本优势与应用对性能上的需求促 进了并行计算的发展。在工程及设计中，并行计算传统上已成功地应用 于机翼设计，内燃机设计，高速电路设计以及结构设计等方面。在工程 与设计的其他应用则着重对各种过程进行优化。并行计算在科学计算中 的应用主要涉及物理学、计算化学、气象模型、矿物勘探以及灾害预测 等领域。在商业应用方面，利用大规模事务数据在优化商业和开拓市场 的数据挖掘和分析方面产生了巨大的商业利益。巨大的数据量以及数据 的地理上分布特性要求采用有效的并行计算算法来解决诸如规则挖掘、 聚集、分类以及时间一序列分析等问题“1 。 并行计算可以通过并行计算机和个人计算机群来实现。典型的并行 计算机系统包括阵列处理机、向量处理机、共享存储多处理机、分布式 存储多计算机和分布式共享存储多处理机；当代并行计算机体系结构包 括并行计算机体系结构模型( 并行向量处理机p v p 、对称多处理机s m p 、 大规模并行处理机m p p 、分布共享存储多处理机d s m 和工作站机群c o w ) 、 并行计算机存储结构模型( 均匀存储访问u m a 、非均匀存储访问n u m a 、 全高速缓存访问c o m a 、高速缓存一致性非均匀存储访问c c n u m a 和非远 程存储访问n o r m a ) 以及分布式高速缓存与主存体系结构”1 。 计算机硬件技术高速发展，处理器和网络的性能不断地迅速提高， 价格日益下降。并行计算日益从传统的并行计算机转移到由一组工作站 或个人计算机构成的机群。机群是一组独立的计算机的集合体，计算机 间通过互连网络连接：各计算机除了可以作为一个单一的计算资源供用 户使用外，还可以协同工作执行并行计算任务。机群是一种造价低廉、 广东工业大学硕士学位论文 易于构筑并且具有较好可扩放性的并行计算硬件基础”，。 并行计算软件基础主要有操作系统和支持并行计算的软件程序，在 操作系统上实现的支持并行计算程序的软件集可以称为并行计算平台。 目前主要的并行计算平台有基于消息传递的m p i 和p v m 、基于共享变量 的o p e n m p 和基于数据并行的h p p 。m p i 是一个消息传递接口的标准，用 于开发基于消息传递的并行程序，其目的是为用户提供一个实际可用的、 可移植的、高效的和灵活的消息传递接口库。p v m 把计算机网络虚拟成 并行机系统，为并行应用提供基于消息传递的并行编程环境和运行环境。 高性能f o r t r a n ( h i g hp e r f o r m a n c ef o r t r a n ) ，简称h p f ，是一个支持 数据并行的并行语言标准。h p f 程序中由于没有显式的任务划分和通信 语句，代码的定义是在高层进行的，因此具有很好的可移植性；通过具 体机器上的编译器可以生成各种系统平台上的高效的代码。o p e n m p 是一 个共享存储并行系统上的应用编程接口，它规范了一系列的编译制导、 运行库例程和环境变量”，。 并行计算平台是并行计算软件基础中重要的部分。p v m 并行计算平台 的出现极大的促进了并行计算在个人计算机群上的发展，国内外的学者 提出了一系列基于p v m 并行计算平台的并行程序设计思想及模型，解决 了一些实际的科学问题和工程问题。然而并行应用在个人计算机群上的 发展，又对并行计算平台的功能提出了更高的要求，比如计算资源的发 现，并行环境的维护，并行程序的建模，并行任务的分配等等。 本课题通过对并行程序进行研究，构造并行程序的模型，同时建立 一个全新的并行计算平台。通过这个平台可以开发和实现一些较为复杂 的并行应用。同时，并行计算平台课题的研究也为并行计算的研究提供 了有力的帮助。 1 2 国内外研究现状 1 2 1 并行计算的研究现状 目前，并行计算研究的主要领域有： 2 第一章绪论 1 并行计算所需的理论。并行计算所需的主要理论包括并行程序的 描述，并行计算的体系结构，并行算法的设计与实现，并行任务的分配， 并行程序的负载平衡等等。 2 并行计算的应用研究。并行计算程序难于移植，往往并行程序的 设计都与特定的平台相关联；并行计算程序的运行需要稳定高效的软硬 件基础，包括稳定高效的计算设备、输入输出设备、通信设备等；并行 计算的通信问题时并行程序运行时的主要问题，减少和优化通信开销也 是并行计算的一个重要研究方向。 3 并行程序的设计环境。目前，串行程序的设计已有了程序的编程 语言和编程环境，但是并行程序的设计环境还没有办法满足大规模并行 应用的需要。 o l i v e rs i n n e n 等人提出了一个实际可行的任务分配模型，这个模型 在原有的经典模型的基础上提出，考虑了并行时对资源使用所引发的冲 突m 。a n n as w i e c i c k a 等人利用自动机械划分与人工派出系统( c e l l u l a r a u t o m a t aa n da r t i f i c i a li m m u n es y s t e m ) 的支持对多处理器进行任务 分配与重分配n ，。 陆林生等人提出了并行程序概念设计方法，该方法将数据并行高层 建模语言研究、并行识别方法、并行程序自动构造和入机交互界面技术 集成在一起，能简化并行程序设计，有效缩短并行程序开发周期，提高并 行计算效率t o ，。宋安军等人分析了并行计算机模型和集群系统的特点， 研究了b s p 并行计算模型在集群环境下的适应性n ，。张志立等人对基于 s c i l a b 的分布式并行计算的方法进行了研究，为实现分布并行计算提供 了新方法m 1 。 1 2 2 并行计算平台的研究现状 基于个人计算机机群的并行计算平台的开发大多都是以p v m 等现有 平台为基础进行研究开发。p v mo nw i n 3 2 平台上的p c 集群技术介绍了 在高速局域网条件下通过p v m + w i n 3 2 构造p c 集群所涉及到的集群技术 “”。并行程序开发平台的可视化实现有利于网络并行计算的发展。该平 广东工业大学硕士学位论文 台基于w p v m 3 4 平台，是一个网络并行可视化平台，它由任务描述器、通 信代码生成器、代码插入器等主要模块组成“。 另外，一些研究也涉及了并行计算的体系结构等方面的问题。并行 程序开发平台体系结构的形式化研究用软件体系结构描述语言w r i g t 对并行程序开发平台结构进行形式化描述，指出这种描述的优点以及软 件体系结构形式化研究的重要性“”。基于部件与连接器的并行程序可视 化开发平台的设计介绍了一下软件体系结构的相关概念，包括部件与连 接器的构成及其表达方式：然后按照软件体系结构中的部件与连接器的 构成来分析与设计这个系统“”。网络并行计算平台新架构给出了一个新 的平台架构，用户只需提交数据和对它的操作，不需要设计者对任务的 分解、分配及子任务间的交互等问题有更高的技术“钉i 1 3 本文的研究目标及内容 1 3 1 研究目标 本课题的目的是建立一个并行计算平台，并且根据平台运行的数据 对平台的性能进行分析。该平台的目标用户是并行计算研究人员。该平 台由一个并行计算信息中心和若干个并行计算控制台组成。该平台的主 要功能有： 1 、并行计算信息中心的主要功能： ( 1 ) 接受并行计算节点的登录和退出信息； ( 2 ) 维护已登录的并行计算节点的信息，主要包括并行计算节点的 i p 地址、提供并行计算服务的端口、等等。 2 、并行计算控制台提供的主要功能： ( 1 ) 提供并行计算服务 ( 2 ) 登录或登出并行计算信息中心以在信息中心添加或删除本节点 的信息。 ( 3 ) 从信息中心获取提供并行计算服务的节点信息，生成并行计算 服务表。 4 第一章绪论 ( 4 ) 根据用户提供的并行程序描述图和控制台维护的并行计算服务 表生成任务分配运行表。 ( 5 ) 根据任务分配运行表分配和运行任务，实现并行程序。 1 。3 2 研究内容 本课题的具体内容是构建一个并行计算平台，它设计了计算机科学 与技术的多方面知识，包括并行计算、计算机网络、软件体系结构，软 件工程、程序设计理论等等。并行计算平台的建立是一个综合性的问题， 研究内容包括： 1 、并行程序模型的分析与建立。并行程序模型的研究主要包括并行 程序的描述，并行程序任务模型的建立与实现以及并行程序通信的实现。 这一部分的研究工作是并行计算平台建立的前提。 2 、现有的并行计算平台的分析。本文把在操作系统上实现的支持并 行计算程序的软件集称为并行计算平台。现有的并行计算平台主要有 p v m ，m p i 等等。这些平台对并行程序的通信提供的很好的支持，同时 提供了较好的编程环境。 3 、并行计算平台的设计。并行计算平台的设计主要是根据对现有并 行计算平台的分析，提出一个新平台架构。该平台支持对并行计算资源 的管理，同时还可以对并行程序进行管理。根据这个设计思想，本文提 出了并行计算平台的系统结构及其相应的功能。 4 、并行计算平台的实现。这一部分主要实现并行计算平台的功能模 块，具体有消息接收发送模块、消息队列、数据存储模块、服务提供 使用模块以及用户界面。 5 、并行计算平台的功能分析。平台的功能分析主要包括对异构并行 计算节点的性能的分析、平台系统性能以及并行程序加速比的分析。 1 4 论文结构 本文共分五章。第一章为绪论，介绍并行计算以及并行计算平台的 广东工业大学硕士学位论文 研究现状；第二章为并行程序模型的分析，主要对并行计算进行分析， 提出并行程序模型，实现并行程序的算例；第三章为并行计算平台的设 计，通过对现有平台的分析与比较，提出一个新的并行计算平台的设计 方案；第四章为并行计算平台的实现，主要实现并行计算的各个功能模 块；第五章为并行计算平台的性能分析，对实现的并行计算平台进行了 量化的理论分析。 6 第二章并行程序的设计及实现 第二章并行程序模型的分析 2 1 并行计算 2 1 1 并行计算概述 并行计算是指将顺序执行的计算任务分成可以同时执行的子任务， 并行执行这些子任务，从而完成整个计算任务。 在这里需要对程序这个词作一个解释。程序一般是指顺序执行的指 令集合，程序一般在一个处理器上执行。这里再引入两个名词：串行程 序和并行程序。串行程序是指一组相互关联的程序的集合，这些程序执 行时是串行的。并行程序也是一组相互关联的程序的集合，这些程序的 执行是同时进行或部分同时进行的。程序的相互关联可能是数据的相互 引用，也可能是程序的相互调用。程序是从指令的执行顺序来说的，而 串行程序和并行程序是从指令的执行效果来说的。 并行程序是一组相互关联的程序的集合，这些程序的执行是同时进 行或部分同时进行的。一般来说，并行程序将可以并行的操作具体分为 一个个可以相互通信的任务，这样也可以得到并行程序的另外一个定义， 即并行程序是一组相互通信的任务，这些任务的可以同时或部分同时进 行。 并行计算不仅仅是一种获得高性能的手段，它同时也具有将计算能 力从单个处理器扩展到多个处理器的潜力。这种潜力在几十年前就已被 人们所熟知，但是直到2 0 世纪8 0 年代末，它才真正显示出来。然而， 可扩展并行性的实现是一条曲折的道路，直到现在，并行计算还没有取 得完全的成功“”。 并行计算研究与应用的三个关键因素是：硬件、软件和应用。 在过去的5 0 年间，计算机产商、计算机体系结构、计算技术，以及 广东工业大学硕士学位论文 计算机应用发生了巨大的变化，推动了科学计算领域的发展。2 0 世纪7 0 年代末，向量机的出现标志着现代超级计算的开始。相对于当时传统的 计算机，向量机的性能至少可以提高一个量级。到了2 0 世纪8 0 年代初， 人们越来越重视将向量化技术集成到常规的计算环境中。2 0 世纪8 0 年 代后期，基于分布式存储的可扩展并行计算成为研究热点。r i s c 革命之 后，微处理器的性能迅速增长，同时大规模生产的成本降低。2 0 世纪9 0 年代初期，当多处理器向量系统达到其全盛时期时，新一代并行机，即 超大规模并行机( m p p ：m a s s i v e l yp a r a l l e lp r o c e s s o r ) ，以与向量系统相 同或更优越的性能进入了人们的视野。2 0 世纪9 0 年代中期，对称多处 理机( s m p ) 出现。对称多处理机系统具有成熟的体系结构架构和高的 性价比，受到工业用户的欢迎“”。 相对于并行计算的硬件来说，并行计算软件的发展较慢。并行编程 的难易直接影响人们对并行计算的接受程度。编写显示并行程序是比较 难的，编程人员必须指明如何在多个处理机上划分计算，且必须进行必 要的同步和数据传输操作，从而保证程序的正确性以及高性能。高端计 算机变化较快，人们较难用一种与机器完全无关的方式来编写程序，因 此将程序从旧的平台移植到新的平台时，需要迸行一些改动。并行计算 的另外一个复杂因素就是求解问题本身的复杂度“”。然而，消息传递接 口m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 、高性能f o r t r a n ( h p f ：h i g h p e r f c i r m a n c ef o r t r a n ) 、o p e n m p 以及p v m 等软件及软件标准的出现 促进了并行计算的发展与应用。 并行计算在对一些具体的数值计算问题的研究中，取得了比较好的 效果，比如向量内积、矩阵乘法等。同时，并行计算在一些特定的应用 领域，也取得的了不错的成果，比如机翼设计、内燃机设计、高速电路 设计以及结构设计等方面。网络和静态与动态信息的广泛使用产生了巨 大的数据量，这些数据在地理上分布的特性要求采用有效的并行算法来 解决诸如规则挖掘，聚集、分类以及时间序列分析等问题，这也为并行 计算在商业应用领域的发展提供了机会。 目前，个人计算机以及工作站的数目不断增加，越来越多的个人计 算机和工作站通过互联网连接在一起。在一个局域网或更大范围的网络 第二章并行程序的设计及实现 内实现并行计算可以极大的提高计算机的使用效率，同时也可以提高计 算机网络的性能。 网络并行计算是利用一组由网络互连的计算机同时解决一个大问题 的过程。由于高性能p c 、工作站的普及和高速网络的成熟，一组互连计 算机的计算能力甚至可以超越一台高性能计算机。由于网络并行计算计 算成本小又具有计算大问题的能力，特别适合我国国情，所以它在高性 能科学计算中已经获得了广泛的应用，包括分子动学模拟、矩阵计算、 超导研究、气象科学等“”。 网络并行计算环境是由多种不同结构的计算机，通过多种互连方式 组合的一个综合计算环境，可以包括p c 、工作站、小型机，还可以包括 各种类型的大型机、巨型机，其规模可以4 , n 几个计算机、局域网，大 到广域网，甚至i n t e r n e t “”。 2 1 2 并行计算的应用 在过去的二十几年，计算物理是并行计算发展的主要动力。很多计 算物理的应用有一些共同的特征，其中包括： 1 采用偏微分方程组，在一些子集上定义应用问题。 2 在多物理模拟中，存在多个明显不同的物理区域，每个区域上的 计算方法不同。 3 在一些计算中心或大学里，许多应用问题至关重要。 根据这些特征，人们重点研究偏微分方程组的离散、相关的分辨率 ( 或精度) 以及由离散产生的线性或非线性方程组的求解。对于这些问 题，一般采用数据并行或区域分解来实现并行化“”。 在过去的几年，并行计算的应用领域得到了扩充。一些与社会、政 治、经济相关的应用，如营销、灾害管理、战斗指挥也需要并行计算。 它们的主要特征有： 1 经常采用图定义问题，如交通和通信。 2 各部分之间的相互作用经常是全局的。 3 需要定义一个标准可信的整体结构“。 9 广东工业大学硕士学位论文 随着并行计算在应用领域中的发展，并行处理可能需要大量的数据 输入输出。例如，在营销、生物科学及地震研究中，就存在大量的新数 据集需要转换。同时，并行应用还需要为终端用户提供一个友好的用户 界面。 在传统的并行计算领域，大型计算问题需要功能强大的大型并行计 算机，但是许多用户由于资金的不足，无法昂贵的并行计算机进行并行 计算。现在，随着高性能p c 、工作站的普及和高速网络的成熟，一组通 过网络互连的计算机的并行计算能力已经达到甚至可以超越一台高性能 计算机，能满足人们对高速度、低成本计算技术的需求。这种通过利用 一组由网络互连的计算机同时解决一个大问题的过程就是网络并行计算 【l 耵 。 网络并行计算是继m p p ( m a s s i v e l yp a r a l l e lp r o c e s s o r s ) 之后， 现代并行计算的又一主要发展趋势。网络并行计算是由高性能网络或局 域网物理地互连的全体计算机节点的集合。一个计算机节点可以是一台 s m p 服务器、一台工作站或是一台p c 计算机，节点可以是同构的，也可 以是异构的。计算机数目一般为几个至几十个，支持控制并行或数据并 行的开发。每个节点上都有完整的操作系统、网络和用户界面，都可作 控制节点或运算节点，即节点之间是平等的“”。 2 1 3 并行计算研究的主要问题 2 1 3 1 并行性的识别 实现并行计算需要识别计算任务中那些是可以并行的。一般认为， 如果多个计算不共享数据，那么这些计算就可以并行。对于两个计算a 和b ， 条件l ：a 写某一存储单元后，b 读该单元数据； 条件2 ：a 读某一存储单元数据后，b 写该单元； 条件3 ：a 写某一存储单元后，b 写该单元。 如果以上三个条件均不满足，则a 和b 可并行执行“”。在这里只是 简单的给出了一个理论上的判断，实际应用中的情况往往要更为复杂。 i o 第二章并行程序的设计及实现 在这里可以举个例子。考虑对一个有n 个元素的数组进行排序( 假 定n 为偶数) 。第一种方法，采用选择排序，对数组进行排序。选择排序 开始的时候，扫描元素个数为n 整个列表，找到它的最小元素然后和第 一个元素交换，将最小元素放到它在有序表中的最终位置上。然后从第 二个元素开始扫描列表，找到最后的n 1 个元素中的最小元素，在和第 二个元素进行交换，把第二小的元素放在它的最终位置上，以此类推。 进行n 1 次扫描就可以得到一个有序数组。在这个算法中，每次扫描都 要对所有未排定次序的元素进行操作。如果把对未排定次序的数组元素 进行扫描并选出其中最小元素的操作看成一个计算，那么这n 1 个计算 是无法并行的。 第二种方法，简单的将待排序的数组a 【n 】分为两部分，即a o 】到 a n 2 l 】和a n 2 至0a n - l 】两部分，并将这两部分分别进行选择排序。将 已经排定次序的两个部分的数据进行归并排序，最后得到有序的数组 b n 1 。在这种排序方法中，对数组前半部分进行选择排序时的n 2 1 次扫 描，与对数组后半部分进行选择排序时的n 2 1 次扫描是可以并行的。 从以上的这个例子可以发现，同一个问题的不同算法之间的并行性 不一定相同。因此，在设计并行计算的算法时，需要对不同问题的不同 算法进行具体的分析。 2 1 3 2 分解策略 把一个计算分为很多小的部分，其中一些或所有部分都可能被并行 执行，该划分过程称为分解( d e c o m p o s i t i o n ) 。任务( t a s k ) 是计算单元， 任务的大小是可以任意确定的，但是一旦定义好，就被认为是不可再划 分的计算单元。由问题分解出的任务大小可能并不相同。 一般来说，并行计算的分解策略有两种方法。第一种方法称为“任 务并行”，即把程序分解为多个任务，标识出它们之间的依赖关系，使得 并行执行的任务互不干扰。另一种方法称为“数据并行”，它将问题的数 据空间分解成多个区域，并分配给不同的处理机，每个处理机负责计算 各个区域的结果“”。 为了更好的进行任务分解，这里给出几类任务分解技术，这些技术 是递归分解、数据分解、探测性分解以及推测性分解。递归分解和数据 广东t 业大学硕士学位论文 分解技术是比较通用的，因为它们能使用于大量的各种问题。探测性分 解和推测性分解技术是专用性质的，因为它们只适用特定类型的问题。 递归分解采用分而治之的策略使问题可并行执行。这种策略首先划 分问题为一组独立的字问题，子问题又可以采用相似的划分得到更小的 子问题。分治策略能得到自然的并发性，因为不同的子闯题可并发求解 【l 】 对于运行在大数据结构中的算法，要在算法中得到并发性，数据分 解是常用的有效方法。在这种方法中，计算的分解分两步完成。第一步 对计算中的数据进行划分，第二步，在数据划分的基础上推导从计算到 任务的划分。通常，对不同数据划分任务执行的操作是相似的( 如矩阵 乘法) ，或者选自一个小的操作集( l u 分解) n 1 。 有些问题的基本计算对应于解空间的一次搜索，探测性分解就是用 来分解这样的问题。在探测性分解中，划分搜索空间为更小的部分，然 后并发搜索这些小的部分，直到找出希望的解“1 。 有时程序会遇到多个可能的对计算很重要的分支，选择某个分支又 取决于之前的其他计算的结果，此时就要用到推测性分解。这种情况下， 当一个任务正在执行计算，而这个计算的结果将决定下一步计算，其他 任务就可以并发地执行下一步计算n 1 。 前面所提到几种分解方法，它们能用于导出许多算法的并发形式。 这些分解方法并不是相互排斥的，往往可以组合运用。通常，计算由多 个阶段构成，有时在不同阶段要使用不同的分解方法。 2 1 3 3 并行程序模型 并行程序是一组相互关联的程序的集合，这些程序的执行是同时进 行或部分同时进行的。一般来说，并行程序将可以并行的操作具体分为 一个个可以相互通信的任务，这样也可以得到并行程序的另外一个定义， 即并行程序是一组相互通信的任务，这些任务的可以同时或部分同时进 行。 并行程序模型一般有数据并行模型、消息传递模型和共享变量模型。 数据并行模型强调的是局部计算和数据选路操作，它比较适合于使用规 第二章并行程序的设计及实现 则网络、模板和多维信号及图像数据集来求解细粒度的应用问题。数据 并行操作的同步是在编译时而不是在运行时完成的。在消息传递模型中， 驻留在不同节点上的进程可以通过网络传递消息相互通信。消息可以是 指令、数据、同步信号或中断信号等。在消息传递并行程序中，用户必 须明确地为进程分配数据和负载，它比较适合与开发大粒度的并行性， 这些程序是多线程的和异步的，要求显式同步，以确保正确的执行顺序。 在共享变量模型中，驻留在各处理器上的进程可以通过读写公共存储器 中的共享变量相互通信。 一、共享存储模型。共享存储模型大多是为p v p ( p a r a l l e lv e c t o r p r o c e s s o r ) 和s m p ( s y m m e t r i cm u l t i p r o c e s s o r ) 提供，共享存储的程序大多 是在特定的多处理器平台上用平台专用的语言写成。在这种模型上，数 据处在单一地址空间，分为共享和私有两种，数据通信通过共享存储来完 成。 二、消息传递模型。目前，一些通用的基于消息传递的开发环境有： p v m 、m p i 、e x p r e s s 、l i n d a 、p a r m a c s 、p 4 、和z i p c o d e 等，其中最 常用的则是p v m 和m p i 。 p v m ( p a r a l l e lv i r t u a lm a c h i n e ) 系统是1 9 8 9 年由美国o a kr i d g e 国 家实验室( o r n l ) 开发出来的一套并行计算工具软件。它具有通用性 强及系统规模小的特点，既适合于t c p i p 网络环境，又适用于大规模并 行系统。p v m 是免费的，使用的范围非常广泛 p v m 系统下的编程主要采用主进程子进程模型，用来在通过网络 连接的多个处理机的集合中完成并发或并行应用，所有通信是通过消息 传递完成的。p v m 包括两个主要部分：在每台处理机上运行的后台进程， 以及进行处理机控制和消息传递需要调用的库接口函数。 m p i 是为了统一不同的大规模并行系统提供商的消息传递a p i ( 应用 程序接口) ，由来自高性能计算领域的专家和大规模并行系统提供商的代 表组成的委员会制定的工业标准，它的目标是开发一个广泛用于编写消 息传递程序的标准，要求编程界面实用、可移植、高效、灵活、能广泛 用于各类并行计算机，特别是分布式存储的并行计算机。 三、数据并行模型。数据并行模型的目的是要在分布存储的机器上实 广东工业大学硕士学位论文 现在全局命名空间进行并行程序设计，以屏蔽显式的通信问题。它是一种 细粒度的并行。数据并行语言用单线程控制用户定义的数据和计算在处 理器上的分布注释，使用户能够有效地将一些低层细节留给编译器和运 行时系统去实现，用户所要做的全部工作就是给出有关并行的指示 ( p a r a l l e ld i r e c t i v e s ) ，说职哪段程序要并行执行。与消息传递模型相比， 数据并行程序设计能在一定程度上减轻程序员的负担，但是完全依赖于 程序员能否确定一个好的数据分布。 在这里采用消息传递模型。任务中所有指令都是顺序执行的，任务 内部是不能并行执行的。一个任务的所有输入完成后，任务中的计算开 始执行；计算完成后，任务同时进行输出。 这里引入有向无环图来描述并行程序中任务之间的关系。用一个有 向无环图g = ( v ，e ，w ，c ) 来表示一个并行程序p 。v 中的节点表示并行程 序p 中的任务，e 中的边表示任务之间的通信。边e i ，e 表示节点n i 与n j 进行通信。节点1 1 的权重w ( n ) 表示任务的运算时问。非负的权重c ( e i ，) 表示节点i 与节点j 之间的通信时间。本文把描述并行程序的有向无环 图和描述任务基本信息的数据结构称为并行程序描述表。 2 2 并行程序的设计 2 2 1 问题的引入 排序( s o r t i n g ) 是计算机程序设计中的一种重要操作。它的功能是 将一个数据元素( 或记录) 的任意序列，重新排列成一个按关键字有效 的序列。在这里只考虑内部排序，即等待排序记录存放在计算机的随机 存储器中，排序过程中不需要访问外部存储设备。 内部排序的串行算法很多，但就其全面性能而言，很难提出一种被 认为是最好的方法，每一种方法都有各自得优缺点，适合在不同的环境 ( 如记录的初始排列状态等) 下使用。如果按排序过程中依据的不同原 则对内部排序方法进行分类，则大致可分为插入排序、交换排序、选择 排序、归并排序和基数排序等五类；如果按内部排序过程中所需的工作 1 4 第二章并行程序的设计及实现 量来区分，则可分为三类：( 1 ) 简单的排序方法，其时间复杂度为o c n 2 ) ； ( 2 ) 先进的排序方法，其时间复杂度为o ( nl o g ( n ) ) ；( 3 ) 基数排序，其 时间复杂度为o ( d n ) ”。 在这里介绍选择排序和归并排序。选择排序开始的时候，扫描元素 个数为n 整个列表，找到它的最小元素然后和第一个元素交换，将最小 元素放到它在有序表中的最终位置上。然后从第二个元素开始扫描列表， 找到最后的n 1 个元素中的最小元素，在和第二个元素进行交换，把第 二小的元素放在它的最终位置上，以此类推。 归并排序中“归并”的含义是将两个或两个以上的有序表组成一个 新的有序表。利用归并的思想容易实现排序。假设初始序列含有n ( 假 设n 为2 的若干次幂) 个记录，则可看成是1 1 个有序的子序列，每个子 序列的长度为l ，然后两两归并，得到n 2 个长度为2 的有序子序列：再 两两归并，如此重复，直至得到一个长度为n 的有序序列为止， 这种排序方法称为2 路归并排序。 在这里可以发现，在归并排序中，每一次的归并过程都是可以并行 进行的。在理想的情况下，可以把n 个记录平均分配到n 台处理机上， 那么每台处理机上就存储了一个长度为l 的子序列；然后不同处理机上 的子序列两两归并，得到r d 2 个长度为2 的有序子序列，这些子序列分 别保存在n 2 台处理机上；再两两归并，如此重复，直至得到一 个长度为1 1 的有序序列为止。 在现实的情况中，当记录数较大时，可能无法获得如此多的处理器 进行计算，而且不同处理器之间需要进行通信以及数据交换。另外，必 须考虑任务划分的问题，过多的任务数增加编程和程序运行的难度。因 此，在这里需要考虑具体使用的处理器的数目和任务的数目。 2 2 2 算法的实现 现在设定可以使用的处理机数目为4 台，本文中使用的编程语言为 c + + 。给出一个在四处理机上运行的并行排序算法。这里可以简单的将 待排序的数组a n 】( 假定n 为4 的倍数) 平均分为四部分，将这四部分 广东工业大学硕士学位论文 分别放到四台处理机上进行选择排序。将四台机器上已经排定次序的四 个部分的数据，两两进行归并得到两个基本有序的序列；最后将这两个 基本有序的序列进行规并，得到有序的数组b n 】。 在这里可以用一个八节点的有向无环图来描述这个并行算法。如果 图2 1 中的节点表示并行程序的任务，那么就可以将图2 一l 看成是八任 务并行程序描述图的直观表示( 这里省去了任务的运行时间以及任务间 的通信时间) 。其中： 任务0 ：获得需要处理的数据，将数据分为四部分并将这些数据发送 给任务l 、2 、3 、4 。 任务l 、2 、3 、4 ：采用选择排序法对接收到的数据进行排序。选择 排序的算法代码如下所示，其中a 【n 】为待排序的数组。 f o r ( i = o ；i n - 1 ；i + + ) f o r ( j = i + 1 ；j a d 】) x = a 【i 】； a 【i 】= a i j ； a 【j 】- x ； ) ) 任务5 、6 ：分别从任务l 、2 以及任务3 、4 接收的有序数组进行归 并排序。归并排序的代码如下，其中d i v n = n 4 ： i = o ；j = d i v n ； k = o ： w h i l e ( i d i v n & & j n 2 ) ( i “a 【i 】 a 【j 】) 1 6 第二章并行程序的设计及实现 b 【k 】= a 【i 】； i + + ： k + + ： ) e l s e b 【k 】= a d 】； j + + ； k + + ： i f ( i d i v n ) w h i l e ( i d i v n ) b 【k 】= a 【i 】； k + + ： i + + ： ) ) i f o a 2 ) w h i l e ( j n 2 ) b 【k 】- a d 】； k + + ： j + + ； ) 广东工业大学硕士学位论文 任务7 ：接收任务5 、6 所发送的数据并进行归并排序；最后输出处 理后的数据。 图2 - 1 ：八节点的有向无环图 f i g u r e2 - 1d i r e c t e da c y c l i cg r a p hw i t h8n o d e s 2 3 并行程序模型的设计 2 3 1 并行程序模型的概述 并行程序是一组相互通信的任务，这些任务的可以同时或部分同时 进行。通过这个定义可以将并行程序模型分为两部分：第一部分，任务 集，即任务的集合；第二部分，描述任务集基本信息和通信关系得数据 结构，即并行程序描述表。 并行程序的运行是通过任务的实现来完成的。任务是并行程序的计 算单元，任务之间可以进行通信。一个任务可以接收o 个或多个任务的 数据，也可以向0 个或多个任务发送数据；一个任务必须接收完其他任 务发送给它的数据之后才能执行。经过对任务共性的抽象，得到一个任 务的结构示意图。 接收端发鳝墒 任务执行体 接收端 发送淄 第二章并行程序的设计及实现 图2 - 2 ：任务的结构示意图 f i g u r e2 - 2t h es t r u c t u r eo ft h et a s k s 在任务机构示意图中：接收端用来接收其他任务发送过来的数据， 一个任务有0 个或多个接收端i 发送端用来向其他端发送任务，一个任 务有0 个或多个发送端；任务执行体实现本任务的计算工作。任务执行 体必须在所有的接收端完成接收任务之后才能进行计算工作。 在任务的实现过程中，可以将一个任务看成是一台计算机上的一个 进程，这个进程可以与其他机器上同类的进程进行通信。 2 3 2 并行程序中各任务之间通信的实现 2 3 2 1t c p i p