并行遗传算法收敛性分析及优化

Convergence analysis and optimization of Parallel Genetic Algorithm

张旭风 王纪川 牟莉

针对并行遗传算法（parallel genetic algorithms，PGA）容易出现收敛过快和陷入局部最优解的问题，综合多种不同进化策略遗传算法之所长，设计了一种混合的粗粒度并行遗传算法。该算法由多个独立的子群体组成，各个子群体并行的、独立的、按照不同的遗传进化策略进化，每隔一定的时间，在子群体之间进行最优个体的迁移，促进群体的共同进化，并抑制群体早熟。在PVM环境下，用该算法实现函数优化问题，仿真实验数据表明了其有效性．[著者文摘]

Aim at the problems of which Parallel Genetic Algorithms is very easy convergence and getting in the local best individual, colligate the strongpoint of manifold genetic algorithms which ttas different evolutionary strategy, a novel Parallel Hybrid Genetic Algorithm is proposed in this paper. It is compose of multi-population. Diferent population evolves independently with different genetic evolutionary strategy. It migrates the best individual between different population termly to accelerate all population together evolving and restrain the population premature phenomena. Under PVM environment, it has been proved that the algorithm is effective by the experiment of settling the question of function optimize.[著者文摘]

遥感图像K—Means并行算法研究

Research on K-Means Clustering Parallel Algorithm of Remote Sensing Image

蒋利顺 刘定生

K—Means算法是对遥感图像在没有先验知识情况下进行无监督分类的重要算法之一，在遥感影像的分析中得到了广泛的应用。针对K-Means算法复杂，处理过程中计算时间长的缺点，人们试图寻求快速的并行处理方式。在这种并行化的探索过程中，由于K-Means算法独特的流程结构，使其并行化处理方式难以顺利进行。本文在分析K-Means算法特点的基础上，对其并行化方式进行了深入的研究。针对K—Means算法并行化在处理速度和分类精度方面存在的问题，提出了一种基于分块逼近的算法并行模型，可兼顾并行效率和分类精度之间的综合要求，实现某种精度可控的并行处理。最后，根据实验结果讨论并提出了迭代算法并行化的有效途径。

基于区域平均执行时间和数据依赖信息的可能并行区域识别

Identifying Possibly Parallel regions Using Average Execution Time of Regions and Data Dependence Profiling

张超 王蕾 向晓娅 冯晓兵

随着多核处理器逐渐成为处理器发展的新趋势,为了持续提高程序性能,必须并行执行应用程序.传统的自动并行技术能够很好地并行科学计算应用中的规则循环,但对于含有大量函数调用和指针引用的不规则程序,目前还不能有效地对其实施并行.针对这一现状,文中提出了基于区域平均执行时间和数据依赖信息的可能并行区域识别方法来对一些不规则程序实施高效并行,主要贡献如下：（1）自动识别程序中的多种并行性,不仅包括传统并行性分析中的循环迭代间的细粒度并行性,而且也包括传统并行性分析尚不能有效处理的循环体和函数调用点间的粗粒度并行性.对于程序中蕴含的众多并行性,文中基于区域平均执行时间实施收益分析来选择合适的并行区域实施并行;（2）自动识别可能并行区域间数据依赖关系的数量、类型以及导致数据依赖关系的程序变量.基于文中的分析结果,作者使用面向行为的投机并行系统（behavior oriented parallelism）对SPEC2006中的4个测试用例实现了并行化.并行化后的程序在Intel和AMD多核处理器上分别得到了300%和260%的平均性能加速.

并行测试任务可并行性分析与应用

Research on Parallelizability of Parallel Test Tasks

胡雷刚 肖明清 王磊

针对并行测试系统中不同UUT测试任务组的并行测试效率提高存在差异的现象，提出了测试任务的可并行性概念，以描述测试任务在并行测试过程中的固有属性；首先根据测试任务组的并行测试效率不同的现象，提出了测试任务可并行性的概念；然后给出了衡量可并行性的可并行度指标，用以定量地指导并行测试系统开发过程中仪器资源的配置；最后通过应用实例验证了可并行性概念的合理性、可并行度指标的实用性；建立的可并行性概念不仅丰富了测试领域的理论基础，对并行测试系统的仪器资源的配置也具有指导价值。

拱坝-地基系统的三维有限元并行计算

刘耀儒 周维垣 刘福深 强天驰

拱坝稳定和破坏过程的三维有限元分析，对高性能并行计算提出了很高的要求。采用节点联系矩阵的概念，基于Jacobi预处理共轭梯度法，推导了适用于分布存储并行机的有限元并行element-by-element(EBE)方法，可以避免形成整体刚度矩阵，显著减少内存需求，并可自动实现计算任务的分配。编制了有限元并行计算程序，采用悬臂梁算例对其进行了验证，然后应用于二滩拱坝的有限元数值分析。计算结果表明，对拱坝一地基系统这样复杂的三维结构，有限元EBE方法是一种很有效的并行计算方法。

基于Beowulf集群的大规模电力系统方程并行PCG求解

Parallel PCG Solution of Large Scale Power System Equations Based on Beowulf Cluster

刘洋 周家启 谢开贵 赵渊 陈炜俊 胡博

研究基于Beowulf集群的大规模电力系统方程并行PCG求解问题,采用常见的硬件设备和廉价且广为传播的软件构建出Beowulf分布式集群环境,基于这一环境,彻底摒弃矩阵的传统直接分解算法,采用多项式预处理的PCG法并行求解大型稀疏线性方程组.文中方法无需进行任何形式的电网络划分,也无需进行任何的矩阵三角分解和前推回代过程,适合各种类型的大规模电力系统方程的并行求解.本文分别在潮流计算、状态估计和静态安全分析中对大规模电力系统方程实现了并行求解,并获得一定的加速比和并行效率,为大规模电力系统快速、准确的仿真计算和在线分析提供一种可行的新途径.

MPI环境下的几何定理并行自动推理

Parallel Automated Reasoning for Geometry Theorem Proving Based on MPI Environment

潘斌 郭红霞

将几何定理机器证明和并行计算结合起来考虑，尝试用并行计算方法来提高传统定理证明算法效率，探讨了前推法、数值并行法的并行算法，分析了两种定理证明算法在消息传递编程模型下的任务划分、通信组织、任务调度等问题，并用MPICH2实现了这两种并行算法，对算法的并行性能指标进行了测试，测试数据表明，两种并行算法在基于MPI-2的并行计算环境下，能很好地发挥并行计算的优势，有效缩短构造性几何命题机器证明的时间。

并行程序设计模型和语言

安虹 陈国良

并行计算技术的发展已有20多年的历史了。时至今日，高性能并行计算仍然缺乏有效的并行程序设计方法和工具，使得编写并行程序、理解并行程序的行为、调试和优化并行程序的性能都很困难，从分析并行程序设计困难的原因入手，指出了当前各种 行机系统支持的并行程序设计方法存在的诸多问题，综述了并行程序设计模型和语言的研究现状，给出了并行程序设计模型的评价标准，并提出了这一研究领域所面临的挑战性问题，指出了一些未来可能的发展方向。

并行计算技术

李鹏 邵明刚

随着计算机产业的不断进步，对于计算机系统当前可能提供的计算速度的需求总是不断增长，对计算的要求也越来越高，并行计算的开发与应用也愈发的重要。本文主要对并行计算技术进行总体介绍，主要涉及并行计算的基本技术和用MPI来编写并行程序。如消息传递计算，并行处理技术。并简单介绍了并行计算发展的最新情况。

LINUX系统下PC机局域网并行计算环境的实现与测试

Implementation and testing of parallel computation environment in PC LAN under LINUX operating system

张鸿雁 陈晓春 王元

为了解决CFD技术在实际使用中碰到的计算资源紧张问题,提出了PC机局域网并行计算的思路.对LINUX操作系统、局域网的组建和网络并行环境MPI的实现进行了研究.搭建了并行计算平台,并利用商用CFD软件对该平台的基本工作性能进行了测试.结果表明：当网格数量超过50万时,两台计算机并行效率超过67.9%;四台计算机并行效率超过52.8%,随着网格数量增加,并行效率逐步得以提高,当网格数量接近200万时,并行效率分别达到168.58%和145.62%,出现了超线性现象.