基于OpenCL的最短路径图算法实现

杨保国

(上海理工大学 光电信息与计算机工程学院，上海 200093)

基于OpenCL的最短路径图算法实现

杨保国

(上海理工大学 光电信息与计算机工程学院，上海 200093)

当今生物医学影像涉及越来越多的成像数据，需要进行快速计算最短曲率值。最短路径算法在这个应用中发挥重要的作用，dijkstra算法就是用于计算源点到其他节点的最短路径的常见算法。过去普遍认为最短路径算法在CPU上的运行速率过低，很难用于交叉学科和曲率测量类型研究的曲率计算。OpenCL架构是基于异构平台的行业标准框架，能够利用GPU作为协处理器，进行通用计算。大脑皮层曲率是生物医学领域研究的热点，该文利用OpenCL在高性能计算领域的巨大优势来进行加速计算，实现了Dijkstra算法的并行编程。实验结果获得了4.73～9.69倍的加速比，表明了OpenCL确实具有很好的加速效果，且对最短路径算法有很好的改进。

Dijkstra算法；OpenCL；通用计算；最短曲率值

图算法是许多特定的应用，如基因组序列和超大规模集成电路自动设计的基础。随着社交网络的迅速成长，图算法被发现在网络中分析用户的关联分析和产品推荐方面有着更重要的应用[1-2]。最短路径算法是许多复杂的图算法的一个重要组成部分。现如今，Dijkstra(迪杰斯特拉)算法研究主要有两个热门的研究方向：1)针对经典Dijkstra串行算法的代码重构，减少循环的使用，以达到减小算法的空间复杂度和时间复杂度，提高算法的运行效率，减少运行时间；2)修改 Dijkstra算法为并行结构，并充分利用计算机的计算资源，如多核结构，提高算法的运行效率。目前一般的做法是根据并行数进行网络节点的平均分配，然后进行并行计算处理。

并行计算是一个新兴的计算方法；作为一种普遍使用的硬件加速器，图形处理单元(GPU)，强大的并行计算能力已使其得到大量使用。近几年，应用通用计算领域图形处理器GPGPU，解决最短路径问题，以提高运行效率，减少运行时间的研究已增加。基于GPU解决SSSP问题已经有了不同的算法，如在之前开发的Dijkstra算法[3-4]。

Dijkstra算法是以起始点为中心向外层遍历，直到遍历搜寻到终点，停止遍历。我们知道，单源最短路径问题为已知有向图G=(V，E)，要求找出从某个定源顶点t，到每个顶点v上的最短路径。简单来说，就是一个图G中，找到一个定点t，然后以t为起点，找出t到图G中其余各个点的最短距离或路径。

神经医学影像工具，能够由MRI图像创建脑皮层三角格重构，作为大脑脑皮层曲率研究的一部分，网格的各条边上存储了一组曲率测量值，查找大脑上不同起始点到脑皮层其余部位所有其他顶点的最短曲率值。计算最短曲率值，需要从指定起始节点找到其他目的节点的最短路径[5-6]。Dijkstra算法能得出最短路径的最优解，然而，由于需要遍历计算的顶点较多，利用传统的CPU串行遍历，计算效率很低。人们自然地就要追求高性能并行计算方法。

GPU上的并行计算是用于以合理的成本和相当高的性能速度进行高性能计算的技术之一。 GPU目前可用于除了图形处理和游戏之外的各种目的，这就是为什么我们将GPU称为通用图形处理单元，因为它提供高性能计算，可以使用标准帧工作进行编程。OpenCL是一个适用于所有GPU的框架，而CUDA仅适用于NVIDIA GPU。因此，由于其可移植性和开放性，我们将使用OpenCL用于我们的GPU实现。OpenCL提供了一种利用系统中的异构资源的方法，并且可以控制特定硬件上的执行。可以使用OpenCL显式选择CPU和GPU执行。控制执行的代码段称为主机代码，并且在CPU或GPU上并行运行的代码称为内核[7]。开放运算语言为程序员提供了一个统一的编程环境，很方便地在高性能计算服务器、桌面计算系统、手持设备编写高效轻便的代码，并广泛地用于游戏[8]、娱乐、医疗[9]等领域。

1 Dijkstra算法串行实现

解决单源最短路径问题，我们必须要明白最短路径中最优子结构(optimal substructure)的含义。它的定义如下：Q(i,j)={Vi…Vk…Vl…Vj}是从起始点i到终点j之间的最短路径及距离，其中k和l是求解得到路径上的中间节点，此时Q(k,l)之间的路径肯定也是从i到j之间的最短距离。证明如下：

目标函数：Q(i,j)={Vi…Vk…Vl…Vj}是从顶点i到j的最短路径，则Q(i,j)等于Q(i,k)与Q(k,l)与Q(l,j)三者之和。假设：Q(k,l)不是从k到l的最短距离，那么也就必定存在另一条从k到l的最短路径Q′(k,l)。但是这时Q(i,k)，Q(k,l)，Q(l,j)之和的距离就小于Q(i,j)的距离。这就与Q(i,j)是从i到j的最短路径矛盾，故假设不成立。由证明的结果可以知道，如果存在从i到j的最短路径(Vi…Vk,Vj)方案，Vk是Vj前面的一个顶点，那么(Vi…Vk)也必定是从i到k的最短路径。为了求出最短路径，Dijkstra就是以最短路径长度依次递增，逐步求解出最短路径。对于起始点V0，首先选择其直接相邻的顶点中长度最短的顶点Vi，那么当前已知可得从V0到达Vj顶点的最短距离dist[j]就是等于dist[j]与dist[i]+matrix[i][j]二者之间的最小值。

算法具体步骤如下：1)初始化时，L只含有源节点；2)选择目标点，从集合U中选取距离v最小的顶点k，然后加入集合L中(这样选择的距离就是v到k的最短路径距离)；3)变更权值，以k为进一步考虑的节点，开始逐步修改U中各顶点的距离；如果从节点v到顶点u的距离比原先计算得到的距离短，则修改顶点u的距离值，修改后的距离值是顶点k的距离加上k到u的距离之和；4)递归循环，循环计算步骤2)和步骤3)，直到所有顶点都包含在L中[10]。如图1所示。

图1 六顶点路径图

伪代码如下：

dist [l]←0

for allvV-{l}

do dist[v]←

L←

Q←V

WhileQ≠

dou← mindistance(Q,dist)

LL{u}

for allvneighbors[u]

do if dist[v] > dist[u] +w(u,v)

then d[v] ←d[u] +w(u,v)

return dist

编程后，得结果从A至F的最短路径为：ACDF。

Dijkstra算法用来计算从源节点t到剩余节点，探索相邻节点以下的节点最小路径。这种探索过程被称为边缘松弛。当边(u,v)从节点u放松，即说明节点u已经达到。因此，从t至u的路径用一个试探性的最短距离到达节点u，这就是遍历过后的状态。算法找到从源节点t的最短路径，算法结束时所有节点都得到遍历了[11]。

从研究传统Dijkstra算法的前人研究结果来看，多数采用的是图层次遍历方式，即从顶点作为出发点的两次循环，然后遍历网格上的剩余节点，从而得出图中节点到节点的最短路径。

2 算法的并行实现

将Dijkstra算法移植到GPU上，充分利用GPU计算资源进行加速是本文的目标。第一步是创建一个可以由GPU高效访问的图数据结构。图由顶点和连接这些顶点的边组成。每条边上都关联有一个权值，需要为经过这条边设立某种开销。我们要知道的是遍历网格时如何最小化曲率值。图数据结构表示为一组数组：

这三个境界也可以对应我们人生的三个阶段。第一个阶段就是，寻找探索阶段，因为这个阶段还没有明确的目标，明确的想法，所以，最需要的就是开拓眼界，开拓思维。古诗文，如果仅仅是理解诗文中的意思，其实只是处于第一个阶段。真正进入第二阶段，就需要把古诗文充分的和生活结合起来。第三境界，也就是追寻理的最高境界，那就是道，是一种超越世间万物的思想。在这方面，我们可以一段公案来看。这段公案牵涉出两首诗。大家请看。

int * vertexArray:每个数组项包含一个索引，指向将作为该顶点一条边的edge-Array的第一个元素。

int*edgeArray:该数组的各个元素通过边与当前顶点连接的各顶点索引。

int*weightArray:对于edgeArray中的各条边，存储了边的权值。

这3个数组构成了整个图数据，应用程序需要建立这些数据才能利用我们的实现运行Dijkstra算法。实现本身还需要3个数组，这些数组将在计算过程中由内核使用：

int *maskArray:为各个顶点存储一个0或1。

float *updatingCostArray:用来存储为顶点计算的当前开销。

float *costArray:存储对于各个顶点最终计算出的最小开销。

typedef struct{

int *vertexArray;

int vertexCourt;

int *edgeArray;

int edgeCount;

float *weightArray;

} GraphData;

void runDijkstra (CL_context gpuContext, CL_device_id deviceId,

GraphData* graph,

Int *sourceVertices, float *outResultCosts,

int numResults);

只需指定要为哪些源顶点运行算法，还需在宿主机上分配一个数组。Dijkstra算法每次执行都会输出一个数组，其大小等于图中顶点的个数，包含从源顶点到图中各顶点的最短距离的总开销。

对于每个源顶点，在OpenCL中排队的第一个内核只负责缓冲区初始化。这要由一个kernel来完成，而不应在CPU上完成，以减少CPU和GPU之间传输数据所使用的额外开销[12-13]。

OpenCL执行算法的高层循环伪代码为：

Foreach sourceVertex to search from

initialize MaskAndCostArraysKernel ()

while(! maskArrayEmpty ()) enqueueKernelPhase1 () enqueueKernelPhase2 ()

ReadMaskArrayFromDeviceToHost ()

ReadCostArrayFromDeviceToHost ()

算法分为两个阶段：1)执行kernel算法要求必须同步，将访问maskArray中标记的所有顶点，确定到各个相邻顶点的开销；2)查看是否为各个顶点找到一个更小的开销。

OpenCL将充分利用计算机的物理资源，通过CL函数划分工作负载，应用程序会检测GPU和CPU设备个数，将工作负载分摊到这些设备上。每个kernel一次处理一个顶点。全局工作组大小等于顶点数。对于CPU设备，OpenCL将实现所有可用的核多线程执行程序。

3 实验结果及分析

在Intel i5-2.67GHz，GPU:NVIDIA GT360上进行试验。使用GPU得到的性能提升依赖于图的大小和图的度。随着图中顶点数的增加，GPU的表现会远远超过CPU。测试的试验数据如表1所示，其折线直观显示如图2所示。

表1 顶点度为5的试验结果

如表1和图2所示， GPU实现相对于CPU实现性能优势会随着图中顶点的增长而显著增长。顶

图2 OpenCL、CPU的性能

点数越多，向GPU传输数据和提交、等待内核的相关开销就能影响较小，处理速度也就越快。所以，基于OpenCL的异构计算，实验获得4.73～9.69倍的加速比。

4 结束语

本文通过试验进行了Dijkstra算法的并行实现，显示出OpenCL异构计算在大数据、高性能领域的应用前景，如在分子流体动力学、基因分析、天文领域也有着很好的应用。由于实验硬件的局限性，试验中只实现了一定的加速比，后续将会在更高配的试验设备上运行，并作进一步研究，实现OpenCL在其他领域的应用。

[1] MALEWICZ G, AUSTERN M H, BIK A J C, et al.Pregel：a system for large-scale graph processing[C] // Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data.New York：ACM Press, 2010：135-146.

[2] KWAK H, LEE C, PARK H, et al.What is twitter, a social network or a news media[C]//Proceedings of the 19th International Conference on Worldwide Web, 2010: 591-600.

[3]MARTIN P J, TORRES R, GAVILANES A.CUDA Solutions for the SSSP Problem[M].Computational Science-ICCS 2009.Springer Berlin Heidelberg, 2009:904-913.

[4]HARISH P,VINEET V,NARAYANAN P J.Large graph algorithms for massively multithreaded architectures, center for visual information technology[R].International Institute of IT, Hyderabad, India, Technical Report IIIT/TR/2009/74, 2009.

[5]XU M H, LIU Y Q, HUANG Q L, et al.An improved Dijkstra’s shortest path algorithm for sparse network[J].Applied Mathematics & Computation, 2007, 185(1):247-254.

[6]LU X, CAMITZ M.Finding the shortest paths by node combination[J].Applied Mathematics & Computation, 2011, 217(13):6401-6408.

[7] MUNSHI A, GASTER B, MATTSON T，et al.OpenCL programming guide[M].苏国金,李璜,杨健康,译.北京：机械工业出版社,2012:140-157.

[8] WU E, LIU Y.General purpose computation on GPU[J].Journal of Computer Aided Design & Computer Graphics, 2004, 38(67):277-288.

[9] CORMEN T H, LEISERSON C E, RIVEST R L, et al.Introduction to Algorithms, Third Edition[M].殷建平, 徐云,王刚,译.北京；机械工业出版社,2013:413-417.

[10] ORTEGA-ARRANZ H, TORRES Y, GONZALEZ-ESCRIBANO A, et al.Comprehensive Evaluation of a New GPU-based Approach to the Shortest Path Problem[J].International Journal of Parallel Programming, 2015, 43(5):918-938.

[11] SCARPINO M.OpenCL IN ACTION[M].陈睿,译.北京：人民邮电大学出版社,2014:98-100.

[12] GASTER B R, HOWES L, KAELI D R.et al.OpenCL异构计算[M].2版.张云泉,张先轶,贾海鹏,译.北京：清华大学出版社，2013:161-181.

[13]何刚, 尹光福, 邹远文.基于OpenCL改进四邻域算法速度的研究[J].实验科学与技术, 2012, 10(2):53-54.

Realization of Dijkstra Graph Algorithms Based on OpenCL

YANG Baoguo

(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technolog, Shanghai 200093, China)

Nowadays, biomedical imaging involves more and more imaging data, which needs quickly calculate the shortest curvature value.Shortest path algorithm plays an important role in this application, dijkstra algorithm is a common algorithm for calculating the shortest path from source to other nodes.In the past, the shortest path algorithm was considered to be too slow on the CPU to be used for curvature calculations in cross-disciplinary and curvature measurement types.The OpenCL architecture, based on heterogeneous platforms, is an industry-standard framework that can be used as a coprocessor for general purpose computing.The curvature of the cerebral cortex is a hotspot in biomedical research.We use OpenCL to accelerate the calculation of the advantages of the field of high-performance computing and achieve the Dijkstra algorithm for parallel programming.The experimental results show that we get 4.73-9.69 times speedup, which shows that OpenCL has a good acceleration effect, and the shortest path algorithm has achieved a good improvement.

dijkstra algorithm; openCL; general purpose computing; shortest curvature value

2015-07-23；修改日期:2016-11-22

杨保国(1994-)，男，硕士，主要从事并行计算方面的研究。

TP391.41

A

10.3969/j.issn.1672-4550.2017.01.016