并行智能优化算法研究进展

基于种群迭代搜索的智能优化算法在农业、交通、工业等很多领域都取得了广泛的应用.但是该类算法迭代寻优的特点使其求解效率通常较低,很难应用到大规模、高维或实时性要求较高的复杂优化问题中.随并行分布式技术的发展,国内外很多学者开始着手研究智能优化算法的并行化.本文首要介绍了并行智能优化算法的基本概念;其次从协同机制、并行模型以及硬件结构3个维度综述了几类常见的并行智能优化算法,详细分析阐述了它们优点及不足;最后对并行智能优化算法的未来研究进行了展望.     

Parallel strategies for the local biological sequence alignment in a cluster of workstations

Recently, many organisms have had their DNA entirely sequenced. This reality presents the need for comparing long DNA sequences, which is a challenging task due to its high demands for computational power and memory. Sequence comparison is a basic operation in DNA sequencing projects, and most sequence comparison methods currently in use are based on heuristics, which are faster but offer no guarantees of producing the best alignments possible. In order to alleviate this problem, Smith–Waterman proposed an algorithm. This algorithm obtains the best local alignments but at the expense of very high computing power and huge memory requirements. In this article, we present and evaluate our experiments involving three strategies to run the Smith–Waterman algorithm in a cluster of workstations using a Distributed Shared Memory System. Our results on an eight-machine cluster presented very good speed-up and indicate that impressive improvements can be achieved depending on the strategy used. In addition, we present a number of theoretical remarks concerning how to reduce the amount of memory used.     

并行算法研究方法学

并行算法是计算机科学中重要的研究内容,已有几十年的发展历程.回顾一下其研究历程,既有高潮也有低谷,究其原因是,它没有形成自身的一套研究方法学.为此文中提出并行算法研究要建立起一套完整的"理论-设计-实现-应用"的学科体系,也就是所谓的并行算法研究的生态环境.只有这样才能够保持并行算法研究稳定、可持续发展,并使得并行算法的研究成果更加实用,从而更富有生命力.     

网络环境中FFT算法的优化设计

以并行FFT算法为例,研究微机构成的网络计算平台上的并行程序设计与优化问题。由于整个系统的性能取决于网络消息通讯,为减少实施负载平衡策略本身所带来的通信开销,在进行数据分配时尽可能使计算数据局部化。由于异构性,数据分配还应考虑节点机的性能。     

Optimization of data exchange in parallel computers with distributed memory

The problem of optimization of communications during the execution of a program on a parallel computer with distributed memory is investigated. Statements are formulated that make it possible to determine the possibility of organization of data broadcast and translation. The conditions proposed are represented in the form suitable for practical application and can be used for automated parallelization of programs. This work was done within the framework of the State Program of Fundamental Studies of the Republic of Belarus (under the code name “Mathematical structures 21”) with the partial support of the Foundation for Fundamental Studies of the Republic of Belarus (grant F03-062). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 166–182, March–April 2006.     

基于PVM的并行程序开发环境研究

开发并行程序要比开发单机串行程序更难。PVM开发环境是应用比较广的环境之一,适合于开发粗粒度的工程科学计算并行程序,而这些工程计算问题一般是一些数值计算问题的集合。编写这些数值计算并行程序有一定的难度和复杂度,并且现在没有很好支持开发PVM并行程序的成熟开发环境。针对这个问题,构造一个基于PVM的并行程序开发环境。开发环境包括一个并行算法库和一个嵌入到Visual Studio的可视化程序开发插件。通过开发平台进行并行程序开发将更加简单、高效。     

Efficient Parallel Graph Algorithms for Coarse-Grained Multicomputers and BSP

In this paper we present deterministic parallel algorithms for the coarse-grained multicomputer (CGM) and bulk synchronous parallel (BSP) models for solving the following well-known graph problems: (1) list ranking, (2) Euler tour construction in a tree, (3) computing the connected components and spanning forest, (4) lowest common ancestor preprocessing, (5) tree contraction and expression tree evaluation, (6) computing an ear decomposition or open ear decomposition, and (7) 2-edge connectivity and biconnectivity (testing and component computation). The algorithms require O(log p) communication rounds with linear sequential work per round (p = no. processors, N = total input size). Each processor creates, during the entire algorithm, messages of total size O(log (p) (N/p)) . The algorithms assume that the local memory per processor (i.e., N/p ) is larger than p ^ε , for some fixed ε > 0 . Our results imply BSP algorithms with O(log p) supersteps, O(g log (p) (N/p)) communication time, and O(log (p) (N/p)) local computation time. It is important to observe that the number of communication rounds/ supersteps obtained in this paper is independent of the problem size, and grows only logarithmically with respect to p . With growing problem size, only the sizes of the messages grow but the total number of messages remains unchanged. Due to the considerable protocol overhead associated with each message transmission, this is an important property. The result for Problem (1) is a considerable improvement over those previously reported. The algorithms for Problems (2)—(7) are the first practically relevant parallel algorithms for these standard graph problems. Received July 5, 2000; revised April 16, 2001.     

计算几何与并行算法

本文首先介绍了计算几何的基本概念,论述了计算几何的四个基本问题,即几何搜索问题、相交问题、邻接问题及凸壳问题。然后重点分析了凸壳构造问题,介绍了其最佳串行算法、及相应的并行算法。接着对一些计算几何的串行及并行算法进行了分析比较。最后提出了笔者对新一代并行计算机系统上设计计算几何并行算法的看法。     

SCHEDULING IN HETEROGENEOUS COMPUTING AND GRID ENVIRONMENTS USING A PARALLEL CHC EVOLUTIONARY ALGORITHM

Scheduling is a capital problem when using distributed heterogeneous computing (HC) and grid environments to solve complex problems. The scheduling problem in heterogeneous environments is NP‐hard, so a significant effort has been made to develop efficient methods for solving the problem. However, few works have faced realistic grid‐sized problem instances. This work presents a parallel CHC (pCHC) evolutionary algorithm codified over MALLBA, a general‐purpose library for combinatorial optimization, for solving the scheduling problem in HC and grid environments. Efficient numerical results are reported in the experimental analysis performed on both a standard benchmark and a set of large‐sized problem instances specially designed in this work. The comparative study shows that pCHC is able to achieve high problem solving efficacy, significantly improving over traditional deterministic scheduling methods, while also showing a good scalability behavior when solving large problem instances.     

基于云计算的物联网数据挖掘模型

物联网中的数据具有数据量大、数据类型复杂、高度动态性与异构性、复杂时空特性等特点,为数据挖掘带来新的挑战。传统的数据挖掘方法无法直接应用于物联网之中。基于此,提出一种基于云计算的物联网数据挖掘模型,以云计算作为技术支持平台,在构建面向物联网的分布式时空数据库的基础上,搭建面向物联网海量数据的数据挖掘模型。通过分析表明该模型能够有效地完成物联网中的数据挖掘任务。     

多图像同态滤波的 CPU 和 GPU 并行计算磁

采取 CPU 分发图像滤波任务和回收滤波结果、将多个图像数据划分分配给多个 GPU 及其线程块、GPU 调用核函数库对图像进行傅里叶变换和反傅里叶变换的方法,设计实现了 CPU 和 GPU 协同计算的多图像同态滤波并行算法。实验结果表明,给出的多图像同态滤波并行算法高效,与单 GPU 计算的并行算法相比,多 GPU 协同计算的并行算法显著缩短了多个图像同态滤波处理所需的时间。     

基于Myrinet上MPICH-2的实现

在当前并行计算环境中的通信网络中,MPICH-1并行系统可以使用Internet和Myrinet千兆位包交换网络,而MPICH-2并行系统只能使用Internet,由于通信时间的限制而影响了整个系统性能.对MPICH-1和MPICH-2中的作业提交模式进行了研究,给出了一种在MPICH-2中使用Myrinet网络来提交作业的应用,从而达到减少了通信时间的目的.     

网络计算环境下并行算法及其可扩放性分析

并行算法的可扩放性是提其有效利用计算节点的能力，它可以预测算法在处理机数目变化时的性能，在网络环境下用ＰＶＭ实现了并行矩阵乘法及ＰＳＲＳ算法，分析了在网络计算环境下这两个算法的可扩放性，并利用试验数据进行了验证。