杨保国

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

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

杨保国

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

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

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

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