第17 卷第4 期2007 年4 月
COMPU TER TECHNOLO GY AND DEVELOPMEN T
Vol. 17 No. 4
熊泽时，李代平
(广东工业大学计算机学院, 广东广州510060)
摘要：首先简单介绍了基于PVM 的网络并行计算环境。接着重点讨论了任务分配方法和负载平衡问题。通过分析静态任务分配方法中存在的不足，提出了以计算能力的大小来动态分配任务的方法，避免了因个别计算机的低性能而影响了整个并行计算系统的加速比。实验表明这种策略实现简单，并且具有很好的并行效果。
关键词：网络并行计算; PVM ；任务分配；负载平衡
中图分类号: T P393 文献标识码:A 文章编号:1673 - 629 X(2007) 04 - 0175 - 03
An Effective Dynamic Task Distributed Method
XION G Ze2shi ,L I Dai2ping
( Faculty of Computer , Guangdong University of Technology , Guangzhou 510060 ,China)
Abstract:First introduces an network parallel computing based on PVM platf orm , and the methods of parallel programming based on it .
Then puts the f ocus on the probl em of tasks distributed and loading balancing. Give a new dynamic t ask distributed method , which tasks distribute based on the perf ormance of computers. It works well in the experiments.
Ke y words :network parallel computing ; PVM ;tasks distributed ;loading balancing
0 引言
网络并行计算是利用一组由网
络互连的计算机同时解决一个大问
题的过程。由于高性能PC、工作站
的普及和高速网络的成熟，一组互连
计算机的并行计算能力可以超越一
台高性能计算机，能满足人们对高速
度、低成本计算技术的需求, 是继
MPP( Massi vely Parallel Processors) 之
后，现代并行计算的又一主要发展趋
势[ 1 ] 。其中PVM 是应用较广泛的并
行程序开发软件, 它具有系统规模
小、成熟度高、通用性强等优点。
PVM 的基本概念是并行虚拟机, 它
将由通用网络连接起来的多台同构的或者是异构的计算机虚拟成一个大的并行计算机。
图1 就是一个由三台计算机构成的并行计算环境。
收稿日期:2006 - 07 - 02
图1 由三台机器组成的虚拟机
1 基于PVM 的并行程序设计
PVM 是一个能用来进行并行程序设计的软件环境，它能把一个由计算机构成的网络虚拟成一个大的并行计算机来使用[ 1 ] 。PVM 是基于消息传递的并行通讯库, 可让用户进行基于消息传递的并行程序设[ 2 ] 十八和谐综合区基金项目：广西自然科学基金资助项目(桂科自0229009)
作者简介：熊泽时(1981 - ) ，男，广东博罗人，硕士研究生，研究方向为网络并行计算；李代平，教授，研究方向为网络并行计算。计。用户必须通过显式地发送和接收信息来实现计算机间的数据交换，因为消息传递的开销比较大，所以PVM 主要用来开发大粒度的并行。
·176 ·计算机技术与发展第17 卷
基于PVM 的并行程序设计采用Master/ Slave 模式。它的并行计算结构由一个主计算机Master 和若干从计算机Slave 组成,Master 维持全局数据结构并负责任务划分，负责用户界面，接受任务，启动计算
人体气化和回收结果。而每个Slave 负责完成子任务计算，包括局部初始化，并行计算和计算机间的数据通信，并把结果返回到Master 。它们都是操作系统的进程。进程一旦登录PVM ，就成为受PVM 控制的任务。每个计算机负责计算分配给它的任务[ 3 ] 。主计算机和从计算机间的关系如图2 所示。
六氯苯
图2 并行计算结构中计算机间的关系示意图
Master 依据问题规模和并行程度, 启动若干个Slave ，开始计算，并对Slave 进行初始化。Slave 从初始化信息中识别自己，接收保存任务数据，再进行计算。每次计算后，各Slave 需要相互交换边界数据，以保证下一次计算使用新值。最后,Slave 通知Master 计算完成，并检验结果。Master 回收结果并输出。
2 任务分配和负载平衡
负载平衡(Load Balancing) 是一种能够通过恰当的任务分配来进行资源优化利用，实施并行计算，提高计算机吞吐量和缩短任务响应时间的技术[ 2 ] 。PVM 对任务分配和负载平衡方面没有提供很多的支持，这个工作留给了程序设计员[ 4 ] 。基于PVM 的并行程序采用Master/ Slave 模式。在这种模式中, 任务分配在Master 程序块中实现。首先将任务按照一定的规则进行划分，然后根据选定的分配策略将子任务分配到各Slave 中去。Sl ave 根据进程ID 识别自己的任务，然后对自己的子任务进行计算，再将计算结果返回给Mas2 ter 。Master 将各Slave 返回的结果再组合成最终的结果。
一般的任务分配方法有两种: 静态任务分配和动态任务分配。下面分别进行讨论。
2 . 1 静态任务分配
静态分配方法是在程序运行前就已经决定好任务的划分和分配。二次均分法是最常用的静态任务分配方法。这种方法是将所有的总任务首先按照参与计算的机器数量进行均分，然后将不能整除的任务数再一次地分配给各台计算机，这样每个结点最多只相差一个子任务[ 4 ] 。
这种方法的思想和实现代码都比较简单，适用于一般并行计算的环境。因为一般单位购买计算机都是一批购买，各台机子在处理能力方面相差不大，所以适合用二次均分法进行任务的划分和分配。但是这种方法的缺点还是显而易见的，即如果参与计算的各结点机能力相差较大，则计算时间遵循木桶原则，取决于最慢那台计算机的处理时间，这样使得并行数据处理的加速比大大降低。
2 . 2 动态任务分配
当计算机间的计算性能差别较大时，采用静态分配方法的效果就不理想了，这时就要考虑采用动态分配方法[ 5 ] 。动态分配方法是在程序运行过程中才进行任务划分和分配的[ 2 ] 。理想的动态分配方法是能够根据不同的计算机的处理能力进行任务分配。处理能力强的机器多分配任务，而处理能力弱的则相应少分配任务。Master 将任务数按性能比值进行分配。这样就可以更好地做到负载均衡，提高处
理效率。在这里，如何得到各计算机的处理能力是一个关键点[ 5 ]。可以考虑两种方案获得计算机处理能力：第一种是调用PVM 库函数。PVM 控制平台上有一个SPEED 的参数，这个就是代表该计算机当前的性能情况, 通过调用pvm - config() 函数就可以返回这个SPEED 参数; 另一种方法是通过向各计算机分发相同的单位任务，测得各计算机的任务计算时间，然后根据相应的公式计算出计算机的相对性能。显然第一种方式使用起来是比较方便的，然而从实验中证明这样得到的性能参数并不是很准确。当计算机空载时, 性能参数都是1000 , 只有当计算机满载时，参数才会少于1000 。当计算机间存在较大的性能差异时，这个参数就没有区分度了, 对进行合理的任务分配价值就不大。这种方法更适合于负载平衡中任务再分配的情况。
因此，采用后一种方法获取系统中各计算机的性能。为了得到各台计算机的性能参数，采用一种二次并行的策略。二次并行策略分两步进行: 第一次并行各台机器计算相同的单位任务，然后取得每台机器的任务计算时间，按计算时间衡量各台计算机的处理能力；第二次并行就按第一次并行时取得的性能参数来分配任务数，按性能的大小来动态分配任务。
首先从Master 机启动一个并行程序Client ，计算一些单位任务, Client 测出各Sl ave 机的完成时间; 然后返回给Master , Master 再根据完成时间计算各台机器的相对处理能力。这是第一次并行。
第4 期熊泽时等：一种有效的动态任务分配方法·177 ·
n
speed[ i ] = w 3 ∑c time[ i ]/ c time[ i ] ( 1)
i = 0
i = 0 ,1 ,2 ,3 ,
其中, w 是一个经验权系数, c time[ i ] 为各台机的单位
任务实际计算时间。日本人眼里的中国
第二次并行就在第一次的基础上进行，下面给出
二次并行的算法。
Master 算法:
1) 初始化。向各Slave 机发送初始化消息。
cdkl5综合症
2) 接收各计算机的消息, t rue 则继续,false
示出错，退出。
3) 接收各计算机的任务计算时间, 存
c time[ i ] 数组中。
4) 根据各计算机的计算时间c time[ i ] , 得到相对
性能参数speed[ i ] 。
5) 广播任务数据, 并进行任务划分, 根据speed[ i ]
进行任务分配。
6) 接收各Slave 机返回的结果。
7) 综合得出最终结果，并保存显示。
8) 退出。
Slave 算法:
(1) 接收初始化消息。
(2) 发送确认信息回Master 。
(3) 计算单位任务，并测得任务计算时间。
(4) 将任务计算时间返回给Master 。
(5) 接收任务数据，根据进程的ID 识别出计算任务，进行计算。
(6) 返回计算结果到Master 。
(7) 退出。
在Master 机器和Sl ave 机器的第一次交互过程中,Client 通过PVM 的消息传递方式向Master 传送各台计算机的性能参数, Master 以每台机的名称存储在本地数据库中，作为以后任务分配的性能依据。然后Master 机根据性能参数进行任务分配，再将子任务分配给Slave 机子，由Sl ave 程序进行计算。计算完后将结果返回的同时，也将这次的计算时间一同发送回来, Master 再根据公式计算出新的性能参数，并且更新数据库中的数据。然后再综合得到最后结果并显示出来。
n
speed[ i ] = p[ i ] 3 w 3 ∑c time[ i ]/ c time[ i ]( 2)
i = 0
i = 0 ,1 ,2 ,3 ,
其中p[ i ] 是各台机器的分配的任务数量。因为这次分配给各台机器的计算任务不一样,
所
以要增加一个任务数p[ i ] 来计算实际计算性能。3 实验和效果评价
分别用静态任务分配方法和动态任务分配方法进
行了实验, 进行大型矩阵相乘运算。分别对300 3
300 ,600 3 600 , 900 3 900 的矩阵进行浮点数相乘运算。并行计算环境由三台计算机组成, 运行在Wi n2 dows XP 的环境下。一台台式机的基本配置是P4 1 .
5 G ,128M 内存; 两台笔记本电脑的配置是奔腾M 1 .
5 G ,512M 内存和赛扬M 1 . 4 G ,256M 内存。首先采
记下了900 3 900 矩阵运算时三台计算机组成的
并行计算环境的每台计算机的计算时间, 分别为
5093ms ,5488ms ,8392ms。最后整个并行计算时间当然是最后一个任务的完成时间，即8392ms 。第三台计算机的计算能力跟前两台有较大的差别，内存不够大, 是整个系统的瓶颈。如果还是分配相同的计算任务, 那么整个并行计算的性能就降低了。
下面再采用动态的任务分配方法进行实验。实验结果见表2 。
表2 动态任务分配方法的实验结果
从表2 和表1 的比较中可以看出，动态分配方法
的加速比都得到了不同程度的提高。同样地，还是记下三台计算机组成的并行计算环境进行900 3 900 矩阵运算的每台计算机的计算时间, 分别为5447ms , 6239ms ,6328ms。从这个结果看来, 动态分配方法的并行效果比较理想，各台机的计算时间相差不大，最后整个系统的加速比也得到了很大的提高。
4 结束语
文中简单介绍了基于PVM 的网络并行计算环境。重点讨论了任务分配方法和负载平衡问题，分别讨论了静态任务分配方法和动态任务分配方法。通过分析静态任务分配方法中存在的不足，提出了以计算机的计算能力的大小来动态分配任务的策略，避免了因个别计算机的低性能而影响了整个并行计算系统的
(下转第181 页)
第 4 期
蒋卫星等 : W eb 搜索算法研究综述 ·181 ·
4 结束语
当前的 Web 搜索算法已经从 Y ahoo 的第一代文 本搜索算法发展到第二代以 PageRank 和 HITS 为
代 表基于链接分析的搜索算法。Web 搜索算法仍然是 一个值得深入研究的课题 ，这个领域仍有许多需要解 决的问题 : (1) 在综合利用各种算法和技术的基础上 , 如何在查询的准确性 、查全率和实时响应性能方面达 到平衡将是一个需综合考虑的问题 ; ( 2) 如何防止欺 骗和垃圾链接对页面排序的影响也是非常重要的问 题 ; (3) 面对用户的不同需求 ，提供个性化的 Web 搜索 算法也正在变得越来越重要 ，同时 Web 搜索算法也将 面对多样性的问题 ; ( 4) 如何利用网上社区发现技术 从而在一定程度上改善 Web 搜索算法返回页面的准 确度和查全率也将是非常关键的问题; ( 5) 语义 Web 的发展将有可能推动 Web 搜索算法朝着新一代的方 向发展。
剧参考文献 :
[ 1 ] Page L , B rin S , Motwani R , et al . The PageRank citation
ranking: Bringing order to the Web [ R ] . Database Grou p , Stanford Universit y ,1998 .
[ 2 ] 宋聚平 , 王永成 , 尹中航 , 等. 对网页 PageRank 算法的改
进[J ] . 上海交通大学学报 ,2003 ,37 (3) :397 - 400 . [ 3 ] Xing W , Ghorbani A. Weighted PageRank Algorithm[ C] ∥
2nd Annual C onference on C ommu nication Networks and Ser 2 vices Research. Fredericton , N.
B. , Canada : IEEE Compu ter Society ,2004 :305 - 314 .
[ 4 ] C ai Deng , He Xiaofei , Wen Ji - Rong , et al . Block - level
Link Analysis [ C ] ∥ In Proc. of the SI GIR ’04 Conf . Sheffield , United Kingdom : AC M Press , 2004 :440 - 447 . [ 5 ] Bradley J T , de Jager D V , Knottenbelt W J , et al . Hyper 2
graph Partitioning for Faster Parallel PageRank Computation [ C] ∥EPEW ’05 . Versailles , France : [ s. n. ] , 2005 : 155 - 171 .
[ 6 ] 李 凯 , 赫枫龄 , 左万利. PageRank - Pro : 一种改进的网 页排序算法[J ] . 吉林大学学报 ：理学版 , 2003 ,41 ( 2) :175
- 179 .
[ 7 ] Xue G u i - Rong , Yang Qiang , Zeng Hua - J un ,et al . E xploit 2
ing the Hierarchical Structure for Link Anal ysis[ C] ∥Proceed 2 ings of the 2005 ACM SIGIR Conference. Salvador , Brazil : [ s. n. ] , 2005 :186 - 193 .
[ 8 ] Kamvar S D , Haveliwala T H , Manning C D ,et al . Exploit 2
ing the Block Structure of the Web for C omputing PageRank [ R] . US :Stanford Universit y , 2003 .
[9 ] Wu Jie , Aberer K. Using a Layered Markov Mod el for De 2
centralized Web Ranking[ R ] . Lausanne : Swiss Federal Insti 2 tute of Technology , 2004 .
[ 10 ] Wang Yuan , DeWitt D J . C ompu ting PageRank in a Dis 2
tributed Internet Search System[ C] ∥Proceedings of the 30th VLDB Conference. Toronto , C anada : [ s. n. ] , 2004 : 420 - 431 .
[ 11 ] d e Jager D. PageRank : Three Distributed Alg orithms [ D ] .
London: the Imperial C ollege of Science , Technology and Medicine ,Universit y of London ,2004 .
[ 12 ] Gleich D , Zhukov L ,Berkhin P. Fast Parallel Pa geR ank : A
Linear System Approach [ C] ∥WWW2005 . Chiba , Japan : [ s. n. ] ,2005 :1 - 8 .
[ 13 ] 陈再良 , 凌 力 , 周 强. dPageRank ———一种改进的分布
式 PageRank 算法[J ] . 计算机应用 ,2006 ,26 (1) :21 - 24 . [ 14 ] B harat K. Hilltop : A Search Engine based on Expert Docu 2
ments [ EB/ OL ] . 2001 . http :/ / www. cs. toronto. edu/ 2 georgem/ hilltop/ , University of Toronto.
[15 ] Haveliwala T H. Topic - Sensitive PageRank [ C] ∥In Pro 2
ceedings of the eleventh international conference on World Wid e Web. [ s. l . ] :AC M Press ,2002 :517 - 526 .
[ 16 ] Lempel R , Moran S. SALSA : The Stochastic Approach for
Link - Structure Analysis [ J ] . AC M Transactions on Infor 2 mation Systems ,2001 ,19 (2) :131 - 160 .
[17 ] Kleinber g J . Au thoritative sources in a hyperlinked environ 2
ment[ C] ∥Proceedings of the 9th ACM - SIAM Symposium on Discrete Algorithms. New Orleans : ACM Press , 1997 : 668 - 677 .
[ 18 ] 石 晶 , 龚震宇 , 裘杭萍 ，等. 一种更稳定的链接分析算法 ———子空间 HITS 算法[J ] . 吉林大学学报 ：理学版 ,2003 ,
41 (1) :49 - 53 .
[ 19 ] 宋建康 , 张礼平. Web 结构挖掘算法探讨[J ] . 华东理工大 学学报 , 2003 ,29 (5) :537 - 540 .
(上接第 177 页) 加速比 。最后还分别采用两种方法进行了并行计算实 验 ，实验结果表明这种以计算机的实际计算能力的大 小来动态分配任务的策略实现比较简单 ，并且具有很 好的并行效果。
参考文献 :
[ 1 ] 孙家昶 ，张林波 , 迟学斌 , 等. 网络并行计算与分布式编程
环境[ M] . 北京 ：科学出版社 ,1996 .
[ 2 ] Wilkinson B ,Allen M. 并行程序设计[ M] . 陆鑫达 等译. 北
京 ：机械工业出版社 ,2001 .
[ 3 ] 张信一 ，李代平 ，章 文. 基于 Win32 平台上的 PVM 并行
程序设计[J ] . 计算机应用研究 2004 (5) :102 - 104 . [ 4 ] 张建军 ，蒋廷耀 ，郭志鑫. PVM 中动态负载平衡的设计和
实现[J ] . 计算机工程 ,2005 (7) :63 - 64 .
[ 5 ] 张信一 ，李代平 ，罗伟刚. 并行程序开发平台的可视化实
现[J ] . 计算机应用研究 ,2004 (11) :266 - 269 .
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议