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

Realization of Dijkstra Graph Algorithms Based on OpenCL

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

Nowadays, biomedical imaging involves more and more imaging data, which needs quickly calculate the shortest curva- ture 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 heterogene- ous 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.