边缘海静力数值预报模式并行算法研究

边缘海静力数值模式是国内针对边缘海特点自主开发的数值预报模式,但该模式因物理求解方程较多且采用不宜并行化的SOR求解算法而程序计算时间过长。针对上述问题,提出基于三维网格和海洋模式特点的SOR并行求解算法,该算法在保留三维网格数据间依赖关系的同时,有效解决了SOR迭代算法难以并行化的问题。同时,引入通信避免算法,采用MPI非阻塞通信方式,细分计算和通信过程,利用计算有效隐藏通信开销,提高了并行程序效率。实验结果表明,并行后的边缘海静力数值模式程序的性能相对串行程序提升了60.71倍,3天(25920计算时间步)预报结果的均方根误差低于0.001,满足海洋数值预报的时效性和精度要求。     

动态中子输运方程迭代初值的选取方法

研究离散纵标动态中子输运方程迭代求解时,迭代初值的不同选取方法,设计合理的迭代初值可以适当放宽对时同步长的限制,缩短计算时间.设计四种迭代初值并应用于数值求解中的等比格式和菱形格式,其中等比格式形成非线性离散方程,菱形格式形成线性离散方程.考察不同迭代初值的计算效率,分别对物理量变化平缓以及变化剧烈的问题进行考察.数值算例表明构造的基于物理量随时间走势的预估值作为迭代初值优势明显,这在保证计算精度的前提下提高了数值计算效率.     

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

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

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

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

不可压N-S方程的高效并行直接求解

对不可压N-S方程的数值计算,当计算规模增大时,不论是采用湍流模型计算还是直接数值模拟（Direct Numerical Simulation,DNS）,大规模的并行计算都难以实现.该问题的关键是求解全场联立的压力泊松方程的并行计算技术.利用并行近似解求解方案,创建高效大规模并行计算的不可压N S方程的直接求解方法.三维窄方腔热对流的DNS计算结果表明,该直接求解并行计算方法具有很好的并行效率,并且计算的三维湍流热对流的特性是合理的.     

三维Navier-Stokes方程分步法的并行算法在异构平台上实现初探

本文选取了三维不可压缩流动方程的分步法(fractional-step method),其中动量方程使用BiCGSTAB算法进行迭代求解,而压力泊松方程使用Fourier变换法进行直接求解。本文研究该算法在集群平台上的并行算法,从区域分解入手,分析一维、两维、三维区域划分三种情况下,各并行处理器上的计算量与通讯量,根据分析结果使用两维区域分解。分析BiCGSTAB算法和泊松Fourier变换法在GPGPU异构平台上的移植方法。最后,本文分析了BiCGSTAB和泊松方程Fourier变换法两种算法在CPU集群和GPGPU异构平台上的并行性能结果。     

一种适于黑油模型并行的快速新解法--改进的GMRES算法

本文应用区域分解算法进行油藏模拟的并行计算研究,寻求可高效并行求解三维三相数值模拟问题的最优算法。在对流行的预处理共轭梯度算法及GMRES算法进行对比研究的基础上,提出了改进的GMRES算法,这种算法具有迭代参数不需优化、收敛快、可得到较精确解等优点。应用该解法对三维三相黑油模型软件进行并行化改造。通过模型及实际油藏计算,比软件原算法及GMRES算法的计算速度得到大幅度提高。并行效率较高,并行化后的模拟软件可以有效地解决大型整装构造油藏的数值模拟问题。     

三维Euler方程的隐式间断有限元算法

为了求解三维欧拉方程,对隐式时间离散格式间断有限元方法进行了研究。根据间断Galerkin有限元方法思想,构造内迭代SOR-LU-SGS隐式时间离散格式,结合当地时间步长技术、多重网格方法,实现了三维流场的计算。数值计算了ONERAM6机翼、大攻角尖前缘三角翼以及DLR-F4翼身组合体的亚声速绕流问题。结果表明,加入SOR内迭代步的LU-SGS隐式算法具有较大的优势,相较于GMRES算法所占用的内存少且收敛速度相当,是LU-SGS算法的三倍以上。针对三维算例,具有较好的稳定性和较高的收敛速度,能够给出准确的流场信息。与原方法相比,SOR-LU-SGS方法无论是在迭代步数上还是在CPU时间上,效率均有明显提高,适合于三维复杂流场计算。     

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

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

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

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

基于局部自适应混合积分的动态布料模拟快速方法

针对布料动态模拟中快速稳定求解的瓶颈问题,提出了一种局部自适应的混合积分方法。在每一时间步长,网格中质点利用自身模拟参数求解一稳定的判断准则,据此自适应判定该质点相连弹簧不同弹性力部分引起的运动方程采用何种数值积分求解,从而有效提高了模拟效率且可以并行计算。另外,针对线性方程组的特点,用快速超松弛迭代法代替传统的共轭梯度法来求解,进一步提高了系统的性能表现。实验表明,该方法具有近似线性的复杂度,便于并行计算,并有良好的稳定视觉效果。     

基于法矢控制的B样条曲面逼近的PIA方法

提出了一种基于法矢控制的 B 样条曲面逼近的渐进迭代逼近(PIA)算法。一方面该方法将离散数据点的切失、曲率、法矢等几何特征充分应用到离散数据点的逼近问题上,利用数据点两个方向的切矢构造出数据点的法矢约束来控制逼近曲面形状,相比于无法矢控制的 B 样条曲面逼近的渐进迭代逼近(PIA)方法,逼近曲面更光顺,可获得更好的逼近效果。另一方面由于该算法选取主特征点作为控制顶点,所以允许在曲面拟合中控制顶点的数目小于数据点的数目。而且PIA算法的每次迭代过程中的各个步骤都是独立的,很容易被应用到并行计算上,可提高计算效率。本文还给出了一些实例来验证该算法的有效性。     

Parallel asynchronous iterations for the solution of a 3D continuous flow electrophoresis problem

This paper deals with the parallel numerical solution of a 3D continuous flow electrophoresis problem governed by Navier-Stokes equations coupled with transport and potential equations. For this problem, using the properties of the discrete operators, the convergence of synchronous and asynchronous parallel Schwarz alternating methods is analysed. Finally, parallel solvers are implemented and the results of simulations are given.     

An elimination approach for fast parallel solution of the model fourth-order elliptic problem

A fast algorithm is developed for the parallel numerical solution of the first biharmonic boundary value problem on a rectangular region with N² interior grid points. The parallel computer considered is of SIMD type. The iterative procedure where one iteration consists in solving two transformed Poisson equations with relaxation is used. This approach allows one to apply the direct block-elimination method with parallel algorithm for linear recurrence relations efficiently to the evaluation of one iteration. For our algorithm the time per iteration does not exceed 9 log N time units, on N² processors. Thus, the technique presented brings a reduction in the arithmetic steps required for the solution of the problem considered.     

一种基于SMP的并行逐次超松弛迭代法

逐次超松弛迭代方法被广泛应用于油藏数值模拟中压力方程的求解.其并行实现是提高模拟速度的重要途径.传统并行方案大都只是在一次迭代内进行数据划分,而没有进一步将数据划分与迭代空间划分相结合,故针对SOR算法和SMP（symmetric multi-processors）系统的特点,以OpenMP为并行化实现工具,提出了基于SMP的并行逐次超松弛迭代方法（parallelSOR）.方法通过改变不同迭代步内数据点的更新次序,使不同区域内的数据点可以并行执行多次迭代.总结出针对三维油藏区域在数据空间划分和迭代空间合并上相对较优的策略,分析了迭代过程中网格块的生长形状.与传统的并行策略相比,该方法具有可减小同步开销、改进数据局部性、cache命中率高等优点.实验结果表明,该方法具有较高的加速比和效率.     

一类基于迭代空间条块的并行有限差分Stencil 算法

高效的并行有限差分Stencil 算法对于求解大型线性方程组是十分重要的.针对并行有限差分Stencil 算法中数据局部性差、同步和通信开销大的问题.首先改进传统有限差分Stencil 算法,提出了多层对称遍历有限差分Stencil 算法.然后给出了以迭代空间条块序作为执行序的串行算法,通过沿时间轴对迭代空间进行时滞划分,在不改变迭代算法性质的同时,对迭代空间条块内部多次迭代计算,提高算法的数据局部性.最后提出一种基于迭代空间条块的并行算法,该算法利用改进的多面体模型对迭代空间网格划分,并通过网格条块重排序减少了Cache 缺失率、通信启动和同步次数.理论分析和实验结果表明,该并行模型比传统的区域分解方法和红黑排序并行算法具有更好的数据局部性,并行效率和可扩展性.     

基于IWOA算法求解并联冷机负荷分配问题

中央空调系统并联冷水机组系统能耗非常大,如果操作不当,能耗会大大增加。针对OCL问题提出了一种求解连续非线性优化问题的改进鲸群优化算法,首先,为使后续迭代寻优的搜索空间更精确,运用混沌映射初始化种群,使初始解均匀遍布解空间。其次引入变异指数对收敛因子进行改进,平衡了局部勘探和全局勘探的关系。之后引入正弦和余弦使算法收敛到全局最优解,防止了算法过早收敛,提高了算法的收敛精度。最后,通过两个典型的案例来评估IWOA算法的性能,并将其与应用于OCL问题的其他优化算法进行了比较。结果表明,IWOA算法是解决OCL问题的有效方法。此外,算法性能的比较显示,IWOA算法在收敛速度和电能消耗方面相比于其他应用于OCL问题的优化方法提供了更好的解决方案。     

一种基于场景图分割的混合式多视图三维重建方法

针对大范围三维重建, 重建效率较低和重建稳定性、精度差等问题, 提出了一种基于场景图分割的大范围混合式多视图三维重建方法.该方法首先使用多层次加权核K均值算法进行场景图分割; 然后,分别对每个子场景图进行混合式重建, 生成对应的子模型, 通过场景图分割、混合式重建和局部优化等方法提高重建效率、降低计算资源消耗, 并综合采用强化的最佳影像选择标准、稳健的三角测量方法和迭代优化等策略, 提高重建精度和稳健性; 最后, 对所有子模型进行合并, 完成大范围三维重建.分别使用互联网收集数据和无人机航拍数据进行了验证, 并与1DSFM、HSFM算法在计算精度和计算效率等方面进行了比较.实验结果表明, 本文算法大大提高了计算效率、计算精度, 能充分保证重建模型的完整性, 并具备单机大范围场景三维重建能力.     

求解TSP问题的自适应离散型布谷鸟算法

对于求解的TSP问题,提出了一种自适应离散型布谷鸟算法（Adaptive Discrete Cuckoo Search,ADCS）。在基于布谷鸟搜索算法（Cuckoo Search,CS）的搜索原理下构造TSP问题的路径求解策略。针对离散型算法整体调整容易破坏已形成的较优路径和随着算法迭代数目增加导致种群多样性下降这两个缺陷,设计了一种针对路径的自适应型局部调整算子和全局随机扰动策略,采用了简单的2-opt优化算子作为局部优化算子以加快算法的收敛速度。最后采用多组不同规模的标准TSPLIB数据与其他的优化算法进行对比实验,结果表明ADCS算法在求解精度和稳定性方面具有优势。     

矩阵乘并行算法的仿真与性能分析

为了优化矩阵乘法的并行运算效率,提高流水线的性能,采用了基于Strassen算法的矩阵来运算,并通过缟码在DLX模拟的并行流水线环境中仿真运行.实验结果表明,优化后的矩阵秉算法降低了时间复杂度,减少了指令条数和运算周期,显著地提高了流水线上矩阵秉法的并行运算效率.