EBE-PCG算法在有限元并行计算中的应用研究

目前,在研究有限元并行计算时,讨论并行算法理论和并行算法设计与分析的居多, 研究并行算法的实现并解决实际问题较少.在Beowulf集群环境下,采用EBE策略设计出基于 PVM平台的EBE-PCG算法,并通过一个电法勘探的典型工程算例对该算法在有限元计算中的性能进行了测试.实验结果表明,该算法加速比和并行效率均较为理想;在处理同等规模的问题时,同CG算法、PCG算法相比,具有并行度更高,耗时更少等优点.     

基于有效并行求解策略的显式有限元分析并行算法

针对大规模结构非线性动力问题的有限元分析非常耗时,基于消息传递接口（MPI）机群环境,提出多种基于并行求解策略的显式有限元并行算法。基于显式消息传递的区域分解技术,采取重叠、非重叠区域分解技术及动态任务分配方法,通过将计算与通信重叠,优化处理器间的通信,对非重叠通信区域分解并行算法、重叠通信区域分解并行算法、群动态任务分配算法、动态任务分配算法及动态负载平衡算法进行研究。为在机群环境下实现非线性动力有限元分析,开发了基于有效并行求解策略的显式有限元并行算法。编写了基于消息传递编程模式的并行有限元程序,在工作站机群上实现了数值算例,分析了算法的性能,并与传统的Newmark算法进行了比较。算例表明：群动态任务分配算法的性能优于动态任务分配算法,低于区域分解算法的性能,动态负载平衡算法最优。对相同规模的问题提出的算法比Newmark算法快,优于Newmark算法。对结构非线性动力问题的有限元分析,所提出的并行算法是可行有效的。     

栅格数据多源成本距离分析并行算法及实现

针对栅格数据成本距离分析串行算法在大数据量、多源点的情况下计算效率低的问题,在串行算法的基础上,设计并实现了一种并行算法。实验结果表明,该算法有效地提高了计算效率。当栅格数据越大,点状源数目越多的时候,并行算法较串行算法的优越性越明显,并且随着线程个数的增加,并行算法的执行效率也在不断提高。     

基于层次化数据结构的并行有限元计算

高效数据结构及并行算法是大规模并行有限元计算的关键。本文面向非结构网格,提出了一种层次化的数据结构,并在该数据结构基础上设计了并行有限元算法。最后,用数值算例验证了数据结构和并行算法的正确性和并行可扩展性。     

嵌入式零树小波压缩和解压缩的并行化算法

嵌入式零树小波压缩算法是图像压缩技术中有效的压缩算法,但其压缩时间较长.对该算法进行了研究,并在多核机群系统下实现了该算法的并行算法,提高了算法的性能.实现了MPI和MPI+OpenMP两种并行算法,并将串行算法、MPI并行算法与MPI+OpenMP并行算法进行比较.结果显示,随着数据量的增多,MPI并行算法和MPI+OpenMP并行算法相对于串行算法的运行效率都有明显提高,其中MPI+OpenMP并行算法的效率更好.     

一种基于并行遗传算法的网格资源分配方法

提出了基于并行遗传算法的网格资源分配方法,并采用粗粒度模型设计了该并行算法。为了评估该并行算法的性能,在PC集群上实现了该并行算法和一个串行遗传算法。通过比较两个算法的执行时间和解的质量,说明了并行算法极大地提高了求解的速度和质量,是一种高效的资源分配方法。     

像素级融合并行算法的模型研究

通过对多种遥感图像像素级融合算法的深入研究,实现了三种具有代表性的像素级融合并行算法,在分析了这些并行算法的数据划分方式、负载平衡及算法设计流程的基础上,总结性地提出了一种通用的像素级融合并行算法模型。该模型对遥感图像融合的并行算法研究提供了有益的指导和借鉴。     

基于残余平滑预处理共轭梯度算法的有限元并行计算

针对弹塑性问题的有限元分析非常耗时,基于消息传递接口(MPI)集群环境,提出了残余平滑的子结构预处理共轭梯度并行算法。采取区域分解,将子结构通过界面条件处理为独立的有限元模型。整体分析时,每个处理器仅存储与其相关的子结构信息并生成局部刚度矩阵。采用对角存储方式和最小残余平滑法,设计出了结合残余平滑(MR)的并行子结构预处理共轭梯度(PCG)算法。并行算法中对负载平衡进行了探讨,对处理器间的通信进行了优化。利用子步法对弹塑性应力应变进行积分,根据预定的容许值自动调整每个子步的大小来控制积分过程的误差。在工作站集群上实现了数值算例,分析了算法的性能,计算性能与传统的PCG算法进行了比较。算例显示:所提算法具有良好的加速比和效率,优于传统的PCG算法,对弹塑性问题的有限元分析,是一种有效的并行求解算法。     

一种基于PVM的矩阵相乘并行算法

研究了一种运行于PVM并行计算平台的矩阵相乘的并行算法。在工作站数量不为某个数的平方数时,Cannon算法在PVM环境下不能充分地利用机群系统中的资源。根据PVM并行编程环境中任务间通信的特点,文中设计了一种基于PVM的矩阵相乘并行算法,该算法根据工作站数量来确定子任务的数量,并对矩阵A进行分块,每个子任务可以计算一个分块。实验表明,该算法提高了机群并行环境中资源的利用率,提高了程序的运行效率。     

广义Hermitian特征问题标准化转换的有效并行块算法

广义Hermitian特征问题并行求解器的性能依赖于所选择的并行算法和矩阵的分布策略等诸多方面.基于块存储和快算法策略,提出了一个新的标准化转化的并行算法,该并行算法将Cholesky分解结合到广义特征问题标准化转换中,降低了已有并行算法的通信开销,并增加了算法的并行性.新算法可显著改善已有并行算法的性能和可扩展性.另外给出了一个有效求解具有多个右端项的三角矩阵方程AX=B的并行块算法.通过自主开发的特征问题并行软件包PSEPS的测试结果表明,并行算法比传统的并行算法快大约1倍,并具有较好的可扩展性.     

基于集群的EBE-PCG算法在物探中的应用

采用有限元法进行电法勘探时,会产生大型稀疏线性方程组,如何提高方程组的求解效率成为物探研究的关键.提出了在Beowulf集群环境下,采用粗粒度EBE-PCG算法处理物探问题.在集群环境下,该算法具有机器间相互通信少,易于并行实现等优点.实验结果表明,采用EBE-PCG算法获得了良好的并行效果.     

Parallel mesh-partitioning algorithms for generating shape optimised partitions using evolutionary computing

In this paper, parallel mesh-partitioning algorithms are proposed for generating submeshes with optimal shape using evolutionary computing techniques. It is preferred to employ a formulation for mesh partitioning, which maintains constant number of design variables irrespective of the size of the mesh. Two distinct parallel computing models have been employed. The first model of parallel evolutionary algorithm uses the master–slave concept (single population model) and a new synchronous model is proposed to optimise the performance even on heterogeneous parallel hardware. Alternatively, a multiple population model is also developed which simulates it’s sequential counter part. The advantage of the second model is that it can fit in large size problems with large population even on moderate capacity parallel computing nodes. The performance of the evolutionary computing based mesh-partitioning algorithm is demonstrated first by solving several practical engineering problems and also several benchmark test problems available in the literature and comparing the results with the multilevel algorithms. Later the speedup of the parallel evolutionary algorithms on parallel hardware is evaluated by solving large scale practical engineering problems.     

Parallel Algorithms for Dynamic Shortest Path Problems

The development of intelligent transportation systems (ITS) and the resulting need for the solution of a variety of dynamic traffic network models and management problems require faster‐than‐real‐time computation of shortest path problems in dynamic networks. Recently, a sequential algorithm was developed to compute shortest paths in discrete time dynamic networks from all nodes and all departure times to one destination node. The algorithm is known as algorithm DOT and has an optimal worst‐case running‐time complexity. This implies that no algorithm with a better worst‐case computational complexity can be discovered. Consequently, in order to derive algorithms to solve all‐to‐one shortest path problems in dynamic networks, one would need to explore avenues other than the design of sequential solution algorithms only. The use of commercially‐available high‐performance computing platforms to develop parallel implementations of sequential algorithms is an example of such avenue. This paper reports on the design, implementation, and computational testing of parallel dynamic shortest path algorithms. We develop two shared‐memory and two message‐passing dynamic shortest path algorithm implementations, which are derived from algorithm DOT using the following parallelization strategies: decomposition by destination and decomposition by transportation network topology. The algorithms are coded using two types of parallel computing environments: a message‐passing environment based on the parallel virtual machine (PVM) library and a multi‐threading environment based on the SUN Microsystems Multi‐Threads (MT) library. We also develop a time‐based parallel version of algorithm DOT for the case of minimum time paths in FIFO networks, and a theoretical parallelization of algorithm DOT on an ‘ideal’ theoretical parallel machine. Performances of the implementations are analyzed and evaluated using large transportation networks, and two types of parallel computing platforms: a distributed network of Unix workstations and a SUN shared‐memory machine containing eight processors. Satisfactory speed‐ups in the running time of sequential algorithms are achieved, in particular for shared‐memory machines. Numerical results indicate that shared‐memory computers constitute the most appropriate type of parallel computing platforms for the computation of dynamic shortest paths for real‐time ITS applications.     

一种基于设计模式的三阶段并行程序设计方法

并行程序的可编程性是并行计算的难点之一，使用传统的方法对非数值问题进行并行求解则更加困难。通过对设计模式概念的扩展，定义了算法模式与结构模式，以此为基础提出了一种基于设计模式的三阶段并行程序设计方法，并通过算法模式库与结构模式库实现对该方法的系统支持，该方法不仅可有于一般的数值问题求解，而且在处理复杂的非数值问题时与传统方法相比要简单得多，通过一个简单的数值问题和一个复杂非数值问题作为实例说明了使用这一方法进行问题并行求解与并行程序设计的过程。     

网格并行计算模型研究

分析了传统分布式并行计算和网格基础上并行计算技术应用中存在的问题,将Log P并行计算模型拓展到网格上,给出双层Log P模型和设计策略,针对网格特点对CG并行算法进行了改进,取得了很好的效果.     

基于网格的并行算法研究

分析了传统分布式并行计算和网格基础上并行计算技术应用中存在的问题。然后将LogP并行计算模型拓展到网格上,给出双层LogP模型和设计策略。针对网格特点对CG并行算法进行了改进,并有很好的效果。     

Synchronous parallelization of Particle Swarm Optimization with digital pheromones

In this paper, Particle Swarm Optimization (PSO) using digital pheromones to coordinate swarms within n-dimensional design spaces in a parallel computing environment is presented. Digital pheromones are models simulating real pheromones emitted by insects for communication to indicate suitable food or nesting location. Particle swarms search the design space with digital pheromones aiding communication within the swarm during an iteration to improve search efficiency. Previous work by the authors demonstrated the capability of digital pheromones within PSO for searching the global optimum with improved accuracy, efficiency and reliability in a single processor computing environment. When multiple swarms explore and exploit the design space in a parallel computing environment, the solution characteristics can be further improved. This premise is investigated through deploying swarms on multiple processors in a distributed memory parallel computing environment. The primary hurdle for the developed algorithm was bandwidth latency due to synchronization across processors, causing the solution duration due to each swarm to be only as fast as the slowest participating processor. However, it has been observed that the speedup and parallel efficiency improved substantially as the dimensionality of the problems increased. The development of the method along with results from six test problems is presented.     

基于网格的CG并行计算研究

分析了传统分布式并行计算和网格,以及并行计算技术应用中存在的问题,将LogＰ并行计算模型拓展到网格上,给出双层LogＰ模型和设计策略。针对网格特点对CG并行算法进行了改进,并取得了很好的效果。     

并行蒙特卡罗方法的应用

该文采用蒙特卡罗方法对欧式期权定价问题进行模拟,并用可移植消息传递标准MPI在分布式存储结构的机群系统上设计并实现了并行算法。该算法有效的解决了金融计算中巨大计算量的问题,在很大程度上提高了计算效率,缩短了计算时间,获得了很好的性能。     

并行蒙特卡罗方法的应用

该文采用蒙特卡罗方法对欧式期权定价问题进行模拟,并用可移植消息传递标准MPI在分布式存储结构的机群系统上设计并实现了并行算法。该算法有效的解决了金融计算中巨大计算量的问题,在很大程度上提高了计算效率,缩短了计算时间,获得了很好的性能。