线性系统求解中迭代算法的GPU加速方法

在求解线性系统时,迭代法是一种基本的方法,特别是在系数矩阵为大规模稀疏矩阵的情况下,高效地使用迭代法求解变得十分重要。本文通过分析迭代法的一般特点,提出了使用具有强大计算能力和存储带宽的GPU加速迭代法的一般方法。利用这些方法,在两种主流GPU平台上实现了一个经典的迭代法PQMRCGSTAB,并且针对不同的GPU平台特点提出了具体的优化方法。与AMD Opteron 2.4GHz 4核处理器相比,双精度版本的PQMRCGSTAB算法经NVIDIA Tesla S1070加速后性能提高31倍,经AMD Radeon HD 4870 X2加速后性能提高9倍。     

基于GPU的LARED-P算法加速

GPU拥有几百GFlops甚至上TFlops的浮点计算能力,将GPU应用于粒子模拟,可有效提高大规模粒子模拟的速度,降低计算成本。本文利用GPU加速三维激光等离子体模拟算法LARED-P,提出了基于CPU+GPU的任务划分、GPU上任务分解、大规模计算核心的分解方法,结合使用了寄存器、纹理内存对算法进行加速。在双精度条件下,移植后的算法在工作频率为1.44GHz的NVIDIA Tesla S1070的单个GPU上获得了相当于主频2.4GHz的Intel(R)Core(TM)2 Quad CPU Q6600单核的6倍加速比。     

基于OpenCL的图像积分图算法优化研究

图像积分图算法在快速特征检测中有着广泛的应用,通过GPU对其进行性能加速有着重要的现实意义。然而由于GPU硬件架构的复杂性和不同硬件体系架构间的差异性,完成图像积分图算法在GPU上的优化,进而实现不同GPU平台间的性能移植是一件非常困难的工作。在分析不同CPU平台底层硬件架构的基础上,从片外访存带宽利用率、计算资源利用率和数据本地化等多个角度考察了不同优化方法在不同GPU硬件平台上对性能的影响。并在此基础上实现了基于OpenCL的图像积分图算法。实验结果表明,优化后的算法在AMD和NVIDIA CPU上分别取得了11.26和12.38倍的性能加速,优化后的GPU kernel比NVIDIA NPP库中的相应函数也分别取得了55.01%和65.17%的性能提升。验证了提出的优化方法的有效性和性能可移植性。     

基于OpenCL的拉普拉斯图像增强算法优化研究

OpenCL是面向异构计算平台的通用编程框架,然而由于硬件体系结构的差异,如何在平台间功能移植的基础上实现性能移植仍是有待研究的问题。当前已有算法优化研究一般只针对单一硬件平台,它们很难实现在不同平台上的高效运行。在分析了不同GPU平台底层硬件架构的基础上,从Global Memory的访存效率、GPU计算资源的有效利用率及其硬件资源的限制等多个角度考察了不同优化方法在不同GPU硬件平台上对性能的影响;并在此基础上实现了基于OpenCL的拉普拉斯图像增强算法。实验结果表明,优化后的算法在不考虑数据传输时间的前提下,在AMD和NVIDIA GPU上都取得了3.7～136.1倍、平均56.7倍的性能加速,优化后的kernel比NVIDIA NPP库中相应函数也取得了12.3%～346.7%、平均143.1%的性能提升,验证了提出的优化方法的有效性和性能可移植性。     

Particle-Mesh-Ewald(PME)算法在GPU上的实现

分子动力学模拟(MD)是分子模拟的一类常用方法,为生物体系的模拟提供了重要途径。由于计算强度大,目前MD可模拟的时空尺度还不能满足真实物理过程的需要。作为CPU的加速设备,近年来,GPU为提高MD计算能力提供了新的可能。GPU编程难点主要在于如何将计算任务分解并映射到GPU端并合理组织线程及存储器,细致地平衡数据传输和指令吞吐量以发挥GPU的最大计算性能。静电效应是长程作用,广泛存在于生物现象的各个方面,对其精确模拟是MD的重要组成部分。Particle-Mesh-Ewald(PME)方法是公认的精确处理静电作用的算法之一。本文介绍在本实验室已建立的GPU加速分子动力学模拟程序GMD的基础上,基于NVIDIACUDA,采用GPU实现PME算法的策略,针对算法中组成静电作用的三个部分即实空间、傅立叶空间和能量修正项,分别采用不同的计算任务组织策略以提升整体性能。使用事实上的标准算例dhfr进行的测试结果表明,实现PME的GMD程序,性能分别是Gromacs4.5.3版单核CPU的3.93倍,8核CPU的1.5倍,基于OpenMM2.0加速的Gromacs4.5.3GPU版本的1.87倍。     

基于OpenCL的实时KD-Tree与动态场景光线跟踪

目前,基于GPU或多核CPU加速的光线跟踪算法是与硬件相关的.研究具有跨平台性能的实时光线跟踪算法既具有挑战性,又具有很强的应用价值.为此,提出一种基于OpenCL并且跨平台的动态场景实时光线跟踪绘制算法.首先通过对通用GPU并行处理性能进行发掘,将光线跟踪中KD-Tree建立、场景遍历和绘制3个过程均设计在GPU上,而CPU只负责其中各过程的调度,从而充分利用了GPU的计算性能,并有效地降低了数据传输开销;通过设计并行分区、并行SAH、紧密的数据管理以及区间性叶结点存储等算法,在GPU中高效、高质量地建立动态场景的KD-Tree,同时高质量的KD-Tree也有效地加速了场景的遍历速度.该算法以广度优先和大规模并行模式建立K D-Tree,更具通用性,既可以运行于NVIDIA GPU(CUDA GPU),也可以运行于AMD GPU.实验结果表明,文中算法可以在NVIDIA GPU和AMD GPU上对中等规模的动态场景实现实时光线跟踪绘制.     

基于OpenCL的连续数据无关访存密集型函数并行与优化研究

连续的数据无关是指计算目标矩阵连续的元素时使用的源矩阵元素之间没有关系且也为连续的,访存密集型是指函数的计算量较小,但是有大量的数据传输操作。在OpenCL框架下,以bitwise函数为例,研究和实现了连续数据无关访存密集型函数在GPU平台上的并行与优化。在考察向量化、线程组织方式和指令选择优化等多个优化角度在不同的GPU硬件平台上对性能的影响之后,实现了这个函数的跨平合性能移植。实验结果表明,在不考虑数据传输的前提下,优化后的函数与这个函数在OpenCV库中的CPU版本相比,在AMD HD 5850 GPU达到了平均40倍的性能加速比;在AMD HD 7970 GPU达到了平均90倍的性能加速比;在NVIDIA Tesla 02050 CPU上达到了平均60倍的性能加速比;同时,与这个函数在OpenCV库中的CUDA实现相比,在NVIDIA Tesla 02050平台上也达到了1.5倍的性能加速。     

晶硅分子动力学模拟的GPU加速算法优化

分子动力学(MD)模拟是研究硅纳米薄膜热力学性质的主要方法,但存在数据处理量大、计算密集、原子间作用模型复杂等问题,限制了MD模拟的深入应用。针对晶硅分子动力学模拟算法中数据访问不连续和大量分支判断造成并行资源浪费、线程等待等问题,结合Nvidia Tesla V100 GPU硬件体系结构特点,对晶硅MD模拟算法进行设计。通过全局内存的合并访存、循环展开、原子操作等优化方法,利用GPU强大并行计算和浮点运算能力,减少显存访问及算法执行过程中的分支冲突和判断指令,提升算法整体计算性能。测试结果表明,优化后的晶硅MD模拟算法的计算速度相比于优化前提升了1.69～1.97倍,相比于国际上主流的GPU加速MD模拟软件HOOMDblue和LAMMPS分别提升了3.20～3.47倍和17.40～38.04倍,具有较好的模拟加速效果。     

GPU加速的差分进化粒子滤波算法

为了解决实时系统中粒子滤波的计算复杂性问题,本文提出了一种零bank冲突并行规约的差分进化粒子滤波方法。该方法首先分析了并行差分进化粒子滤波算法在GPU中的内存访问模式,根据粒子滤波器的均方根误差与内存访问bank(存储体)冲突度成正比的关系,提出了一种去除bank冲突的有填充寻址的差分进化粒子滤波算法,降低了计算复杂度。将该算法在NVIDIA GTX960 GPU中实现,与串行差分进化粒子滤波算法进行比较。实验表明,随着粒子数增加,计算量以指数增加,采用GPU加速的跟踪算法的执行时间明显减少,有效提高了跟踪精度、降低了计算时间。     

可扩展的实时自然景物模拟算法

针对传统的粒子系统实时仿真存在只能针对单一自然景物模拟、计算耗时、图像不真实、算法复杂等问题,提出了一种基于粒子系统和图形处理器（GPU）加速通用可扩展的自然景物模拟算法。在该算法中,粒子的物理运动计算过程和渲染阶段完全由CPU转移至GPU,可以增加粒子数量和提高渲染速度;同时,在渲染过程中,可以较好地利用硬件支持的粒子图技术来改善渲染中粒子的外表,选择不同纹理,从而能够较方便地模拟不同的自然景物。最后,在GPU上实现了雪花、喷泉、烟花、瀑布等模拟,算法充分利用了GPU的多通道并行处理性和可编程性,提高了自然景物模拟的实时性,可运用于虚拟现实系统。     

Vector optimization of amber 3.0 on the NEC SX-2/400 supercomputer

The AMBER 3.0 molecular mechanics and molecular dynamics programs have been ported to and vectorized on the NEC SX-2/400 supercomputer. A detailed discussion of the vector enhancement of the AMBER non-bonded pair list generation subroutine is presented. Automatic vectorization using the FORT77SX compiler yielded speed-up factors of 1.2 to 1.5 over unvectorized code. Recoding of key portions of the program, as described in this paper, yielded speed-up factors of 1.8-2.7. The perturbation molecular dynamics program, PERDYN, now runs up to 35 times faster on the SX-2/400 than the VAX optimized version of the same program runs on the VAX 8650.     

基于OpenCL的MD5破解算法

在基于GPU的异构平台上,采用开放计算语言(OpenCL)实现破解算法,利用分轮生成攻击密码、图形渲染管线加速存取以及多密码并行等方法对算法进行优化,在Intel四核CPU Q8230(2.3 GHz)和一片NVIDIA GT200组成的平台上进行实验。实验结果表明,在相同CPU平台上该算法能够获得高于破解软件John the ripper 17倍的破解速度。     

On parallelization of static scheduling algorithms

Most static algorithms that schedule parallel programs represented by macro dataflow graphs are sequential. This paper discusses the essential issues pertaining to parallelization of static scheduling and presents two efficient parallel scheduling algorithms. The proposed algorithms have been implemented on an Intel Paragon machine and their performances have been evaluated. These algorithms produce high-quality scheduling and are much faster than existing sequential and parallel algorithms     

A Random Sampling O(n) Force‐calculation Algorithm for Graph Layouts

This paper proposes a linear‐time repulsive‐force‐calculation algorithm with sub‐linear auxiliary space requirements, achieving an asymptotic improvement over the Barnes‐Hut and Fast Multipole Method force‐calculation algorithms. The algorithm, named random vertex sampling (RVS), achieves its speed by updating a random sample of vertices at each iteration, each with a random sample of repulsive forces. This paper also proposes a combination algorithm that uses RVS to derive an initial layout and then applies Barnes‐Hut to refine the layout. An evaluation of RVS and the combination algorithm compares their speed and quality on 109 graphs against a Barnes‐Hut layout algorithm. The RVS algorithm performs up to 6.1 times faster on the tested graphs while maintaining comparable layout quality. The combination algorithm also performs faster than Barnes‐Hut, but produces layouts that are more symmetric than using RVS alone. Data and code: https://osf.io/nb7m8/     

基于FPGA的HEVC后处理CNN硬件加速器研究

针对高效视频编解码标准中后处理CNN算法在通用平台运行时产生的高延时缺点,提出一种基于现场可编程逻辑门阵列（FPGA）的后处理卷积神经网络硬件并行架构。提出的并行架构通过改进输入与输出缓冲的数据并发过程,调整卷积模块整体并行度,加快模块硬件流水。实验结果表明,基于本文所提出的并行架构设计的CNN硬件加速器在Xilinx ZCU102上处理分辨率为176×144视频流,计算性能相当于每秒360.5 GFLOPS,计算速度可满足81.01 FPS,相比时钟频率4 GHz的Intel i7-4790K,计算速度加快了76.67倍,相比NVIDIA GeForce GTX 750Ti加速了32.50倍。在计算能效比方面,本文后处理CNN加速器功耗为12.095 J,能效比是Intel i7-4790K的512.90倍,是NVIDIA GeForce GTX 750Ti的125.78倍。     

PARALLEL PROCESSING FOR CHROMOSOME RECONSTRUCTION FROM PHYSICAL MAPS - A CASE STUDY OF MIMD PARALLELISM ON THE HYPERCUBE

Ordering clones from a genomic library into physical maps of whole chromosomes presents a pivotal computational problem in genetics. Previous research has shown the physical mapping problem to be isomorphic to the NP-complete Optimal Linear Arrangement (OLA) problem for which no polynomial-time algorithm for determining the optimal solution is known. Serial implementations of stochastic global optimization techniques such as simulated annealing yielded very good results but proved computationally intensive. The design, analysis and implementation of coarse-grained parallel MIMD algorithms for simulated annealing on the Intel iPSC/860 hypercube is presented. Data decomposition and control decomposition strategies based on Markov chain decomposition, perturbation methods and problem-specific annealing heuristics are proposed and applied to the physical mapping problem. A suite of parallel algorithms are implemented on an 8-node Intel iPSC/860 hypercube, exploiting the nearest-neighbor communication pattern on the Boolean hypercube topology. Convergence, speedup and scalability characteristics of the various parallel algorithms are analyzed and discussed. Results indicate a deterioration of performance when a single Markov chain of solution states is distributed across multiple processing elements in the Intel iPSC/860 hypercube.     

多核/众核平台上推荐算法的实现与性能评估

用OpenCL语言标准设计并实现了推荐系统领域的两种经典算法:交替最小二乘法(Alternating Least Squares,ALS)与循环坐标下降法(Cyclic Coordinate Descent,CCD)。将其应用到CPU,GPU,MIC多核与众核平台上,探索了在该平台上影响算法性能的因子:潜在特征维数与线程个数。同时,将OpenCL实现的两种算法与CUDA和OpenMP的实现进行比较,得出了一系列结论。在同等条件下,与ALS算法相比,CCD算法的精度更高,收敛速度更快且更稳定,但所耗时间更长。ALS和CCD算法基于OpenCL的实现性能不亚于CUDA(CCD 上加速比为1.03x,ALS上加速比为1.2x)和OpenMP的实现(CCD与ALS上加速比大约为1.6~1.7x),并且两种算法在CPU平台上的性能均比GPU与MIC好。     

Tabu Search with two approaches to parallel flowshop evaluation on CUDA platform

The introduction of NVidia’s powerful Tesla GPU hardware and Compute Unified Device Architecture (CUDA) platform enable many-core parallel programming. As a result, existing algorithms implemented on a GPU can run many times faster than on modern CPUs. Relatively little research has been done so far on GPU implementations of discrete optimisation algorithms. In this paper, two approaches to parallel GPU evaluation of the Permutation Flowshop Scheduling Problem, with makespan and total flowtime criteria, are proposed. These methods can be employed in most population-based algorithms, e.g. genetic algorithms, Ant Colony Optimisation, Particle Swarm Optimisation, and Tabu Search. Extensive computational experiments, on Tabu Search for Flowshop with both criteria, followed by statistical analysis, confirm great computational capabilities of GPU hardware. A GPU implementation of Tabu Search runs up to 89 times faster than its CPU counterpart.     

A hybrid decomposition parallel implementation of the Car-Parrinello method

We have developed a flexible hybrid decomposition parallel implementation of the first-principles molecular dynamics algorithm of Car and Parrinello. The code allows the problem to be decomposed either spatially, over the electronic orbitals, or any combination of the two. Performance statistics for 32, 64, 128 and 512 Si atom runs on the Touchstone Delta and Intel Paragon parallel supercomputers and comparison with the performance of an optimized code running the smaller systems on the Cray Y-MP and C90 are presented.     

Efficient convexity and domination algorithms for fine- and medium-grain hypercube computers

This paper gives hypercube algorithms for some simple problems involving geometric properties of sets of points. The properties considered emphasize aspects of convexity and domination. Efficient algorithms are given for both fine- and medium-grain hypercube computers, including a discussion of implementation, running times and results on an Intel iPSC hypercube, as well as theoretical results. For both serial and parallel computers, sorting plays an important role in geometric algorithms for determining simple properties, often being the dominant component of the running time. Since the time required to sort data on a hypercube computer is still not fully understood, the running times of some of our algorithms for unsorted data are not completely determined. For both the fine- and medium-grain models, we show that faster expected-case running time algorithms are possible for point sets generated randomly. Our algorithms are developed for sets of planar points, with several of them extending to sets of points in spaces of higher dimension.