一种求解线性方程组的SOR并行算法

逐次松弛迭代算法(SOR)是求解线性方程组的一种常用迭代算法,当系数矩阵正定时,它具有较快的收敛速度。但是,由于每个迭代步内存在数据相关,它难以实现并行计算。目前的SOR并行算法采用数据分解的方法,但由于该法并行区域过小,同步通讯代价大,并行效率低。本文提出了SOR的一种新型并行算法,该算法与传统SOR方法等价,具有相同的收敛性和迭代结果。该并行算法通过矩阵分块增大了可并行计算的区域,并引入流水线技术,利用各处理器间通讯与计算时间的重叠,获得较理想的并行加速效率。通过多核微机以及小规模集群上的数值实验证明,本文提出的SOR并行算法在求解大型稠密线性方程组时具有较好的并行效率。     

一类大规模稀疏矩阵特征问题求解的并行算法

本文提出一种求解大规模稀疏矩阵特征问题的并行共轭梯度算法.为了提高算法的并行效率,设计了负载平衡的行划分方式,实现了计算和通信重叠的稀疏矩阵重排序方法,通过预处理减少计算过程中各进程间消息传递的通信量.另外,基于多核处理器高性能并行计算,实现了MPI和细粒度(线程级)OpenMP混合并行算法.在深腾7800并行计算机上对并行算法进行了测试,结果表明在进程数增多时并行算法可保持通信时间稳定性,在并行计算机上有很好的扩展性,适合大规模稀疏特征问题的求解.     

基于MPI的并行Kriging空间降水插值

为减少空间降水插值的计算时间,以MPI并行接口为技术手段,采用数据划分建模方法,实现改进Kriging算法的并行算法.在Linux操作系统上搭建并行计算环境,试验数据表明,该并行算法能有效节省计算时间并具有良好的加速比、并行效率和扩展性.为Kriging插值算法的并行化实现和应用提供有意义的参考.     

面向异构架构的传递闭包并行算法

传统求图传递闭包的方法存在计算量大与计算时间长的问题。为加快处理大数据量的传递闭包算法的计算速度,结合算法密集计算和开放式计算语言（OpenCL）框架的特征,采用本地存储器优化的并行子矩阵乘和分块的矩阵乘并行计算,提出一种基于OpenCL的传递闭包并行算法。利用本地存储器优化的并行子矩阵乘算法来优化计算步骤,提高图形处理器（GPU）的存储器利用率,降低数据获取延迟。通过分块矩阵乘并行计算算法实现大数据量的矩阵乘,提高GPU计算核心的利用率。数据结果表明,与CPU串行算法、基于开放多处理的并行算法和基于统一设备计算架构的并行算法相比,传递闭包并行算法在OpenCL架构下NVIDIA GeForce GTX 1070计算平台上分别获得了593.14倍、208.62倍和1.05倍的加速比。     

粒度可调的并行Kriging地层空间插值算法

为提高层状地层空间数据插值的计算速度和实现系统负载平衡,在采用动态调整并行粒度策略的基础上开发混合粒度的并行Kriging插值算法.在此算法中,根据CPU与地层层数之间的数量关系动态调整并行计算的粒度,优先使用粗粒度的并行计算策略,同时利用中粒度并行算法平衡负载.基于Windows2000 操作系统搭建了PC机群并行环境,大量的试验统计数据表明该方法具有良好的可扩展性和并行计算效率.     

多体动力学优化的并行SQP方法

并行计算的发展大大提高计算机的计算效率,降低计算时间.针对多体动力学的优化问题,分析了求解灵敏度的三种方法的并行性,建立了有限差分法与直接微分法的并行算法.同时采用并行Armijo线性搜索,构成了完整的并行序列二次规划(SQP)算法.将上述算法应用到曲柄滑块的优化中,并与串行SQP算法进行了比较,证实了并行SQP算法可以大大降低计算时间.上述研究为多体动力学优化提供了一种并行求解思路.     

海量数据流的提升小波变换并行算法研究

提升小波变换算法在图像去噪中有广泛的应用,但是对于海量数据流该算法计算速度缓慢无法达到实时性.为了提高计算速度,提出一种基于图形处理器(GPU)的并行计算策略,把传统提升小波变换算法映射到CUDA编程模型,利用具有大规模并行计算特征的GPU作为计算设备,结合GPU存储器的优势实现了基于滑动窗口的提升小波变换并行算法.实验的测试结果表明,在现有的实验条件下,随着图像的增加,提升小波变换并行算法可以把计算速度提高50倍,效率提高明显.本文提出的方法也可以用其他图像处理算法的并行化.     

水平集中符号距离函数并行降维计算

目的 符号距离函数在水平集图像分割,视觉特征提取等图像处理领域有重要应用。随着图像分辨率越来越高,符号距离函数计算效率直接影响图像处理速度,为实现高分辨率图像实时处理,本文在降维法的基础上提出了并行算法,并针对并行计算对降维法进行了改进。方法 降维法将2维距离计算转化为两个1维距离计算,并采用抛物线下界法计算1维距离,是当前最快的一种符号距离计算方法。首先利用行和列计算的独立性,提出了降维法的并行算法。然后再对并行降维法进行改进,提出了抛物线下界法的并行算法。该方法采用多线程分段并行计算抛物线下界,即每个像素点与段内相邻像素点并行进行抛物线求交运算,快速搜索抛物线下界,从而实现了抛物线下界法的分段并行距离函数计算。所有并行算法在CUDA平台上采用GPU通用并行计算方法实现。结果 对不同分辨率及包含不同曲线的9幅图像进行实验测试,在距离计算误差小于1的条件下,并行降维算法对所有测试图像计算时间均小于0.06 s,计算效率比串行方法有了10倍以上的提升,改进并行降维算法对所有测试图像计算时间均小于0.03 s,计算效率比串行方法有了20倍左右的提升。结论 该方法实现了符号距离函数的快速并行计算,其优势在于当图像分辨率较高时仍然能够实现实时处理。     

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

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

基于BSP并行计算模型的并行微粒群算法

在对标准微粒群算法分析的基础上,将它与BSP并行计算模型相结合,设计并实现了一种基于BSP并行计算模型的并行微粒群算法.这种基于BSP并行计算模型的并行微粒群算法改变了标准微粒群算法的结构,提高了算法求解效率.实验结果表明,该并行算法的性能比标准微粒群算法有了很大的提高.     

Study on the propagation properties of TM electromagnetic wave in Lossy left‐handed material based on CUDA‐implemented parallel

By using the method of Finite Difference Time Domain (FDTD) and the technology of Compute Unified Device Architecture (CUDA), the propagation characteristics of electromagnetic waves in Left‐Handed Materials (LHM) have been studied in this paper. The LHM slab was matched with the free space and the secondary focusing phenomenon of LHM was simulated. Compared with the serial FDTD program, our work showed that this method had a high accuracy. The phase compensation effect and the inverse Snell effect of LHM were also discussed by using the parallel FDTD method based on CUDA, which further proved that our results were consistent with the theoretical study. By comparing the calculation time of traditional FDTD program with that of the CUDA based parallel FDTD program, we conclude that the latter is more efficient than the former. This parallel method can be used as a more efficient way to study LHM.     

一种等值线填充并行算法

通过获得的计算机CPU个数对要形成的网格场进行子区域划分,对各子区域用反距离加权插值法,双线形插值方法将离散气象数据格点化后形成网格数据场,对各子区域进行OPENMP的并行算法处理形成等值线填色场。实验结果表明,并行计算使系统的处理速度有较大提高。     

基于CUDA架构的三维CPML-FDTD并行方法

为解决时域有限差分（FDTD）算法应用于电大尺寸目标仿真的巨大耗时问题,应用FDTD算法的并行特性和通用图形处理器（GPGPU）技术,实现了一种基于计算统一设备架构（CUDA）的三维FDTD并行计算方法,采用了时域卷积完全匹配层（CPML）吸收边界条件模拟开域空间,对不同网格数目标仿真计算。进一步结合FDTD算法和CUDA的特点进行了优化,当计算空间元胞数在十万数量级及以上时,优化前后GPU运算相对于同时期的CPU分别可获得10和25倍以上的加速,结果表明该方法较适合用于实际电磁问题的仿真。     

A new parallel meshing technique integrated into the conformal FDTD method for solving complex electromagnetic problems

A new efficient parallel finite-difference time-domain （FDTD） meshing algorithm, based on the ray tracing technique, is proposed in this paper. This algorithm can be applied to construct various FDTD meshes, such as regular and conformal ones. The Microsoft F# language is used for the algorithm coding, where all variables are unchangeable with its parallelization advantage being fully exploited. An improved conformal FDTD algorithm, also integrated with an improved surface current algorithm, is presented to simulate some complex 3D models, such as a sphere ball made of eight different materials, a tank, a J-10 aircraft, and an aircraft carrier with 20 aircrafts. Both efficiency and capability of the developed parallel FDTD algorithm are validated. The algorithm is applied to characterize the induced surface current distribution on an aircraft or a warship.     

The sub-implicit method: New multiprocessor algorithms for old implicit codes

This paper presents a new approach to the parallel solution of an implicit system of difference equations. The sub-implicit method operates on sub-regions of the data which are evaluated at spatial points and synchronous times. Each sub-region has a border node which is shared with an adjacent sub-region (in one dimension). Values for this shared node are computed independently by the two solution processes for two adjacent sub-regions. Nodes outside the sub-region are treated as having fixed values during the solution. At the finish of the two sub-region solutions, the two sub-regions are blocked against further changes (a pairwise synchronization) and the two different values for the shared node are reconciled. This can be done in such a way that energy conservation is exact. Results for test problems for heat diffusion in one dimension are given and compared against standard methods and analytic results. Implementation of the method into a demonstration two-dimensional hydrodynamics code SIMPLE is described. The best speedups observed for parallel execution of this version of SIMPLE on a twelve CPU Sequent multiprocessor were 9.6 for 50 by 50 grid and 10.4 for a 95 by 95 grid. Some generalization of this approach are discussed.     

三维FDTD众核算法的设计与实现

在电磁学中,时域有限差分算法(FDTD)能够精确地模拟空间中电磁场的变化,在电介质器件设计领域得到了广泛的应用。众核(many-core)处理器片上计算资源丰富,对于计算密集型课题有较好的适应性。通过对麦克斯韦方程FDTD仿真算法的分析,并根据众核处理器的特性,实现了FDTD算法的众核并行。实验结果表明,FDTD算法在众核处理器平台上具有较好的计算效率,能够很好地发挥众核结构的优势。     

光子晶体并行Matlab仿真研究与实现

由于Madab软件的网络通信局限,使得在并行时域有限差分(FDTD)计算仿真中,难以实现子域间的消息发送与接收操作.针对这个问题,提出一种新的基于磁盘-内存互逆映射的解决方法,在简化并行FDTD算法实现的同时,显著提高了算法执行性能.作为算法实现的应用,对光子晶体光波导的电磁耦合效应进行了数值仿真研究,结果证实:波导耦合区域内不同半径比介质柱所导致的结构变化将造成耦合长度的改变,且其耦合关系曲线具有平稳区与迅变区两类不同特性的变化范围区间.     

大规模并行时域有限差分法电磁计算研究

基于我国超级计算机平台,开展了大规模并行时域有限差分法(Finite-Difference Time-DomainFDTD)的性能和应用研究。在我国首台百万亿次"魔方"超级计算机、具有国产CPU的"神威蓝光"超级计算机和当前排名世界第一的"天河二号"超级计算机上就并行FDTD方法的并行性能进行了测试,并分别突破了10000 CPU核,100000 CPU核和300000 CPU核的并行规模。在不同测试规模下,该算法的并行效率均达到了50%以上,表明了本文并行算法具有良好的可扩展性。通过仿真分析多个微带天线阵的辐射特性和某大型飞机的散射特性,表明本文方法可以在不同架构的超级计算机上对复杂电磁问题进行精确高效电磁仿真。     

基于OpenCL的GPU加速三维时域有限差分电磁场仿真算法研究

提出了一种基于开放运算语言（OpenCL）的GPU加速三维时域有限差分（FDTD）电磁场仿真计算的方法．该方法利用图形处理单元（GPU）的并行处理特性并结合OpenCL接口标准实现了时域卷积完全匹配层（CPML）吸收边界条件的三维FDTD的高性能加速计算．首先设置FDTD仿真参数并动态申请内存空间,然后初始化OpenCL的计算参数,对三维电磁模型基于OpenCL进行FDTD加速仿真．本方法显著提升了FDTD电磁场仿真速度,与利用CPU计算相比速度提升可达5-8倍,且具有CPML吸收边界条件,可以模拟电磁波在自由空间的传播;基于OpenCL编译的语言程序可以运行在CPU或GPU硬件上,并可充分发挥多核CPU的并行计算能力,使得FDTD电磁场仿真具有更广泛的实际应用．     

MPICH在Windows操作系统中的实现与应用

该文给出了对应于MPI标准的MPICH软件包在Windows操作系统中的配置和在MSVC＋＋中的实现方法，并对MPI与C／C＋＋绑定的基本编程进行了简要介绍。然后将其与一种电磁场数值算法——时域有限差分法相结合，以一维情况为例，讨论了网络并行时域有限差分法的实现方法。通过在由两台PC机构成的最简单的PC机群上的编程实现，验证了这种方法的可行性和高效性，实验结果表明通过MPICH软件包实现时域有限差分法的网络并行运算，可以使这种算法的加速比达到1．8。