（计算机应用技术专业论文）异构环境中并行计算模型与任务调度的研究.pdf

- 论文原创性说明 本人郑重声明：此处所提交的博士口硕士论文异构环境中并行计 算模型与任务调度的研究，是本人在导师指导下，在曲阜师范大学攻读博 士口硕士母学位期间独立进行研究工作所取得的成果。论文中除注明部分 外不包含他人已经发表或撰写的研究成果。对本文的研究工作做出重要贡献 的个人和集体，均已在文中已明确的方式注明。本声明的算法律结果将完全 由本人承担。 作者签名：l 刁甜日期：2 0 1 0 6 2 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“”) 异构环境中并行计算模型与任务调度的研究系本人在曲阜师范大学攻 读博士口硕士翻学位期间，在导师指导下完成的博士口硕士回学位论文。 本论文的研究成果归曲阜师范大学所有，本论文的研究内容不得以其他单位 的名义发表。本人完全了解曲阜师范大学关于保存、使用学位论文的规定， 同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅 和借阅。本人授权曲阜师范大学，可以采用影印或其他复制手段保存论文， 可以公开发表论文的全部或部分内容。 作者签名：田香甘日期：2 0 0 6 2 刷噬钐“一 醐谚仉了 异构环境中并行计算模型与任务调度的研究 摘要 计算机硬件成本的不断降低、微处理器处理能力的快速提升和网络技术的高速发展， 为用普通微机建立并行计算系统提供了条件。通常这类并行计算系统都具有异构性，而且 异构并行计算系统已经广泛应用于科学领域和商业领域，对异构计算系统的研究也成为近 年来的研究重点。因此研究异构并行环境下的并行计算模型和任务调度有着重要的意义。 本文介绍了并行计算的概念和并行计算系统的分类，重点论述了异构并行计算系统， 并详细阐述已经提出的并行计算模型。并行计算模型在并行计算系统硬件与软件之间起着 f i r s t ，t h i sp a p e ri n t r o d u c e st h ec o n c e p to fp a r a l l e lc o m p u t i n ga n dt h ec l a s s i f i c a t i o no f p a r a l l e lc o m p u t i n gs y s t e m s ，t h e ni ta n a l y z e st h eh e t e r o g e n e o u sp a r a l l e lc o m p u t i n gs y s t e m sa n d d i s c u s s e st h ep a r a l l e lc o m p u t i n gm o d e l sp u ta l r e a d yf o r w a r dt ot h i sd a y p a r a l l e lc o m p u t a t i o n m o d e lp l a y sar o l ea sab r i d g eb e t w e e nh a r d w a r ea n ds o f t w a r ei np a r a l l e lc o m p u t i n gs y s t e m a v a r i e t yo fc h a r a c t e r i s t i c so fp a r a l l e lc o m p u t i n gs y s t e ma r ea b s t r a c t e d t oo b t a i nt h ep a r a l l e l c o m p u t i n gm o d e l f o rap a r a l l e la p p l i c a t i o n ，a l g o r i t h m s a r ed e s i g n e da n da n a l y z e do nt h e p a r a l l e lc o m p u t i n gm o d e la n dc a r r i e do u tb yh a r d w a r et h r o u g hc o m p i l e dh i g h l e v e ll a n g u a g e h o w e v e r , w i t ht h ed e v e l o p m e n to fp a r a l l e lc o m p u t i n g ，t h e r ei sn og e n e r a l p u r p o s ec o m p u t i n g m o d e l p a r a l l e lc o m p u t i n gm o d e l sw h i c hh a v e b e e np r o p o s e de i t h e ra r es i m p l eo rt o oa b s t r a c tt o a p p l yt os p e c i f i cc i r c u m s t a n c e s b a s i n go nt h eb s pm o d e l ，t h i sp a p e rp r e s e n t sa n o n + e x c l u s i v e h e t e r o g e n e o u sa s y n c h r o n o u sp a r a l l e lc o m p u t i n gm o d e l - - n h a - b s p m o d e l t h e o r e t i c a la n a l y s i s s h o w st h a tt h en h a b s pm o d e ld e s c r i b e st h es y s t e mp e r f o r m a n c ep a r a m e t e r sm o r ea c c u r a t e l y a n dd e p i c t sn o n e x c l u s i v ea n dh e t e r o g e n e o u sc h a r a c t e r so fp a r a l l e lc o m p u t i n gs y s t e m sa n dt h e i r i m p a c t st op a r a l l e lc o m p u t i n gi m p l e m e n t a t i o ne f f i c i e n c yi nd e t a i l m o r e o v e r , t h em o d e li n c r e a s e s s y s t e mt h r o u g h p u ta n di m p r o v e st h ei m p l e m e n t a t i o ne f f i c i e n c yo fp a r a l l e lp r o g r a mt h r o u g h a l l o w i n ga s y n c h r o n o u si m p l e m e n t a t i o no ft h ep r o g r a m t h ee x p e r i m e n tr e s u l t sv e r i f y t h e a v a i l a b i l i t yo ft h em o d e la n dt h ep a p e rg i v e s t h em e t h o do fp r o g r a mo p t i m i z a t i o n h e t e r o g e n e o u sp a r a l l e lc o m p u t i n gs y s t e m sc o n s i s to fm u l t i p l eh e t e r o g e n e o u sp r o c e s s o r s a n dp r o c e s s o r sa r ec o n n e c t e dt h r o u g hd i f f e r e n tc o m m u n i c a t i o nl i n k s p a r a l l e lt a s ks c h e d u l i n g a l g o r i t h mp l a y sa ni m p o r t a n tr o l ei nt h ec o m p u t a t i o n a le f f i c i e n c yo f t h ew h o l es y s t e m t h e r e f o r e ， t h eo p t i m a ls c h e d u l i n gs t r a t e g yi sa n o t h e rr e s e a r c hc o n t e n to ft h i sa r t i c l e t h i sp a p e rd e s c r i b e s c o n t e n tr e l a t e dt a s ks c h e d u l i n g ，i n c l u d i n gt h ef o u rs t e p so fh e t e r o g e n e o u sc o m p u t i n ga sw e l la s t h ec l a s s i f i c a t i o no ft a s ks c h e d u l i n g ，a n df o c u s e so nt h eh e u r i s t i cs c h e d u l i n gp o l i c yo fs t a t i ct a s k s c h e d u l i n g b a s e do nc r i t i c a lp a t ho nap r o c e s s o r sc p o pa l g o r i t h mu n d e rh e t e r o g e n e o u s p a r a l l e lc o m p u t i n ge n v i r o n m e n t ，t h i s a r t i c l e p r o p o s e s as c h e d u l i n ga l g o r i t h m sb a s e dt a s k r e p l i c a t i o n t h i sa l g o r i t h mh a st h es a m et i m ec o m p l e x i t ya sc p o pa l g o r i t h m t h r o u g hc a s e i i i a c h i e v e sh i g h e re f f i c i e n c y m p u t i n gm o d e l ；t a s k - 度的研究 1 1 研究背景和意义1 1 2 研究现状2 1 3 本文组织结构3 第二章并行计算系统4 2 1 并行计算4 2 2 并行计算机的分类5 2 3 异构并行计算系统7 2 4 总结9 第三章并行计算模型1o 3 1 传统的并行计算模型1 0 3 2 基于b s p 模型扩展的并行计算模型1 2 3 3 并行计算模型的比较1 3 3 3 1 传统并行计算模型的比较13 3 3 2 基于b s p 模型的扩展并行计算模型的比较1 3 3 4 总结1 4 第四章一种改进的b s p 模型1 5 4 1n h a b s p 模型1 5 4 2 实例分析1 6 4 2 1m p i 基本介绍16 4 2 2 实验环境介绍17 4 2 3 实验算法描述18 4 2 4 实验结果及分析1 9 4 3 总结2 0 第五章异构计算环境中的调度算法2 2 5 1 任务调度概述2 2 5 2 任务调度的分类2 3 5 3 静态任务调度2 5 5 4 问题描述和算法设计2 5 5 4 1 任务模型和异构并行计算系统模型2 5 5 4 2 相关术语介绍2 6 i v 与任务凋度的研究 v ：1 6 ：1 8 ：! ； ：；1 ：；：! 3 3 3 4 3 7 3 8 异构环境中并行计算模型与任务凋度的研究 1 1 研究背景和意义 第一章绪论 计算机的高速发展，使得计算机在各个领域得到了广泛和深入的应用，对科学发展和 人类社会的进步产生了巨大的影响。同时，也对计算机性能的要求愈来愈高。尤其随着在 医学，工程设计，自动化等领域的深入应用，计算机的数值模拟与辅助设计对计算提出了 极高的要求，通常对这些问题要进行高精度大规模的计算。为了满足这种需要，提高计算 机的性能需要两种手段。一种是提高处理机的运行速度和线路的传输速度，但是这一类技 术要受限于物理上的空间和工艺技术和光速的限制。另外一种是依靠现有资源，采用并行 技术，利用多个处理器同时进行计算，这样可以有效提高计算能力。以此，来满足高性能 计算中对计算机的性能要求。 随着网络技术的快速发展和单处理机性能的不断提高，以并行技术为基础的高性能计 算机得到了快速发展。特别是从9 0 年代以来，高性能并行计算更是得到了空前的发展。 高性能并行计算俨然象征着一个国家综合实力的水平，世界上许多国家为了提高自己的综 合竞争能力，制定了许多科学战略攻关项目，并把高性能计算提高到国家战略的高度。美 国在近1 0 年来在大规模科学与工程计算应用领域，启动了三次重大计划，极其有力地推 动了并行计算的发展和应用。这3 次重大计划的成功使得美国在并行计算机的研制和并行 应用程序的开发方面具备了国际领先水平。 在中国，国家高技术研究发展计划将并行计算机的研制列为关键攻关技术。中国高性 能计算技术紧随国际高性能计算机的发展进度，已经实现了并行计算机的大规模并行而不 是原来的适应性并行。截止目前，我国已经成功研制了1 0 万亿次并行计算系统，完成了 高性能计算机的跨越式发展，中国继美国、日本之后成为世界上具备研制高性能计算机的 能力的三个国家之一。中国科学院计算所、国防科技大学和江南计算所已经实现了通用微 处理器结合定制网络的大规模并行计算机技术，中国科学院计算所和联想集团、国防科技 大学以及江南计算所研究出了以商用部件为基础的集群并行计算机技术。与此同时我们也 应该清醒地看到，中国的高性能计算技术的发展极其应用与美国和日本等发达国家相比较 还是有很大的差距。 简单的讲，高性能并行计算就是在分布式计算机或并行计算机等高性能系统上所做的 计算，它以高性能并行计算机和分布式网络计算机为物质基础。并行计算机的性能、结构 和规模可以有很大差异，因此其价格也差别很大。对于小规模的研究机构或者一般的学校 和企业购置专门的并行机耗资巨大。为了解决这个问题，研究如何利用当前的网络技术， 凭借商业化的软件和硬件提高计算效率，完成高性能计算成为必须。在这种形势下，b e o w u l f 系统的出现受到了广大校园和中小企业的欢迎。更一般的情况，由p c 机通过商用网络互 i 异构环境中并行计算模犁与任务调度的研究 联，利用开放的软件构建的b e o w u l f 系统，一般具有异构或非独占性。本文对异构并行计 算系统进行研究具有重要的理论和实际意义。 如同串行计算拥有理想的计算模型冯诺依曼机一样，为使并行计算更好的解决复杂 的问题，并行计算模型必不可少。虽然已经提出了很多并行计算模型，但是目前并行计算 领域还没有一个像冯诺依曼机这样真正通用的并行计算模型。目f i 流行的模型有p r a m ( p a r a l l e lr a n d o ma c c e s sm a c h i n e ) 模型，异步p r a m 模型，b s p ( b u l ks y n c h r o n o u sp a r a l l e l ) 模型，l o g p 模型等。当前对并行计算模型的研究，一般都是在这三种模型的基础上进行的。 一个良好的并行计算模型应容易理解和编程，独立于体系结构，可预测代价，性能保障等。 并行模型的研究应在以上几点之间进行权甜。 并行计算系统中的任务调度对提高并行计算的效率和系统的性能同样起着至关重要 的作用。在异构并行计算系统，根据每个计算节点不同的性能，进行任务分配，提高计算 效率是本文的另一研究目的。本文在异构并行计算环境下，提出了一种新的并行计算模型 和任务调度算法，为并行计算系统的研究拓宽了思路。 1 2 研究现状 第一代并行计算模型以p r a m 模型为主，它是一种理想的并行计算模型。根据处理机 对共享存储单元同时读写的限制，p r a m 模型又分为p r a m e r e w ，p r a m c r e w ， p r a m c r c w 和p r a m c r e w 模型。第二代并行计算模型主要有b s p 模型，l o g p 模型， l o g g p 模型等。这些模型的提出几乎都是针对专门的大型并行计算机，现在广泛应用的以 集群为基础的并行计算系统与专门并行机明显不同，因此这些模型并不十分适合分析以集 群为基础的并行算法。而且这些模型都是以并行系统同构为前提的，显然不适合于异构并 行计算系统。 b s p ( b u l ks y n c h r o n o u sp a r a l l e l i s m ) 模型【2 j 是l e s l i ev a l i a n t 在19 9 0 年提出的，也是被 认为最有前途的并行计算模型，现今对于并行计算模型的研究大都是基于b s p 模型的扩展 和改进。通常认为并行计算模型的研究顺序是从p r a m 模型到b s p 模型到l o g g p 模型p j ， 现在的研究重点似乎又回到了对b s p 模型的研究。基于b s p 模型和l o g g p 模型的其他扩 展模型有：d b s p 模型【4 1 ，c s a b s p 模型【5 】，n h b l 模型【6 】，n h c b l 模型【7 】，以及阶段并 行模型【8 】等。其中，c s a b s p 模型和阶段并行模型是对b s p 模型的改进。c s a b s p 模型 取消同步限制，利用通信和计算之间的重叠提高程序的执行效率。阶段并行模型将每个超 步分为并行化，计算和通信三个阶段，他们都在一定程度上改进了程序的执行效率，但 是只考虑了同构并行计算环境下的情况。n h b l 模型更为准确地刻画了异构并行计算系统 中非独占性对计算效率的影响，n h c b l 模型在n h b l 模型的基础上考虑了网络拥塞对并 行算法执行效率的影响。这两个模型是在l o g g p 模型的基础上进行的推广，在描述节点之 间的通信时仍然采用l o g g p 模型。 2 异构环境中并行计算模型与任务调度的研究 在异构并行计算系统中，计算节点之间通过网络实现全相连。在静态的任务调度中， 每个任务只能被分配在一个唯一的计算节点上。若两任务之间存在一定的先后关系，并且 被分别分配到了不同的计算节点，那么两任务之间存在着通信代价。已经证明，对任务进 行最优调度是一个n p 完全问题一j 。近年来，很多学者致力于研究异构系统下的任务调度。 静态任务调度通常是在并行计算应用运行前经过计算为每个任务分配个优先级，根据系 统中各个计算节点的性能，任务之间的通信代价，确定好所有任务的分配方法和调度顺序； 系统根据调度顺序分配任务到各个处理器，静态调度大多采用启发式思想，目的是最小 化任务的执行时间。文献中介绍了多种适用于异构环境下的启发式调度算法，包括t d s 算法【1 0 1 、c h p 算法】、h e f t 算法【1 2 】、c p o p 算法和p e t s 算澍13 1 。动态任务调度与静 态任务调度不同，静态任务调度在并行任务执行前，在任务执行的开始阶段，根据系统中 各个节点的性能和各子任务在各个节点上的执行时间分配任务。动态任务调度在任务执行 的时间内，根据系统各节点执行各个子任务的能力和各个节点的负载情况重新分配子任 务。 1 3 本文组织结构 论文组织结构如下： 第一章阐述了论文的研究背景和研究背景和意义，并介绍了研究现状和论文的组织 结构。 第二章详细介绍了并行计算系统和异构并行计算系统，给出了异构并行计算系统的 定义。 第三章介绍了并行计算模型的概念，介绍了传统的并行计算模型和基于b s p 模型扩 展的并行计算模型。重点分析了p r a m 模型，b s p 模型，l o g p 模型和c 3 模型以及c s a b s p 模型，阶段并行模型，h b s p 模型。并对它们进行了比较分析。 第四章提出了一种基于b s p 模型扩展的n h a b s p 模型，并在新模型下实现了矩阵 相乘的并行程序，通过实验分析证明了该模型的有效性。 第五章详细介绍了异构并行计算系统下的任务调度的相关知识和算法，对现有的算 法进行优化，提出了一个基于复制的任务调度算法，通过实例分析和仿真实验验证算法的 可行性和高效性。 第六章总结论文已经完成的工作，提出下一步的研究方向。 异构环境中并行计算模型与任务调度的研究 2 1 并行计算 第二章并行计算系统 并行性是指计算机系统同时进行操作或运算的特性，它具有两个方面的含义，两个同 性质或不同性质的事件在同一时间间隔内发生或者在同一时刻发生，前者称为并发性，后 者称为同时性。提高并行性主要通过时问重叠、资源重复和资源共享来实现l l 4 。 一般来讲，并行计算就是在各类并行计算机上所进行的计算，目的是能够快速的解决 庞大且复杂的计算问题。实质上是将多个任务映射到具有多个处理器的并行计算机上执 行，或者将某个多维问题映射到具有特定拓扑连接结构的并行计算机上进行求解。由于所 有的超级计算和高性能计算都使用并行技术，所以通常认为三者是同一概念。上面提到了 提高并行性的三种途径，因此并行计算包含了时问重叠，资源共享和资源重复三个要素。 时间重叠是指多个任务同时执行，也称为时间并行技术；资源重复是指重复设置硬件资源， 以提高计算系统的性能，资源重复又叫做空间并行技术；资源共享包括信息资源共享，硬 件资源共享和软件资源共享，它是一种软件技术，目的是降低成本，提高硬件设备的利用 率【1 5 】。 从上面可以看出，实现并行计算必须要有的三个条件是：并行计算机、并行编程和具 有一定程度并行度的应用。并行计算机一般包含多台处理机，这些处理机通过定制或商用 网络相互连接完成通信；应用问题应能够分解为多个可以并行执行的子任务，将任务分解 为多个子任务的过程即为并行算法的设计过程；并行编程，依托并行计算机上的编程环境， 有效实现并行算法，编写并行程序并运行，完成对应用问题的并行求解。 并行计算按照运算对象的不同分为数值型计算和非数值型计算。 数值型计算：根据代数关系进行计算的一类问题，这类问题属于数值分析的范畴。 非数值计算：基于比较关系的一类计算问题，它属于符号处理的范畴。矩阵相乘、求 解线性方程组等属于数值计算、排序和查找等属于非数值计算。 根据并行进程相互执行顺序的不同可分为同步、异步、独立并行计算。 同步并行计算：因为运算执行顺序的限制，各个进程必须相互等待。 异步并行计算：进程之间相对独立的执行，不用相互等待。 独立并行计算：进程之间完全独立的执行，即在整个计算过程中没有任何通信。 根据并行计算任务粒度的不同可分为：粗粒度、中粒度、细粒度并行计算。 粗粒度并行计算：任务中包含程序段较长或者有较大计算量，是当前并行算法设计的 主流。 细粒度并行计算：任务包含程序段比较短或者计算量较小，通常指基于向量和循环级 并行的算法。 中粒度并行计算：介于细粒度并行计算和粗粒度并行计算之间的一类计算。通常指基 4 - 型与任务调度的研究 根据指令流与数据流的不同方式，并行计算机主要分为四大类，单指令流单数据流 ( s i n g l e i n s t r u c t i o ns i n g l e d a t a ，s i s d ) 计算机，单指令流多数据流( s i n g l e i n s t r u c t i o n m u l t i p l e d a t a ，s i m d ) 计算机，多指令流单数据流( m u f i p l e i n s t r u c t i o ns i n g l e d a t a ，m i s d ) 计算机，多指令流多数据流( m u l t i p l e i n s t r u c t i o nm u l t i p l e d a t a ，m i m d ) 计算机，多指令流 多数据流( m u l t i p l e i n s t r u c t i o nm u l t i p l e d a t a ，m i m d ) 计算机【l 6 j 目前通用的多指令流多数据流( m i m d ) 计算机又分共享存储m i m d 计算机、分布式存 储m i m d 并行多处理机和分布式共享存储计算机，下面分别进行介绍。 其中并行向量处理机和对称多处理机属于共享存储m i m d 计算机，大规模并行处理机 和工作站集群属于分布式存储m i m d 并行多处理机。 1 ) 并行向量处理机 系统使用专门的高带宽交叉开关网络连接少量定制的向量处理器和共享存储模块，每 个处理器至少有1 g f l o p s 的处理能力。系统中一般使用向量寄存器和指令缓冲器，而不使 用高速缓存。我国研制的银河1 号就是并行向量处理机。结构模型见图2 1 。 图2 1并行向量处理机 2 ) 对称多处理机 系统使用交叉开关或高速总线将商用微处理器和共享存储器相连，这种微处理器都具 有片上或者外置高速缓存。系统的特点主要是对称，每个处理器在访问操作系统服务、i o 设备和共享存储器时具有相同的地位，具有较高的并行度。但是由于共享存储，所以系统 中的处理器数目不能太多，而且交叉开关或总线在形成之后，很难做进一步扩展。这种系 统主要用于商务领域，如数据库，数据仓库和在线事务处理系统等。曙光1 号和d e c a l p h a 是典型的对称多处理机。 3 ) 大规模并行处理机 系统采用专门设计和定制的高通信带宽低延迟的通信网络，处理节点使用商用微处理 - 异构环境中并行计算模型与任务调度的研究 器，系统中具有物理的分布存储器。这种系统能扩放到成百上千个处理器，属于异步的 m i m d 机器，运行在系统中的程序由多个进程组成，每个进程有私有进程空间，进程问采 用消息传递进行通信。大规模并行处理机主要应用与工程模拟，科学计算等以计算为主的 领域。我国研制的曙光1 0 0 0 就属于这种大规模并行处理机。结构模型见图2 2 。 节 m bm b 图2 2 大规模并行处理机 4 ) 分布共享存储多处理机 具有分布在多个节点上的物理存储器，系统中的高速缓存目录d i r 支持分布高速缓存 的一致性，使多个分布的物理存储器构成一个共享的存储器。从用户的角度，系统硬件与 软件提供了一个单一的编程地址空间，相对大规模并行处理机来说，分布共享存储多处理 机的优点是容易编程。s t a n f o r dd a s h 属于这种系统。 5 1 工作站集群 系统中的节点通过低成本的商用网络互联。每一个节点都是无头工作站( 没有监视器， 键盘，鼠标) ，也可以一台p c 机或者对称多处理机。各个节点通过像以太网，a t m 开关 等低成本标准网络进行互联，商业用的工作站集群也会用定制的网络。 把工作站集群和大规模并行处理机做在以下几点比较。 ( 1 ) 对于工作站集群，节点内有本地磁盘；大规模并行处理机没有。 ( 2 ) 节点内的网络接1 ：3 松耦合到i o 总线上；大规模并行处理机的n i c 紧耦合连接到 节点的存储总线上。 ( 3 ) 每个节点内都具有完整的操作系统；大规模并行处理机一般是只有微核。 更详细的说，工作站集群具有以下特点【1 7 】： ( 1 ) 使用方便工作站集群中每个单独的节点都是一个传统的平台，用户能够在自己熟 悉的环境中开发运行他们的程序。传统平台提供了功能很强的程序设计工具，很多为单处 理机执行所丌发的程序可以不加修改地再集群上执行。 ( 2 ) 高可靠性系统中有多个存储器，处理器和磁盘，若个部件出现故障问题其他仍 然能正常使用，保证系统能正常工作。 6 异构环境中并行计算模型与任务调度的研究 ( 3 ) 高缩放性系统的计算能力随着节点数目的增加而增加。系统中的处理器、存储器、 磁盘以及i o 设备等都可以增加或减少。因为节点问是松耦合的，所以容许系统中节具有 较多的节点数目。 “) 高性能价格比集群系统的节点和互连网络都是商品化的产品，可以大批量生产， 成本较低，因此集群系统的性能价格比好。在同样的性能峰值情况下，集群系统的价格比 传统的并行向量处理机和大规模并行处理机可以低1 至2 个数量级。 因为集群是有多台完整的计算机构成的，因此它的维护工作量和费用比较高，相当于 是同时去管理多个计算机系统。 目前的集群系统主要有两种类型分别是专用集群和企业集群。 专业集群通常具有的特点是：集中管理，由专门的人员统一控制，就像管理大型并行 计算机一样；计算节点同构，具有相同的体系结构和操作系统；装置紧凑，各个节点的物 理距离很近，一般放在机房中使用；集群内的通信对外界屏蔽。 企业集群的特点是：分散控制，集群中的节点由不同的人拥有和控制，系统的管理者 只对各个节点进行有限的管理；计算节点异构；装置松散，每一个节点都是一台完整的工 作站或对称多处理机；集群内的通信对外界开放，可以采用标准的通信协议连接到通信链 路。这也造成了一定的安全隐患，需要采取额外的措施保证系统的安全。工作站集群结构 模型见图2 3 所示。 工作 站 本地磁盘 研器高速 缓存 主存储器 存储器总线 与i 0 总疆得 桥 工作 站 本地磁盘 处珲器7 缓俘 主存储器 存储器总线 与i ，o 总显得 桥 商品化网络 2 3 异构并行计算系统 图2 - 3 工作站集群 异构并行计算系统是一个计算机集群，如果系统中的每个处理器具有相同的处理能 力和相同的操作系统，称为同构系统。当有两个或多个处理器的能力不相同或操作系统不 7 异构环境中并行计算模型与任务调度的研究 同时，称为异构系统。它协调地使用结构、性能不同的机器，满足不同规模、不同类型的 计算的不同要求，以获得最大总体性能的方式来执行代码。与同构计算不同，异构并行计 算系统在各种不同类型不同性能的计算机相互组合的环境下，互相协作满足不同类型计算 的需求，以执行各种并行计算任务。一个异构计算系统包括高速网络、接口、通信协议、 操作系统、编程环境和异构计算机等。 异构环境下的计算在于不把负载平衡作为主要问题，使用算法与体系结构相匹配的思 想，根据并行应用问题中含有的不同并行特性对其进行分解，为不同类型的计算匹配相应 计算资源。 一个典型的异构并行计算系统包含三部分。分别是： ( 1 ) 一组不同结构，不同性能的计算机； ( 2 ) 连接各个计算机的通信网络； ( 3 ) 支持异构计算的用户编程界面。 应用层 通信层 网络层 图2 4 异构计算系统的层次结构 应用层为确保任务的高效率的完成，提供负载均衡，任务分析，任务分解和编程环境 等工具。通信层在网络层的上面，提供使不同计算机相互通信的机制，保证各个异构计算 机的相互连接，实现信息交换，提供统一的通信协议，使整个异构系统具有单一的系统映 像。目前，在通信层比较流行的通信工具软件是m p i ( m e s s a g ep a s s i n gi n t e r f a c e ，消息传递 接口) 和p v m ( p a r a l l e lv i r t u a lm a c h i n e ，并行虚拟机) 。网络层的功能与一般计算机网络中 的相似，主要是实现路由选择和流量控制等，保证各个异构计算机之间的连接。 8 - 究 9 的分类，并深入探讨了工作 行计算系统的定义，组成和 i 异构环境中并行计算模型与任务调度的研究 第三章并行计算模型 当采用并行技术实现一个应用问题时，需要考虑三个问题：并行算法、并行计算模型 和并行计算机体系结构【l 圳。并行计算模型是程序设计者、算法设计者、系统运行者在完成 一个并行计算任务时，三者之间的桥梁【2 0 1 。它是设计并行算法的基础，是多种不同并行计 算机体系结构模型的抽象，具有非常重要的作用。但是在并行计算领域还没有出现一个像 串行计算领域的冯诺伊曼机那样真正通用的并行计算模型。 并行计算模型提供抽象性和稳定性。并行计算模型提供的操作比并行机底部结构提供 的操作高级很多，这就简化了软件结构，减轻了软件设计的复杂性和困难性，所以说模型 提供了抽象性。稳定性是指模型提供了一个长久不变的标准接口，不用关心并行计算机的 发展。 并行计算模型又叫做编程模式。有两类主要的并行计算模型：一种是模型以共享内存 的并行计算系统为基础进行抽象和提取，另一种是以分布式的消息传递并行计算系统中为 基础来建立模型。虽然在消息传递模型中编程者负责各个并行执行部分之间的协调控制和 信息交换，但是消息传递的通信模式简单清楚，这使得消息传递的编程模式成为并行计算 的计算模型。 并行计算模型、并行计算系统和并行算法三者之间的关系可以用图3 1 描述。 并行算法 瞰 身| l并行计算模型 并行计算系统 图3 1并行计算模型、并行计算系统、并行算法之间的关系 3 1 传统的并行计算模型 1 ) p r a m ( p a r a l l e lr a n d o ma c c e s sm a c h i n e ) 模型 它是同步处理器的共享存储多处理机模型，p r a m 模型是一个理论模型，它假定有若 干个功能相同的处理器，并存在一个具有无限容量的共享存储器，忽略通信和同步开销， 不适用于消息传递系统或者模型化存储器层次。根据处理器对共享存储单元的并发读写控 制，p r a m 模型又分为互斥读写( e x c l u s i v e r e a da n de x c l u s i v e w r i t e ) 的p r a m 模型，并 1 0 - 异构环境中并行计算模型与任务凋度的研究 发读互斥写( c o n c u r r e n t r e a da n de x c l u s i v e w r i t e ) 的p r a m 模型，并发读写( c o n c u r r e n t r e a da n dc o n c u r r e n t r e a d ) 的p r a m 模型。 p r a m 模型的扩展模型有：异步p r a m ( a p r a m ) 模型，每个处理器上都有本地存储 器，处理器之间通过共享存储器进行通信。计算分几个阶段，每个阶段异步执行，阶段结 束后使用同步障进行同步。存储竞争模型，存储器分成了若干模块，个模块一次处理一 个访问，在模块级处理存储器之间的竞争。延迟模型b l o c kp r a m ( b p r a m ) 把信息的产生 和能够使用之间的延迟考虑在内。分层存储模型，将存储器看成分层的存储模块，每个模 块由它的大小和存储时间来表示，用叶表示处理器，多处理器用模块树表示。局部p r a m 模型，假定每个处理器都有无限大小的本地存储器，而访问全局存储器的代价是比较昂贵 的。 2 1b s p ( b u l ks y n c h r o n o u sp a r a l l e l ) 模型 b s p 模型由哈佛大学l ge v a l i a n t 提出。一个b s p 计算机由一个处理器存储器的集 合组成【2 1 1 。b s p 模型用下面三个参数描述分布存储的多计算机模型：处理器、进行处理器 之间点对点传递消息的选路器、全局同步之间的时间间隔。分别用p 、g 、l 表示处理器数、 选路器吞吐率和时间间隔。计算由一系列周期为l 的超步组成，超步之间使用路障进行同 步。每个超步分为计算、通信和同步三部分。每个处理器执行局部计算，以点对点的方式 在处理器之间交换数据，最后做一个全局检查，确定超步中计算和通信是否都已经完成。 如果完成，则进入到下一个超步，否则下一个l 周期分配给没有完成的超步。 每个超步的完成时间为计算、通信、同步三部分的执行时间之和，用w + 幽+ 表示， 其中w 是在超步内处理器中的最大的计算时间，h 表示在一个超步中最大的通信量。如果 一个计算由n 个超步组成，则总的执行时间为n ( w + g h + l ) 。b s p 模型中一个超步的 计算方式如图3 2 示。 节点1节点2节点n 图3 - 2b s p 模型 异构环境中并行计算模型与任务调度的研究 3 ) l o g p 模型 l o g p 模型由c u l l e r 等人在1 9 3 3 年提出，是分布存储、点到点通信的多处理机模型。 主要有以下四个参数：l ( a t e n c y ) 表示网络中消息从源处理机传送到目的处理机所需要的延 迟；0 ( o v e r h e a d ) 表示处理机发送或接收一条消息所需要的时间开销，在这个时间内处理 器不能执行其他操作；g ( g a p ) 表示处理机连续两次接收或发送消息之| 、日j 的最小时间问隔； p ( p r o c e s s o r ) 表示处理器的数目。 l o g p 模型反映了并行算法设计时的主要问题，并且支持详细的算法分析。l o g p 模型 无须说明通信协议或编程风格，可以等同地用于消息传递、数据并行、共享存储等风范。 但是它也存在一些问题。第一，通信延迟与网络负载之间几乎是指数关系，很难用参数去 刻画这种非线性增长。第二，根据l o 妒模型设计出的最优算法，它的通信效率和处理机 利用率可能不是最佳结果。第三，相对通信丌销，网络延迟比较小，为使通信和计算能进 行有限的重叠，在算法设计时需要进行细致的同步和复杂的任务分配。l o g p 模型适合于短 消息的消息发送。 l o g p 模型的扩展l o g g p 模型在l o g p 模型中考虑了长消息，发送一个长消息的开销表 示为，。+ n t 。，t s 表示消息传送的启动时间开销，t p 表示传递单位字节的消息所需的时问开 销，n 为消息的长度。l o g p h m m 在l o g p 模型基础上将存储器进行分级，l o g p c 将不同 线程对计算资源的竞争考虑在内，它关注网络d m a 接口和网络竞争的影响，l o g p s 关注 消息库自身协议开销等。 4 ) c 3 ( c o m p u t a t i o n ，c o m m u n i c a t i o n ，c o n g e s t i o n ) 模型f 2 2 】 c 3 模型是一个粗粒度的并行计算模型，目的是反映计算复杂度、通信和通信中存在的 拥塞等方面对粗粒度网络算法的影响，在粗粒度机器上，并行算法的性能对通信模式非常 敏感。在b s p 和l o g p 模型中因为只采用点对点方式进行通信，复杂的通信操作由程序员 编程实现，而c 3 模型强调用公用的通信操作来开发粗粒度的并行算法，大大减轻了程序员 的负担。 3 2 基于b s p 模型扩展的并行计算模型 1 1 计算一发送段b s p ( c s a - - b s p ) 模型 一个计算发送段由计算和数据发送部分组成。每个超步的前一部分是计算发送段， 后一部分是接收语句。c s a - - b s p 模型与b s p 模型具有相同的体系结构。超步中不显含同 步。通信延迟，通信带宽，进程之间关系的概念与b s p 模型相同。添加所有计算段所需时 间的最小值和准备发送的数据在高速缓存中的百分比来减少网络拥塞和提高数据的发送 速率。 2 1 阶段并行模型 对于阶段并行模型，并行程序也是由一系列超步构成，超步之间用路障进行同步。每 i 异构环境中并行计算模型与任务调度的研究