GPU加速技术在图论算法中的应用探讨.pdf

"GPU加速技术在图论算法中的应用探讨" 本文探讨了GPU加速技术在图论算法中的应用，特别是针对FB算法的研究。FB算法是一种图论算法，旨在解决图论问题中的强连通分量问题。通过使用GPU加速技术，可以将FB算法的计算过程加速，并提高其并行化能力。 在FB算法中，需要对下面两个引理进行重点的观察：给定有向图G=(V,E)，v∈V，则FW D(G,v) n BW D(G,v) = SCC(G,v)。给定有向图G=(V,E)，v∈V，那么对于任何不包含v的强连通分量，其一定是FW D(G,v) BW D(G,v)和Rem(G,v)三个集合的交集。 在使用GPU加速FB算法时，需要首先选取一个顶点，然后对其前闭包和后闭包进行计算，两个集合之间的交集就是强连通分量值。然后，通过剩余的顶点对原图进行3个子集的划分，并通过迭代计算对三个子图进行重复性的计算，这样就能够实现子图的并行处理计算。 在基于CUDA的FB算法中，首先是GPU中的图存储，对于当前的图算法，其采用的都是邻接表或邻接矩阵，对于G=(V,E)，其采用的邻接表来对其进行表示，定义数组Adi来表示lVI，其包含了满足(v,u)∈E的全部顶点，然后通过IVI×IVI来对矩阵进行表示。通过邻接表对无向图进行表示时，其大小为|E|，而有向图的表达则是|E|。而采用邻接矩阵进行表示时，其空间需求都是O(V^2)。 在使用GPU技术进行图数据的存储时，需要考虑以下几点内容：首先是同现代的传统CPU主机系统相比，GPU的系统内存相对较小，然后是CUDA的模型，其采用的是一种CPU-GPU的异构模型，这种模型在进行数据传输时与传统计算机不同，最后是对CUDA的存储系统，其内存和主存两者之间选择不同的地址空间，因此，在进行指针数据的操作时较为困难，且设备的内存采用的是线性内存，这种存储方式更适合数组形式的数据结构存储。 然后是算法的主体结构，对于FB算法，其SIMT架构也能够对顶点的闭包进行计算，通过迭代方式能够对非平凡的强连通分量进行计算，然后通过核函数起到时的线程分配来实现线程的计算和访存。 GPU加速计算图的最小生成树是一个重要的研究方向。对于生成树中的各边权，将其综合定义为G的耗费，因为不同的子图生成的生成树具有不同的耗费，而其中耗费最小的就是最小生成树。在CUDA模式下的最小生成树进行了简单的介绍。为了能够更好地对图的数据结构进行处理，同时节省存储空间，在对生成树进行计算时，往往 采用的是两种图的数据结构，下面的(a)和(b)两种不同的结构构成了两种不同的计算方法。