一种基于正弦变换的三维泊松方程并行求解算法

泊松方程的数值解法在许多物理或者工程问题上得到广泛应用,但是由于大部分三维泊松方程的离散化格式不具有明显的并行性,实际中使用整体迭代的思想,这使得计算效率和稳定性受到了限制。摒弃了传统数值解法中整体迭代的思想,结合离散正弦变换理论(DST),基于27点四阶差分格式,将三维泊松方程求解算法在算法级进行修改和并行优化,把整个求解问题转化成多个独立的问题进行求解,稳定性和并行性能得到大幅提升。对于确定的离散化形式,可以使用同一套参数解决不同的泊松方程,大大提高了编程效率。基于共享存储并行模型实现了该算法,实验结果显示,对于给出的实例,新算法具有较好的加速效果,计算结果精度误差约为10e-5,在可接受范围内,并且计算精度随着维数的升高具有一定提升。     

基于FFT的泊松方程快速求解器的硬件实现

针对传统的泊松方程求解算法执行效率低、功耗大,很难满足实际需要的缺点,设计了一种FPGA硬件平台的泊松方程快速求解器。设计采用软件与硬件结合的方式,由软件执行控制复杂、计算量较小的任务,而由硬件完成控制简单、计算量大的任务,从而达到硬件加速的目的。在FPGA平台上,独立设计的FFT协处理器可以流水和高度并行化的处理数据,提高了求解器的性能。实验结果表明,硬件实现的基于FFT的泊松方程快速求解器具有较高的计算性能和良好的可扩展性。     

二维泊松问题的并行共轭梯度算法

该论文研究了利用并行共轭梯度算法求解二维泊松方程的方法,在由24台微机组成的机群上进行了实验。实验数据表明并行共轭梯度算法适用于求解二维泊松方程,它具有收敛快,可扩展性强的特点。在实验的基础上提出并验证了适用于并行共轭梯度算法的合理计算节点数的选择函数。     

大规模集群上多维FFT算法的实现与优化研究

快速傅里叶变换(fast Fourier transform,FFT)是用于计算离散傅里叶变换(discrete Fourier transform,DFT)或其逆运算的快速算法,在工程、科学和数学领域的应用非常广泛,例如信号分解、数字滤波、图像处理等。因此,在实际应用中对FFT算法进行细粒度优化是非常重要的。研究了FFT算法常用的分解策略以及FFT算法在大规模集群系统上的并行实现,并提出了相关的优化策略。在此基础上,对多种FFT算法在不同平台上进行了性能评估,并分析了各算法的实现、优缺点及其在大规模计算时的可扩展性。实验结果表明,相关研究有助于对现有的FFT算法进行进一步的优化,以及指导如何在大规模CPU+GPU的异构系统上根据不同需求选择实现性能更优的FFT算法。     

电大尺寸复杂目标散射问题的并行矩量法分析

目前飞机和导弹等电大尺寸复杂目标的电磁散射特性采用高频分析法精度较低,本文研究在PC集群环境下三维导体散射问题矩量法的并行化,并应用于复杂目标的RCS计算。本文使用混合积分方程,再用RWG基函数进行离散,阻抗矩阵元素按行分解,并行共轭梯度法进行求解,通过MPI通信库实现。最后使用基准目标NASA杏仁核验证了该并行计算的准确性。     

基于卷积金字塔的屏蔽泊松方程快速求解算法

屏蔽泊松方程在图像视频处理和图形学领域有着广泛应用,传统上一般借助离散余弦变换或快速傅里叶变换求解,计算复杂度为O(nlogn).提出了一种基于卷积金字塔的快速近似求解算法,将屏蔽泊松方程求解视为一个"大核"卷积过程,利用卷积金字塔,将"大核"卷积分解为若干个"小核"卷积,从而将计算复杂度改善至线性.实验发现,在图像无缝拼合和梯度域绘制的应用中,对于千万像素级别图像,所提算法能获得5～6倍的性能提升.进一步,屏蔽泊松方程求解也是许多图像迭代算法的中间步骤,以加权最小二乘图像光滑和基于总变差正则化的图像重建算法为例,运用所提算法,在视觉效果和均方误差上都有着很好的近似,在速度上有显著的提升.     

大尺度图像编辑的泊松方程并行多重网格求解算法

随着获取设备的发展,大尺度、高分辫率数字图像已逐步进入人们的生活,大尺度图像的梯度域编辑显得更为重要,求解大规模未知数的泊松方程是大尺度图像梯度域编辑的关键。传统多重网格算法的迭代、约束和插值操作单独进行,内存和外存间通讯量大,算法效率低,为此提出了一种面向大尺度图像梯度域编辑的并行多重网格求解泊松方程的算法。该算法利用多重网格的迭代、约束和插值过程的内存数据访问局部性和更新相关性,构造滑动工作窗口,使迭代、约束和插值操作并行运行,提高了多重网格算法求解泊松方程的计算效率。全景图拼接实验表明,所提算法的运行效率高于超松弛迭代、高斯塞德尔迭代和传统多重网格算法。     

三维热传导方程的Krylov子空间方法并行分析

热传导方程在地下水流动数值模拟、油藏数值模拟等工程计算中有着广泛应用,其并行实现是加速问题求解速度、提高问题求解规模的重要手段,因此热传导方程的并行求解具有重要意义。对Krylov子空间方法中的CG和GMRES算法进行并行分析,并对不同的预处理CG算法作了比较。在Linux集群系统上,以三维热传导模型为例进行了数值实验。实验结果表明,CG算法比GMRES算法更适合建立三维热传导模型的并行求解。此外,CG算法与BJACOBI预条件子的整合在求解该热传导模型时,其并行程序具有良好的加速比和效率。因此,采用BJACOBI预处理技术的CG算法是一种较好的求解三维热传导模型的并行方案。     

多尺度并行坐标插值实时图像克隆算法

作为一种重要的数字图像合成编辑技术,图像克隆能够将源图像中的克隆区域平滑自然地嵌入目标图像的指定位置。 传统的图像克隆技术通过分析图像的梯度域并求解泊松方程来获取图像信息, 具有算法复杂度高、内存消耗大的缺点, 从而限制了其在高分辨率图像中的实时应用。本文提出了一种改进的均值坐标计算方法, 将图像克隆转化为高效且易于实现的图像插值流程。此外本文还采用多尺度和GPGPU并行计算技术进一步提升了算法的整体运算效率, 从而能够实现对100万像素图像区域的实时克隆。     

基于CUDA的二维泊松方程快速直接求解

二维泊松方程离散化之后可以转化为一个具有特殊格式的块三对角方程的求解问题,通过对这一结构化线性方程组的研究,提出了一个适用于统一计算架构(CUDA)的泊松方程并行算法.该算法通过离散正弦变化,可以将计算任务划分为若干相互独立的部分进行求解,各部分求解完成后再通过一次离散正弦变换即可获得最终解,整个求解过程只需要两次全局通信.结合GPU的硬件特征进行优化之后,该算法相比CPU上的串行算法可以获得10倍以上的加速比.     

广义稠密对称特征问题标准化算法在GPU集群上的有效实现

广义稠密对称特征问题的求解是许多应用科学和工程的主要任务,并且是计算电磁学、电子结构、有限元模型和量子化学等计算中的重要部分。将广义对称特征问题转化为标准对称特征问题是求解广义稠密对称特征问题的关键计算步骤。针对GPU集群,文中给出了广义稠密对称特征问题标准化块算法在GPU集群上基于MPI+CUDA的实现。为了适应GPU集群的架构,广义对称特征问题标准化算法将正定矩阵的Cholesky分解与传统的广义特征问题标准化块算法相结合,降低了标准化算法中不必要的通信开销,并且增强了算法的并行性。在基于MPI+CUDA的标准化算法中,GPU与CPU之间的数据传输操作被用来掩盖GPU内的数据拷贝操作,这消除了拷贝所花费的时间,进而提高了程序的性能。同时,文中还给出了矩阵在二维通信网格中行通信域和列通信域之间完全并行的点对点的转置算法和基于MPI+CUDA的具有多个右端项的三角矩阵方程BX=A求解的并行块算法。在中科院计算机网络信息中心的超级计算机系统“元”上,每个计算节点配置2块Nvidia Tesla K20 GPGPU卡及2颗Intel E5-2680 V2处理器,使用多达32个GPU对不同规模矩阵的基于MPI+CUDA的广义对称特征问题标准化算法进行测试,取得了较好的加速效果与性能,并且具有良好的可扩展性。当使用32个GPU对50000×50000阶的矩阵进行测试时,峰值性能达到了约9.21 Tflops。     

Parallel multigrid finite volume computation of three-dimensional thermal convection

A parallel implementation of the finite volume method for three-dimensional, time-dependent, thermal convective flows is presented. The algebraic equations resulting from the finite volume discretization, including a pressure equation which consumes most of the computation time, are solved by a parallel multigrid method. A flexible parallel code has been implemented on the Intel Paragon, the Cray T3D, and the IBM SP2 by using domain decomposition techniques and the MPI communication software. The code can use 1D, 2D, or 3D partitions as required by different geometries, and is easily ported to other parallel systems. Numerical solutions for air (Prandtl number Pr = 0.733) with various Rayleigh numbers up to 10⁷ are discussed.     

ParaC:面向GPU平台的图像处理领域的编程框架

GPGPU加速器是当前提高图像处理算法性能的主流加速平台,但是,在GPGPU平台上,同一个程序充分利用硬件体系结构特征和软件特征的优化版本与简单实现版本在性能上会有数量级的差异。GPGPU加速器具有多维多层的大量执行线程和层次化存储体系结构,后者的不同层次具有不同的容量、带宽、延迟和访问权限。同时,图像处理应用程序具有复杂的计算操作、边界处理规则和数据访问特性。因此,任务的并发执行模式、线程的组织方式和并发任务到设备的映射不仅影响到程序的并发度、调度、通信和同步等特性,而且也会影响到访存的带宽、延迟等。因此,GPGPU平台上的程序优化是一个困难、复杂且效率较低的过程。本文提出基于语言扩展的领域编程模型：ParaC。ParaC编程环境利用高层语言扩展描述的程序语义信息,自动分析获取应用程序的操作信息、并发任务间的数据重用信息和访存信息等程序特征,同时结合硬件平台特征,利用基于领域先验知识驱动的编译优化模型自动生成GPGPU平台上的优化代码,最后,利用源源变换编译器生成标准OpenCL程序。本文在测试用例上的实验结果表明,ParaC在GPGPU平台上自动生成的优化版本相对于手工优化版本的加速比最高达到3.22倍,但代码行数只是后者的1.2%到39.68%。     

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

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

基于MPI的并行计算集群通信及应用

对能有效解大型稀疏矩阵方程的LSQR串行算法进行了并行化分析，并应用可移植消息传递标准MPI的集群通信机制在分布式存储并行系统上设计和实现了LSQR并行算法，该并行算法和程序在地震表层模型层析反演中得到了有效的应用。     

基于通信优化的Infiniband集群MPI作业加载*

针对如何缓解Infiniband集群中因通信冲突引起的MPI程序性能下降问题进行了研究,从系统管理的角度出发,提出了通过改变进程映射来优化MPI作业加载方案从而优化应用程序通信性能的方法,设计了用于评价MPI作业加载方案的通信性能损失系数（CPLR）指标,基于模拟退火算法设计了优化加载方案的搜索算法,并对所提出的指标和算法进行了实现和测试。测试结果表明,经过优化加载后的MPI程序在通信性能上有一定程度的提高。     

Parallelization of Full Search Motion Estimation Algorithm for Parallel and Distributed Platforms

This work presents an efficient method to map the Full Search algorithm for Motion Estimation (ME) onto General Purpose Graphic Processing Unit (GPGPU) architectures using Compute Unified Device Architecture (CUDA) programming model. Our method jointly exploits the massive parallelism available in current GPGPU devices and the parallelism potential of Full Search algorithm. Our main goal is to evaluate the feasibility of video codecs implementation using GPGPUs and its advantages and drawbacks compared to other platforms. Therefore, for comparison reasons, three solutions were developed using distinct programming paradigms for distinct underlying hardware architectures: (i) a sequential solution for general-purpose processor (GPP); (ii) a parallel solution for multi-core GPP using OpenMP library; (iii) a distributed solution for cluster/grid machines using Message Passing Interface (MPI) library. The CUDA-based solution for GPGPUs achieves speed-up compatible to the indicated by the theoretical model for different search areas. Our GPGPU Full Search Motion Estimation provides 2×, 20× and 1664× speed-up when compared to MPI, OpenMP and sequential implementations, respectively. Compared to state-of-the-art, our solution reaches up to 17× speed-up.     

Multi-GPU performance of incompressible flow computation by lattice Boltzmann method on GPU cluster

GPGPU has drawn much attention on accelerating non-graphic applications. The simulation by D3Q19 model of the lattice Boltzmann method was executed successfully on multi-node GPU cluster by using CUDA programming and MPI library. The GPU code runs on the multi-node GPU cluster TSUBAME of Tokyo Institute of Technology, in which a total of 680 GPUs of NVIDIA Tesla are equipped. For multi-GPU computation, domain partitioning method is used to distribute computational load to multiple GPUs and GPU-to-GPU data transfer becomes severe overhead for the total performance. Comparison and analysis were made among the parallel results by 1D, 2D and 3D domain partitionings. As a result, with 384 × 384 × 384 mesh system and 96 GPUs, the performance by 3D partitioning is about 3-4 times higher than that by 1D partitioning. The performance curve is deviated from the idealistic line due to the long communicational time between GPUs. In order to hide the communication time, we introduced the overlapping technique between computation and communication, in which the data transfer process and computation were done in two streams simultaneously. Using 8-96 GPUs, the performances increase by a factor about 1.1-1.3 with a overlapping mode. As a benchmark problem, a large-scaled computation of a flow around a sphere at Re = 13,000 was carried on successfully using the mesh system 2000 × 1000 × 1000 and 100 GPUs. For such a computation with 2 Giga lattice nodes, 6.0 h were used for processing 100,000 time steps. Under this condition, the computational time (2.79 h) and the data communication time (3.06 h) are almost the same.     

A balanced accumulation scheme for parallel PDE solvers

We present a tailored load balancing technique that addresses specific performance issues in the boundary data accumulation algorithm for non-overlapping domain decompositions. The technique is used to speed up a parallel conjugate gradient algorithm with an algebraic multigrid preconditioner to solve a potential problem on an unstructured tetrahedral finite element mesh. The optimized accumulation algorithm significantly improves the performance of the parallel solver and we show up to 50 % runtime improvements over the standard approach in benchmark runs with up to 48 MPI processes. The load balancing problem itself is a global optimization problem that is solved approximately by local optimization algorithms in parallel that require no communication during the optimization process.     

一种优化MPI程序性能的改进方法

在分布式存储系统上,MPI已被证实是理想的并行程序设计模型。MPI是基于消息传递的并行编程模型,进程间的通信是通过调用库函数来实现的,因此MPI并行程序中,通信部分代码的效率对该并行程序的性能有直接的影响。通过用集群通信函数替代点对点通信函数以及通过派生数据类型和建立新通信域这两种方式,两次改进DNS的MPI并行程序实现,并通过实验给出一个优化MPI并行程序的一般思路与方法。