一种求解最大团问题的并行交叉熵算法

为了提高交叉熵算法求解最大团问题(maximum clique problem,MCP)的性能,提出一种领导者-跟随者协作求解的并行策略来实现交叉熵算法,从而达到减少计算时间和保障解的质量这两方面的平衡.算法中领导者活跃在并行处理器之间采集数据,并根据当前获得信息对跟随者作出决策;受控的跟随者则主要根据领导者的决策信息自适应地调整搜索空间,完成各自的集团产生任务.采用了OpenMPI在MIMD平台上实现了该算法,并应用到MCP基准测试问题上.加速比和效率分析结果表明,算法具有很好的加速比和效率.而与其它几种当前最好的启发式算法相比,结果表明算法相对于基于种群的启发式算法有一定的性能改善.     

对一类带聚类特征TSP问题的并行遗传算法求解

提出了一种带聚类处理的并行遗传算法,该算法首先对大规模TSP问题进行聚类处理,将其分解成一些小规模TSP问题,然后分别对每个小规模TSP问题利用遗传算法并行求解,最后将所有小规模TSP问题的解按一定规则合并成大规模TSP问题的解。对大规模TSP问题的模拟实验表明该算法极大地提高了遗传算法的收敛速度。     

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.     

Efficient External Memory Algorithms by Simulating Coarse-Grained Parallel Algorithms

Abstract. External memory (EM) algorithms are designed for large-scale computational problems in which the size of the internal memory of the computer is only a small fraction of the problem size. Typical EM algorithms are specially crafted for the EM situation. In the past, several attempts have been made to relate the large body of work on parallel algorithms to EM, but with limited success. The combination of EM computing, on multiple disks, with multiprocessor parallelism has been posted as a challenge by the ACM Working Group on Storage I/ O for Large-Scale Computing. In this paper we provide a simulation technique which produces efficient parallel EM algorithms from efficient BSP-like parallel algorithms. The techniques obtained can accommodate one or multiple processors on the EM target machine, each with one or more disks, and they also adapt to the disk blocking factor of the target machine. When applied to existing BSP-like algorithms, our simulation technique produces improved parallel EM algorithms for a large number of problems.     

并行算法研究方法学

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

Parallel Implementation of Linear Algebra Problems on Dawning-1000

In this paper,some parallel algorithms are described for solving numerical linear algebra problems on Dawning-1000.They include matrix multiplication,LU factorization of a dense matrix,Cholesky factorization of a symmetric matrix,and eigendecomposition of symmetric matrix for real and complex data types.These programs are constructed based on fast BLAS library of Dawning-1000 under NX environment.Some comparison results under different parallel environments and implementing methods are also given for Cholesky factorization.The execution time,measured performance and speedup for each problem on Dawning-1000 are shown.For matrix multiplication and IU factorization,1.86GFLOPS and 1.53GFLOPS are reached.     

一种主从式并行遗传算法设计

该文对串行遗传算法进行了并行设计,加入对当前通用消息传递接口MPI的支持,形成了一个主从式并行遗传算法。针对该算法用经典的测遗传算法效率的OliverTSP问题进行测试,得出并行遗传算法可以更好的提高遗传算法的收敛性。     

分层并行遗传算法和遗传复合形算法及其应用

基于复合形算法、遗传算法、分层和并行思想,设计了一种求解复杂多目标、多约束和多变量工程优化问题的分层并行遗传或复合形算法,编制了界面友好和计算可靠性高的VC++软件。对于一类复杂三多工程综合优化问题,进行了遗传算法、复合形算法、分层并行遗传算法和分层并行遗传复合形算法的大量计算,结果表明：分层并行遗传算法计算效率最高;为解决复杂的三多工程综合优化问题提供了有效的可行方法。     

Scalable Parallel Algorithms for Geometric Pattern Recognition

This paper considers a variety of geometric pattern recognition problems on input sets of size n using a coarse grained multicomputer model consisting of p processors with Ω(n/p) local memory each (i.e., Ω(n/p) memory cells of Θ(log n) bits apiece), where the processors are connected to an arbitrary interconnection network. It introduces efficient scalable parallel algorithms for a number of geometric problems including the rectangle finding problem, the maximal equally spaced collinear points problem, and the point set pattern matching problem. All of the algorithms presented are scalable in that they are applicable and efficient over a very wide range of ratios of problem size to number of processors. In addition to the practicality imparted by scalability, these algorithms are easy to implement in that all required communications can be achieved by a small number of calls to standard global routing operations.     

一个基于消息传递接口和面向对象的图像信号处理并行向量库

传统并行软件系统的设计和实现存在着开发效率低、质量难以保证和可移植性差等问题。针对这些问题,采用开发标准并行库的方法加以解决。借鉴高性能嵌入式计算软件计划(high performance embedded computing software initiative,HPEC_SI)的解决方法,基于消息传递接口(message passing interface,MPI)的消息传递机制,对图像/信号处理中的一些典型并行算法以类组件的方式进行封装,设计和实现了具有面向对象特征的、用于图像/信号处理的并行向量库,提供给应用软件开发人员一个良好的开发环境。通过测试和实验证明,该库可以高效地实现相应的向量矩阵并行算法,并具有简单易用、可复用性和可移植性强、效率高的特点。     

粗粒度并行遗传算法性能分析

依据实验来分析影响并行遗传算法性能的因素得到的结论缺乏理论上的说服力．通过对粗粒度并行遗传算法加速比公式的分析，提出了影响并行遗传算法性能的关键因素，同时否定了以迁移率作为评价并行遗传算法性能指标的合理性，并通过实难进一步验证结论的正确性．得到的结论为提高遗传算法的并行化效率提供了可靠的依据。     

一种主从式并行遗传算法设计

该文对串行遗传算法进行了并行设计,加入对当前通用消息传递接口MPI的支持,形成了一个主从式并行遗传算法。针对该算法用经典的测遗传算法效率的OliverTSP问题进行测试,得出并行遗传算法可以更好的提高遗传算法的收敛性。     

众核计算平台的高吞吐率密码算法加速

众核处理器适应于加速高吞吐率的计算密集型应用,而密码算法需要进行大量的数学计算,特别需要使用高吞吐率的计算平台。提出了一种面向众核平台的粗粒度并行加速框架,该框架不考虑算法内部的运算过程,将数据以计算函数为单位分配到众核协处理器上执行。使用MIC众核协处理器,采用三级并行结构及任务分配机制,提升了高吞吐率密码算法处理的并行性。针对多种密码算法应用的实验结果表明,该框架可充分利用众核平台实现粗粒度并行的高吞吐率加解密处理。     

Parallel path consistency

Filtering algorithms are well accepted as a means of speeding up the solution of the consistent labeling problem (CLP). Despite the fact that path consistency does a better job of filtering than arc consistency, AC is still the preferred technique because it has a much lower time complexity. We are implementing parallel path consistency algorithms on multiprocessors and comparing their performance to the best sequential and parallel arc consistency algorithms.^(1,2) (See also work by Kerethoet al. ⁽³⁾ and Kasif⁽⁴⁾) Preliminary work has shown linear performance increases for parallelized path consistency and also shown that in many cases performance is significantly better than the theoretical worst case. These two results lead us to believe that parallel path consistency may be a superior filtering technique. Finally, we have implemented path consistency as an outer product computation and have obtained good results (e.g., linear speedup on a 64K-node Connection Machine 2).     

动力学系统实时仿真数值方法研究

从6个方面概述动力学系统实时仿真数值方法的一些最近的研究进展，内容包括：产时仿真快速混合算法、实时并行Rosenbrock算法、实时并行组合算法、微分代数系统的实时算法与实时并行算法、实时间断处理并行算法以及一些并行算法的效率分析等。给出构造实时仿真算法新的思想和方法，同时也涉及一些有关问题的讨论。     

Data parallel volume-rendering algorithms for interactive visualization

The increasing availability of parallel computing platforms has led to the development of parallel volume-rendering algorithms. In the present paper we compare two algorithms for volume raytracing in a data-parallel framework: a shearing technique and a line-drawing technique. The two algorithms are primarily distinguished by the level of parallelism they exploit. Both algorithms have been implemented on the Connection Machine CM2 massively parallel computer and execute at speeds suitable for interactive volume-rendering applications. Since considerable floating-point resources are available on the CM2, we have used rendering algorithms based on transport theory. In the second part of the paper we examine some of the tradeoffs involved between image quality and rendering speed when using high-fidelity rendering algorithms.     

微分代数方程的一类并行算法

本文提出求解微分代数方程的一类并行算法,进行误差估计。对于一个模型问题进行稳定性分析,画出稳定区域。计算实例表明算法是有效的。     

MapReduce技术在物资调运与配载问题中的应用

针对用于求解复杂物资调运及配载问题的多目标遗传算法耗时较长的问题,设计了基于云计算MapReduce技术的并行化部署和改进方案。实验对比了算法在多种串行、并行环境下的时效性,证实了MapReduce架构在一定环境下能较大幅度提高算法的时耗性能。     

非定常Monte Carlo输运问题的并行算法

文中给出了非定常MonteCarlo(下文简写为MC)输运问题的并行算法 ,对并行程序的加载运行模式进行了讨论和优化设计 .针对MC并行计算设计了一种理想情况下无通信的并行随机数发生器算法 .动态MC输运问题有大量的I/O操作 ,特别是读取剩余粒子数据文件需要大量的I/O时间 ,文中针对I/O问题 ,提出了三种并行I/O算法 .最后给出了并行算法的性能测试结果 ,对比串行计算时间 ,使用 6 4台处理机时的并行计算时间缩短了 30倍     

Platform impact on performance of parallel genetic algorithms: Design and implementation considerations

Many problems in the operations research field cannot be solved to optimality within reasonable amounts of time with current computational resources. In order to find acceptable solutions to these computationally demanding problems, heuristic methods such as genetic algorithms are often developed. Parallel computing provides alternative design options for heuristic algorithms, as well as the opportunity to obtain performance benefits in both computational time and solution quality of these heuristics. Heuristic algorithms may be designed to benefit from parallelism by taking advantage of the parallel architecture. This study will investigate the performance of the same global parallel genetic algorithm on two popular parallel architectures to investigate the interaction of parallel platform choice and genetic algorithm design. The computational results of the study illustrate the impact of platform choice on parallel heuristic methods. This paper develops computational experiments to compare algorithm development on a shared memory architecture and a distributed memory architecture. The results suggest that the performance of a parallel heuristic can be increased by considering the desired outcome and tailoring the development of the parallel heuristic to a specific platform based on the hardware and software characteristics of that platform.