Parallel exact sampling and evaluation of Gaussian Markov random fields

Markov chain Monte Carlo algorithms are computationally expensive for large models. Especially, the so-called one-block Metropolis-Hastings (M-H) algorithm demands large computational resources, and parallel computing seems appealing. A parallel one-block M-H algorithm for latent Gaussian Markov random field (GMRF) models is introduced. Important parts of this algorithm are parallel exact sampling and evaluation of GMRFs. Parallelisation is achieved with parallel algorithms from linear algebra for sparse symmetric positive definite matrices. The parallel GMRF sampler is tested for GMRFs on lattices and irregular graphs, and gives both good speed-up and good scalability. The parallel one-block M-H algorithm is used to make inference for a geostatistical GMRF model with a latent spatial field of 31,500 variables.     

OpenFoam中多面体网格生成的MPI+OpenMP混合并行方法

网格生成是计算流体力学中非常重要的一环,大规模数值模拟过程中对网格精度要求的提高会导致网格生成所耗的时间增加。文中基于OpenFoam开源软件中的网格生成算法,主要研究多面体网格的并行生成,并提出OpenMP和MPI混合并行的多面体网格生成方法。通过理论分析得到,使用混合并行方法生成相同质量的网格时,混合并行方法生成网格的时间消耗随着线程数量和网格单元数量的增加而减少。3组使用不同求解器的数值模拟实验结果表明,该混合并行方法不但可以保证生成网格的质量——可以正常进行数值计算模拟且模拟结果与原方法相比几乎没有差别,而且生成同样质量与数量网格的耗时最多可以缩短至未使用OpenMP并行方法之耗时的1/4以内。     

基于曙光并行机的超大规模非线性方程组并行算法研究

该文讨论了一类求解大规模非线性方程组算法的并行性能及其在曙光并行机上的实现过程，与传统的算法不同之处是用一个块对角矩阵作为迭代矩阵，且该矩阵可由一个仅包含向量内积和矩阵与向量乘积的递推关系简便计算得到，在对算法进行描述之后，分析了算法的并行加速比和存储需求，讨论了算法在基于消息传递的MPI并行环境下的实现流程，数值计算表明理论分析与数值结果相比，算法在分布式并行环境下具有有较好的并行主攻较低的存储要求，可适用于大规模科学与工程的高性能计算。     

Recent Advances in Parallel Advancing Front Grid Generation

The quest for scalable, parallel advancing front grid generation techniques now spans more than two decades. A recent innovation has been the use of a so-called domain-defining grid, which has led to a dramatic increase in robustness and speed. The domain-defining grid (DDG) has the same fine surface triangulation as the final mesh desired, but a much coarser interior mesh. The DDG renders the domain to be gridded uniquely defined and allows for a well balanced work distribution among the processors during all stages of grid generation and improvement. In this way, most of the shortcomings of previous techniques are overcome. Timings show that the approach is scalable and able to produce large grids of high quality in a modest amount of clocktime. These recent advances in parallel grid generation have enabled a completely scalable simulation pipeline (grid generation, solvers, post-processing), opening the way for truly large-scale computations using unstructured, body-fitted grids.     

A parallel linear solver for multilevel Toeplitz systems with possibly several right-hand sides

A Toeplitz matrix has constant diagonals; a multilevel Toeplitz matrix is defined recursively with respect to the levels by replacing the matrix elements with Toeplitz blocks. Multilevel Toeplitz linear systems appear in a wide range of applications in science and engineering. This paper discusses an MPI implementation for solving such a linear system by using the conjugate gradient algorithm. The implementation techniques can be generalized to other iterative Krylov methods besides conjugate gradient. These techniques include the use of an arbitrary dimensional process grid for handling the multilevel Toeplitz structure, a communication-hiding approach for performing matrix–vector multiplications, the incorporation of multilevel circulant preconditioning for accelerating convergence, an efficient orthogonalization manager for detecting linear dependence in block iterations, and an algorithmic rearrangement to eliminate all-reduce synchronizations. The combined use of these techniques leads to a scalable solver for large multilevel Toeplitz systems, possibly with several right-hand sides. We show experimental results on matrices of size up to the order of one billion with nearly perfect scaling by using up to 1024 MPI processes. We also demonstrate an application of the solver in parameter estimation for analyzing large-scale climate data.     

基于二维结构化网格的可压缩流体并行算法研究

基于二维/轴对称高精度可压缩多相流计算流体力学方法 MuSiC-CCASSIM的结构化网格部分,设计了区域并行分解方法;针对各处理器边界数据的通信,设计了阻塞式通信与非阻塞式通信并行算法;为了减少通信开销,设计了MPI/OpenMP混合并行优化算法。在天河二号超级计算机上进行了测试,每个核固定网格规模为625*250,最多调用8 192核。测试数据表明,采用MPI/OpenMP混合并行算法、纯MPI非阻塞式通信并行算法和纯MPI阻塞式通信并行算法的程序的平均并行效率分别达到86%、83%和77%,三种算法都具有良好的可扩展性。     

基于视觉区域聚合与双向协作的端到端图像描述生成

近几年,基于Transformer的预训练模型展现了强大的模态表征能力,促使了多模态的下游任务(如图像描述生成任务)正朝着完全端到端范式的趋势所转变,并且能够使得模型获得更好的性能以及更快的推理速度.然而,该技术所提取的网格型视觉特征中缺乏区域型的视觉信息,从而导致模型对对象内容的描述不精确.因此,预训练模型在图像描述生成任务上的适用性在很大程度上仍有待探索.针对这一问题,提出一种基于视觉区域聚合与双向协作学习的端到端图像描述生成方法 (visual region aggregation and dual-level collaboration, VRADC).为了学习到区域型的视觉信息,设计了一种视觉区域聚合模块,将有相似语义的网格特征聚合在一起形成紧凑的视觉区域表征.接着,双向协作模块利用交叉注意力机制从两种视觉特征中学习到更加有代表性的语义信息,进而指导模型生成更加细粒度的图像描述文本.基于MSCOCO和Flickr30k两个数据集的实验结果表明,所提的VRADC方法能够大幅度地提升图像描述生成的质量,实现了最先进的性能.     

基于IBA构建高性能的MPI环境

IBA作为一种I/O间、主机间的下一代高速互联方式,在高性能计算领域越来越成为瞩目的焦点。消息传递接口MPI已经成为并行程序设计事实上的国际标准。该文详细介绍了在IBA之上构建一个高性能的MPI环境的方法,并对消息延迟和消息带宽进行了测试,对测试数据进行了分析。     

Balancing conflicting requirements for grid and particle decomposition in continuum-Lagrangian solvers

Load balancing strategies for hybrid solvers that involve grid based partial differential equation solution coupled with particle tracking are presented in this paper. A typical Message Passing Interface (MPI) based parallelization of grid based solves are done using a spatial domain decomposition while particle tracking is primarily done using either of the two techniques. One of the techniques is to distribute the particles to MPI ranks to whose grid they belong to while the other is to share the particles equally among all ranks, irrespective of their spatial location. The former technique provides spatial locality for field interpolation but cannot assure load balance in terms of number of particles, which is achieved by the latter. The two techniques are compared for a case of particle tracking in a homogeneous isotropic turbulence box as well as a turbulent jet case. A strong scaling study is performed to more than 32,000 cores, which results in particle densities representative of anticipated exascale machines. The use of alternative implementations of MPI collectives and efficient load equalization strategies are studied to reduce data communication overheads.     

Parallel Implementation of 2-D Telegraphic Equation on MPI/PVM Cluster

In this paper, a parallel implementation of the Iterative Alternating Direction Explicit method by D’Yakonov (IADE-DY) to solve 2-D telegraphic problem on a distributed system using Message Passing Interface (MPI) and Parallel Virtue Machine (PVM) are presented. The parallelization of the program is implemented by a domain decomposition strategy. A Single Program Multiple Data (SPMD) model is employed for the implementation. The implementation is discussed in relation to means of the parallel performance strategies and analysis. The model enhances overlap communication and computation to avoid unnecessary synchronization, hence, the method yields significant speedup. The level of speedup observed from tables as the mesh increases are in the range of 5–10%. Improvement has been achieved by numbers of tables and figures in our experiment. We present some analyses that are helpful for speedup and efficiency. It is concluded that the efficiency is strongly dependent on the grid size, block numbers and the number of processors for both MPI and PVM. Different strategies to improve the computational efficiency are proposed.     

基于JavaCC的C代码自动并行化的设计与实现

针对当前大量遗产代码无法重复利用的问题,设计一种新的编译工具将C的串行代码转换为基于MPI+OpenMP的混合并行编程代码,降低了并行编程的开发成本。首先,通过对JavaCC的优化,实现一种可以解析C语言的词法和语法分析器,进行源代码分析并生成抽象语法树;其次,根据语法树对源代码进行控制依赖性和数据依赖性分析,产生可并行化的语句块分区;再次,按照提出的并行代码生成方法得到目标代码;最后,基于Visual Studio 2010构建目标代码仿真验证环境。实验结果表明,该工具可以较为理想地实现串行代码自动并行化,与手工编写的代码在加速比上的误差为8.2%~18.4%。     

基于代理的网格计算中间件

WADE系统是基于代理技术实现的一个可屏蔽异构和分布性的动态自适应的校园计算网格，提出了基于代理技术在校园网络内实现并行计算的方法，详细论述了基于代理的网格计算中间件的体系结构和主要模块功能，阐述了利用代理实现异构编译、协同计算的过程，给出了代理的Java实现方法，利用软件代理实现网格计算中间件，可以解决异构计算平台下多种并行编程环境的协同计算问题，为用户提供统一的服务接口，这将大大增强系统的可用性。     

Parallelization Strategies for Computational Fluid Dynamics Software: State of the Art Review

Computational fluid dynamics (CFD) is one of the most emerging fields of fluid mechanics used to analyze fluid flow situation. This analysis is based on simulations carried out on computing machines. For complex configurations, the grid points are so large that the computational time required to obtain the results are very high. Parallel computing is adopted to reduce the computational time of CFD by utilizing the available resource of computing. Parallel computing tools like OpenMP, MPI, CUDA, combination of these and few others are used to achieve parallelization of CFD software. This article provides a comprehensive state of the art review of important CFD areas and parallelization strategies for the related software. Issues related to the computational time complexities and parallelization of CFD software are highlighted. Benefits and issues of using various parallel computing tools for parallelization of CFD software are briefed. Open areas of CFD where parallelization is not much attempted are identified and parallel computing tools which can be useful for parallelization of CFD software are spotlighted. Few suggestions for future work in parallel computing of CFD software are also provided.     

Structural testing criteria for message‐passing parallel programs

Parallel programs present some features such as concurrency, communication and synchronization that make the test a challenging activity. Because of these characteristics, the direct application of traditional testing is not always possible and adequate testing criteria and tools are necessary. In this paper we investigate the challenges of validating message‐passing parallel programs and present a set of specific testing criteria. We introduce a family of structural testing criteria based on a test model. The model captures control and data flow of the message‐passing programs, by considering their sequential and parallel aspects. The criteria provide a coverage measure that can be used for evaluating the progress of the testing activity and also provide guidelines for the generation of test data. We also describe a tool, called ValiPar, which supports the application of the proposed testing criteria. Currently, ValiPar is configured for parallel virtual machine (PVM) and message‐passing interface (MPI). Results of the application of the proposed criteria to MPI programs are also presented and analyzed. Copyright © 2008 John Wiley & Sons, Ltd.     

A framework for adaptive collective communications for heterogeneous hierarchical computing systems

Collective communication operations are widely used in MPI applications and play an important role in their performance. However, the network heterogeneity inherent to grid environments represent a great challenge to develop efficient high performance computing applications. In this work we propose a generic framework based on communication models and adaptive techniques for dealing with collective communication patterns on grid platforms. Toward this goal, we address the hierarchical organization of the grid, selecting the most efficient communication algorithms at each network level. Our framework is also adaptive to grid load dynamics since it considers transient network characteristics for dividing the nodes into clusters. Our experiments with the broadcast operation on a real-grid setup indicate that an adaptive framework allows significant performance improvements on MPI collective communications.     

MPI程序在网格环境下移植的研究

将现有MPI并行程序移植到网格环境下有着非常现实的意义，本文介绍了网格计算的概念和MPI并行计算模型。阐述了将现有的MPI并行程序移植到Globus网格环境下的重要性，并针对这类移植的一种折中方案——MPICH—G2进行了研究、实验，总结了这种方案的特点和相关技术。     

An efficient 3-dim FFT for plane wave electronic structure calculations on massively parallel machines composed of multiprocessor nodes

Three-dimensional Fast Fourier Transforms (FFTs) are the main computational task in plane wave electronic structure calculations. Obtaining a high performance on a large numbers of processors is non-trivial on the latest generation of parallel computers that consist of nodes made up of a shared memory multiprocessors. A non-dogmatic method for obtaining high performance for such 3-dim FFTs in a combined MPI/OpenMP programming paradigm will be presented. Exploiting the peculiarities of plane wave electronic structure calculations, speedups of up to 160 and speeds of up to 130 Gflops were obtained on 256 processors.     

LogGPO: An accurate communication model for performance prediction of MPI programs

Message passing interface (MPI) is the de facto standard in writing parallel scientific applications on distributed memory systems. Performance prediction of MPI programs on current or future parallel systems can help to find system bottleneck or optimize programs. To effectively analyze and predict performance of a large and complex MPI program, an efficient and accurate communication model is highly needed. A series of communication models have been proposed, such as the LogP model family, which assume th...     

Efficient parallel implementations of near Delaunay triangulation with High Performance Fortran

Unstructured mesh generation exposes highly irregular computation patterns, which imposes a challenge in implementing triangulation algorithms on parallel machines. This paper reports on an efficient parallel implementation of near Delaunay triangulation with High Performance Fortran (HPF). Our algorithm exploits embarrassing parallelism by performing sub‐block triangulation and boundary merge independently at the same time. The sub‐block triangulation is a divide & conquer Delaunay algorithm known for its sequential efficiency, and the boundary triangulation is an incremental construction algorithm with low overhead. Compared with prior work, our parallelization method is both simple and efficient. In the paper, we also describe a solution to the collinear points problem that usually arises in large data sets. Our experiences with the HPF implementation show that with careful control of the data distribution, we are able to parallelize the program using HPF's standard directives and extrinsic procedures. Experimental results on several parallel platforms, including an IBM SP2 and a DEC Alpha farm, show that a parallel efficiency of 42–86% can be achieved for an eight‐node distributed memory system. We also compare efficiency of the HPF implementation with that of a similarly hand‐coded MPI implementation. Copyright © 2004 John Wiley & Sons, Ltd.     

基于SMP集群系统的并行编程模式研究与分析

并行计算技术是计算机技术发展的重要方向之一,SMP与集群是当前主流的并行体系结构。当前并行程序设计方法主要采用基于消息传递模型的MPI和基于共享存储模型的OpenMP,两种编程模式各有特点和适用范围。对SMP集群以及MPI和OpenMP的特点进行了分析,介绍了在SMP集群系统中利用MPI和OpenMP混合编程的可行性方法。