（计算机应用技术专业论文）基于局域网的并行计算负载平衡.pdf

摘要 摘要 本文是在天津理工大学校级科研项目“基于局域网的并行计算负载平衡系 统”的基础之上完善而成的，主要研究利用局域网实现并行计算时的负载甲衡 问题。 采用的研究方法是分析国内外的相关资料及实际网络的特点，按照从特殊 到一般的方法，逐渐细化，得到结论，最后再用程序模拟验证。 论文的主要内容如下： 一、概述：分析国内外对并行计算提出的模型以及实现方法，讨论利用局 域网实现并行计算的特点和常用的前提假设。 二、模型：分析几种模型，然后分析在局域网中实现并行计算时的不确定 特点与统计规律。提出进行研究的前提假设，并在此摹础上给出更适合于不确 定网络的模型。 三、负载平衡：并行计算初期的数据划分和后期的负载平衡是统一的。本 部分首先分析了可测量的参数，然后讨论了数据划分的方法，最后分析了负载 平衡策略，提出了“分段双向计算”算法。 四、模拟实验：用计算指定范围内的质数为例，在单机上进行了若干组模 拟实验，结果表明，使用“分段双向计算”算法可以达到良好的负载平衡效果。 研究的结论是： 利用局域网实现并行计算是一种具有很高性价比的可行方案。虽然其中含 有大量的不确定因素，但是通过针对具体的情况采取相应的负载平衡算法，也 可以获得比较好的效果。 关键词： 基于局域网的并行计算，并行计算模型，数据划分，负载平衡 a b s 仃a c t a b s t r a c t t h ed i s s e r t a t i o ni sd e v e l o p e du p o nt h ep r o j e c t l o a db a l a n c i n gi np a r a l l e l c o m p u t i n gw h i c hi sr e a l i z e di nl a n ，w h i c hi sf u n d e db yt i a n j i nu n i v e r s i t yo f t e c h n o l o g y i tf o c u s e so ns t u d y i n gs o m ep r o b l e m sa b o u t i t f o ri t ，t h em a i ns t u d ym e t h o di sa n a l y s i ss o m er e c e n tr e s u l t sa n dt h ec h a r a c t e r o fr e a ln e t w o r k s b ys t u d y i n gs o m ec a s e sf r o ms p e c i a lt og e n e r i c ，w eg o ts o m e c o n c l u s i o n sa n ds i m u l a t e d 廿l e m t h ep a p e ri n c l u d e s ： 1 i n t r o d u c t i o n t h i sc h a p t e ra n a l y s e ss o m ep a r a l l e lc o m p u t i n gm o d e l sa n d r e a l i z em e t h o d sa r o u n dt h ew o r l d ，a n dt h e nf i n g e r so u tt h el a n sc h a r a c t e r sw h e n d o i n gp a r a l l e lc o m p u t i n g a st h eb a s i c ，t h i sp a r ta l s ol i s t ss o m eh y p o t h e s e s - 2 m o d e l t h i sc h a p t e rc o m p a r e ss o m em o d e l s ，a n dt h e nl i s t ss o m eu n c e r t a i n c h a r a c t e r sw h e nr e a l i z ep a r a l l e lc o m p u t i n gi nl a n b a s e do nt h es t a t i s t i cr u l e s ，t h e p a p e rd e s c r i b e st h eb a s i ch y p o t h e s e sa n dam o d e l 3 l o a db a l a n c i n g t h ea l g o r i t h m so f d a t ap a r t i t i o n i n gw i l le f f e c tt h eo n eu s e d i nl o a db a l a n c i n g t h i sc h a p t e ra n a l y s e se v e r yt e s t a b l ep a r a m e t e r s ，d e s c r i b e st h e a l g o r i t h mo fd a t ap a r t i t i o n i n g ，a n do fl o a db a l a n c i n g a tl a s t ，i t d e s c r i b e st h e t w o w a ys u b s e c t i o nc o m p u t i n ga l g o r i t h r n 4 s i m u l a t i o n t ov a l i d a t et h ea l g o r i t h m ，w ed e v e l o p e das i m u l a t i o ns y s t e m t h ec a s ei ss e a r c h i n gf o ra l lp r i m en u m b e r si ns p e c i a lr a n g e f r o mt h ee x p e r i m e n t s ， w ec o u l dd r a wac o n c l u s i o n ，t h a ti st w o w a ys u b s e c t i o nc o m p u t i n ga l g o r i t h m c o u l do b t a i np r o s p e c t i v ee f f e c t c o n c l u s i o n ： d o i n gp a r a l l e lc o m p u t i n gi nl a nc o u l dg e th i g hp e r f o r m a n c ew i t hl o wp r i c e t h e r ea r em a n yu n c e r t a i nc h a r a c t e r sd u r i n gc o m p u t i n g ，b u ti ta l s oc o u l dg e t p r o s p e c t i v ee f f e c tb yt a k i n g e f f e c t i v ea l g o r i t h m ，s u c ha st w o - w a ys u b s e c t i o n c o m p u t i n g k e vw o r d s p a r a l l e l c o m p u t i n gb a s e do nl a n ，p a r a l l e lc o m p u t i n gm o d e l ，d a t a p a r t i t i o n i n g ，l o a db a l a n c i n g i i 独创性声明 本人卢明所呈交的学位论文是本人存导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得墨壅盘茔或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意。 一繇焉稍、一期：貉年7 学位论文版权使用授权书 本学位论文作者完全了解墨注盘堂有关保留、使用学位论文的规定。 特授权墨盗盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名 导师签名 ) 而乙意 签字日期：0 以脚月动日 签字目期：7 矾巾年6 , 9 - z o 日 第t 章绪论 第1 章绪论 为了解决计算速度不能满足时间要求的问题，人们发明了计算机。几f 年 过去了，计算机的速度一直在迅猛地提高，然而，人们不断发现周围仍然存在 许多问题需要依赖于计算机速度的更人提高来解决，这些问题的计算规模非常 之大，以至于利用一台现有最快的计算机也小能在规定的时间内完成计算。在 这种情况下，人们自然地想到并行计算。 1 1 并行计算的特点 传统计算机执行的是串行计算，也就是由单一的处理器按照顺序迓语句地 执行程序，实现对数据的处理。而并行计算就是把一个大的问题分解成若干小 的模块，然后在多个处理器上同时运行这些小模块，最后再由一个或者多个处 理器汇总计算结果的过程。由于使用了多个处理器同时进行计算，计算时间将 明显缩短。考虑到任务划分、数据在处理器之间的传播、结果汇总等时间的开 销，以及计算问题中串行计算部分的影响，总的计算时间 强行 等 其中n 是参与并行计算的处理器数。 研究并行计算，首先要解决的问题是硬件连接。硬件的物理连接方式影响 到数据传递的速度和效率，因此在具体实现时需要精一t l , 设计。硬件的连接方式 有两大类：一种是专门设计的、内部含有多个处理器的计算机，即并行计算机， 另一种是以某种方式百i 连的若干台相对独立的计算机，即多机系统。 前者是专fj 设计的，因此可以在许多方面进行优化，例如在处理器之间的 通信方面进行优化，从而获得比较理想的加速比和相对稳定的性能。 而后者是实现并行计算的另一种途径，这种途径在如下诸多方面优于含有 多处理器的单机系统： ( 1 ) 能够以比较低的成本同时使用多台性能很高的工作站和p c 机； ( 2 ) 如果需要，可以很容易升级到最新的c p u ，与并行计算机相比，牛 竟是工作站和p c 机的更新速度快； ( 3 ) 可以比较容易地扩展系统，增加计算节点数目； r 4 ) 工作站的开发工具比并行计算机的专用工具成熟得多，而许多并行系 统没有做到标准化； ( 6 ) 使用现有的软件或者对现有软件进行修改后就可以使用； 第1 章绪论 ( 7 ) 如果需要，仍然町以作为中独的计算机使用。 在具体实现时，按照各计算机( 后面我们将它们称为计算节点，或者节点) 的连接方式还可以分成两种方式。一种方式是把各个计算节点使用专用的网络 ( 例如m y r i n e t 和高速以太网等) 连接成个独立的局域网。其中各节点通常 使用完全相同的硬件结构和软件环境( 即同构) 。这种方式的主要优点是便于分 析和研究。毕竟各个节点是完全相同的，因此每个节点的计算性能也相同。这 个特性极大地简化了任务划分和后期的负载平衡算法。目前更多的研究都是针 对这种连接方式的。 另一种方式是使用普通局域网( 或者广域网，甚至是i n t e m e t ) 上的计算机 实现并行计算。这种方式的突出特点是包含大量的“不确定”因素，其中主要 包括： ( 1 ) 连接各个节点的网络是不确定的，节点口j 以分布在同一个网络中，也 可以分散在若干连接在一起的网络中。 ( 2 ) 参与计算的节点往往是异构的，它们可以是工作站，也可以是高档或 者低档的p c 机，或者其他计算机；在操作系统方面，可能是w i n d o w s 系列操 作系统，也可能是l i n u x 或者其他操作系统。但是它们采用相同的网络协议( 例 如t c p f l p ) ，能够以某种方式进行通信和协作。 ( 3 ) 各节点参与计算的时间是不确定的，每个节点都可以随时加入或者退 出计算，因而参与计算的节点数量也是不确定的。 ( 4 ) 节点在参与计算的同时，很可能还在进行其他工作，例如进行w e b 浏览、文字处理、访问网络数据库等。 ( 5 ) 数据在网络卜传递的过程中，可能会受到其他不确定业务的干扰。 j 卜凼为在整个计算过程中有很多的不确定因素，因此很难为这种结构建立 数学模型，而且也很难对系统进行精确的分析和评价。 虽然从概念上讲，这两种连接方式都属于集群计算，但资料中提到的“集 群”或者“机群”更多的是前一种连接方式，即使用专用网络把各个计算节点 连接成一个独立的局域网。 1 2 有关并行计算的研究现状 就我找到的参考资料来看，目前国内外部分专家在并行计算的研究和应用 方面取得了一定的成绩。其中两个比较典型的案例是：中国的“南丌之星”和 日本的“g r a p e d r ”。 “南开之星”的计算能力是每秒3 2 3 1 万亿次。使用了8 0 0 个c p u ，4 0 0 个 节点，投资近2 0 0 0 余万元。 “g r a p e d r ”是门本东京大学、信息通信研究机构、同本电信电话公司、 第1 章绪论 国立天文台和理化研究所组成的联合小组2 0 0 4 年4 月2 6 宣布开始开发的世界 最高速的电子计算机。它使用2 0 0 万个运算处理装置，其运算速度将达到每秒 2 0 0 0 万亿次。 这两个案例都属于集群计算。 在利用连接在广域网( i n t e m e t ) 上的计算机进行，f = 行计算的成功案例中， 比较著名的是破译密码。1 9 9 7 年成功破译d e s 密钥使用了9 6 天，参与计算的 计算机数量达到了7 力- 个。对于破解r s a 密码也有过类似的实验，同样取得了 非常好的效果。现在国内外仍然有一些大规模计算问题是利用i n t e r n e t 上空闲 c p u 进行的。 虽然连接在i n t e r n e t ：的计算机带有大量的不确定因素，但有资料表明， 目日u 这是解决大规模计算问题的一个重要途径，而且具有广泛的应用。我们研 究的虽然是基于局域网的并行计算负载平衡，但是其中很多概念和基y - i n t e r n e t 的并行计算是类似的。 1 3 本文研究的内容及其实现目标 1 3 1 研究内容 本文研究的主要内容是在局域网上实现并行计算时的负载平衡问题。与理 想的并行计算环境相比，局域网中充满了大量的不确定因素，例如节点的连接 方式、计算性能等。本文具体的研究内容如下： 第1 章绪论。主要分析了并行计算的一些主要特点，有关并行计算的研 究现状，还介绍了本文要研究的主要内容和实现目标。 第2 章模型。重点讨论分析实际网络的特点、前提假设和三层模型。 第3 章负载平衡。首先分析可测量的参数，然后讨论任务划分方法，最 后重点分析负载平衡的策略。 第4 章模拟程序。首先介绍模拟程序的一些基本情况，例如测试实例、 方法等，然后给出实验结果并进行统计分析。 第5 章总结与讨论。本章是对整篇文章的归纳和总结，同时也给出了进 一步研究的建议。 1 3 2 实现目标 评价并行计算算法以及性能的个主要指标是加速比。而本文在研究过程 中使用的指标是时间差r ，即，从出现第1 个空闲节点的时刻t o 到最后1 个 节点开始空闲的时刻t n 的时问差，如图1 一l 和图l - 2 所示。写成公式就是 a t = f 。一f o 第1 章绪论 围立天文台和理化研究所组成的联合小组2 0 0 4 年4 月2 6 宣布开始开发的世界 最高速的电子计算机。它使用2 0 0 万个运算处理装置，其运算速度将达到每秒 2 0 0 0 万亿次。 这两个案例郁属于集群计算。 在利用连接在广域网( i n t e m e t ) 上的计算机进行并行计算的成功案例中， 比较著名的是破译擀码。1 9 9 7 年成功破译d e s 密钥使用了9 6 天，参与计算的 计算机数量达到了7 万个。对于破解r s a 密码也有过类似的实验，同样取得了 非常好的效果。现在国内外仍然有一些大规模计算问题足利用l m e m e t 上空闲 c p u 进行的。 虽然连接在i n t e r n e t 上的计算机带有大量的不确定凶素，但有资料表明， 目前这是解决大规模计算f o q 题的一个重要途径，而且具有广泛的应用。我们研 究的虽然是基于局域网的并行汁算负载平衡，但是其中很多概念和基于i n t e m e t 的并行计算是类似的。 1 3 本文研究的内容及其实现目标 1 3 1 研究内容 本文研究的丰要内容是在局域网上实现并行计算到的负载平衡问题。与理 想的并行计算环境相比，局域网中充满了大量的不确定网素，例如节点的连接 方式、计算性能等。本文具体的研究内容如下： 第1 章绪论。主要分析丁并行计算的螳丰要特点，有关并行计算的研 究现状，还介绍了本文安研究的主要内容和实现h 标。 第2 章模型。重点讨论分析实际网络的特点、前提假设和二层模型。 第3 章负载平衡。首先分析町测量的参数，然后讨论任务划分方法，虽 后重点分析负载平衡的策略。 第4 章模拟程序。首先介绍模拟程序的些基本情况，例如测试实例、 方法等，然后给出实验结果并进行统计分析。 第5 章总结与讨论。本章是对整篇文章的归纳和总结，同时也给出了进 一步研究的建议。 1 3 2 实现目标 评价并行计算算法以及性能的个主要指标是加速比。而本文在研究过程 中使用的指标是时间差r ，即，从出现第1 个空闲节点的刑刻t o 到最后1 个 节点开始空闲的时刻t n 的时间差，如图1 - 1 和图1 - 2 所示。写成公式就是 节点开始空闲的时刻t n 的酬问差，如图1 1 和图l 一2 所示。写成公式就是 a t = r 。一f 。 第1 章绪论 国立天文台和理化研究所组成的联合小组2 0 0 4 年4 月2 6 宣布开始开发的世界 最高速的电子计算机。它使用2 0 0 万个运算处理装置，其运算速度将达到每秒 2 0 0 0 万亿次。 这两个案例都属于集群计算。 在利用连接在广域网( i n t e m e t ) 上的计算机进行，f = 行计算的成功案例中， 比较著名的是破译密码。1 9 9 7 年成功破译d e s 密钥使用了9 6 天，参与计算的 计算机数量达到了7 力- 个。对于破解r s a 密码也有过类似的实验，同样取得了 非常好的效果。现在国内外仍然有一些大规模计算问题是利用i n t e r n e t 上空闲 c p u 进行的。 虽然连接在i n t e r n e t ：的计算机带有大量的不确定因素，但有资料表明， 目日u 这是解决大规模计算问题的一个重要途径，而且具有广泛的应用。我们研 究的虽然是基于局域网的并行计算负载平衡，但是其中很多概念和基y - i n t e r n e t 的并行计算是类似的。 1 3 本文研究的内容及其实现目标 1 3 1 研究内容 本文研究的主要内容是在局域网上实现并行计算时的负载平衡问题。与理 想的并行计算环境相比，局域网中充满了大量的不确定因素，例如节点的连接 方式、计算性能等。本文具体的研究内容如下： 第1 章绪论。主要分析了并行计算的一些主要特点，有关并行计算的研 究现状，还介绍了本文要研究的主要内容和实现目标。 第2 章模型。重点讨论分析实际网络的特点、前提假设和三层模型。 第3 章负载平衡。首先分析可测量的参数，然后讨论任务划分方法，最 后重点分析负载平衡的策略。 第4 章模拟程序。首先介绍模拟程序的一些基本情况，例如测试实例、 方法等，然后给出实验结果并进行统计分析。 第5 章总结与讨论。本章是对整篇文章的归纳和总结，同时也给出了进 一步研究的建议。 1 3 2 实现目标 评价并行计算算法以及性能的个主要指标是加速比。而本文在研究过程 中使用的指标是时间差r ，即，从出现第1 个空闲节点的时刻t o 到最后1 个 节点开始空闲的时刻t n 的时问差，如图1 一l 和图l - 2 所示。写成公式就是 a t = f 。一f o 第1 薹绪论 图1 - 2 实际情况f 的负载平衡 本文要实现的目标就是在含有不确定因素的局域网中进行并行计算时，针 对不同的情况设计对应的负载平衡方法，使得丁在允许的范围之内。 第2 章模掣 第2 章模型 在研究不确定的局域网模型之前，有必要先分析一下理想情况下的并行计 算模型。 2 1 理想的并行计算环境 1 ，f l y r m 系统结构 m i c h a e lf l y n n 按照数据与指令的关系把计算枫体系结构分成s i s d ( 单指 令流单数据流) 、s i m d ( 单指令流多数据流) 、m i s d ( 多指令流单数据流) 和 m i m d ( 多指令流多数据流) ，分别如图2 - 1 ( a ) ( d ) 所示。 s i 撕司堕! i m m i l l _ j 弘 而孓=| m m 2 i l 一 丽竺兰 l m m ，l i 一 ( a ) s i s d( b ) s i m d ( c )m i s d ( d )m l m d 图2 - 1f l y n n 分类法各类机器结构 第2 章模型 在上面的图中，c u 表示控制部件；p u 表示处理部件：m m 表示存储器模 块；i s 表示指令流；d s 表示数据流。 对应于这四种系统结构，传统顺序处理机属于s i s d 。阵列处理机或者并行 处理机通常属于s i m d ，目前多数的并行计算研究都集中在这种结构，而目许 多重要应用的绝大部分都是对数据阵列进行计算，例如密码攻击、天气预报、 油藏、图形图像处理等方面的计算。如果我们将一个最小的待计算数据单位称 为数据单元，那么在这种结构中，完成对一个数据单元的计算并不复杂，也不 会占用太多的时间，但复杂的是整个问题中包含的数掘单元数量相当多，如果 简单地按照s i s d 的方式处理，是绝对不可能在希望的时间内完成的。利用 s i m d 模型，可以把数据单元分布到多个处理器上，然后由这些处理器同时进 行计算。由于引进了更多的处理器，因此可以明显提高计算速度，缩短计算时 间。 m i s d 描述了另外一种复杂的情况：问题中数据单元的数量并不是很多， 但是计算过程相当复杂，需要经历很多步骤才能完成。也就是说，由于完成1 个数据单元的时间比较长，所以会导致整个问题计算时间也比较长。通常使用 流水线结构的计算机解决此类问题，我们也把它称为并行计算。计算时，各个 处理器依次连接，每个处理器只完成整个问题的1 个子问题。当数据单元依次 通过每个处理器之后，问题就得到了解决。由图2 、2 可知，虽然延长了单个数 据单元的计算时间( 增加了处理器间的通信等时间) ，但由于缩短了f 一个数据 单元的等待计算时间，因此也可以缩短整个问题的处理时间。 图2 - 2 流水线的时空图 多处理机系统属于m i m d ，这里就不具体讨论了。 2 负载平衡方法 从图1 2 可以看出，所谓负载平衡就是在计算过程中，尽可能让所有的节 点同时结束计算。这意昧着需要合理分配每个节点上的数据单元( 或者指令) 6 第2 章模颦 数量。 如果在开始计算之前就合理评价了每个节点的综合性能( 主要包括计算性 能、与接收计算结果的服务器之间的网络通信能力等) ，并分配了数据单元( 或 者指令) ，那么这种方式称为静态负载平衡。与动态负载平衡相比，静态负载平 衡算法的突出优点是相对简单，而且节点之间不需要因为平衡负载而通信，所 以网络开销比较小。 如果计算彳i 同的数据单元需要彳i 同的而且是升i 确定的时间，静态负载平衡 就产生了严重的问题：计算之前不论如何划分数据，都有可能出现很大的7 1 ( 如图1 - 2 所示) 。 动态负载平衡很好地解决了这个问题。简单地讲，动态负载平衡就是在计 算过程当中( 或者之后) 及时合理估计每个本节点的状况，然后系统及时调整 相关节点上的负载，以减小a ，。显然，动态负载平衡增加了额外的开销，但 是如果设计合理，那么总的效果将好于静态负载平衡。这样，动态负载平衡就 成为了整个并行计算系统的关键。 3 ，s i m d 和m i s d 类型的并行计算 s 1 m d 和m i s d 是两种截然不同的并行计算。在实现m i s d 时，平衡节点 之间的负载意味着需要“平衡”节点上的指令。但是，在节点之间“平衡”指 令的难度是比较大的。通常的做法是在测试之后使用静态负载平衡的方式均衡 节点之间的负载，而且最好在专用的设备( 例如并行处理机或者专用的集群系 统) 上实现，本文对此不进行研究。 即便同属于s i m d 类型，不同的问题之间也有很大的差距。例如计算天气 预报的问题和密码攻击问题就属于不同的问题。其差别主要在于数据。 在天气预报问题中，数据的数量没有明显变化。如果要预报的是2 4 小时后 的天气状况，假设以1 立方公里的空间为一个计算单位，计算的时间间隔是l 小时，那么任一个计算单位在某时间的状态( 气温、湿度、风速等) ，都是受到 周围计算单位在前个状态影响后的结果。也就是，前1 小时的计算结果将作 为后1 小时的初始条件输入，最终的计算结果将是若干时问间隔之后，某些计 算单位的状态组合( 仍然由气温、湿度、风速等组成) 。在处理这种问题时，各 个计算节点在同步方面、数据传递方面都有比较高的要求，因此最好也在专用 的并行处理机或者专用的集群系统上实现。天体仿真系统的计算也属于此类。 整个过程是一种反复迭代计算的过程。 密码攻击属于另外一种问题。在这种问题中，待计算的数据也有许多，但 是在处理时，由于数据带有明显的连续性，因此不论待计算的数据有多少，都 可以用两个数据向量描述数据区间的上下限。随着计算的进行，待计算数据区 间的数量会有从少到多再到少的变化过程。数据区i 、日j 的大小通常也随着计算的 第2 章模型 进行而变化。如果使用了动态负载平衡技术，那么进行到计算后期，数据区间 将逐渐变小。这类问题的另一个特点是计算结果相对简单。此外，问题中待计 算数据之间也不像前一种问题那样联系紧密。邮递员问题、积分、下棋等问题 都属于此类。 当然，这只是两种比较极端的情况，还有一些问题的待计算数据特征没有 这么明显，在计算时需要单独处理。 4 常见的连接模型 计算节点之问需要进行通信。连接方式直接影响到了节点之间通信的效率。 常见的连接模型有树型、网格型、3 一瓿方体、超立方体等，如图2 3 所示。 图2 - 3 常见的连接模型 这些都属于静态连接。在集中式系统或者分布式系统的多个计算节点之间 经常使用。为了使系统达到多用或者通用的目的，可以使用动态连接网络，例 如，使用总线系统、多级的互连网络、交叉开关网络等。 不论使用那种连接方式，其性能和价格都与具体的设备有关。在集群计算 中也有应用，例如1 2 8 个节点的r w cp c 集群1 1 ( 如图2 - 4 所示) 。 图2 - 4r w cp c 集群i i 第2 章模型 2 2 局域网实现并行计算的特点 随着微型计算机以及网络技术的发展，很多单位都购置了大量的p c 机作 为办公使用，而且铺设了高速的局域网。所有这些都为实现大规模并行计算提 供了可能。前面曾经讨论过，利用局域网完成并行计算可以有两种方式，即搭 建号用的同构局域网和利用现有的异构网络。本文是在后者的基础上展开研究 的。 为了进一步讨论，我们先看看利用单位局域网实现并行计算的特点： ( 1 ) 局域网在目前各单位中得到了广泛的使用。 ( 2 ) 多数参与计算的节点是普通的p c 机。考虑到购买时间和使用目的的 不同，计算机的性能指标和软件方面都存在比较大的差异。 ( 3 ) 作为计算节点的计算机可以随时参与或者退出计算，也可以反复多次 参与和退出计算。 ( 4 ) 在进行计算的同时，可能会有突发性的任务，占用计算机资源。 ( 5 ) 在计算的过程中，网络上可能会出现其他负载。 ( 6 ) 网络设备可能存在差异。 总之，除了为保证计算的顺利进行，而安排了少量专用计算机以完成计算 时的管理工作以外，很多方面都有可能存在着差异和不确定因素。 2 3 前提假设 局域网中的异构特性导致并行计算中的任务调度成为了关键。 对于同构系统，k h o k h a re ta 1 提出了三个调度层次。高层调度也称为作业 调度，它从所有对可用资源要求的已提交作业中选择一个子集。中间层调度响 应系统负载的短期波动，它通过临时挂起或者激活进程来使得系统运行平稳。 低层调度决定某个时间段内分配给处理机的下一个就绪进程。 在异构系统中，除了通常的调度方法之外，还需要增加一个调度层。其功 能是监控任务的执行情况，以便维护系统范围内的负载平衡。 鉴于问题的复杂性，我们只研究其中的- - d 类问题：在含有不确定冈素的 异构局域网上进行并行计算( s i m d 类型) 时的负载平衡。为了能够展丌研究， 我们需要做出如下假设： 假设一：在编写并行计算程序时虽然不能确定参与计算的计算机数量，但 是可以预计，例如大约有几台，2 0 多台，数百台或者更多。从某种意义上讲， 计算节点的数量将直接影响到整个任务的划分方式、负载平衡的算法、待计算 数据的划分粒度等诸多方面。因此需要提前能够预计，而这也是比较容易预计 的。 第2 章模犁 假设- - 假设在进行并行计算的时间内，网络中其他任务的负载很少，而 且节点计算机也是在空闲状态参与计算的。做出这点假设的目的并不是要简化 算法，而是并行计算本身所决定的。一方面，引入并行计算的目的就是提高计 算速度、缩短计算时间，冈此我们有理由暂停一些次要事务，让计算机专门用 于计算；另一方面，计算也会占用定的c p u 资源，因此也不便于进行其他操 作。如果必须要让计算机执行其他操作，可以先退出计算，等完成之后再参与 进来。这个假设的最大好处是可以更准确地估算节点完成剩余任务的时f a j 。网 络方面也有类似的问题。值得强调的是，网络上其他任务的负载对于并行计算 的影响更大：一次突发性的网络通信，可能造成某个或者几个节点传递数据 的延迟，进而往往会调用负载平衡系统，产生不必要的网络开销。 假设三：允许在计算过程中出现突发性的事件，例如网络中来自其他任务 的干扰、计算节点的随机参与和退出、计算节点卜同时运行着其他程序等。从 前面可知，虽然我们不希望，但还是要考虑可能出现的突发性事件。 假设四：计算环境在段时间内相对稳定。即网络结构、网络设备，以及 网络中计算机的位置、计算机的软硬件配置等都不会频繁变化。实际的局域网 通常都具备这个特点。当然，随着无线网络和便携式计算机的普及，目前的确 出现了一些需要频繁移动的用户。我们没有考虑这些用户使用的计算机。 假设五：单位的业务相对稳定。计算机通常是因工作岗位而设定，每个岗 位都带有明显的工作特点。而这个特点也就意味着计算机的忙闲时间符合统计 规律。而且统计的时间越长，忙闲的概率分布越明显。 假设六：单位内部的局域网是使用一个或者多个h u b 连接的星型或者树 型拓扑结构。这种连接方式是目前普遍使用的连接方式。 这六个假设虽然简单，但却是进一步研究异构局域网上负载平衡的基础。 2 4 三层模型 考虑在局域网上实现并行计算时，连接模型是各个计算节点在逻辑上的“连 接”方式，i 面不是物理连接方式。根据前面的假设和局域网的特性，可以知道， 其中的重点在于如何平衡各个计算节点之间的负载，为此，我们定义了两种连 接模型： 节点紧耦合模型：计算节点之间( 至少是相邻的计算节点之间) 需要传递 数据。在这种模型中，动态负载平衡是必须的，尤其到计算的后期，会有大量 的平衡任务需要在节点之间传递。计算节点在模型中的位置相对固定，而且参 与和退出计算都需要调整相关节点之间的关系。环型、网格型、立方体等都属 于此类模型。 节点松耦合模型：任意两个计算节点之间都不需要传递数据。当某个计算 第2 章模型 节点加入或者退出计算时，只需要调整上级节点中记录的数据即r t j ，不需要调 整其他计算节点上的数据。因此，在设计时必须最大限度地独立各计算节点， 减少对其他计算节点的依赖性，即降低节点之问的耦合度。这样，使用树型具 有更现实的意义。 显然，这两种模型都有不足之处：紧耦合模型中的节点间传递数据需要过 多地依赖于其他节点，首先带来的问题是受到不稳定节点的影响，系统的稳定 性会下降；其次，由于网络实际采用的是星型或者树型拓扑结构，因此借助于 多个中间节点传递数据反而会增加网络负担；此外，如果各个节点频繁地加入 和退出计算，那么维护系统的丌销也不容忽视。 松耦合模型的主要问题是也在于节点间的通信。如果节点之间的通信依靠 上一级的服务器实现，那么必然会增加服务器的负担，而且这个负担还主要集 中在统计计算结果的并行计算后期。 鉴于这个问题，最近国内有专家设计了另外一种可扩展的树型结构。在这 种结构中，如果某个计算节点上的负载过多，那么它将自动升级为服务器，然 后将它的负载分配给空闲计算节点，如图2 - 5 所示。 彝耨譬 图2 - 5 可扩展的树型结构 在我们面对的局域网上，这种模型也存在无法解决的缺陷。其中最大的问 题是由于不确定因素造成的开销比较大。例如假设服务器s 上连接了两个计算 节点a 1 和a 2 。当计算节点a 1 上面的负载比较大时，节点b 1 b 8 连接到了 a 1 上并分担了其上的负载，经过一段时间的计算发现节点b 8 上的负载比较火， 需要进一步平衡其上面的负载。假设节点c 1 c 4 连接到了b 8 。最后，d 1 和 d 2 连接到了负载比较重的c 4 卜。但如果此时b 8 和c 4 突然退出了系统，那么 c 1 c 3 、d 1 、d 2 上的计算结果将发送给哪里呢? 我们可以设计更强大的容错 功能解决这种问题，但是不可否认，当退出系统的计算节点距离服务器越近， 连接它的节点越多，由此产生的开销也就越大。 为了更好地解决局域网上含有的不确定因素，我们设计了三层的带有连接 的模型，如图2 - 6 所示。 第2 章模型 犬器 蕊蕊郴黼 幽2 6 三层模型 其巾，最上层是服务器，它负责管理整个项目，维护所有的待计算数据。 在计算之后，负责回收计算结果。在计算过程中，负责分配和平衡中间层上的 负载。通常，一个计算项目只需要配置一个专用的服务器。 中间层是建议使用的组件，由多个中问层节点组成，负责从服务器接收要 完成的数据，然后把这些数据再分配给隶属于它的各个计算节点。在计算的后 期，负责平衡各节点卜的负载。最后，汇总各节点的计算结果并把结果上传给 服务器。中间层另外一个重要的作用是协助服务器完成中间层级的负载平衡。 如果问题的规模比较小，使用的计算节点数量也不多时，完全可以取消中 间层，只使用一台服务器完成所有的任务。但是当问题的规模比较大，而且使 用了比较多的计算节点时，频繁的数据交换将导致服务器成为整个系统的瓶颈， 这时使用多个中间层节点可以比较好地分散负载。此外，受到网络本身的影响， 例如网络中使用了多个v l a n ，也需要将计算节点分组，这时可以把相对独立 的、相互问传输速度比较快的节点作为一组，隶属于同一个中间层节点。为了 保证整个计算顺利进行，把少量性能可靠的计算机专门作为服务器和中间层节 点，而且假设它们在计算过程中不会退出系统。 考虑到底层计算节点之间的差异，在实现时，有必要在中间层节点上使用 中间件技术。 最底层是计算节点。它的主要作用是完成具体的计算，并协助中间层完成 节点缴的负载平衡。 包围中间层节点的虚线框表示任意两个节点之间都町以直接进q ? l t 各时的点 到点通信。包围计算节点的虚线框表示虚线框内的任意两个节点之间都可以直 接进行临时的点到点通信( 在含有大量不确定因素的网络中，这种点到点的通 信是没有保证的，因此在设计算法时，个人认为应该限制使用节点间的通信) 。 此外，为了叙述方便，在相对于上一级讨论时，不妨将下一级的中间层节 点或者计算节点统称为计算单元。 这里采用的“临时的点到点通信”具有f 列优点： ( 1 ) 有效地缩短了传播路径，可以有效地降低网络方面的开销。这是点到 点通信方式的特点。 ( 2 ) 在传递数据时，不会涉及其他任何计算单元，因此比较好地回避了由 于其他计算单元的不确定性带来的问题。 第2 章模型 ( 3 ) 由于采用了临时通信，因此没有改变计算模型的整体结构，即在大部 分时间里，计算单元之间仍然保持比较好的相互独立性。所以比较容易管理。 从整体上看，此模型是树型结构的一种变形。第3 章将从负载平衡的角度 进步讨论。 2 5 分配与请求 在并行计算的模型中，上级向下级发送待计算数据通常有两种方式：一种 方式是“分配接收”和“请求一应答”。简单地讲，前一种方案中，上级先按照 某种方式划分数据，然后将数据主动发送给下级；而后一种方案巾，先南卜级 向上级发送计算请求，然后上级再发送待计算数据。 常规的并行计算模型中，多数采用的是“分配接收”方式。这种方式的主 要特点是：在计算开始之前，各节点均处于等待状态；由服务器把划分好的待 数据以广播或者其它方式分配给每个节点，然后等待接收计算结果。 我们的模型采用以“请求一应答”方案为主的方案。其主要原因是上级不能 确定哪些计算机能够参与计算，哪些不能，因此在接收到“请求计算”消息之 前划分和分配数据将是盲目的、没有任何依据的，也是没有任何意义的。因此， 在计算的初期，我们采用“请求一应答”方案来分配数据。到了计算的后期，为 了配合完成负载平衡，也需要使用其它分配方案在下一级已连接的空闲节点和 忙节点之间平衡数据。 有关数据划分的问题，请参见3 - 2 节。有关的具体算法，请参加3 4 和3 5 节。 第3 章二层模型 第3 章负载平衡 负载平衡是本论文研究的重点，本章首先分析待计算数据的特征，给出相 关定义和前提假设，然后详细分析数据划分和平衡策略，最后在此基础之上给 出“分段双向计算”算法。 3 1 关于待计算数据 为了叙述和后面研究的方便，本文针对待计算的数据做出如卜 定义： 定义一：待计算的数据可以分成若干更小的数据单元。不可继续划分的数 据单元称为原子数据单，二，用带下标的小写字母d 表示。 定义二： 由全部待汁算数据组成的有序序列称为源数据序列，用s d 表示 s d = d o ，d 。，破，九一。 其中m 是s d 中包含的原子数据单元个数。 定义三：由s d 中多个连续原予数据单元组成的序列称为源数据序列的一 个子序列，简称为源数据子序列，用带下标的字母s 表示，或者使用大写字母 a ，b ，c 表示。我们将子序列中包含原子数据单元的个数称为该子序列的长 度。 定义四：所含原子数据单元个数为0 的源数据予序列称为空序列。空序列 用庐表示。 定义五：如果s d 和一组s i ( i = o ，1 ，2 ，m 1 ) 同时满足 ( 1 ) s 矿 ( 2 ) s d = s o u s l u s ：u u s 。一l ( 3 ) 对于任意的i 和j ，如果有0 i 掰一l ，0 j m 一1 ，且i j ，都有 s ，n s = 则称这组s i 为s d 的个划分，记为 ，或 者简写为 。将生成s d 一个划分的过程称为划分s d 。 如果有 ，那么根据前面的定义，为了更好 地保证s d 有序，可以做出下面的规定。 规定一：s 。有序。 规定二：s i 中的元素有序。 定义六： 如果a 是s d 的一个非空子序列，且有a = d 。，d 。l ，d o ) ，则 分别称m 和n 是a 的下限和上限。 1 4 第3 章三层模型 定理一：如果a ，b ，c 是s 。中个连续的非空了序列，那么可以山b 计 算出a 的上限和c 的f 限。 按照前面的定义和规定，可以很容易证明此定理，这罩证明从略。 从前面的讨论町以看出，在我们研究的s i m d 模型中，不论是数据紧耦合 的天气预报系统，还是松耦合的密码攻击，进行动态负载平衡的过程也就是对 待计算数据进行重新划分和重新分配的过稗。 当然，根据问题的不同，按照这种模型定义待计算数据的具体方法也会有 很大的差距。对于比较简单的问题，例如计算密码攻击、邮递员问题等都可以 直接套用该定义来划分待计算数据。这种问题的特点是在计算过程中，如果不 考虑效率的话，计算节点之问完全可以不需要进行数据交换。 比这种问题再复杂一些：如果节点需要在计算过程中不断进行数据交换， 那么经过简单调整，也可以套用此模型来完成计算。例如预测太空中天体的运 动，n 个天体相互之问都存在万有引力，每个天体都受到来自其他天体的n 1 个力的共同影响，从而会在下个时刻改变位置。根据万有引力定理，这种位置 的改变必然会造成n 个天体之间的作用力发生变化，这需要重新计算，以得到 新的位置。因此在模拟时，必须每隔一段时间就更新一次各个天体的位置。如 果第i 个节点负责维护m 个天体的位置，那么把这n 个天体编号，并按照编号 排列成个序列，就可以按照上面的定义来划分数据、平衡负载了。 对于很难划分数据的问题，通常也不太适合采用并行计算，我们对此不予 考虑。 3 2 数据划分粒度 并行计算前期的数据划分粒度和后期的负载平衡同样重要。通常，所谓粒 度的粗细通常指的是一次传递给下一级计算单元( 可能是中间层节点或者是计 算节点) 的源数据子序列中包含原子数据单元的个数。个数比较多的称为粗粒 度，相反，个数比较少的称为细粒度。 使用粗粒度的好处是可以一次发送更多的原子数据单元，进而可以有效地 减少分配数据的次数，减少了因发送数据造成的开销，而且计算单元能够更稳 定地进行计算。当各个计算单元能够平稳高效运行时，粗粒度能够取得非常好 的效果。但受到各种不确定因素的影响，数据粒度越大，我们对计算单元完成 任务的估计时间和实际完成任务时间的差异有可能会越大( 这个差异视问题而 定，在有的计算问题中，这种差异是不确定的。例如，在天气预报的计算中， 如果原了数据单元是l 立方公里，那么不论数据粒度是粗还是细，估计时间和 实际使用时间都不会有较大的差异；而在邮递员或者对弈问题中，由丁在计算 过程中涉及了剪枝，所以数据粒度越大，两个时间之间的差异也就越大) 。这时 第3 章= 层模型 往往需要使用负载平衡彳能比较好地解决此问题。而负载平衡又增加了计算后 期的网络等方面的丌销。另外，考虑到计算节点的随机退出，单纯的粗粒度将 面临数据丢失的危险。具体地讲，受到不