面向多核CPU与GPU平台的图处理系统关键技术综述

图计算作为分析与挖掘关联关系的一种关键技术,已在智慧医疗、社交网络分析、金融反欺诈、地图道路规划、计算科学等领域广泛应用.当前,通用CPU与GPU架构的并行结构、访存结构、互连结构及同步机制的不断发展,使得多核CPU与GPU成为图处理加速的常用平台.但由于图处理具有处理数据规模大、数据依赖复杂、访存计算比高等特性,加之现实应用场景下的图数据分布不规则且图中的顶点与边呈现动态变化,给图处理的性能提升和高可扩展性带来严峻挑战.为应对上述挑战,大量基于多核CPU与GPU平台的图处理系统被提出,并在该领域取得显著成果.为了让读者了解多核CPU与GPU平台上图处理优化相关技术的演化,首先剖析了图数据、图算法、图应用特性,并阐明图处理所面临的挑战.然后分类梳理了当前已有的基于多核CPU与GPU平台的图处理系统,并从加速图处理设计的角度,详细、系统地总结了关键优化技术,包括图数据预处理、访存优化、计算加速和数据通信优化等.最后对已有先进图处理系统的性能、可扩展性等进行分析,并从不同角度对图处理未来发展趋势进行展望,希望对从事图处理系统研究的学者有一定的启发.

多核CPU环境下的并行遗传算法的研究

多核CPU已经成为当前CPU市场上的主流产品,设计适应多核CPU环境的算法与软件势在必行。遗传算法是一种具有很强通用性的全局搜索方法,也是一种计算量大、极耗计算资源的算法,其传统的串行计算形式并不能充分利用多核的计算资源,将其设计为适应多核CPU环境的并行计算形式,具有重要的现实意义。将遗传算法的基本操作设计成并行执行形式,并利用OpenMP将其线程化,从而对不同规模的TSP问题的求解结果来看,加速比与计算效率随着规模的增大而提高。

在集群多核CPU环境下的等高线并行提取方法

分析集群环境下分布式存储编程模型和多核CPU环境下共享存储编程模型各自的优缺点,采用结合集群和多核CPU的并行环境来取长补短;并研究其在等高线提取中的相关并行算法,其中以建立三角网和跟踪等高线作为共享存储并行的研究实例;最后通过实验验证了该并行方案的可行性。

多核CPU的海量点云并行kNN算法

提出基于多核CPU的海量点云k最近邻(kNN)快速搜索算法。该算法先将点云数据按格网方式进行组织存储于外存;在搜索kNN点时,从搜索点所在的块向外扩张搜索;在多核CPU环境下采用多线程模式进行数据的内外存调度和kNN点搜索。当内存达到设定上限时,采用距离搜索点最远策略释放内存,降低内外存数据交换的频率。将该方法应用于基于kNN的滤波和格网化方法中,处理速度显著提高。

多核CPU环境下小生境混合遗传算法的研究

为克服遗传算法的缺点,利用小生境的启发作用,引入改进的模拟退火操作,构造了一个兼顾全局搜索与局部探测的混合遗传算法。针对该算法内在的良好并行性及串行计算难以发挥多核CPU计算优势的问题,将遗传操作和模拟退火操作设计成并行计算形式,利用OpenMP将其线程化。对TSP的求解验证了该算法的有效性,并行算法的加速比和计算效率随着TSP规模的增加而显著提高。

基于多核CPU的复杂液压产品快速并行优化方法

为缩短复杂液压产品的研发周期和提高系列化产品的开发效率,提出一种基于多核CPU的复杂液压产品快速并行优化方法。该方法利用粒子群算法寻求产品设计参数的优化和性能指标的约束,将每个仿真程序视作粒子群个体。采用两级加速策略,即CVODE求解器加速和多核CPU加速。以非对称轴向柱塞泵三角槽优化设计为研究对象,通过物理样机试验对CVODE求解器加速方法的准确性进行验证,结果显示,试验与仿真结果吻合度较高。利用粒子群算法对三角槽主要参数进行优化以降低泵输出流量脉动。对比三角槽结构优化前后的流量脉动率,结果显示,在不增加柱塞腔压力的条件下,非对称轴向柱塞泵三角槽优化后的流量脉动相比优化前降低了36%。该方法可脱离专业仿真软件平台,能够独立运行于Windows操作系统,解决液压动态仿真对专业软件依赖的问题,且多进程比多线程编程更容易实现。在8核CPU工作站仿真条件下,与SimulationX平台仿真方法相比,该多核CPU并行方法的仿真效率提高10倍以上,与双核计算机并行运行效率相比提高近5倍。

并行帧缓存设备:基于多核CPU的Xorg并行显示优化

Xorg图形服务器软件在帧缓存设备上采用单线程绘制模式,难以发挥多核CPU的性能.针对多核CPU上的帧缓存设备,设计了带有互斥操作的任务队列,并按照屏幕划分的方法,实现了Xorg的矩形填充操作在帧缓存设备上基于私有任务队列的多线程并行化,并实现了主从线程负载均衡.x11perf测试结果表明,该算法在一台4核商用台式机上的加速比可以达到2.06.

多核CPU-GPU协同的并行深度优先算法

针对多核CPU和GPU环境下图的深度优先搜索问题,提出多核CPU中实现并行DFS的新算法,通过有效利用内存带宽来提高性能,且当图增大时优势越明显。在此基础上提出一种混合方法,为DFS每一分支动态地选择最佳的实现:顺序执行;两种不同算法的多核执行;GPU执行。混合算法为每种大小的图提供相对更好的性能,且能避免高直径图上的最坏情况。通过比较多CPU和GPU系统,分析底层架构对DFS性能的影响。实验结果表明,一个高端single-socket GPU系统的DFS执行性能相当于一个高端4-socket CPU系统。

基于多核CPU和GPU的高光谱数据并行几何校正

针对高光谱几何校正计算复杂,大数据量频繁传输降低处理效率,无法满足实时需求等问题,提出基于多核CPU和GPU的并行计算模型。实现基于GPU的并行几何校正,并引入流水线并行思想提出基于多线程的数据读写优化方法,实现重采样部分的数据I/O优化。应用航空推扫成像仪所得高光谱数据进行实验,验证该方法能够有效地隐藏部分硬盘与内存间的数据I/O时间,几何校正加速比达到4.03,在基于GPU的并行计算基础上提高了1.74倍。

基于多核CPU的遥感去雾并行算法研究

针对数据量较大的遥感影像进行去雾处理时出现的运行效率低下或者是计算无法进行的问题,提出了多核CPU并行去雾算法。首先对影像进行分块分割,再根据滤波影响域对分块影像进行扩边,并建立影像索引,然后将分块影像分配给不同的CPU内核进行去雾处理,最后利用影像索引将去雾处理后的分块影像进行合并。实验表明,经本文改进的并行去雾算法与传统暗通道去雾算法的去雾效果一致,而算法的执行效率得到了提高,具有很强的实用价值。

基于多核CPU+GPU运算的电磁场高效体绘制算法研究

雷达探测范围作为电磁场的一个典型代表,由于其在军事决策时扮演着重要的作用,所以对探测范围可视化的准确性和实时性的要求很严格。传统的面绘制三维数据场信息会造成大量的空间信息丢失。因此,采用体绘制技术来获取电磁场中的三维数据场信息。针对传统体绘制技术算法执行效率较低的问题,提出使用多核CPU+GPU的架构来加速体绘制,从而实现实时处理。实验表明,采用提出的方法可以大幅减少体绘制中光线绘制的时间,充分利用CPU的空闲存储资源和计算资源。

基于多核CPU的干涉成像光谱仪快速数据重建方法

成像光谱仪作为一种航空航天遥感器工作,可以同时得到地物的二维空间图像信息和一维光谱的丰富信息,在颜色和光谱测量、真彩色图像合成、军事侦察等领域有着很高的实用价值。为了达到对干涉成像光谱仪数据快速处理的要求,使用OpenMP并行计算技术设计了基于多核CPU的成像光谱仪快速数据重建优化算法,并将其应用到我国"环境一号"卫星的高光谱数据处理任务中。实验结果表明,基于多核的并行计算技术能有效调动多核CPU的硬件资源,大幅度提高光谱重建处理任务的计算效率。如果将该技术应用到更多核的并行计算工作站上,单台计算机完成干涉成像光谱仪数据的实时处理任务将成为可能。

多核CPU上快速傅里叶变换并行算法的优化

快速傅里叶变换在数字信号处理和通信领域具有广泛的应用.多核CPU日益普遍,根据FFT算法自身的并行性,灵活分解蝶形运算,通过探究并行块的分配和嵌套关系对算法加以优化,合理地分配线程实现多核CPU的并行计算,可以提高FFT的计算效率.

一种新的APGA算法及其在多核CPU环境下的Java实现

研究了遗传算法(SGA)的遗传自适应策略和并行遗传算法(PGA)迁移时的自适应策略,提出了一种新的自适应并行遗传算法(APGA),描述了算法的流程和关键算子,最后给出了在多核CPU环境下用Java实现的APGA算法。

Windows操作系统多核CPU内核线程管理方法

Windows是采用CPU时间片轮转多任务分配机制的非实时操作系统,无法满足实时性要求比较高的任务需要。而随着CPU技术的快速发展,当前市场上双核甚至多核CPU已成为主流,这使得在Windows平台上用多核CPU的某些核独立执行任务,从而有效地提高软件的实时性成为可能。本文介绍一种在Windows内核模式下编写Windows驱动程序,有效分配多核CPU资源从而提高软件实时性的方法。

基于多核CPU的并行程序在指控系统中的应用

简单介绍了多核处理器产生背景和原理,分析了多核处理器和基于多线程的并行程序设计在指控系统中的应用前景,介绍了并行应用的编程过程。最后在Microsoft Visual Studio.Net 2005环境下采用OpenMP编程实现了指控系统中一个算法的并行化,并根据多次运行给出该程序在不同线程数目下的平均耗时,验证和分析了基于多核CPU的并行程序的性能。

基于多核CPU的无人机影像连接点并行匹配方法

影像连接点匹配是无人机影像摄影测量处理的一个关键步骤,匹配速度直接关系着处理的效率。本文提出一种基于多核CPU的无人机影像连接点并行匹配方法。该方法以SURF特征匹配和最小二乘匹配为基础:首先利用POS数据计算影像间的邻接关系;然后根据CPU处理核数确定匹配任务单元,制定并行处理策略;最后在指定CPU处理核上对匹配单元进行几何约束的影像匹配和粗差剔除。多组影像匹配试验表明,设计的多核并行匹配方法,能够大幅提高处理效率;在特定的硬件环境下,与常规串行匹配处理相比,其加速比与CPU处理核的个数成近线性关系。

64位多核CPU中交叉开关总线的设计与实现

交叉开关是无阻塞网络,允许所有可能的点对点间的同时连接。随着制程工艺的发展,越来越多的多核处理器开始采用交叉开关作为内部互连机制。本文论述了在64位多核处理器中交叉开关总线的设计与实现,在本设计中,它的主要功能是控制多个处理器核以及存储、功能单元之间的通信。本设计的优点是采用全定制方式实现数据通路的后端物理设计。最终结果显示本设计比采用自动布局布线方式节省版图面积达30%以上。

基于多核CPU的DVB-RCS2并行Turbo译码方法

DVB-RCS2在卫星广播、海事卫星通信、军事卫星通信等领域有着广泛应用,而无论是通信还是军事侦察都需要大吞吐量高速译码。多核CPU算力不断提升以及软件无线电SDR平台的广泛应用,使得基于多核CPU的并行译码成为一种灵活高效的应用方式。为了满足其中双二元Turbo码大吞吐量软件译码的需求,提出了一种基于多核CPU的高速并行软件译码方案。首先对比分析了双二元Turbo码与传统二进制Turbo码的计算复杂度;然后重点对并行计算过程中的内存占用和采用8比特位宽整型数据时的输入量化方法进行了分析和优化,设计了基于多核CPU并行译码的实现方案;最后在Intel 12核CPU上使用SSE并行指令集实现了大于169 Mbps的译码吞吐率,且纠错性能较浮点运算损失小于0.1 dB。通过与现有GPU译码方案对比,说明了所提方案在译码效率和能耗方面的优势,其在高速卫星接收机中具有极高的应用价值。

多核CPU/GPU平台下的集合求交算法

提出一个多核CPU/GPU混合平台下的集合求交算法。针对CPU端求交问题,利用对数据空间局部性和中序求交的思想,给出内向求交算法和Baeza-Yates改进算法,算法速度分别提升0.79倍和1.25倍。在GPU端,提出有效搜索区间思想,通过计算GPU中每个Block在其余列表上的有效搜索区间来缩小搜索范围,进而提升求交速度,速度平均提升40%。在混合平台采用时间隐藏技术将数据预处理和输入输出操作隐藏在GPU计算过程中,结果显示系统平均速度可提升85%。