全球(z)双三次数值模式并行算法设计与实现

针对双三次数值天气预报模式进行了并行算法研究。采用一维区域分解算法,借鉴块棋盘划分矩阵转置算法,设计和实现了数据转置通信算法,并采取计算与通信重叠技术减小通信时间对并行效率的影响,最终实现了双三次数值天气预报模式的并行算法,并在机群系统上进行了并行性能测试评估。结果表明,实现的双三次数值预报模式并行算法的并行效率较高,设计实现的数据转置通信算法、计算与通信重叠技术取得了较好的效果。     

多重网格格子Boltzmann方法的并行算法

针对复杂流动数值模拟中的格子Boltzmann方法存在计算网格量大、收敛速度慢的缺点,提出了基于三维几何边界的多重笛卡儿网格并行生成算法,并基于该网格生成方法提出了多重网格并行格子Boltzmann方法（LBM）。该方法结合不同尺度网格间的耦合计算,有效减少了计算网格量,提高了收敛速度;而且测试结果也表明该并行算法具有良好的可扩展性。     

多核图像处理并行设计范式的研究与应用

多核计算环境下采用图像处理并行算法可提高图像处理的速度,但已有的并行设计只针对边缘检测、图像投影等特定算法进行,没有形成通用的并行算法设计范式。为此,在研究图像处理算法可并行处理机制和多核架构特点的基础上,提出分析、建模、映射、调试和性能评价及测试发布等5个设计步骤的基于多核计算环境的图像处理算法并行设计范式,以图像傅里叶变换并行算法设计为例在单核、双核、四核、八核计算环境下验证了该并行范式的有效性。实验结果表明,该范式在图像处理并行设计方面可扩展图像处理的应用空间。     

Euler方程非结构网格分布式并行计算

在二维非结构网格情形下,针对PC集群并行系统提出一种新的并行算法,在前景网格与背景网格之间建立起逻辑映射关系来交换边界计算数据并提高并行效率,该算法在应用中能有效地保持并行系统的负载平衡和边界计算数据的正确交换,多个数值算例的结果表明了该算法的有效性。     

基于神威太湖之光架构的LOBPCG并行算法研究

LOBPCG是一种适合大规模稀疏对称问题的特征值数值解法.本文研究了适合神威太湖之光架构的LOBPCG并行算法.首先提出了基于主、从核的混合并行模型;研究了稀疏矩阵-向量积的并行算法,通过核组间通信隐藏、核组内通信隐藏等技术提高程序速度,并提出一种自动调节从核缓冲数据量的算法,可自动逼近最佳的通信隐藏效果;研究了稠密矩阵积在神威太湖之光架构上的并行算法,针对不同"形态"的输入矩阵提出了不同的矩阵分割算法,速度显著优于其它算法库;在计算最高1.25亿阶矩阵、使用936000计算核心的特征值求解测试中表现出良好的扩展性.我们还测试了该应用在凝聚态物理领域的强关联系统中的性能.     

一种在多核嵌入式平台上实现FFT的快速并行算法

快速傅利叶变换（fast Fourier transform,FFT）算法是对实时数字信号进行快速分析处理的一个基本方法。针对多核嵌入式实时环境下并行FFT算法进行了研究,以有效提高实时信号处理的速度。提出了一种新的静态多项式FFT算法,充分利用静态多项式奇偶项的不同特点直接代入数据计算,免去了层层迭代的计算过程,减少了运算过程中的通信提高并行性能。对该算法思想本文在理论进行了严密论证,通过嵌入式实时平台上运行测试和仿真实验,证实了在数据分段较短的约束条件下,该多项式静态算法较经典的FFT并行算法在时间复杂度上有一定优势。本文结论:多项式静态FFT算法能够有效提高并行FFT运行速度。     

一类Toeplitz三对角方程组的有效分布式并行算法

针对大型方程组的特点,本文提出了一种求解一类Toeplitz三对角方程组的分布式并行算法.该算法首先并行求出原Toeplitz三对角方程组的近似解,然后在给定的误差范围内对近似解进行修正,该算法的通信机制简单、冗余计算量少.数值试验表明该算法具有较高的并行效率.     

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

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

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

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

水质预报系统中垂向湍扩散并行算法实现研究

为了能更好地提高水质预报模式中物质输运方程的计算速率,以胶州湾数值预报系统中垂向扩散的串行算法为基础,提出了一种主要针对物质输运方程中的垂向扩散的MPI(message-passinginterface)并行算法。该算法将计算分解为多个子任务,并在基于MPI消息传递模式的集群系统中进行运算。与原串行算法进行比较,并行的加速比提高了33%以上,且并行效率最大可达90%,该结果表明了MPI技术在海洋数值模拟领域应用的潜力。     

CTC与网络编码的联合设计研究

Turbo码由于具有并行级联的特点,更易于与网络编码进行联合设计,迄今为止成为信道编码与网络编码联合设计领域的一个热点。在研究无线网络中物理层网络编码技术的基础上,提出了一种新型的物理层网络编码和信道编码的联合设计方案,即CTC码（卷积Turbo码）与网络编码的联合设计方案,该方案具有较小的译码时延,更强的纠错性能,对于移动台（MS）来说,不仅提高了码率,还比MS直接使用CTC编码的算法简单。仿真结果表明CTC-网络编码系统具有较强的纠错性能,更适合于各种恶劣环境下的通信。     

Hadoop平台的海量数据并行随机抽样

在“信息爆炸”的当今社会,海量数据对数据挖掘提出新的挑战。在数据挖掘转向云计算平台实现并行化的同时,研究并行化数据随机抽样进一步降低处理的数据规模。提出一种单次扫描即可实现清理脏数据并实现等概率抽样的mapreduce并行抽样算法。在hadoop平台上实现并与普通随机抽样方法进行比较,得出其时间效率非常高,是一种行之有效的方法。为以后数据挖掘中的抽样研究和推动数据挖掘在海量数据下的发展奠定良好基础。     

Comparative investigation of GPU-accelerated triangle-triangle intersection algorithms for collision detection

Efficient collision detection is critical in 3D geometric modeling. In this paper, we first implement three parallel triangle-triangle intersection algorithms on a GPU and then compare the computational efficiency of these three GPU-accelerated parallel triangle-triangle intersection algorithms in an application that detects collisions between triangulated models. The presented GPU-based parallel collision detection method for triangulated models has two stages: first, we propose a straightforward and efficient parallel approach to reduce the number of potentially intersecting triangle pairs based on AABBs, and second, we conduct intersection tests with the remaining triangle pairs in parallel based on three triangle-triangle intersection algorithms, i.e., the Möller’s algorithm, Devillers’ and Guigue’s algorithm, and Shen’s algorithm. To evaluate the performance of the presented GPU-based parallel collision detection method for triangulated models, we conduct four groups of benchmarks. The experimental results show the following: (1) the time required to detect collisions for the triangulated model consisting of approximately 1.5 billion triangle pairs is less than 0.5 s; (2) the GPU-based parallel collision detection method speedup over the corresponding serial version is 50x - 60x, and (3) Devillers’ and Guigue’s algorithm is comparatively and comprehensively the best of the three GPU-based parallel triangle-triangle intersection algorithms. The presented GPU-accelerated method is capable of efficiently detecting the potential collisions of triangulated models. Overall, the GPU-accelerated parallel Devillers’ and Guigue’s triangle-triangle intersection algorithm is recommended when performing practical collision detections between large triangulated models.

     

一种基于范围搜索的并行多维分类算法PRSMC

针对高速网络应用对基于范围查找的分组分类算法的要求以及高性能并行计算环境的特点,提出了一种高速多维分组分类算法——PRSMC(基于范围搜索的并行多维分类)算法。该算法具有较快的搜索速度和较强的并行性,特别适合在多CPU多核高性能计算机上实现。同时提出了算法的双缓冲并行实现技术,使得在软件环境中具有良好空间和时间性能。性能实验表明该算法具有良好的可扩展性,算法速度较同类基于区域划分的算法有较大提升,平均分类速率能达到1Mpkt/s左右。     

遗传算法研究综述

遗传算法是一种基于生物自然选择与遗传机理的随机搜索与优化方法。近年来，由于遗传算法求解复杂优化问题的巨大潜力及其在工业工程领域的成功应用，这种算法受到了国内外学者的广泛关注。本文介绍了遗传算法的研究现状，描述了它的主要特点和基本原理，概述了它的理论、技术和应用领域，讨论了混合遗传算法和并行遗传算法，指出了遗传算法的研究方向，并对遗传算法的性能作了分析。     

同时送取货车辆路径问题算法研究综述

针对同时送取货车辆路径问题的研究算法进行了评述.将该问题的求解方法分为精确算法、构造型启发式、现代启发式以及并行算法四个大类.从算法的原理、性能、适用环境,以及算法之间差异性等方面对各类算法进行了较为全面的介绍.最后,说明了VRPSDP算法研究在节点具有双重需求车辆路径问题理论研究方面的意义,并提出未来VRPSDP算法研究的两个发展方向,即适合多处理器上运行的并行现代启发式算法,以及有效的混合算法如量子行为粒子群算法.     

基于不完全算法的并行FPGA SAT求解器

可满足性问题是计算机理论与应用的核心问题。在FPGA上提出了一个基于不完全算法的并行求解器pprobSAT+。使用多线程的策略来减少相关组件的等待时间,提高了求解器效率。此外,不同线程采用共用地址和子句信息的数据存储结构,以减少片上存储器的资源开销。当所有数据均存储在FPGA的片上存储器时,pprobSAT+求解器可以达到最佳性能。实验结果表明,相比于单线程的求解器,所提出的pprobSAT+求解器可获得超过2倍的加速比。     

Parallel implementations for determining the 2D convex hull

A number of related factors determine whether the ideal offered by parallel processing of a linear increase in performance with an increased number of processors is approached. It is vital to understand the nature of the application being ‘parallelised’ so that each factor can be considered for that application to determine if it is suitable for parallelisation. This paper demonstrates the value of analysing a serial implementation as part of understanding the application's nature. It also describes a parallel implementation of a divide-and-conquer parallel algorithm for determining the convex hull of a set of 2D points, following an earlier serial implementation. It is compared with an earlier parallelisation of the serial divide-and-conquer Preparata–Hong algorithm. It analyses the algorithms and determines the factors affecting their parallelisation. © 1998 John Wiley & Sons, Ltd.     

基于面向对象八叉树的虚拟漫游碰撞检测

借助面向对象概念,根据层数和叶结点链表个数上限来构建存储场景物体信息的高效八叉树。每个叶结点指向记录对应空间区域内物体信息的链表,每个空间物体信息链表按照其对象大小降序排列。在逐步求精阶段用降序包围球遍历链表进行检测,然后根据凸多面体剖分算法,使用主从MPI模式并行处理以实现精确碰撞检测。该方法利用物体空间位置关系进行碰撞检测,毋需存储大量空间物体三角面片。在基于粒子系统的土壤可视化漫游中的运行结果表明,该方法精度高、实时性好,具有一定的研究和应用价值。     

基于Hausdorff距离的图像匹配并行算法设计与实现

随着图像匹配的应用越来越广泛,图像匹配的实时性要求也越来越高。为了提高图像匹配的速度和更好地利用多核计算资源,设计了一种基于Hausdorff距离的图像匹配并行算法。首先介绍了Hausdorff距离的定义,然后分析了图像匹配串行算法的效率,在此基础上设计了基于Hausdorff距离的图像匹配并行算法,最后采用Matlab在多核计算机上对并行算法进行了实现。实验结果表明,文中所设计的并行算法能够显著提高图像匹配速度,并具有较好的抗失真和抗噪声性能。文中设计的并行算法有较好的扩展性,可以将这种并行思想应用到其它图像匹配算法的并行设计中。