（计算机应用技术专业论文）超大规模分布式系统负载平衡研究.pdf

大连理工大学硕士学位论文 摘要 经半个世纪的努力，计算机硬件设计已获得令人不可思议的提升并趋向于高性能低 开销化。例如：i b m 正在试图研发的蓝色基因p 的目标是达到峰值l p e t a f l o p s ，处理节 点达到2 5 6 k 个。在如此大规模分布式系统中，如果不能实现合理任务调度将使世界顶 级计算机无用武之地。 在国家自然科学基金赞助下，本文针对超大规模分布式系统负载平衡问题展开深入 研究。主要工作包括以下几方面： 首先，研究并分析了几种典型的完全集中式以及分布式策略在解决超大规模分布式 系统负载平衡的局限性。集中式策略包括：贪婪策略( g r e e d y l b ) 、精细化策略( r e f m e l b ) 、 正交递归半分策略( o r t h o g o n a lr e c u r s i v eb i s e c t i o na l g o r i t h m ，o r b l b ) 、贪婪通信策略 ( g r e e d y c o m m l l b ) 。分布式策略包括：相邻分配策略( n e i g h b o r h o o da v e r a g i n g ) 、任务偷 取策略( w o r k s t e a l i n g ) 。并通过仿真实验验证了集中式负载平衡策略在内存开销以及负 载平衡开销存在的瓶颈以及分布式负载平衡策略c p u 利用率低等缺点。 其次，研究并分析了解决超大规模分布式系统负载平衡问题经典策略所存在的缺 陷。包括层次策略以及混合式负载平衡策略的通讯开销以及负载平衡开销。 然而，以上所有策略都是基于通讯是固定的或是不考虑通讯延迟开销，近几年的研 究发现延迟依赖于通讯介质呈现出时变性。这是由于网络中的通信量、阻塞情况以及一 些未知因素所决定。目前提出的基于延迟的负载平衡策略并不能针对该特性进行有效预 测。 最后，本文根据大规模分布式系统通讯开销时变的特点，提出一种基于随机延迟论 的层次结构负载平衡策略。此策略具有以下三个特点：( 1 ) 应用通讯优化的层次结构减 小超大规模机群的负载平衡开销。( 2 ) 考虑到节点计算速率以及通讯介质的随机延迟性。 ( 3 ) 通过广义神经网络理论建模进行延迟预测，从而优化任务通讯延迟及迁移延迟。此 方法为基于延迟的一类负载平衡策略提供了优化方案。 仿真实验验证了应用广义神经网络进行延迟预测优于目前同类预测算法，适用于超 大规模机群。 关键词：负载平衡；超大规模并行机；层次结构策略；广义神经网络 大连理工大学硕士学位论文 r e s e a r c ho nl o a db a l a n c i n gf o rp e t a s c a l ed i s t r i b u t e ds y s t e m s a b s t r a c t w i mh a l fac e n t u r yo fe f f o r t s d e s i g n e d ，c o m p u t e rh a r d w a r eh a sb e e ni n c r e d i b l y i m p r o v e da n dt e n d st ob el o wc o s ta n dh i 曲p e r f o r m a n c e f o re x a m p l e ，i b mh a sr e v e a l e da n a m b i t i o u sp r o g r a mt oe x p a n dt h eh o r i z o n so fs u p e r c o m p u t i n gw i t ht h eg o a lo fc r e a t i n ga s y s t e mc a l l e db l u eg e n ept a r g e t i n gl p e t a f l o p so f p e a kp e r f o r m a n c ew i t hp r o c e s s i n gn o d e st o a c h i e v e2 5 6 k s oi tw i l lm a k et h ew o r l d st o pc o m p u t e ru s e l e s sw i t h o u tar e a s o n a b l et a s ko f s c h e d u l i n gs t r a t e g yi ns u c hp e t a - s c a l ed i s t r i b u t e ds y s t e m s u n d e rt h ea u s p i c e so fn a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o n , t h ew o r k si nt h ep a p e rf o c u s o nl o a db a l a n c i n gf o rp e t a - s c a l ed i s t r i b u t e ds y s t e m s i t sm a i nt a s k sa r r e 弱f o l l o w s ： a tf i r s t ，t h ep a p e ra n a l y s e st h el i m i t a t i o n so fc e n t r a l i z e da n dd i s t r i b u t e ds t r a t e g i e s c e n t r a l i z e d s t r a t e g i e s i n c l u d e g r e e d y l b ，r e f i n e l b ，o r b l b a n d g r e e d y c o m m l l b d i s t r i b u t e ds t r a t e g i e si n c l u d en e i g h b o r h o o da v e r a g i n ga n dw o r k - s t e a l i n g e x p e r i m e n t a l r e s u l t sp r o v et h a tt h ec e n t r a l i z e ds t r a t e g i e sa b o v eh a v ed i m c u ! t i e si nm e m o r yc o s ta n d o v e r h e a do fl o a db a l a n c i n g ，b u td i s t r i b u t e ds t r a t e g i e sh a v ep r o b l e m si nl o wc p uu t i l i z a t i o n s e c o n d l y ，t h ep a p e ra n a l y s e st h ec o m m u n i c a t i o nc o s ta n do v e r h e a do fl o a db a l a n c i n go f t h es t r a t e g i e sf o rp e t a - s c a l ed i s t r i b u t e ds y s t e mw h i c hi n c l u d e sh i e r a r c h i c a ls t r a t e g ya n d h y b r i d s t r a t e g y b u ta l lt h es t r a t e g i e sa b o v ea r ep r e d i c a t e do nt h ea s s u m p t i o nt h a td e l a y sa r ed e t e r m i n i s t i c i na c t u a l i t y , d e l a y sa r er a n d o mi ns u c hc o m m u n i c a t i o nm e d i a , e s p e c i a l l yi nt h ec a s eo f p e t a s c a l ed i s t r i b u t e ds y s t e m t i l i si sa t t r i b u t a b l et ou n c e r t a i n t i e sa s s o c i a t e dw i t ht h ea m o u n t o ft r a f f i c ，c o n g e s t i o n , a n do t h e ru n p r e d i c t a b l ef a c t o r sw i t h i nt h en e t w o r k b u tt h ee x i s t e n t s t r a t e g i e sp e r f o r mp o o r l yt op r e d i c tt h ec o m m u n i c a t i o nd e l a y d u r i n gt h er e a s o n sa b o v e ，a c c o r d i n gt ot h ef e a t u r eo ft h er a n d o md e l a y , t h ep a p e r p r o p o s e sr a n d o m n e s sb a s e dh i e r a r c h i c a l l o a db a l a n c i n gf r a m e w o r ki nc o n c l u s i o n 1 1 1 e f r a m e w o r kh a st h r e ef e a t u r e s ：( i ) p r o p o s i n gh i e r a r c h i c a lf r a m e w o r kt od e c r e a s et h eo v e r h e a d o fl o a db a l a n c i n g ( i i ) c o n s i d e r i n gt h eh e t e r o g e n e i t yi nt h ep r o c e s s i n gr a t e so ft h en o d e sa s w e l la st h er a n d o m n e s si nt h ed e l a y si m p o s e db yt h ec o m m u n i c a t i o nm e d i u m ( i i i ) p r o p o s i n g t h eg e n e r a l i z e dn e u r a ln e t w o r k ( g n n ) p o l i c yb a s e do ni n t e l l i g e n tn e u r o n sf o rd e l a yf o r e c a s t i nd i s t r i b u t e ds y s t e m ，t h i sm e t h o dp r o v i d e sas o l u t i o nf o rt h ec o m m u n i c a t i o nb a s e dl o a d b a l a n c i n gs t r a t e g i e s o u rs i m u l a t i o nr e s u l t sp r o v et h a tt h i sf r a m e w o r ki sf i tf o rp e t a - s c a l ed i s t r i b u t e ds y s t e m c o m p a r e dw i t ht h ec e n t r a l i z e df r a m e w o r k a sw e l la st h ed i s t r i b u t e df r a m e w o r k i i i 超大规模分布式系统负载平衡研究 k e yw o r d s ：l 0 a db a l a n d n g ；p e t a s e r ed i s t r i b u t e ds y s t e m ；h i e r a r c h i c a lf r a m e w o r k ； g e n e r a l i z e dn e u r a ln e t w o r k i v 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 学位论文题目： 壁叁查噬仝鼗! 芷亟蛐骂赵 作者签名： 2 茎鞋璺垒日期：尘竺 年一l 三月上乙日 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题 作者签名： 导师签名： 大连理工人学硕士学位论文 1 绪论 1 1 研究背景及意义 众所周知，负载平衡技术是考虑分布式系统中节点计算性能、通讯性能等参数从而 保证所有节点高效运行的有效手段。目前已被广泛应用于生物科学、宇宙计算科学、工 程设计、地震建模和天气预报等领域。随着科学计算的发展大量世界性难题都需要借 助大规模科学计算来解决。例如大范围气象预报与灾害预警，生态模拟与环境控制，天 体物理学，分子动力学等许多领域都提出了大规模科学计算的大量需求。当前我国也亟 待解决很多大规模科学计算问题。例如，我国生态环境先天脆弱，水土流失，污染严重， 经常蒙受多种自然灾害。加强大气、海洋和环境的数值模拟和预测将可找到更多有效的 措施减灾妨害。又如，研究强地震场和强台风场及其动力作用下重大工程的损伤破坏演 化过程，揭示重大工程的损伤机理和破坏倒塌机制，建立重大工程动力灾变模拟预测分 布式系统，将能有效的降低地震、台风等自然灾害的破坏作用。 大规模科学计算的水平与高性能计算机的发展紧密相连、互相依赖。经半个世纪的 努力，计算机硬件设计己获得令人不可思议的提升并趋向于高性能低开销化。例如，美 国能源部的a s c 计划已经为国家实验室提供了一系列强大的平台。包括a s c 红色暴风 ( 1 0 k 机器、4 0 t f l o p s ) ，紫色暴风( 1 2 k 机器、1 0 0 t f l o p s ) 和i b m 研制的蓝色基因 u 1 8 0 3 6 0 t f l o p s ) 拥有6 4 k 双处理器节点。甚至更早意图设计的蓝色基因c 拥有超过 1 ，0 0 0 ，0 0 0 浮点单元，超过8 ，0 0 0 ，0 0 0 条指令流支持各自的线程单元，目标峰值性能达到 1 删0 p s 。i b m 正在试图研发的蓝色基因p 的目标是达到峰值l p e t a f l o p s 。 图1 1 大型机在过去3 0 年性雏增长系鼓 f i g1 1a 舯w 曲出m 田o f a 坷i i i n p e r f o r m a a e c i a 也e p u t3 0 y e a r s 超大规模分布式系统负载平衡研究 美国国家科学委员会f n s b ) 通过了一项决议，授权美国国家科学基金会m s f ) 资助两 台超级计算机的建设。p e t a s c a l e 级的t r a c k l 系统的持续运算能力将超过每秒l p e t a f l o p s 。 t r a c k 2 系统运算速度则稍低一些。目前两个项目的立项工作还要经过一些行政和财务程 序，最终将于秋季完成。n s f 的网络基础设施办公室支持多个级别的超级计算机项目， 以帮助美国科学家和工程师解决科技难题。获n s b 通过的两个项目将为美国学术界带 来世界领先级的计算资源。伊利诺斯大学将承担t r a c k l 项目，并在未来4 年半的时间 里将获得2 亿8 百万美元的经费打造名为“b l u ew a t e r s 的系统。预计系统将于2 0 11 年上线。系统将帮助用户研究复杂过程，如日冕物质抛射与地球磁气圈和电离层之间的 交互；宇宙早期星系的形成与演变；活细胞中发生的化学反应链；新材料设计。 尽管在研究超大规模并行机的负载平衡策略上许多学者已做过许多工作，然而，在 逐渐演变的超大规模机的负载平衡研究中，负载平衡问题面临着新的考验。首先，机器 拓扑结构变成了不得不考虑的重要因素。其次，由于节点数目庞大，难以做出全局决策。 再次，负载平衡开销加剧，算法复杂度要求苛刻。传统的负载平衡策略势必不适应超大 规模并行机负载平衡，新型的负载平衡策略迫切渴求。 1 2 研究现状及分析 1 2 1 传统分布式系统负载平衡研究现状 分布式技术是当今计算机领域的研究热点之一。在分布式技术飞速发展的同时，分 布式系统中的负载平衡问题也变得越来越重要。负载平衡的目的是在包含大量节点的分 布式系统中，同时考虑各节点的计算性能、节点之间的通讯性能等参数，把不同的任务 以最合理的方式分配到相应的节点去完成。负载平衡问题也称为任务调度问题。由于在 分布式环境中各处理器的运行速度、主机的负载、网络通讯的时间等是动态变化的，任 务调度问题同时也是一个非常困难的n p 完全问题，因此启发式调度算法在分布式计算 环境得到广泛的应用【l 】。 目前，围绕着分布式计算中的任务调度算法，国内外已经做了大量的研究工作，先 后提出了各种静态和动态的调度算法。静态负载平衡s l b ( s t a t i cl o a db a l a n c i n g ) 是根据 服务器和网络的负载特性，预先制定一个调度策略或分配算法，在集群运行的整个阶段 都按照这个不变的策略或算法给各个节点分配任务。而动态负载平衡需要在集群系统运 行时实时检测系统的负载信息，动态地将任务在各个结点之间进行分配和调整以达到 系统负载的均匀分配。相对于静态负载平衡，它具有更大的灵活性和针对性，可根据当 前的负载状态有目的地进行负载平衡，临时决定每个任务的执行过程。通常，静态负载 平衡比较简单，但它并不能保证负载时刻平衡；动态负载平衡比较复杂，虽然能够得到 大连理工大学硕士学位论文 较好的平衡效果，但必然导致一定的额外开销。实验表明，通常情况下动态负载平衡较 静态负载平衡有3 0 4 0 的性能提高【2 1 。由于动态负载平衡有较好的平衡效果，本文的研 究主要基于动态负载平衡。 而另一种负载平衡分类方式则是按照管理方式可分为集中式负载平衡策略以及分 布式负载平衡策略。集中式策略由指定负载平衡协调节点统一来完成负载信息的收集、 负载的分配。而分布式负载平衡策略是每个节点自主完成负载的分配。集中式策略主要 包括：g r e e d y l b 、r e f i n e l b 、o r b l b 、g r e e d y c o m m l l b 。分布式策略主要包括：相邻分 配策略、w o r k - s t e a l i n g 策略等。本文将在第三章着重讨论以上几种策略。 使用动态负载平衡需要解决如下问题： ( 1 ) 同步。负载平衡时需要对集群中所有的服务器同一时刻的负荷进行的比较，可 以采取发送同步信号的方法解决这个问题。 ( 2 ) 性能度量。就是以多大的频率采集各处理器节点负荷参数，采集什么样的参数 能最好地反映系统性能，如何采集负荷参数。合理地解决这些问题才能达到最佳的负载 平衡效果。 早在1 9 9 3 年m a r ch 总结出对于负载平衡的研究着重考虑以下两个因素【3 】： 第一负载平衡调度决策的准确性。 第二负载平衡的通讯和计算的额外开销。 截止到1 9 9 3 年止，主流的动态负载平衡调度算法可以分为以下五种：发送者( 接 收者) 发起的负载分配策略( s d g i d ) 、层次负载策略( h b m ) 、梯度模型( g m ) 、元交换 模型( d e m ) 。各算法的具体策略如下： s i d ：利用临节点的负载信息进行超载量的分配，这是一个同步集中式负载平衡策 略。将每个重载节点任务量向相邻轻载节点进行迁移。此后s i d 策略发展出分布式策略， 即每个节点掌握其邻节点信息，将重载任务量向相邻轻载节点进行迁移。 h b m - 是一个异步全局方法，组织系统成一个层次的子系统。负载平衡先在最低层 发起，直至上至最高层。 g m ：采用一种需求驱动方式【4 1 。最基本的方式是欠载节点通知其它处理器他们的 当前状态，超载机器收到信息后做出响应分配一部分多余的负载给最近的轻载机器。结 果使机器负载呈梯度减少。 d e m 是一个全局同步式负载平衡策略。采用与h b m 策略相类似的方法，只不过 它是同步的。 m a r ch 在i p s c 2 超立方体机器上做了仿真实验，仿真结果验证s i d 策略的性能最优， 能较好支持并行系统。 超大规模分布式系统负载平衡研究 随着分布式系统的快速发展，动态负载平衡策略也随之快速发展。直至1 9 9 8 年，人 们逐渐认识到节点任务之间的通讯关系也成为影响负载平衡优劣的重要因素。w a t t sj ， t a y l o rs 提出基于减少通讯开销的负载平衡策略【5 】。后来逐渐演变出t d s 、o s a 、p p a 以 及c p f d 等相应基于通讯的任务复制式算法。截止2 0 0 7 年，该类算法已发展到基于动态 关键任务的d c t 算法【6 】。此类算法属于静态负载平衡算法，目前关于该理论还没有动态 调度算法，因而在本文不做详细介绍。 2 0 0 0 年后，负载平衡算法趋于多样化发展。由于贪婪算法在解决负载平衡问题具有 快速准确的特点，因而出现了许多基于贪婪算法的改进。如：m c t 、m e t 、s a 以及k p b 等。m c t 算法是快速贪婪启发式调度算法【7 ，8 】的一个变体，可作为在线模式下的启发式 调度算法的基准点，其执行情况被用来与在线模式下其它启发式调度算法的执行情况进 行比较。 本文将在第二章详细讨论s i d 算法以及m c t 算法。 1 2 2 超大规模分布式系统负载平衡研究现状 尽管在研究超大规模并行机的负载平衡策略上许多学者已做过许多工作，然而，在 逐渐演变的超大规模机的负载平衡研究中，负载平衡问题面临着新的考验。因为在如此 大规模的节点中定位的效率面临很大困难。 首先，机器拓扑结构变成一个值得去考虑的重要因素。在小型并行机系统中，机器 拓扑结构经常被忽略。任务可以在任意远度的节点间迁移，但是对于超大规模并行机来 讲，尽管延迟很小，但是通讯量却随着跳数的增多而明显增大。因此，在网络直径非常 大的情况下，系统拓扑结构不再可以不被考虑。 其次，随着规模的增大，在缺乏系统全局负载信息时，很难做出负载均衡决策。而 分布式策略又存在节点掌握信息不足，难以做到迁移目标的准确。 再次，由于节点数量和任务量的增多，负载平衡的速度必将会变慢。举一个简单的 例子，当有n 个进程跑在p 个处理器上，负载平衡算法的复杂度为o ( n l o g p ) ，但是当n 从1 6 k 增加到1 m 并且p 从1 k 增加到6 4 k ，负载平衡的执行时间就会变为原来的2 5 6 倍。负载平衡开销增大，甚至有可能出现内存不足的情况【9 1 。因而算法的复杂度成为考 虑负载平衡策略的重要因素。 最后，近几年的研究发现延迟依赖于通讯介质呈现出时变性。这是由于网络中的通 信量、阻塞情况以及一些未知因素所决定。并且，s a g a rd h a k a l 的研究指出分布不考虑 延迟随机性的负载平衡在实际的分布式计算中将获得很差的性能【l o 】。并在2 0 0 7 年给出 一4 一 大连理工大学硕士学位论文 了随机延迟预测公式【l l 】。通过延迟预测反应出网络时变特性的负载平衡策略成为负载平 衡问题热点讨论的问题。 目前，关于超大规模分布式系统负载平衡策略可以分为以下几类： ( 1 ) 完全分布式负载均衡策略： 分布式负载均衡，在有些文献中也称为扩散性负载均衡，是对负载均衡的一种非集 中式和可扩展的实现。它基于物理学中的扩散原理，能量和物质从高浓度区域流向低浓 度区域，导致分布上的同构。完全分布式策略的典型算法有：相邻分配策略( 在1 2 1 中提到的分布式s i d 策略) 、w o r k s t e a l i n g 策略。 尽管完全分布式负载均衡器在超大规模并行机上具有可扩展性，但是此类策略因为 每个结点都进行自我决策，没有节点能掌握整个系统的全局状态，因此很难达到最优负 载均衡，尤其在节点负载状态变化剧烈的情况下。其次，完全分布式策略只使用系统状 态的很少一部分信息，通常一个结点只和有限几个邻居结点交换负载信息。如果负载最 重结点和负载最轻结点距离较远，那么在这种模式下，需要经过大量迭代才能使负载信 息在这二者之间传播。如果负载情况变化剧烈，这种情况将导致更坏的性能。 ( 2 ) 集中式负载均衡策略： 对所有节点采用集中式管理的方式，管理节点掌握全局信息，并完成负载的分配， 目前集中式负载平衡主要有：随机集中式策略( r a n d c e n t l b ) 、贪婪策略( g r e e d y l b ) 、精 细化策略( r e f i n e l b ) 、精细化k 策略( r e f i n e k l b ) 、正交递归半分策略( o r t h o g o n a lr e c u r s i v e b i s e c t i o na l g o r i t h m ，o r b l b ) 、贪婪通信策略( g r e e d y c o m m l l b ) 、精细化通信策略 ( r e f m e c o m m l l b ) 、图划分策略( m e t i s l b ) 、递归半分策略( r e c b i s e c t b f l b ) 。 集中式负载均衡策略的优点是能够获得整个系统的全局负载和通信信息，进而做出 更加优化的负载均衡决策。但是，集中式策略是固定不可扩展的，在超大规模系统中会 呈现出如下局限性： 在超大规模并行系统中获取全局状态信息可能是一个费用昂贵的操作。 全局信息被收集到一个结点用来做出负载均衡决策，这对内存开销提出了挑战。 在超大规模并行系统中，单协调者可能会造成通信瓶颈。 在处理器和迁移对象数量较多时，集中策略的决策制定算法可能造成非常高的执 行开销。 基于贪婪的集中式策略可以在不考虑对象迁移的情况下做出全局决策。在超大规 模并行系统中，这可能导致所有对象离开原来位置，从而产成巨额开销。 ( 3 ) 混合式负载均衡策略： 一5 一 超大规模分布式系统负载平衡研究 实验表明，集中式策略和分布式策略都不能很好的解决p e t a 规模机器上的负载均衡 问题，于是就产生了结合集中式和分布式两种策略的混合式负载均衡策略。 分层策略在文献中被广泛研究，对于处理器中节点建立层次树型结构，对于 l e a d e r 节点实行自适应算法，从而计算出内存利用率，这样在不同层次之间可根据 c p u 利用率和内存利率的不同进行判定，从而在需要考虑通讯的情况下和不需要考虑通 讯的情况，不同层次之间采用不同的策略进行负载平衡。 多数研究都把目标应用假设为连续子任务流，这样，所研究的问题就转换为任务调 度问题或任务分配问题。这些应用一般都包括一个子任务生成器和动态变化的负载。 f u r u i c h i 等【1 2 】给出了在分布式分层模式下使用多处理器对o r p a r a l l e l 图进行任务划 分的策略。其中一些处理器充当子任务生成器的角色，负责把任务分配到其它处理器。 在这种模式下，空闲处理器向其它处理器申请子任务。进行负载均衡时，子任务被传递 到需要它们的处理器上。 a h m a d 等【1 3 】给出了普通拓扑结构( 例如超立方体) 下任务分配的半分布式策略， 以替代传统的完全分布式或完全集中式策略。这种策略以一些控制点为中心，把计算机 系统划分成一些相互独立的区域( 球体) 。这些球体的中心点( 调度器) 在球体内部进 行最优化调度，并使用很低的开销维护系统状态信息。这篇论文给出了一种任务调度中 超立方体系统划分的高效策略，消息传递开销较低。 而上述策略考虑的通讯延迟开销皆是在假设延迟固定不变的条件下提出的【1 4 1 8 】。 1 2 3 负载平衡框架研究现状 负载均衡框架是能够动态平衡应用负载的负载均衡软件，可以通过六种属性对其进 行区分： ( 1 ) 支持数据迁移：迁移进程或线程增加了运行时系统的复杂性而且通常不易移植。 数据迁移是一种隐式的计算迁移方法，是一种更简单的解决方案，而且具有更强的可移 植性。 ( 2 ) 支持显式消息传递：消息传递是一种开发者比较熟悉的编程模式，它不想开发 者隐藏并行性。 ( 3 ) 支持全局名字空间：全局名字空间是动态数据迁移的前提条件，应用程序可以 直接引用数据而不需要知道数据在系统种的具体位置。 ( 4 ) 单线程应用模型：单线程模型可以显著降低应用程序开发的复杂性和难度。 ( 5 ) 自动负载均衡：运行时系统自动迁移数据和计算。 一6 一 大连理工大学硕士学位论文 ( 6 ) 可定制负载均衡：允许用户较容易的开发和测试不同的负载均衡策略，而不需 要大量修改应用程序代码。 许多负载均衡框架，例如s p l i t c 【1 9 】，提供了对全局名字空间的支持，但是不支持数 据迁移并且需要用户显式维护名字空间的一致性。g m b e 4 2 0 1 ，e m e r a l d t 2 1 1 和c o o l 2 2 2 】 提供另外一种解决方案，但是这些系统经常需要借助虚拟地址空间划分模式，使用新型 编程语言实现并行，这种方法增加了系统开销，并且需要开发者掌握将来可能不被支持 的语言。同时，这些系统只提供了负载均衡必需的基础设施，而没有考虑自动负载均衡 中的决策制定。 v d s 2 3 1 和m i l l i p e d e t 2 4 】通过计算线程的散布和迁移实现了自动动态负载均衡。这与 p r e m a 2 5 】提供的单线程编程模型不同，单线程模型不但能够简化应用程序开发的难度， 而且增加了代码的可移植性。cr e g i o nl i b r a r y ( c r l ) 【2 6 】实现了并行机算的共享内存编程 模型，通过访问虚拟内存的共享区域来实现并行性。z o l t a n 2 7 1 ，c h a r m + + 【2 8 】与p r e m a 2 5 】 三者功能比较接近。z o l t a 提供了一些图划分算法和几何负载均衡算法，但是因为这种 负载均衡方法需要同步，所以同其它“停止一重划分( s t o p a n d r e p a r t i t i o n ) 算法一样效 率较低。 相比之下，c h 删+ + 是建立在一种c + + 变种语言的基础之上的，它提供可扩展的 负载均衡策略。现将三者功能比较如下： 表1 1 支持动态负载平衡软件系统 t a b 1 1s o f t w a r es y s t e m st h a ts u p p o r td y n a m i cl o a db a l a n c i n g 基于c h 删+ + 有其它负载平衡框架不可比拟的特点，本文的主要负载平衡研究都 是基于c h a r m + + 均衡框架【9 】。 1 3 超大规模分布式系统负载平衡研究难点以及技术路线 目前超大规模分布式系统负载平衡面临的主要困难来自于两个方面：一方面是缺乏 超大规模分布式系统仿真环境。另一方面是缺少系统的方法论。 虽然并行计算机的发展速度很快，但是应用程序在如此大规模的机器上运行的性能 却难以评测。在目前机器不可操作的情况下，迫切需求一个能够模拟超大规模分布式系 超大规模分布式系统负载平衡研究 统的模拟器。即使目标机器是可操作的，在计算时由于连接受限也难以做到大规模的并 行编译。能够模拟超大规模并行计算环境成为研究的首要条件。 其次，该研究领域属于负载平衡研究较新的一个领域，因而许多成熟的负载平衡策 略在这一领域并不适合，而成熟的适合于超大规模分布式系统的负载平衡策略并没有形 成。因而，以现有负载平衡研究理论为基础，对超大规模分布式系统网络拓扑结构进行 建模给出优于混合式负载平衡模型成为首要任务。 综上所述，超大规模分布式系统负载平衡研究技术路线如下： ( 1 ) 将负载平衡与拓扑图论联系起来，实现基于拓扑图划分的负载平衡策略。 ( 2 ) 将集中式与分布式负载平衡框架结构结合起来建立新型负载平衡结构。 ( 3 ) 重点关注结点间通信问题，利用合理化模型着重考虑延迟变化情况，比较和分 析当前可扩展负载均衡策略对超大规模计算的性能影响，在此基础之上设计更优策略。 1 4 本文的主要工作 根据超大规模分布式系统节点数量多全局管理难、拓扑延迟大、负载平衡开销大等 特点，研究者建立了新型负载平衡模型，并利用超大规模并行机模拟器进行仿真实验验 证。 本文的主要工作主要包括以下几点： 第一，超大规模负载平衡现在面临的问题。节点数量多全局管理难、拓扑延迟大、 负载平衡开销大以及网络延迟时变等特点，这四种统计特性被研究者视为检验一个模型 有效性的基本度量标准。为下一步检验各模型有效性做好铺垫。 第二，本文研究并分析了几种典型的完全集中式以及分布式策略在解决超大规模分 布式系统负载平衡的局限性。集中式策略包括：g r e e d y l b 、r e f i n e l b 、o r b l b 、 q e e d y c o m m l l b 。分布式策略包括：相邻分配策略、w o r k s t e a l i n g 策略。并通过仿真 实验验证了集中式负载平衡策略在内存开销以及负载平衡开销存在的瓶颈以及分布式 负载平衡策略c p u 利用率低等缺点。 第三，分析了解决超大规模分布式系统负载平衡问题经典策略，包括层次策略以及 混合式负载平衡策略的通讯开销以及负载平衡开销。并分析了以上所有算法均没有考虑 到拓扑通讯时变性的特点。 第四，本文根据大规模分布式系统通讯开销时变的特点，提出一种基于随机延迟论 的层次结构负载平衡策略。此策略具有以下三个特点：( 1 ) 应用通讯优化的层次结构减 小超大规模机群的负载平衡开销。( 2 ) 考虑到节点计算速率以及通讯介质的随机延迟性。 一8 一 大连理工大学硕士学位论文 ( 3 ) 通过贝叶斯理论建模进行延迟预测，从而优化任务通讯延迟及迁移延迟。仿真实验 验证了此策略较集中式和分布式负载平衡策略更适用于超大规模机群。 第五，对本文工作做了总结，并展望了下一步工作要点。 1 5 本文组织结构 本文剩余部分组织如下： 第二章动态负载平衡框架。重点介绍负载平衡框架的信息、发起、转移、位置、 选择五个相位具体策略详细介绍。 第三章分布式系统传统负载平衡策略研究与分析。分析介绍了传统分布式负载平 衡策略以及集中式负载平衡策略，并进行仿真实验验证指出其存在的不足。 第四章超大规模分布式系统负载平衡策略研究与分析。分析介绍了目前超大规模 分布式系统负载平衡策略包括层次策略以及混合式负载平衡策略，并进行仿真实验验证 指出不足之处。 第五章基于随机延迟论层次结构负载平衡策略。根据超大规模负载平衡现在面临 的问题。节点数量多全局管理难、拓扑延迟大、负载平衡开销大以及网络延迟时变等特 点，提出一种基于随机延迟论的层次结构负载平衡策略。并通过仿真实验验证了有效性。 最后是结论。对全文工作做简要总结，并提出下一步工作思路。 一9 一 超大规模分布式系统负载平衡研究 2 动态负载平衡框架 负载平衡是保证在分布式计算以及通讯过程中并行机中无处理器处于超载状态的 技术。是解决高性能计算机高效完成高动态性以及不规则任务的重要因素。 负载平衡问题包括将已确立好的计算任务映射到处理器，以及迁移现存任务到其他 处理器以达到负载平衡。负载平衡问题是n p 难解问题。然而，许多学者开始研究各种 启发式算法给出合理解。 负载平衡问题同样向软件设计提出了挑战。许多现存的动态负载平衡是直接将算法 加入到特定的应用并行程序中去。这样做具有众多不利因素。首先，因为负载平衡直接 通过应用直接实现，这样难以检测不同策略的有效性。其次，既然负载平衡与实际应用 是紧耦合的关系，负载平衡策略难以应用到其它应用中，不具备可移植性。最后，应用 程序的开发者也不会有兴致关心优化负载平衡策略。 在本章中，研究者将讨论负载平衡理论以及时实动态负载平衡框架。 2 1负载平衡问题 现将负载平衡的目标定义如下： 给定一个包括计算和通信的任务集( 将一个问题分解为多个子任务，所有子任务组成 一个集合) ，以及一组通过一定拓扑连接起来的处理器。求解任务到处理器的一个合理 映射，使得每个处理器具有与之处理能力相匹配的计算量，同时保证计算机间的通信开 销最小以及任务的完成总时间最小 2 9 】。 其中，任务可以是子程序、迁移对象或线程等。达到平衡的任务到处理器的映射可 以增强整个并行程序的有效性。然而单纯的负载平衡并不能提高并行有效性。 2 1 1基本定义 在本小节中，本文给出负载平衡问题的基本定义如下： ( 1 ) 处理器图 分布式系统的处理器可以抽象为一个网络拓扑图。其网络拓扑结构可以表示为一个 无向加权图g 卢= ( 圪，q ) ，其中p = i 咋l 。每一个中的节点代表一个处理器，e ，代表 处理器之间的实际连接。 ( 2 ) 任务图 并行应用程序可以抽象为一个加权无向图q = ( 形，巨) 。节点形代表并行任务，e 代 表任务之间的通讯。每一个节点，形都具备权值w ，w 代表该任务计算量。同样每条 大连理工大学硕士学位论文 边= ( y a ) e t 也具备权值c 4 6 ，代表屹与屹之间的通讯量( 以字节为单位) 。因为 不考虑通讯的方向，因而该图为无向图。 ( 3 ) 任务映射 任务映射可用如下公式来表述： p ：k 一匕 ( 2 1 ) 如果任务图中1 ，形被映射到处理器p 则p ( d 印。 映射后，每个节点p 具备权值睨代表处理器p 的总的负载量： = m ，t = t ip ( f ) = p ) ( 2 2 ) ，e 7 考虑到在权值中对于p 匕的通讯开销，则公式2 2 可表示为： = ( 嵋+c ，6 ) ， r = 川p ( f ) = p ) ( 2 3 ) t e t e , e e t p ( 6 ) i i p 讨论问题的分解和映射是有必要的，问题分解分属并行程序设计的一部分，它试图 分解程序为几个部分分别运行在不同处理器上。问题分解的结果是解决该并行任务的一 系列并行任务集。任务间是独立的或通过通讯相联系。 2 2 负载平衡相关工作 应用程序的动态行为以及机器特性均影响到动态负载平衡策略的设计。在本章中， 研究者将讨论三种应用程序特性以及描述能够影响负载平衡算法的机器特性，最后对任 务迁移机制做概括介绍。 2 2 1 非迭代应用 非迭代应用无时间相关性与可预测性。举一个例子，考虑一个用于解决问题的给定 空间搜索应用。考虑给定空间为离散结构集。状态空间限定系统地扫描这些状态为寻找 问题解。一些情况下，任何解都可被接受。但是更经常的情况是，需要在最小开销条件 下得到可行解。在并行算法中，问题可以被分解为若干子任务进行子状态空间的搜索。 这些子任务是短时任务，但可以根据现存计算过程产生新的子任务。负载平衡器需要在 掌握全局信息最少的条件下独立地对新任务做出调度。既然计算是不可预测的，负载平 衡算法很难获得全局分布信息。 负载平衡问题同样被称为任务调度问题【3 0 , 3 1 】。负载平衡调度问题可被定义如下：给 定任务集和处理器集，选择有效方式调度任务，使任务有更快响应时间、吞吐量和资源 利用率，并保持调度开销最小。 超大规模分布式系统负载平衡研究 调度策略在文献中得到广泛研究。调度策略可被定义为以下两类：静态调度策略， 要求执行任务前进行调度，这类策略需要任务调度的先行知识。图论模型例如网络流【3 2 】 和启发式算法【3 3 】经常被用于任务分配。 第二类调度策略不需要任务先行知识，而是在实时过程中进行调度。这类策略被称 为动态负载平衡策略 1 4 , 16 】。而非迭代应用由于缺乏可预测计算信息，因而不适宜采用静 态负载平衡策略。 2 2 2 可预测迭代应用 第二类应用称为可预测迭代应用。实际上，许多科学计算问题，特别是物理模拟都 是迭代的。这类计算往往时间比较长并且由一系列时钟步组成最终迭代收敛。对于这类 问题计算负载量和通讯类型往往是恒定不变的。因而，这类问题是可预测的，这在启发 式中称为“恒定性 3 4 1 。在这类应用中，基于测量的负载平衡策略是有效的。 2 2 3 不可预测迭代应用 第三类应用包含迭代，但却不可预测。这类应用包含迭代计算相关性。但因为迭代 不够健壮或机器环境不可预测导致负载量突发改变。这类不可预测性因素对操作系统时 间步造成干扰。对于这类应用程序建模，难以平衡负载。最佳解决方法是采用基于测量 的负载平衡策略和动态负载平衡相结合。 2 2 4 分割算法 负载平衡问题从本质上来看是一个将一系列任务分配到目标处理器上的分割问题。 分割算法从简单的不考虑通讯量的分割到复杂的考虑通讯量的分割。下面将这两类分割 策略介绍如下： ( 1 ) 无通讯意识分割 该问题分配n 个任务到p 台处理器并且最小化最大负载量，这类问题称为“跨度最小 化问题 ( m a k e s p a nm i n i m i z a t i o np r o b l e m ) ，这是一个n p 困难优化问题 3 5 1 。h o c h b a u m 和