论文部分内容阅读
数学与计算机科学领域，积极的对各种高效的图算法进行设计是十分重要的内容。就目前的实际情况来看，算法相关理论经过一点时期的发展，已经较为程度和丰富。但同时，也面对一定的发展平台，积极的开发并行的图算法已经成为摆在研究人员面前的重要课题。考虑到传统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加速技术
最小生成树 应用
前言
当前，在人们的日常工作和生活中存在着海量的数据，为了更好的进行数据分析，对高性能计算也产生了较大的需求。而传统的单核计算方式显然已经无法满足现实情况的需求，为此，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.