（计算机应用技术专业论文）beowulf并行计算系统可扩展性的研究与应用.pdf

b e o w u l f 并行计算系统可扩展性的研究与应用 摘要 近年来，高性能计算技术蓬勃发展，越来越多的科学计算问题能够通过并行程序设计 得到解决。但在基础理论研究等众多领域，问题规模越来越大，需要更多的计算资源，所 以并行计算系统必须随之扩展，以提高计算能力。然而系统的效率并不是随节点数目的增 加而呈线性增长，当系统到达一定规模时会出现效率降低、执行时间难以预测等问题，在 异构系统中这些问题更为严重。因此，深入了解可扩展性将有助于对大型应用问题的并行 计算系统的性能做出合适的评价，也有益于并行算法与并行系统的设计与改进。 基于消息传递通信的b e o w u l f 并行计算系统作为高性能计算的一个分支或流派，具有 廉价、易管理、性价比高等众多优点，应用越来越广泛。本文主要从效率方面分析异构 b e o w u l f 并行系统的可扩展性，研究当处理机节点增加时，问题规模应如何变化才能使扩 展日i 后的效率保持不变，并以此来预测系统的可扩展性。 由于异构系统各节点处理能力的差异，任务分配策略的好坏将严重影响系统的可扩展 性。因此，本文从研究任务分配、负载均衡出发，改进了m p i c h 任务分配上的缺点，构 建了一个基于o p e n p b s 和m p i c h 的负载均衡模型。模型使用相对处理速度的概念，把每 个节点的处理能力进行量化，调度节点根据每台节点处理能力的权重值来分配任务，以达 到整个系统的负载均衡。实验表明本文构建的模型可以把任务较为合理的分配到各节点去 执行，为分析系统的可扩展性以及可扩展性实验提供了良好基础。 目前可扩展性研究主要集中在并行算法与并行系统相结合的可扩展性上，即研究如何 随节点数目的增加而扩展问题规模，使得执行时间较合理且效率较高。 等效率模型揭示了由并行算法和并行系统共同影响下的计算性能，但它主要针对同构 系统，没有考虑各处理节点的差异。虽然异构系统已经越来越普遍，但在效率和可扩展性 的概念方面一直没有合适的定义来研究它的特性。本文改进了同构系统下的等效率模型， 提出了一个效率的定义，使它能够同时应用到同构系统和异构系统，并构建了一个适合同 构系统和异构系统的等效率模型，找到了使扩展前后系统保持相同效率的充分必要条件。 由此可以分析系统规模和工作负载应如何变化，才能使得扩展前后的效率保持一致。最后， 本文做了一系列实验用来验证以上理论，结果证明此方法具备有用性和有效性，较好的分 析了同构系统和异构系统的可扩展性，能够定量度量由物理扩展和能力扩展带来的效率变 化，并能够对系统的可扩展性进行预测。 关键词：集群，异构，等效率，可扩展性，m p i c h b e o w u l f 并行计算系统可扩展性的研究与应用 a b s t r a c t i nr e c e n ty e a r s ，n l eh i g hp e r f o r m a n c ec o m p u t i n g ( h p c ) t e c h n o l o g yv i g o r o u sd e v e l o p m e n t ， m o r ea n dm o r es c i e n c ec o m p u t i n gp r o b l e mc o u l db es o l v e dt h r o u g ht h ep a r a l l e lp r o g r a m m i n g b u ti nd o m a i n sa n ds oo nb a s i ct h e o r ys t u d y ，t h eq u e s t i o ns c a l ei sg e t t i n gb i g g e ra n db i g g e r ，n e e d m o r ec o m p u t i n gr e s o u r c e s ，t h e r e f o r ei no r d e rt oi m p r o v et h eh a n d l i n ga b i l i t y ，t h ep a r a l l e l c o m p u t i n gs y s t e mm u s ta l o n gw i t hi te x p a n s i o n h o w e v e rs y s t e m se f f i c i e n c yi sn o ti n c r e a s e s a l o n gw i t ht h en o d en u m b e rp r e s e n t st h el i n e a r i t yg r o w s ，w h e n t h es y s t e ma r r i v e sa tt h ec e r t a i n s c a l ew i l lp r e s e n tt h ee f f i c i e n c yt or e d u c e ，t h ee x e c u t i o nt i m eh a r dt o f o r e c a s ta n ds oo n q u e s t i o n s ，t h eq u e s t i o nw i l lb em o r es e r i o u si nh e t e r o g e n e o u ss y s t e m t h e r e f o r e ，d e e pr e s e a r c h s c a l a b i l i t yw i l lb eh e l p f u lt o s o l v et h el a r g e s c a l ea p p l i c a t i o nq u e s t i o np a r a l l e lc o m p u t i n g s y s t e m t sp e r f o r m a n c et o m a k et h ea p p r o p r i a t ea p p r a i s a l ，i sa l s o b e n e f i c i a li nt h ep a r a l l e l a l g o r i t h ma n dp a r a l l e ls y s t e m sd e s i g na n dt h ei m p r o v e m e n t b e o w u l fp a r a l l e lc o m p u t i n gs y s t e mb a s e do nt h em p ia s t h eh p c sab r a n c h ，h a s i n e x p e n s i v e ，e a s y t om a n a g e ，t h ep e r f o r m a n c e - t o - p r i c e r a t i oh i g h e rn u m e r o u sm e r i t ，t h e a p p l i c a t i o ni sg e t t i n gm o r ea n dm o r ew i d e s p r e a d t h i sp a p e rm a i n l ya n a l y z e sh e t e r o g e n e o u s b e o w u l fp a r a l l e ls y s t e m ss c a l a b i l i t yf r o mt h ee f f i c i e n c ya s p e c t ，w h e nt h ep r o c e s s o rn o d e i n c r e a s e s ，h o ws h o u l dt h eq u e s t i o ns c a l ec h a n g ec a nm a i n t a i nt h es a m ee f f i c i e n c y ，a n dp r e d i c t s y s t e m se x t e n d i b i l i t y a sh e t e r o g e n e o u ss y s t e m sh a n d l i n gc a p a c i t yo fe a c hn o d ed i f f e r e n c e s ，t a s ka l l o c a t i o n s t r a t e g yw i l ls e r i o u s l ya f f e c tt h eq u a l i t yo ft h es y s t e ms c a l a b i l i t y t h i sp a p e rf r o mr e s e a r c ht a s k a l l o c a t i o n ，l o a db a l a n c i n gs t a r t i n g ，i m p r o v e di nt h em p i c h t a s ka l l o c a t i o ns h o r t c o m i n g ，a n d c o n s t m c t e do n eb a s e do no p e n p b sa n dt h em p i c hl o a db a l a n c i n gm o d e l m o d e lu s i n gt h e c o n c e p to fr e l a t i v ep r o c e s s i n gs p e e d ，t h eh a n d l i n gc a p a c i t y o fe a c hn o d ew e r eq u a n t i f i e d ， s c h e d u l i n gn o d e sa l l o c a t et a s ka c c o r d i n gt ot h ec a p a c i t yo f e a c hn o d ew e i g h t si no r d e rt oa c h i e v e t h el o a db a l a n c i n gs y s t e ma saw h o l e t h ee x p e r i m e n ti n d i c a t e dt h a tt h em o d e lm a yc a r r y o u tt h e t a s ka l l o c a t i o nt ov a r i o u sn o d e sr e a s o n a b l y ，h a sp r o v i d e dt h eg o o df o u n d a t i o nf o rt h ea n a l y s i s s y s t e m ss c a l a b i l i t ya sw e l la st h es c a l a b i l i t ye x p e r i m e n t a tp r e s e n tt h es c a l a b i l i t yr e s e a r c hm a i n l yc o n c e n t r a t e si nt h ep a r a l l e la l g o r i t h ma n dt h e p a r a l l e ls y s t e m ，sc o m b i n a t i o n ，t h a ti s ，h o wt oi n c r e a s ea l o n gw i t ht h en o d en u m b e re x p a n d s t h e q u e s t i o ns c a l e c a u s e st h ee x e c u t i o nt i m e t ob er e a s o n a b l e ，a n dt h ee f f i c i e n c yi sh i g h i s o e f f i c i e n c y m o d e lh a sp r o m u l g a t e dt h ec o m p u t i n gp e r f o r m a n c eu n d e rt h ep a r a l l e l a l g o r i t h ma n dt h ep a r a l l e ls y s t e m ，b u t i tm a i n l ya i m sa tt h eh o m o g e n e o u ss y s t e m ，h a sn o t c o n s i d e r e de a c hp r o c e s s i n gn o d et h ed i f f e r e n c e a l t h o u g hh e t e r o g e n e o u ss y s t e mw a sa l r e a d y h b e o w u l f 并行计算系统可扩展性的研究与应用 g e t t i n gm o l ea n dm o l ec o m m o n , b u td i dn o th a v et h ea p p r o p r i a t ed e f i n i t i o ni nt h ee f f i c i e n c ya n d t h es c a l a b i l i t yc o n c e p ta s p e c tt os t u d yi t sc h a r a c t e r i s t i c t i l i sp a p e ri m p r o v e du n d e rt h e h o m o g e n e o u ss y s t e m si s o e f f i c i e n c y ，p r o p o s e d a n e f f i c i e n c y sd e f i n i t i o n ，e n a b l e si t s i m u l t a n e o u s l yt oa p p l yt h eh o m o g e n e o u ss y s t e ma n dh e t e r o g e n e o u ss y s t e m ，a n dc o n s t r u c t e d o n et os u i tt h eh o m o g e n e o u sa n dh e t e r o g e n e o u ss y s t e m si s o e f f i c i e n c ym o d e l s ，f o u n dt h e n e c e s s a r ya n ds u f f i c i e n tc o n d i t i o no fm a i n t a i n i n gt h es a m ee f f i c i e n c y f r o mt h i sw ec a na n a l y z e t h es y s t e ms c a l ea n dt h eq u e s t i o ns c a l es h o u l dh o wt oc h a n g e ，c a nc a u s et h ee f f i c i e n c ym a i n t a i n s c o n s i s t e n t f i n a l l y ，t h i sp a p e rh a st a k e nas e r i e so fe x p e r i m e n t st ov e r i f yt h ea b o v et h e o r y ，r e s u l t s s h o wt h a t t h i sm e t h o du s e f u la n de f f e c t i v e ，a n db e t t e ra n a l y s i so ft h eh o m o g e n e o u sa n d h e t e r o g e n e o u ss y s t e m sp h r r s i t sa n da b i l i t ys c a l a b i l i t y ，a n db e a b l et op r e d i c tt h es y s t e m s s c a l a b i l i t y k e y w o r d s ：c l u s t e r , h e t e r o g e n e o u ss y s t e m ，i s o e f f i c i e n c y , s c a l a b i l i t y , m p i c h i i l 曲阜师范大学博士硕士学位论文原创性说明 ( 在口划“4 ) 本人郑重声明：此处所提交的博士口硕士叫论文( ( b e o w u l f 并行计算系统可扩展性的研究与应用，是本人在导师指导下，在曲 ， 阜师范大学攻读博士口硕士曰学位期间独立进行研究工作所取得 的成果。论文中除注明部分外不包含他人已经发表或撰写的研究成 果。对本文的研究工作做出重要贡献的个人和集体，均已在文中已明 确的方式注明。本声明的法律结果将完全由本人承担。 作者签名：砖两睁 日期：沙蜉仫夕 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“ ) ( ( b e o w u l f 并行计算系统可扩展性的研究与应用系本人在曲阜 师范大学攻读博士口硕士回学位期间，在导师指导下完成的博士口 硕士耐学位论文。本论文的研究成果归曲阜师范大学所有，本论文的 研究内容不得以其他单位的名义发表。本人完全了解曲阜师范大学关 于保存、使用学位论文的规定，同意学校保留并向有关部门送交论文 的复印件和电子版本，允许论文被查阅和借阅。本人授权曲阜师范大 学，可以采用影印或其他复制手段保存论文，可以公开发表论文的全 部或部分内容。 作者签名： 名函撵日期：渺曾乒、 导师签名：肋如吞一 日期：d - z 砀8 4 - 7 b e o w u l f 并行计算系统可扩展性的研究与应用 1 1 研究背景 第一章绪论 随着计算机技术的迅猛发展，计算机的运行速度越来越快，容量越来越大，体系结构 越来越完善，软件越来越丰富，处理能力越来越强。这使得计算机扩大了其应用的领域， 不仅应用在数据处理上，而且延伸到信息处理、知识处理和智能处理。但人类对计算机性 能的需求是无止境的，在诸如海洋建模、图像分析、医疗药品试验、物理、化学、基因工 程以及基础理论研究等领域中都对计算机性能提出更高要求。 例如，在预测天气的时候，考虑3 0 0 0 x 3 0 0 0 平方公里的范围，垂直方向考虑高度为l l 公罩。将3 0 0 0 x 3 0 0 0 x l l 立方公里的区域分成0 1 0 1 o 1 立方公里的小区域，则将近有1 0 个不同的小区域。另外还需考虑时间因素，将时间参数量化。假定考虑4 8 小时天气预报， 每一小区域的计算包括参数的初始化及与其它区域的数据交换。若每- , b 区域计算的操作 指令为1 0 0 条，则整个范围一次计算的指令为1 0 1 0 0 = 1 0 1 3 ，假设两天的计算次数为1 0 0 次，因此，指令总数为1 0 ”条。用一台1 0 亿次秒( p i i i s 0 0 ) 计算，将大约需要2 8 0 小时。 若我们用1 0 0 个l o 亿次秒的处理器构成一台并行处理机，每个处理器计算的区域为1 0 8 个，不同的处理器通过高速通信来传输参数，假设每个处理器的计算能力能够得到充分利 用，则整个问题的计算时间不超过3 小时。这说明并行计算机可以大大缩短计算时间，解 决了原先不能解决的问题。 其它应用还包括：卫星数据处理、石油数据处理( 连续优化问题) ，调度问题、平面 性问题及v l s i 设计( 离散优化问题) 等。美国h p c c 计划( h i g hp e r f o r m a n c ec o m p u t i n g a n dc o m m u n i c a t i o n ) 提出了重大挑战性问题，对科学与工程具有重大经济与科学意义的一 些基础课题，它们的解可通过高性能并行计算技术得到，这些重大挑战性课题的应用领域 如下： ( 1 ) 磁记录技术：研究静磁和交互感应以降低高密度磁盘的噪音； ( 2 ) 新药设计：通过抑制人的免疫故障病毒蛋白酶的作用来研制治疗癌症与艾滋病的 药物； ( 3 ) 高速民航：用计算流体动力学来研制超音速喷气发动机； ( 4 ) 催化作用：仿生催化剂计算机建模，分析合成过成中的酶作用； ( 5 ) 燃料燃烧：通过化学动力学计算，揭示流体力学的作用，设计新型发动机： ( 6 ) 海洋建模：对海洋活动与大气流的热交换进行整体海洋模拟； ( 7 ) 臭氧耗损：研究控制臭氧损耗过程中的化学与动力学机制： ( 8 ) 数字解析：用计算机研究适时临床成像、计算层析术、磁共振成像： b e o w u l f 并行计算系统可扩展性的研究与应用 ( 9 ) 大气污染：对大气质量模型进行模拟研究，控制污染的传播，揭示其物理与化学 机理： ( 1 0 ) 蛋白质结构设计：对蛋白质组成的三维结构进行计算机模拟研究： ( 1 1 ) 图像理解：实时绘制图像或动画； ( 1 2 ) 密码破译：破译由长位数组成的密码，寻找该数的两个乘积因子。 解决这些问题的关键在于提高运算速度。自计算机问世以来计算机的高速发展已经持 续了半个世纪，由于物理极限的限制，单个计算机速度的提高越来越困难，向量计算机 c r a y - l 诞生2 0 年来单机速度只提高了一个数量级。与此形成鲜明对比的是大规模并行技 术使计算机的理论峰值在2 0 年内提高了4 个数量级( 从每秒l 亿次提高到1 万亿次浮点 运算) 。从另一个角度，1 9 9 6 年美国宣布全面禁止核实验，制定了a s c i 计划，它的目标 是“在2 0 1 0 年以前，武器系统的性能、安全、可靠性和制作方面要达到三维全物理、全 系统的应用”。禁止核试验、要求全物理模型化和高可信的计算机模拟，同时也推动了大 规模并行技术的空前发展。由此可见数据的处理必须走并行化道路。 在网络速度和微处理器性能迅速提高的情况下，集群系统( c l u s t e r s ) 的研究和应用得 到迅速发展。建立在通用( c o m m o d i t y o f - t h e s h e l f , c o t s ) 器件、普遍使用的免费或商业 软件( 如l i n u x ) 上的集群系统对重新定义高性能计算( 大规模并行计算或超级计算) 产 生了重要作用乜3 儿钔。1 9 9 4 年i b ms p 的诞生为设计大规模高性能系统提供了许多新见解， 它利用集群方法来构造m p p 瞄1 。1 9 9 5 年由1 6 台p c 组成的b e o w u l f t 蝴并行工作站为科学计 算提供了很好的性能价格比。实际上，b e o w u l f 集群现在已被人们看作高性能计算中的一 个分支或流派。目前，b e o w u l f 系统已经成为t o p 5 0 0 中重要的成员之一订1 。并行机的发展 为科学计算提供日益强大的计算平台的同时，也带来了新的挑战。目前仍然缺乏能求解“巨 大挑战性问题”的数值计算方法和并行度高、可扩展性好的应用软件协1 。 大规模并行计算的一个关键问题是可扩展性问题四1 ，不可能期望通过将串行代码简单 移植到并行系统上就能获得很大的性能提高。事实上，当处理机节点超过6 4 、1 6 甚至8 台时就会使系统的可扩展性降低。目前，并行计算在我国的应用仍局限于中小型计算，原 有算法和软件是否能求解更大规模的问题是个值得关注的问题。因此，研究可扩展模型、 可扩展性的度量方法以及并行算法在并行机上的可扩展性是很有必要的。 从体系结构来划分，并行计算系统包括同构和异构系统，由于异构系统的复杂性远远 超过同构系统，所以“异构计算”的概念及相关技术产生最近才逐步发展起来。在异构计 算环境中，不同计算机体系结构之间并存协作，并行程序的工作负载被分配到各个计算机 上并行执行。这就要求工作负载的分配能够充分发挥各种计算机的长处，以获得最短的执 行时间。异构计算的研究目标主要是追求更高的计算效率、程序开发效率以及费用有效性 ( c o s t e f f e c t i v e n e s s ) 。在异构集群中，原来面向m p p 的平均负载分配策略效率低下。因此， 必须针对其特点，研究如何平衡负载、以及更有效地利用有限的计算资源。另外，异构系 统的性能模型和可扩展模型的研究也是一个重要课题，以帮助用户对并行算法在异构系统 2 b e o w u l f 并行诗篝系统霉扩震毪骶研究与癍瘸 上豹缝髓进行评价和优化。 综上掰述，在分蠢主存m p p 秘集群环壤下，磷究霹扩展模燮耘可扩震性鹣度量方法， 并针对系统的特点研究高效率算法的设计蠢法嬲策略，能起到以点带蘸麴作簏，具毒很大 推广和应用价值，顺应当前并行计算发展的潮流。 1 2 国惠外发震动态 近年来，m p p 和微处理器领域取得了巨大的进菇。2 0 0 7 年l1 月最新全球超级计算机 5 0 0 强塞攀书，美霆匿际翥震枫器公司( i b m 研铡翁拜蓝色萋嚣7l 撵联冠军，运算速 度赢达每秒4 7 8 ，2 万亿次浮点运算n 0 1 。2 0 0 6 年时，中匿上海超级计算孛心的“曙悲4 0 0 0 a 名列第5 3 位，运算速度峰值为每秒1 0 万亿次浮点运算。藏在向前十位进发。2 0 0 7 年5 月， i b m 掰攉高的双核p o w e r 6 处理器的速度尧4 7g h z ，是目前僦界上处理速度最快的微处 理器芯片豫。 题前，并孳亍软件的发展仍然落后予硬件，可扩展性作失并镗软件舱一个重要性能指标 觉菊重要。警前对可扩展性的研究可以分为两个方面，一是可扩展模型的研究，二是大规 模并行应用较蒋每著行橇相结合鹩可扩震性研究。在谣扩展模型方面，西际上先后提出了 等时闻可扩震模型、等效率霹扩震模型、眷储受限哥扩震模型、等速度霹扩震模型等。这 些模型从不同的方面评估算法的瓤扩展性，并获得了广泛的应用。 国予集群系统的广泛使用，基予这种平台的性能模型、可扩展模型、算法设计方法以 及评徐方法，都成为姿翦翁研究热熹。僵是已有的研究工作仍存在一些不楚： ( 1 ) 对髯橡集群的讶扩袋模型研究缀少； ( 2 ) 对予异构集群上的任务分配，使用以往的做法对某姥算法不能达到负载平衡； ( 3 ) 对资源受隈条律下的资源有效利用阀题研究较少。 1 3 本文的主要工作与刨凝 本文主要面囱健价巍较离瓣b e o w u l f 集群系统，在并行计算模型、萄扩震模型戡及巢 群计算方瑟徽了一些磷究和截薪工作； ( 1 ) 在深入分板已有并行计算模型的基础上，对常用并行计算模型、可扩展模型进行 分类，分祈它们的使掰范围、优缺点； ( 2 赞对异褥系统的物理扩震释能力扩震，瓣供宥效静度量方法。奉文扶效率角度， 趱盘了群适合同构系统叉适会异构系统的效率模型，鬻来评价算法或痤用程序在并行系统 上的可扩展性； ，这是释平衡酌逶 瀑模式。该模型是撒网步熬，鄢在黧步操作之阕是爨步熬本地计算。只京当所鸯进程都宠 成当髓超步后，越步中的任何一个才能开始下超步n 们。 b s p 模型不需任何特殊的交互机锖：它可以是共享变整或是消息传递。德它被广泛 邀鏖瘸子基于游惠黄递酌计算领城，嚣戴这里将它翔茺基于消息赞递酶并褥计算模型这 类之巾。 该模型规范了并行算法设计的模式，即计算和通信交叉进行。但是，它存在以下缺 点：它认为所有的h 关系均是完全的h 关系，舔所有处理枫燕好发送或接收h 个清息； 它霾辩谈舞窑与溺络通燕无关。 最近，j o a n - j o s e pc l i m e n t 等“5 1 摊出了完全司扩展的墼璺并纷方法，不需要通讯，就埘 以得到与精确解等价的近 徽解，僵怒会增加大量的计算，从丽降低了并抒抟效率。 幻妒模型： l o 妒模型是一种分布存储的、点到点通信的多处理桃模型，其中通信网络由4 个主 要参数来描述； 1 ) 丢( l a t e n c y ) 表示源簸莲撬与霉翡魅瓒概迸行清怠 个或死个字遴壤所需 要豹等待或延迟蹲间憋上限，表示熙终审涟息的延迟； ( 2 ) 0 ( o v e r h e a d ) 表示处理机准备发送或接收每个消息的时间开销( 包括操作系统 核心歼销和网络软件并销) ，在这段时间曩处理枫不能执行其它操作； ( 3 g ( g a p ) 表示一螽楚理巍连续两次发送或接牧满意时匏最枣薄阏闯隔，其餐数鼯 微处理梃的遥镄繁宽； ( 4 ) p ( p r o c e s s o r ) 处理机存储器模块个数。 假定一个周期完成一次局部操作，并定义为一个时阊单位，那么，毛、0 藕g 都可黻 表示戒楚理器蠲鬻的整数倍。 b 妒模型的特点： ( 1 ) 抓住了网络与处理机之间的性能瓶颈。g 反映了通信带宽，单位时间内最多宵l g 个潲意能迸行处理枫闻传送； 2 ) 瑟理瓿之阏异步工捧，并通过楚建辊越魏瀵息转送来党或爨步； ( 3 ) 对多线程技术有定反映。每个物理处理机可以模拟多个虚拟处理机v p ，当某个 v p 有访问请求时，计算不会终止，但v p 的个数受限于通信带宽和上下文交换的开销时间。 v p 受蔽予鼹络容量，至多有l g 个v p 棼瀵息延迟不确定，但惩迟不大予戚。摸怠经历赞等德对阕是苓可鞭测的，但在没誊 阻塞的情况下，最大不超过三# 8 b e o w u l f 并行计算系统可扩展性的研究与应用 ( 5 ) l o g p 模型鼓励编程人员采用一些好的策略，如作业分配，计算与通信重叠以及平 衡通信模式等； ( 6 ) 可以预估算法的实际运行时间。 l o g p 模型的不足之处： ( 1 ) 对网络中的通信模式描述的不够深入。如重发消息可能占满带宽、中问路由器缓 存饱和等未加描述： ( 2 ) l o g p 模型主要适用于消息传递算法设计，对于共享存储模式，则简单地认为远地 读操作相当于两次消息传递，未考虑流水线预取技术、c a c h e 引起的数据不一致性以及 c a c h e 命中率对计算的影响； ( 3 ) 未考虑多线程技术的上下文开销： ( 4 ) l o g p 模型假设使用点对点消息路由器进行通信，这增加了编程者考虑路由器上相 关通信操作的负担。 c 3 模型： c 3 模型假定处理机不能同时发送和接收消息，它对超步的性能分析分为两部分：计算 单元c u ，依赖于本地计算量；通信单元c o u ，依赖与处理机发送和接收数据的多少、消 息的延迟及通信引起的拥挤量。该模型考虑了两种路由( 存储转发路由和虫蚀寻径路由) 和两种发送接收原语( 阻塞和无阻塞) 对c o u 的影响。 c 3 模型有5 个参数： ( 1 ) p 处理器个数 ( 2 ) h 网络延迟 ( 3 ) b 网络的对分宽度 ( 4 ) s 启动时间，及建立一个消息时的开销 ( 5 ) 消息包的长度，即消息包所含字节数 c 3 模型用2 个量c 和三口来描述网络的拥挤，其中，c 表示参与通信的处理机对的数 目，l a 表示处理机问路由消息包的平均数目，则有 ( 1 ) 连接上的拥挤量c = l a c b ( 2 ) 处理机上的拥挤量c 。= l a c b h 在一个超步中，若s 与r 分别表示第j 个处理机总的发送和接收时间，则有 c o u = m a x ( s ，+ r 1 ) + c ，+ c p ，0 f l = = 一 1 + 毛( ，p ) w 根据这个效率丞数，如果闻题援模保持不变，当p 增加时，效率会降低，因为总的额 外开销会随着p 的增加而增加。如果处理器数目保持不变，增大问题规模，那么对可扩展 的并行系统，效率会提高，这是因为对固定的处理器数目p ，额外开销函数的增长速度要 比o ( w ) 慢，对这些并行系统，增加p 时，可以通过增大的方法来得到需要的系统效率。 对不同的并行系统，为了得到稳定鹩效率，当处理器数目增加时，必须以不霜的速 率相应增加，比如，在某些情形下，当处理器数目增长时，为了保持效率不变，需要以 p 的指数函数的速率增长。这样系统的可扩展性很差，因为当使用大量的处理器时，并行 系统很难得到良好的加速比，除菲采用巨大的问题规模。另一方面，为了保持效率不变， 如果相对p 的增长，问题规模只需要以p 的线性丞数形式增长，那么这样的系统具有较高 的可扩展性，这是因为当处理器的数目增加后，只需要采用合理的问题规模就可以得到较 好的加速比。 对于可扩展的并行系统，效率可以维持在一个固定的值，只要瓦w 保持不变。设e 为 所需要的并行系统效率，根搀前面的效率表达式，骞 e ： ! t o ( w , p ) 。坐 1 十死( 矽，p ) w e 妒 = # t o ( w ，p ) l 一乜 令k = e ( 1 一e ) ，当给定效率后，这是一个常数。因为瓦是关于矽和p 的函数，则上 1 8 “ b e o w u l f 并行计算系统可扩展性的研究与应用 面的表达式可以写成 w = k t o ( 形，p ) 这样，可以通过代数变换的形式，将表示成p 的函数，这个函数描述了为了保持效 率不变，当p 改变时所需要的问题规模，我们把这个函数称为一个并行系统的等效率函数， 这个等效率函数确定了一个并行系统为了保持效率为常数，从而使加速比随处理器数目成 比例的增长的容易程度，它描述了并行系统的可扩展能力。一个小的等效率函数意味着当 处理器数目增长时，只需要较小的问题规模增长就可以达到处理器的充分利用，对应的并 行系统当然具有很高的可扩展能力。相反的，一个大的等效率函数对应着一个可扩展性很 差的并行系统。 按照等效率函数的定义，对于某一并行算法( 或并行程序) ，为了运行效率保持不变， 随着处理数目的增加，若只需增加较小的工作量( 即加大问题规模) ，比如说随p 成线 型或亚线型增长，则表示该算法具有良好的可扩展性；若需增加非常大的工作量，比如w 随p 成级数增长，则表示该算法是不可扩展的。对不可扩展的系统来说，等效率函数不存 在，因为对这种并行系统，当处理器数目增加时，不管如何增加问题规模，都不可能使系 统的效率保持为常数。 下图4 1 给出了三种等效率函数曲线，曲线1 表示算法具有很好的扩展性；曲线2 表 示算法是可扩展的；曲线3 表示算法是不可扩展的。 p 图4 i 等效率函数曲线 等效率函数揭示了并行算法和并行机结构兆同影响下的计算性能。另外，等效率函数 慨i 移明为了维持效京是一个常数，当节r 毫数变化时，相旷地问题规模也要焚似。然而等效 率司扩展性评价准则把机器数p 作为一个参数，显然不适笛异构系统n 。 4 3 异构等效率可扩展模型 可扩展性是衡量算法与并行系统匹配程度的一项重要指标。算法在同构系统中的可扩 1 9 b e o w u l f 并行计算系统可扩展性的研究与应用 展性研究已经很深入，但是针对异构系统的研究还缀少。针对n o w s 系统的延迟度量方法 o 1 较为复杂，不便使用。在异构系统中，系统规模扩展可以从两个方面进行：一是增加节 点个数，称为物理扩展：二是通过升级来提高节点的处理能力，称为能力扩展。采用物理 扩展，由于有更多的节点参与通讯和同步，使得这部分开销增加。而采用能力扩展，开销 计算比增加了，从丽使得计算效率下降。对于算法在既有物理扩展又有能力扩展的并行系 统上的可扩展性，可以采用在保持某种性能指标的基础上获得问题规模随系统规模扩展的 关系式的方法。本章将同构系统中的等效率可扩展模型推广到异构系统中，提出了一个面 向异构系统的等效率可扩展模型，在保持效率的情况下，获得闯题规模与系统规模的扩展 关系式。 由于异构系统中各节点的处理能力不同，所以必须对每个机器的处理能力进行处理能 力的度量。常用的表征各节点的处理能力的方法有两种： ( 1 ) 用每秒中能完成的浮点操作数来表征各个节点的处理能力骆朝，都“绝对处理能力”， 但是这种方法难以准确的预测浮点操作数网； ( 2 ) 选用标准节点，其它节点的处理能力用相对于该标准节点的处理速度来表示，也 称“相对处理能力拜。 选用不同的标准节点可以导致不同的性能模型。采用系统中最快的节点作为标准节点 时，如果要在系统中加入更快的节点，则原来建立的模型就要做出改变。有的模型要求必 须采用一个不属于此系统的节点作为标准节点口钉，这样在加入其它的节点时，原来的模型 改动不大。但是，标准节点的选取不属于该系统的限制是没有必要的。本章给出的性能模 型取消了这一限制，标准节点可以任意选取。 首先考虑这样的异构系统：它包含个节点，至少有两个节点的处理能力不同。指定 某节点作为标准机，其他节点和整个系统的处理能力在此节点的基础上确定。假设某算法 a 的计算量为形，不考虑i o 时闻的情况下，它在标准枫上执行的时闽t = w t ，其中r ，表 示执行单个浮点操作的平均时间，理论上为一常数。若a 在第i 个节点上执行的时间为丁， 则可定义每个节点的相对速度。 定义一：系统中第f ( 1 i v ，则称s 是可扩展系统，如采当系 统幽s 扩展到s 时，总能找到一个合适的炒+ ，使得s 和s 的效率保持一致。 显然，如果不改变其他参数，只增加工作负载，则系统的效率增加，反之则降低。 另外系统的最后反应时间取决于最幔的那个节点的执行时间，这和负载均衡算法有必然的 关系。本章旨在对可扩展性进行理论研究，假定任务合理的分配到各节点，本文将在下一 章讨论有关异构系统负载均衡的问题。 根据上述定义，下面是对系统可扩展性得出的结论： ( 1 ) 给定一个异构系统s ( n ，v ，w ) 、一个扩展系统s ( ，y ，矽) ，和一个固定的、可任 意分解的工作负载w = ( w l ，w 2 ，人，h ) ，如果工作负载相对备节点的处理能力被合理分配到 各节点并且各节点开销时间为一常数，韶霉。= c o ，l 嚣| n ，如果矽+ = 渺导器成 立，受l 系统扩展前后两系统效率相同。 证明：要保持扩展前后效率e = - - 影，即 南一参驴堋筹，由予磊= 舞曰埘) ，t t - c o 棚 = m a x ( c o + z 5 ) 。又因为假定任务被合理分配给各节点，所以节点上的计算时间z 5 的值 可以表示成总工1 7 f 负载和总处理能：j = 的比值，故司+ 表示成的函数即7 ：? = c 。( j 7 v ：) 。 圃理砭= g ( 妒，所以矿= 矽器。 l ( 2 ) 由于系统规模不同，导致的通信开销时间也肯定不同。设由系统规模大小不同导 致鹃各节点开镄时闯分别为霉8 = 岛+ q ，帮节点的固定开销时间加上出于系统规模大小 不同导致的开销时间，则要保持系统扩展前后效率不变，则必须满足下面的条件 2 l b e o w u l f 并行计算系统可扩展性的研究与应用 w t ：矽刍! 竺! ：! ! 刍篓：竺 c o ( ) v + c l n v 证明：要保持扩展前后效率e = e 。，即 专= 考= 嗉等t 由于拳舞( 班驴喃x ( g + c l 州5 ) = c o ( n ) + c i n ，丽理= c o ( ) + q ， 所以w ：! 鱼! 攫1 2 g ! 型羔竺：矽刍! 型：2 ：兰! 曼! 型! = 兰! 。 ( c o ( ) + c l ) yc o ( ) v + c i n v ( 3 ) 开销时间除了和以上两方面有关系，其主要开销时间和各节点及各节点对应的工 作负载有关。可设各节点的开销时间为互。篇c o + c ：等k ，即固定开销时刚加上工作负载 带来的开销时间。要使扩展前后效率不变，则必须满足： w = w c o ( ) y + c l wm a xv , 1 2 1 c o ( n ) v + c i w m ，：a 。xv , 证明：和( 2 ) 的证明类似，因为 瓦=，n。+互5)=兰+c2等+霉5)=c0()+wnmax(t, m a x ( c o n v c 2 万m _ a x e vv ， 瓦=o + 互5 ) =+ c 2 ，+ 霉5 ) = c 0 ( ) + ， # l，# l 一 = c 。( ) + c ：等舞杉，要保持扩展前后效率不变，则 肚彩琴= 矽一w n 篇矽 巧矿 ( c o ( ) + c ：等舞k ) y g ( 。) y + c 2 wm a xk # l c o ( ) 矿+ c 2 w m a x 形 f 再l ( 4 ) 根据上述结论，定义节点开销时间为以下三个时间之和，即每个节点的固有丌销 时间或者初始化时间q ，由于系统规模导致的开销时间c 。，以及由于工作负载导致的开 销时间c ：等k ，即z 。= c o + q n + c 2 等k 。令c o ( ) = c o + c ，n ，姑k = 圪觚，t u ( 3 ) 中的模型变为 w ：w ( c o - b c i a1 v + c 2 w v m a x ，：渺鱼k ! 刍型! 兰! 曼! 笙匕! 坠 ( c o + c l n i l c 2 黟勰c o l ：c ；n v + c 2 吼 本义将在第六章的具体实验不境下验证其正确。1 7 蔓。 4 4 小缝 本章分析了同构系统下的等效率模型，并且给出了一种适合同构系统和异构系统的效 b e o w u l f 势行计算系统可扩嶷性的研究与应用 率定义，搬据此定义对霹扩展性进行了分析，得港了即适用于弱掏系统又适用于异秘系统 的等效率模型，并提燃了使扩展前后系统保持楣阕效率的充分必要条件。由此霹以分析系 统规模和工作负载应如何变化，才能使得扩展前后的效率能够保持一致。 b e o w u l f 并行计算系统可扩展性的研究与应用 第五章基于m p i c h 的异构b e o w u l f 负载均衡模型 负载均衡是并行计算中的一个十分重要的研究领域，主要思想是将计算任务合理分配 到各节点。负载均衡能力的高低将会严重影响异构集群的