图论算法在GPU加速技术的应用

图论算法在GPU加速技术的应用

杨迪

辽宁石化职业技术学院辽宁锦州121001

摘要：就大部分学科而言，图数据是其基础理论，尤其在数学领域及计算机领域，通过怎样的途径可以使图算法提升其计算效率是当前研究的一个重点内容，而现今算法已日趋成熟，传统形式的图算法早已不能与之相适应，因而，并行图算法的相关研究受到越来越多人的关注。而相较传统形式的CPU，GPU的运算能力更加强大，因而受到的关注度也越来越高，使得图算法在该领域也得到了有效的发展。本文主要简析了现阶段图论算法中引入的GPU领域中的加速技术。

关键词：图论算法GPU加速技术应用

伴随社会信息量的不断增加，人们对于计算能力的要求也越来越高，传统模式的CPU属于单核计算，这已无法满足目前的社会发展，所以，多核计算以及并行算法的相关开发研究已成为发展的必然趋势。而图算法可以有效解决这一问题。

本文主要介绍了怎样通过GPU加速技术有效提升图算法的应用。

一、GPU和传统模式中并行计算之间的区别

1.和多核CPU之间的区别。

CPU具有的应用目的限制了其体系的发展，据研究表明，CPU应用时很少有并行指令，主要采取指令级形式的并行技术，这便与GPU有着质的区别。而且二者的设计目的也不一样，CPU主要是为了对ALU指令进行获取以及相关执行；而GPU则是为提升其计算能力，所以逻辑控制方面的设计要更简单。

2.和集群之间的区别。

GPU方面同集群方面存在的区别主要在于:其一计算方式不同。集群采取主从模式进行分割计算；GPU虽然通用计算类似于集群模式，但却是Slave。其二通信方式不同。集群以局域网形式过互联网形式进行通信；GPU以PCI-E接口形式来传输数据。

二、通过GPU对有向图的有关强连通分量进行加速计算

1.FB计算方法。

FB算法并不将DFS作为子问题，而是采取分配模式的形式把各子问题进行分配，在对应的单元里处理这些问题，其中主要以顶点具有的可达性特征来分析各子问题，所以，FB算法在并行化方面的能力比较强大。其中FB算法的计算过程为:先选取一个顶点，接着计算它的前闭包部分和后闭包部分，其集合交集便是强连通分量值。再利用剩下的那些顶点将原图划分出三个子图，以迭代计算的方式对其重复以上计算，以此来完成子图方面的并行计算。

2.以CUDA为基础的FB计算方法。

现阶段的图算法主要是邻接表形式或邻接矩阵形式，若G=(V,E)，则使用邻接表形式，数组Adj表示，所有满足(v,u)E的顶点都在其中，再用x表示矩阵，用邻接表方式表示无向图的时候，大小是2，表示有向图时为。而通过邻接矩阵形式来表示的时候，其空间需求方面均为O(V2)。以GPU技术存储有关图数据的时候应考虑以下问题:其一是存储方式方面的问题；其二是算法所具有的主体结构方面的问题。

三、GPU图中的最小生成树

在某子图中加入G，则该子图含有G的所有顶点，即G的生成树。而其中哪个的耗费最小哪个便是最小生成树。以下基于CUDA模式对其最小生成树展开介绍:为提升对图包含的数据结构方面的处理效率，可通过两种图形式的数据结构，以下（a）及（b）为两种不一样的结构分别构成两种计算方法，此图（a）可将全部边视为无方向的，以（S，E，W）来表示，而（b）则选择对邻接表进行压缩的方式，将所有边视为方向相反的边来表示，以(E,W)元组表示。Vp用于存放索引位置，W数组用于存储边权值。

四、GPU图中的最短路径

此问题经常被用于网络领域及物流领域之中，其中怎样有效选取最短路径是目前科学家最为关注、最值得探究的问题。本文主要选择以CUDA为基础的并行算法，此算法可以重复运行SSSP算法，达到边权值出现非负APSP目的。为实现以CUDA为基础的SSSP算法，采取压缩数据结构的方式计算，但是对现阶段CUDA编程而言，主要是CPU联合GPU同步运行方式，而实现multiprocer间的同步，可以同步全局线程。采取在各顶点上面对上一节进行运行的SSSP算法可以有效解决APSP问题，进而使GPU的整体内存都得以有效利用。

由于GPU具有的计算能力日益完善，因此其应用能力也将随之提升，相较传统模式的CPU技术及集群算法而言，GPU不仅成本低，而且功耗少，因此其势必会被应用于更多的领域。

参考文献

[1]郭绍忠王伟周刚等基于GPU的单源最短路径算法设计与实现[J].计算机工程，2012，（02），42-44。

[2]郭绍忠王伟王磊基于GPU的并行最小生成树算法的设计与实现[J].计算机应用研究，2011，（05），1682-1684。

[3]王一同GPU加速技术在图论算法中的应用[D].电子科技大学，2014，12。

[4]纪泽宇GPU加速技术在图论算法中的应用探讨[J].中国新通信，2016，18，（13），41-42。

[5]于平基于GPU加速的辐射度光照算法的研究及应用[J].国外电子测量技术，2016，35，（11），46-52。