一种基于GPU的枚举排序算法及其并行化

针对枚举排序算法在处理大规模数据时存在运算量大、计算时间长、计算效率低等问题,提出一种利用GPU并行运算提升大规模数据处理速度的方法。在CUDA下对枚举排序算法进行串-并行分析,分别从细粒度与粗粒度角度进行优化,根据CPU与GPU的结构特点优化排序数据的读取和存储方式,内核采用一个GPU线程对应一次比较操作的计算方法,以充分利用GPU计算能力。实验结果表明,当排序数据规模大于40 000时,在GPU上的运算速度比在CPU上快3倍左右,并且随着数据规模的不断增大,加速比越来越大。研究结果对于提升大规模数值计算效率具有重要的意义。     

面向CPU-GPU集群的分布式机器学习资源调度框架研究

随着GPU硬件设施的广泛应用,越来越多的分布式机器学习应用程序开始使用CPU-GPU混合集群资源来提高算法的效率。但是,现有的分布式机器学习调度框架要么只考虑CPU资源上的任务调度,要么只考虑GPU资源上的任务调度,即使综合考虑CPU与GPU资源的不同,也很难提高整个系统的资源使用效率,即使用CPU-GPU集群进行分布式机器学习作业面临的关键挑战是如何高效地调度作业中的任务。在对现有的方法进行分析后,提出了一种基于不均匀数据分片的策略,利用线性规划的原理,使得CPU任务时间与GPU任务时间尽可能接近,从而减少分布式机器学习作业的整体执行时间。介绍了CPU-GPU混合计算框架的调度结构,这种调度结构针对CPU计算能力与GPU计算能力的不同特点,将数据分割成大小不等的数据分片以适应于CPU和GPU计算资源,给出了CPU-GPU混合资源下的任务调度方法,对该方法进行K-Means算法验证。使用CPU-GPU混合资源计算框架,K-Means性能平均提高1.5倍,且随着GPU数量的增加,K-Means性能能够显著提升。     

基于CUDA架构下的直方图均衡并行算法

为了提高图像对比度, 解决传统的直方图均衡算法处理速度慢的问题, 提出了基于统一计算设备架构(CUDA)的直方图均衡图像实时处理加速方案。利用图形处理器(GPU)强大的计算能力和CUDA 优化的存储器结构, 以加速直方图均衡中的图像灰度级投票、 分布概率累加并映射以及图像新的灰度值填充等功能进行运算。在CUDA 条件下, 对直方图均衡算法进行串-并行分析, 分别从粗粒度与细粒度角度进行并行设计, 通过实验测定进行了设计参数寻优, 获得了线程块设计参数的最优尺寸。结果表明, 基于CUDA的图像直方图均衡并行算法的性能相比基于CPU 的串行算法和基于开放多处理(OpenMP)并行算法分别获得了61. 58 和32. 00 倍的加速比, 能够为大规模实时性图像处理系统设计提供参考。     

基于GPU的势能场骨架提取并行算法

为解决势能场骨架提取方法计算效率低、提取过程耗时大的问题,同时为降低该方法的时间复杂度,提出了基于GPU的势能场骨架提取并行算法,并充分利用CUDA架构特有的常量存储器和共享存储器对普通并行算法进行改进.讨论了如何根据程序和显卡设备的固有属性来分配线程以达到最高的GPU占用率,从而得到最优的加速效果.对多组3D模型进行测试的结果表明,随着数据规模的增大,加速效果逐渐提升,处理256×256×487的体数据时,可获得18倍的加速比.     

CUDA架构下的快速Wallis影像增强算法

针对图像增强通常需要较大的计算量、用传统方法难于进行实时处理的问题,提出了一种基于图形处理器加速的Wallis变换影像增强方法.借助于图形处理器较强的运算能力,利用CUDA并行计算架构在PC机上实现了快速Wallis图像滤波算法,包括图形处理器（GPU）上任务分解、大规模计算核心的分解方法,结合使用共享存储器、全局存储器对算法进行加速,使用线程块内的共享存储器较好地解决了同一计算子空间的各线程同步问题.对比了CPU和GPU计算Wallis影像变换的时间,结果表明,随着图像分辨率的增大,Wallis并行算法可以把计算速度提高40倍.该方法具有较好的实时性,可大大提高图像增强过程的处理速度,显著地减少了计算时间.     

数据中心上异构资源的细粒度分配算法研究

数据中心的出现,使得大数据分析任务被分散到不同的计算节点。随着GPU计算的广泛应用,如何为不同的计算框架合理分配异构计算资源是目前的研究热点。研究了传统大数据计算框架和GPU计算的特点,针对现有的集群资源管理和GPU管理模式,提出了一种集中式异构资源管理模型,计算节点负责本地资源管理和任务的执行和管理,资源管理中心统一管理各个计算框架。对于不同的计算框架,根据其使用CPU以及GPU资源的不同,设计并实现了一种混合主资源共享分配算法,通过计算不同框架对主资源的使用,优先从可用资源中为主资源使用率最小的框架分配资源,实现主资源在各个框架的公平共享,防止CPU任务过多而导致GPU资源"饥饿",或者反过来导致CPU资源"饥饿"的现象发生。通过实验验证,该分配算法在异构资源使用效率以及任务完成数量方面能提高15%左右。     

基于GPU的曲面自适应细分

为了充分利用图形处理器(GPU)的强大计算力和并行处理能力,并有效克服CPU/GPU间数据传输的瓶颈,提出了一种新的基于GPU的曲面自适应细分算法.通过采用细分模板(SP),在GPU的顶点处理器上将从CPU上传送来的控制网格进行求值细分.给出了自适应细分层次的判定,以及通过带裙边的SP来解决可能出现的裂缝问题.将该方法用于Catmull-Clark细分曲面和Loop细分曲面的求值显示,并推广应用到其他类型细分,和GPU上的其他着色器组合使用,对硬件要求很低,只需要能够支持顶点着色器的显卡.与CPU求值渲染、基于片段处理器求值渲染方法运行效率的对比分析,证明了该方法的高效性.     

片上网络良率评估的GPU加速

针对片上网络良率评估速度较慢、效率较低的问题,研究片上网络良率评估的GPU加速,提高评估算法的执行效率.将良率评估中的样本分析算法移植到GPU平台;在分析、比较了不同平台,随机样本生成算法优劣的基础上,发现GPU平台不适合生成样本;进一步优化CPU平台上的样本生成算法,使之能与GPU一起,实现异构并行;提出CPU生成样本、GPU执行样本分析的异构并行方案.与仅使用CPU的评估算法相比,采用提出的异构并行算法实现了10倍的运行效率提升.     

基于图形处理器的高速中值滤波算法

针对中央处理器(CPU)平台中值滤波算法在实际应用中运算速率低且实时信号处理性能较差的问题,提出了一种基于图形处理器(GPU)的并行高速中值滤波算法。该算法采用统一计算设备架构(CUDA)并行架构对大规模数据处理进行了优化,从而有效提高了中值滤波算法的计算效率,实现了中值滤波的实时数据处理。通过构建GPU可任意伸缩的动态数组、优化多维索引的线性化方法解决了GPU动态显存空间分配问题。仿真试验结果表明:基于TITAN X GPU的5×5中值滤波,对4096像素×4096像素的图像处理计算速度比CPU平台提高了438倍。在同等计算规模条件下GPU高速中值滤波算法可大大提高计算性能。     

基于GPU并行技术的超大型海面舰船电磁散射仿真

为了解决超电大尺寸海面舰船场景中电磁散射计算的瓶颈问题,研究基于多图像处理单元(Multi-GPU)并行加速技术的弹跳射线法(SBR)。借助统一设备计算架构(CUDA)提供的多线程服务(MPS),构建Multi-GPU并行加速框架,研究基于区域射线束划分GPU计算任务和实现方式;研究基于矩阵网格的任务分割技术,最大限度提高GPU全局内存利用率;针对不同运算单元间的差异所带来的计算不同步问题,设计基于动态负载均衡算法的调度系统,进而提高计算资源利用率。仿真结果表明,在双GPU硬件平台上,该方案与现有并行技术算法相比,在确保结果准确性的情况下加速比接近甚至超过200%。因此,该技术方案能够有效解决超电大海面舰船电磁散射问题。     

基于阿里云的四维弹簧模型并行运算性能

四维弹簧模型（Four-Dimensional Lattice Spring Model,4D-LSM）是一种考虑额外维相互作用的新型离散数值计算方法。该方法用于岩石破坏分析需要消耗大量计算资源,不适合在普通个人电脑上运行。基于多核并行技术,在阿里云和多核工作站等多种硬件环境下对4D-LSM的计算极限性能及瓶颈进行详细分析,主要研究了求解规模、求解类型、线程数、硬件配置等对4D-LSM求解效能的影响。研究发现,内存容量决定可计算的模型规模,弹性问题的计算时间与模型规模成正比,并行计算效率受CPU性能和内存带宽的共同影响。在不考虑经济因素的情况下,云计算在多核匹配和内存分配方面的灵活性特别适合于四维弹簧模型的并行计算分析。结果表明：基于阿里云的4D-LSM最大运算规模可以达到十亿单元,由于目前的瓶颈在于前后处理,4D-LSM目前的可分析规模仍然限制在两千万单元。最后,展示了采用极限规模的并行四维弹簧模型求解三维币形裂纹扩展的实际应用案例。     

Study of the scalable heterogeneous parallel out-of-core higher order method of moments

To achieve the across-nodes technology of the heterogeneous parallel method of moments (MoM), a parallel MoM programming model is studied on CPU/GPU and CPU/MIC heterogeneous platforms. By utilizing the CONTEXT technology in the CUDA which contains the GPU common programming criterions, and the concept of environment variables in MIC, a general heterogeneous parallel programming model for the CPU/GPU and CPU/MIC is proposed, which meets the static load-balancing for the across-nodes heterogeneous parallel MoM. Numerical results show that the heterogeneous parallel MoM codes based on the proposed parallel programming model can obtain ideal speedup and good scalability.     

一种基于GPU的快速半全局优化深度图计算方法

由于图像集规模巨大、匹配信息丰富,快速精准多视图立体匹配受计算效率严重制约。针对该问题,提出一种基于GPU的快速半全局优化深度图计算方法。首先,在CPU上通过平面扫描方法计算单张图像初始匹配代价。然后,提出GPU半全局优化并行计算架构,对匹配代价进行聚合,其核心算法为：在全局进行各方向聚合任务流并行以提升众核处理器的利用率;在局部通过将各像素计算任务准确分配到各线程块内实现并行处理,且注重GPU上数据重用以避免带宽限制。再通过GPU滤波剔除突变点进行图像增强。最后,将3维空间点在各深度图像上的一致性作为异常值检测和优化的约束条件。在多组数据集上测试结果显示,该方法计算速度最高为多核CPU系统中开启2线程实现方法的22.41倍,为开启8线程实现方法的9.13倍,且与两者精度相当;与同类深度图计算方法比较结果表明, 该方法在重建过程中加速效果均为其他算法的5倍及以上;通过使用开源点云比较软件在标准测试数据集上与其他算法比较,验证了该方法能有效提高重建结果的精度和完整度。     

基于多核计算的雷达并行仿真结构

针对顺序仿真结构下回波生成与信号处理环节软件仿真速度慢等瓶颈问题,提出一种基于多核处理器共享内存的多数据链路计算模型,通过构建多数据链路并行仿真的方法提升软件仿真效率。根据同一调度间隔内各雷达事件相互独立的特性,从数据划分、任务分配、时间同步及负载监测与度量等层面上进行阐述。仿真结果表明,该方法与传统的雷达串行仿真相比,数据帧处理平均时间可以降低37.5%,数据帧处理加速比曲线表现出良好的仿真加速特性,大大缩减雷达系统仿真时间。     

并行I/O技术在海洋数值模式中的应用研究

在海洋数值模拟过程中,随着计算区域的扩大以及计算精度的提升,大量数据输出使得I/O效率成为系统整体性能提升的一个瓶颈。针对这一问题,使用并行I/O技术对系统的输出模块进行优化,并与传统的几种串行I/O方式在不同节点,以及不同计算规模下进行性能比较。通过实验研究数据,对不同I/O方式的不同特点和不同适用场景进行分析,证明在海洋数值模式中使用并行I/O技术切实可行,并且I/O速率得到大幅度提升。     

一种新的视界覆盖遗传算法

空间分析是实现各种应用的关键．视界覆盖问题是空间分析的一种．寻求最优部署点源网以覆盖视界工作是一个NP完全问题．提出了一种基于动态负载平衡的并行遗传算法来解决视界覆盖问题,以减少问题的求解时间．仿真实验表明,该算法的加速比已接近最优,求解时间得到了有效减少;与静态负载平衡相比,该算法可有效减少程序执行时间,提高加速比和并行计算效率．     

置信规则库参数学习的并行差分进化算法

为解决置信规则库中现有参数学习方法主要是串行算法且不适用于求解大数据下参数优化模型的问题,结合群智能算法中的差分进化算法和集群系统中分布式方法,提出了基于消息传递接口的并行参数学习方法。以输油管道检漏问题为例,对比分析了本算法与现有参数学习方法在收敛时的误差,并在不同结点数的集群系统中分析了本算法的加速比和效率。实验结果表明,并行的参数学习方法是有效可行的。     

基于Spark平台的FP-Growth算法优化与实现

针对FP-Growth算法面对海量数据挖掘时串行操作机制出现内存瓶颈或者数据挖掘失效等问题,提出将基于Spark平台的FP-Growth算法在数据分组策略和项头表结构两方面进行优化。一方面提出一种S型的负载权值均衡分组的方式;另一方面,设计出一种新的项头表结构,此结构包含Hash查找表,能有效降低查找时间复杂度。实验证明,优化的基于Spark平台的FP-Growth算法(OptFP-Spark算法)具有更高的并行运算加速比、更好的并行挖掘效果及更高效的计算效率。     

数据挖掘网格中决策树并行算法设计及性能分析

提出了C4.5决策树算法的一种并行算法,使传统的串行分类算法能在多台PC机和服务器组成的数据挖掘网格上并行数据挖掘. 采用数据纵横剖分,结合递归过程的并行化,实现了可扩展的高性能并行计算,解决了处理海量数据时没有较好并行分类算法的问题. 并给出了指导该并行算法高效计算的方法. 数据运行试验和算法分析表明,该并行算法的性能受多个因素影响,并具有高效的并行效率计算加速比.     

GPU加速技术在医学三维可视化中的应用

针对三维可视化体显示技术在医学影像领域应用时,在没有硬件加速的情况下几乎很难做到实时交互显示的效果问题。本文尝试了基于GPU架构进行并行计算的方法。同时利用MFC扩展动态库及导出类技术,避免了大量代码移植。在试验过程中,针对特定显卡,对GPU同时执行的线程数与计算时间做了统计分析,找到了计算时间最少的最优线程数。实验表明,本文提出的GPU加速方法,计算速度可以提高5～6倍。