第４卷第４期福建工程学院学报
』！坠墨型堂！山ｉ！！旦！业！望ｉ！ｚ丛里！！呈！！！艇
ｖ０１．４Ｎｏ．４
三Ｑ堕生！星
文章编号：１６７２—４３４８（２００６｝０４—０４４８—０３
垒竖：兰咝
ＭＰＩＣＨ在ＰＣ集群系统中的应用
徐巍，李玉榕
（福州大学电气工程与自动化学院，福建福州３５０００２）
摘要：采用ＭＰＩＣＨ并行技术，建立了基于Ｐｃ局域网平台的并行集群系统，并通过ＶＣ＋＋６．０调用消
息传递库ＭＰＩ函数编写并行遗传算法，完成了相关并行计算实例。计算结果表明：在现有并行集群系统下能有效地利用现有计算机资源，大幅度提高计算效率，并可获得可观的加速比，为一些复杂问题的求解提供了可行方案。
关键词：并行计算；并行遗传算法；ＭＰＩＣＨ；ＭＰＩ中图分类号：ＴＰ３９３：０２４２
文献标识码：Ａ
ＡｐｐｌｉｃａｔｉｏｎｏｆＭＰＩＣＨｉｎｔｈｅＰＣｃｌｕｓｔｅｒｓｙｓｔｅｍ
ＸＵＷｅｉ，ＬＩＹｕｒｏｎｇ
（ＣｏｌｌｅｇｅｏｆＥｌｅｃｔｒｉｃａｌＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｕｔｏｍａｔｉｏｎ，ＦｕｚｈｏｕＵｎｉｖｅｒｓｉｔｙ，Ｆｕｚｈｏｕ３５０００２，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ａｐａｒａｌｌｅｌｃｌｕｓｔｅｒｓｙｓｔｅｍｂａｓｅｄ
ｏｎ
ＰＣｌｏｃａｌａｒｅａｎｅｔｗｏｒｋｐｌａｔｆｏｒｍＷａｓ
ｓｅｔ
ｕｐ
ｂｙＭＰＩＣＨｓｐｅｃｉｆｉ。
ｔｏ
ｃａｔｉｏｎ．ＳｏｍｅｃｏｒｒｅｓｐｏｎｄｉｎｇｅｘａｍｐｌｅｓｗｅｒｅａｃｈｉｅｖｅｄｂｙｕｓｉｎｇＶＣ＋＋６．０ｃａｌｌｉｎｇＭＰＩｆｕｎｃｔｉｏｎ
ｐｒｏｇｒａｍ
ｄｅｓｉｇｎ
ａ
ｆｏｒｐａｒａｌｌｅｌｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ．＇Ｉｌａｅｒｅｓｕｌｔｓｈｏｗｓｔｈａｔｔｈｅｃｏｍｐｕｔｉｎｇｒｅｓｏｕｒｃｅｉｓｂｅｔｔｅｒｕｔｉｌｉｚｅｄａｎｄ
ａ
ｔｈｅｃｏｍｐｕｔｉｎｇｅｆｆｉｃｉｅｎｃｙｉｓｓｉｇｎｉｆｉｃａｎｔｌｙｉｍｐｒｏｖｅｄｖｉａｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇｗｉｔｈ
ｈｉｇｈｅｒｃｏｍｐｕｔｉｎｇｓｐｅｅｄｆｏｒ
ｔｈｅｐａｒａｌｌｅｌｃｌｕｓｔｅｒｓｙｓｔｅｍ．Ｆｅａｓｉｂｌｅｓｃｈｅｍｅｓａｒｅｐｒｏｖｉｄｅｄｆｏｒｔｈｅｓｏｌｕｔｉｏｎｏｆｓｏｍｅｃｏｍｐｌｉｃａｔｅｄｐｒｏｂｌｅｍｓ．Ｋｅｙｗｏｒｄｓ：ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ；ｐａｒａｌｌｅｌｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ；ＭＰＩＣＨ；ＭＰＩ（ｍｅｓｓａｇｅｐａｓｓｉｎｇ
ｉｎｔｅｒｆａｃｅ）
Ｏ
引言
随着工作站和ＰＣ机性能的提高和网络技术
优点…，且网络中的计算机资源具有复用性，网络上的处理机既可作为并行系统的一个处理单元来使用，又可作为一个普通的计算系统来使用，因而很有研究与利用价值。基于网络的并行遗传算法研究和应用目前刚刚起步，国内在这方面的研究文献几乎没有，国外所做的研究也相对较少。是近年来国际上并行处理的一个重要研究方向。
的发展，集群系统（Ｃｌｕｓｔｅｒ）是近年来人们开始研究的一种新计算机系统，也称网络并行计算系统，是利用高速通讯网络将一组高性能工作站或ＰＣ机连接起来而形成的一种分布式并行计算系统。它通常采用消息传递（ＭｅｓｓａｇｅＰａｓｓｉｎｇ）的方式进行并行计算，这种计算系统较适合于粗粒度的并行处理问题，利用局域网将这些同构或异构的计算系统连接起来，通过相应的并行计算支撑软件（例如消息传递程序库和并行程序开发环境）作为平台，就可以构成一个进行网络并行计算的机群系统。与昂贵的高性能并行计算机相比，这种网络并行具有投资少，易实现，见效快，灵活性强等
收稿１３期：２００６—０７—０４
基金项目：福建省教育厅资助项目（ＪＢ０４００２）
１并行遗传算法
１．１遗传算法的并行性分析
遗传算法的并行设计可从２个方面分析：（１）遗传算法的内在并行
遗传算法本身适
合大规模并行，可以把初始种群分为若干子种群，每个子种群交给一台计算机单独进化，等进化结束后进行通讯比较，选择最佳个体，适合在各种并
第一作者简介：徐巍（１９８１一），男（汉），上海人，硕士研究生，研究方向：基于Ｉｎｔｅｒａｃｔ的并行分布式进化计算研究
万方数据
第４期徐巍，等：ＭＰＩＣＨ在ＰＣ集群系统中的应用
４４９
行机或分布式系统中进行并行处理。
（２）遗传算法的隐含并行遗传算法采用种群方式组织搜索，可以同时搜索解空间中的多个区域，并相互交流信息。这种搜索方式使得它虽然每次只执行与种群规模Ⅳ成比例的计算，而实质上进行了大约Ｄ（，ｖ３）次有效搜索，这就使得遗传算法能以较少的计算获得较大的受益。１．２遗传算法的并行化
遗传算法的固有并行性可通过不同的方法和途径去挖掘和实现，从而产生了不同类型的并行化方法。并行遗传算法大体可分为３种计算拓扑模式乜】：主从式、粗粒度和细粒度模式。
（１）主从式
主从式模型（见图１）将选择、交
叉、变异等全局操作交给主处理器串行执行，而将适应度评估等局部操作交给从处理器网络并行执行。主从式模型对计算机体系结构没有严格要求，适合运行在共享存储和分布式存储的并行计算机上。
图１主从式模型
Ｆｉｇ．１
Ｍａｓｔｅｒ－ｓｌａｖｅｍｏｄｅｌ
（２）粗粒度式粗粒度模型又称分布式模型或岛屿模型，是适应性最强和应用最广的并行化模型（见图２）。粗粒度模型是将随机生成的初始群体依处理器个数分割成若干个子群体。各个子群体在不同的处理器上相互独立地并发执行进化操作。为了防止群体早熟，每经过一定的进化代数，各子群体间会交换部分个体以引入其他子群体的优秀基因，丰富各子群体的多样性，防止早熟收敛的发生。粗粒度模型的通讯开销较小，可获得接近线性的加速比，而且非常适合运行在通讯带宽较低的集群系统上¨】。
图２岛屿模型
ｒｉｇ．２
Ｉｓｌａｎｄ－ｂａｓｏｄｍｏｄｅｌ
万方数据
（３）细粒度式细粒度模型又称领域模型、扩散模型或细胞模型（见图３），当并行计算机系
统的规模很大，处理器多到可以与染色体一一对应（理想情况），即每一处理器上驻扎一个染色体时，可以采用细粒度模型的并行进化算法。子群体之间具有极强的通讯能力，便于优良解传播到整个群体。全局选择被领域选择取代，对于每个染色体，进化操作都只在其所处的处理器及其领域中进行，这样的并行模型元需或只需很少的全局控制，在最大的限度上发挥了ＧＡ的并行潜力。由于对处理器数量的要求很高，所以细粒度模型的应用范围不广，一般只运行于大规模的ＳＩＭＤ
（ＳｉｎｇｌｅＩｎｓｔｒｕｃｔｉｏｎ，ＭｕｌｔｉｐｌｅＤａｔａ）并行计算机。
图３领域梗型
ｒｉｇ．３
Ｃｅｌｌｕｌａｒｍｏｄｅｌ
目前，以粗粒度并行遗传算法模型最为流行，因为一是其实现较容易，只需在串行ＧＡ中增加迁移子例程，在并行计算机的节点上各自运行一个副本，并定期交换几个个体即可；二是在没有并行计算机时，也可在网络或单机系统上模拟实现。
２算法的程序设计及实现
２．１
函数优化问题的描述
函数优化可以描述为极大值或极小值问题：
ｍａｘｆ（髫）或ｍｉｎｆ（ｘ）。
，∈Ｓ
，ｅ
Ｊ
这里：ＳＣ
Ｒ“称搜索空间；，：Ｓ—Ｒ称目标
函数。
２．２算法的实现平台
本文的并行遗传算法采用粗粒度模式，其拓扑连接模式采用单向环结构（见图４），既能保证优良基因在群体问的扩散，又较好地隔离了子群体，保护了群体间的多样性，虽然收敛速度慢，但
