原创《图论算法中GPU加速技术应用分析》：本论文可用于图论算法论文范文参考下载，图论算法相关论文写作参考研究。
数学和计算机科学领域,积极的对各种高效的图算法进行设计是十分重要的内容.就目前的实际情况来看,算法相关理论经过一点时期的发展,已经较为程度和丰富.但同时,也面对一定的发展平台,积极的开发并行的图算法已经成为摆在研究人员面前的重要课题.考虑到传统CPU在数据处理方面所受的限制,GPU运算处理器开始被逐渐应用于研究之中.文章从GPU 和传统并行计算架构的差异入手,分析GPU加速技术在图论算法中的应用效果.
图论算法 GPU加速技术
最小生成树 应用
前言
当前,在人们的日常工作和生活中存在着海量的数据,为了更好的进行数据分析,对高性能计算也产生了较大的需求.而传统的单核计算方式显然已经无法满足现实情况的需求,为此,GPU（图形处理单元）作为具有大量计算核心的众核架构,开始被逐渐应用于各种实际问题之中.但是,目前关于在GPU上的图算法,相关的研究还相对较少.
GPU和传统并行计算架构的差异
（1）GPU和分布式集群
GPU和分布式集群之间的差异主要体现在通信方式以及计算方式上.其中,在通信方式上,集群在实现通信的时候,主要借助于互联网或者局域网.在具体的计算过程中,需要充分重视传输的细节,以免设计方面出现传输限制的问题.但是,在使用GPU芯片的时候,在对数据等进行传输的时候,采用的是PCI-E接口,不需要对传输细节予以过分的關注,仅需要解决如何对计算内容进行分配等问题即可.在计算方式上,集群在计算方面采用的是主从模式,通过分割计算的方式来完成相关的计算.而GPU则利用Slave来完成计算.
（2）GPU和多核CPU
GPU和多核CPU的区别主要体现在架构以及设计目的方面.在CPU芯片上,在对电路予以应用的时候,大多将其视为逻辑控制或者缓存.这样一来,也导致计算单元的晶体管数量十分有限.经过大量的实践也发现,在应用GPU的时候,涉及到的并行指令数量十分有限.但绝大多数CPU采用的是长指令字等指令级的并行技术,其架构和GPU之间差异较大.另外,另外,从设计目的角度进行分析,CPU的主要设计目的是为了对ALU指令的获取以及执行予以实现.为此,涉及到的逻辑控制电路等的数量较多.但是,GPU的主要设计木的是实现自身计算能力的不断提高.同时,也十分注重提高对各种数据的吞吐效率,于是在逻辑控制设计方面进行了一定的简化处理.
GPU加速技术在图论算法中的应用
（1）GPU加速计算有向图的强连通分量
将GPU加速技术应用于图论算法之后,可以设计一个基于CUDA的FB算法.该算法具有一定的独特性,可以很好的计算非平凡图的强连通分量.应用过程种,在利用GPU技术存储图数据的时候,需要进行综合性的考虑.首先,要注意到和现代的传统CPU主机系统进行比较,在系统内存方面,GPU处于相对较小的状态.其次,对CUDA模型进行分析,认识到其采用的是一种CPU-GPU的异构模型.该模型在传输各种数据的时候,和以往的计算机之间存在一定的差异.另外,对CUDA存储系统进行分析,充分考虑到在其内存和主存之间,要注意选择不同的地址空间.这样一来,也导致在进行指针数据操作的时候,存在较大的难度.除此之外,在内存方面,设备采用的是线性内存的方式,更有利于数组形式数据结构的存取.
（2）GPU加速计算图的最小生成树
GPU加速计算图的最小生成树方面,对于生成树中涉及到的不同边权,可以对其进行综合性的定义,将其定义为G的耗费.考虑到不同的子图所生成的生成树在耗费方面存在极大的差异,相应耗费最小的便被视为最小生成树.在CUDA模式下,为了能够更好处理各种图的数据结构,并尽可能的占据较小的存储空间,在计算生成树的时候,大多会选择两种图的数据结构.两种不同的数据结构共同构成了一个整体,这一整体中包含两种不同的计算方法.
（3）GPU加速计算图的最短路径
在现实生活中,经常会遇到一些最短路径问题,例如物流运输等.如何科学的选择最短路径,成为备受人们关注的重要问题.在本次研究中,选择使用一种基于CUDA的并行算法进行分析.利用该算法,可以对SSSP算法实现多次重复运行.并通过重复运行,实现边权值的非负APSP问题.具体来看,基于CUDA的SSSP算法计算过程中,为了顺利的实现这一算法,需要对邻接表予以压缩,进而计算图中的数据结构.但就目前的实际情况来看,在CUDA编程中,所使用的运行方式是CPU和GPU两种线程同步运行的方式.现实生活中,人们通过开发multiprocer之间的同步,可以很好实现全局线程的有效同步.另外,为了妥善解决APSP问题,还可以在每一个顶点上对上一节的SSSP算法予以运行.通过应用上述并行方案,可以对GPU的全局内存予以有效的利用.
结束语
随着时代的发展,计算领域,各种算法和理论、计算方式等也在发生着极大的改变.和传统的CPU以及集群算法进行比较,GPU具有十分明显的应用优势,在降低功效,减少成本等方面十分突出.GPU的计算能力不断增强,并在多个不同的领域得到广泛的应用.
相信,在未来的图论算法中,GPU加速技术必将得到越来越广泛的应用,并发挥出更大的作用来.
作者简介：杜衡吉（1976.3-）,男,汉族,江苏邳州人,讲师,硕士,主要从事计算数学及计算机应用研究
[1] 郭绍忠,王伟,周刚,等.基于GPU的单源最短路径算法设计和实现[J].计算机工程,2012,38（2）：42-44.
[2] 郭绍忠,王伟,王磊,等.基于GPU的并行最小生成树算法的设计和实现[J].计算机应用研究,2011,28（5）：1682-1684,1702.
[3] 王卫星,田利平,王悦,等.基于改进的图论最小生成树及骨架距离直方图分割细胞图像[J].光学精密工程,2013,21（9）：2464-2472.
图论算法论文参考资料：
结论：图论算法中GPU加速技术应用分析为大学硕士与本科图论算法毕业论文开题报告范文和相关优秀学术职称论文参考文献资料下载，关于免费教你怎么写图论基础知识方面论文范文。
