Dijkstra算法的并行实现算法的并行实现
文章研究了一种多核架构下基于OpenMP的Dijkstra并行算法,以Dijkstra算法为基础设计并行程序。对传统
Dijkstra算法进行分析,明确优化方向,再利用OpenMP开发工具对并行程序进行优化调试。结果表明,文中算
法易于操作,并充分利用了多核处理器并行计算的优势,提高了算法的运行效率,验证了算法的优越性。
逄淑玲,王晓升
(山东女子学院 信息技术学院,山东 济南 250300)
摘要摘要:文章研究了一种多核架构下基于OpenMP的Dijkstra并行算法,以Dijkstra算法为基础设计并行程序。对传统Dijkstra
算法进行分析,明确优化方向,再利用OpenMP开发工具对并行程序进行优化调试。结果表明,文中算法易于操作,并充分利
用了多核处理器并行计算的优势,提高了算法的运行效率,验证了算法的优越性。
关键词 关键词:多核;Dijkstra算法;OpenMP;并行算法
中图分类号中图分类号:TP312文献标识码:ADOI: 10.19358/j.issn.1674-7720.2017.09.008
引用格式 引用格式:逄淑玲,王晓升.Dijkstra算法的并行实现[J].微型机与应用,2017,36(9):25-27.
0引言引言
随着多核的发展,串行执行程序的缺点暴露无遗,传统的Dijkstra算法是串行算法,搜索过程易懂,程序设计简单,但大量
内存空间与计算时间的耗费成为此算法的瓶颈,而有效解决的途径之一就是并行计算。为将计算能力最大化,需将一个应用程
序划分为多个相对独立的任务并交由多个计算核执行。为从语言成分上直接支持并行,完全摆脱串行语言的束缚,设计了一种
全新的程序设计模型,该并行算法与以往传统算法相比能够更有效地提高运行效率,充分发挥高性能多核处理器的功效。
1OpenMP
OpenMP是一种支持跨平台共享内存方式的多线程并发编程模型,开发过程中无需考虑数据分布,具有良好的可移植性、
可扩展性,同时支持C、C++和FORTRAN语言。OpenMP提供一系列体系结构和编程平台,建立简洁高效的编程指导命令和
并行编程方式,并提供各类串行程序并行化的可行方案[1]。OpenMP不是独立的并行语言,通过在适当位置加入编译指令
和运行库函数来并行化串行程序。OpenMP从主线程开始执行,一直串行地执行该线程,当线程某些点需要并行执行时,程序
则派生出额外的线程,组成一个线程组,这些线程在并行域的代码区中并行执行,线程到达整个并行区域的末尾时等待,直到
整个线程组都到达,最终相连接,这时只有主线程继续执行直到下一个并行区域或程序结束[2]。举例说明[3]:
int main(int argc,char*argv[]){
#pragma omp parallel for
for(int i=0;i<10;i++)
{
printf(“i=%d/n”,i);
}
printf(“finished.\”);
return 0;
}
这段程序就是使用OpenMP编译指导语句“#pragma omp parallel for”将for循环里的内容并行执行,从而提高效率。
2Dijkstra最短路径算法最短路径算法
2.1算法思想算法思想
Dijkstra算法是典型的单源最短路径,以起始点为中心向外层层扩展,直到拓展到终点为止。假设Len(v)表示一个顶点
到给定顶点U的最短距离,w(u,v)表示两个顶点间的距离。给出两个顶点V1、V2,求两顶点之间最短距离。算法描述如下
[4]:
(1)给定顶点V1,标记这个顶点并初始化所有的顶点,将顶点V1放入集合S。
(2)对于集合S中的所有顶点Vi,计算Vi相邻的所有顶点Uj的md(ui,vi)=w(ui,vj)+Len(vj)值并找出最小的md(u,v)值的顶
点U,将顶点U放入集合S中。
(3)重复上述步骤,直到将目标顶点V2放入集合S中,即可求出顶点V1到V2间的最短距离,得到最短路径[5]。