1绪论
1.1研究背景及意义最短路径问题是许多学科中普遍存在和广泛研究的问题，如计算机科学、计算机网络通信、计算机图形学、地理信息系统和智能交通系统等。近年来，由十二角网格模型在几何建模、计算机图形学等领域的广泛应用，使得人们开始关注十二角网格模型上最短路径问题的研究。在二维网格模型上寻找任意两个顶点间的最短路径是几何模型计算的基本问题，也是网格模型有意义的分割、机器视觉、模式识别等热点研究工作必须面对的基础问题fll若将二角网格模型石‘作是一个带权降}，网格中的顶点就是降}的顶点，两点间的距离长度为权值，则求解二角网格模型上两点间的最短路径就是求此带权图中两点间的最短路径。采用经典的最短路径算法如Dijkstra算法[f2l求解该问题，结果得到二角网格模型中首尾相连的边集:如果将可行路径进行细分，可以得到沿二角网格表面行走的最短路径结果，已有的算法分为精确算法和近似算法f=}-51两类。
虽然不断发展完善的训一算机数据结构与算法的有效结合涌现了大量二角网格模型上的最短路径算法f}-}l，但是这些算法都是基十串行方法求解的，随着网格规模的不断增大，串行最短路径算法的计算时间和存储需求也急剧上升，有时甚至出现单机无法求解的情况[f}l并行计算为快速求解大计算量的任务提供了一个有效途径，并行计算与并行算法是大规模科学计算的理论基础和支持工具【io-川。并行处理不仅可以为求解大规模复杂问题提供强大的计算能力和存储能力，还能够大大节省计算时间、提高计算效率。如对十顶点数目为1104,面片数目为2104的网格模型，在GenuineIntel(R)[email protected]处理器，1G内存的计算环境下，采用Dijkstra算法的计算时间超过8小时，这个时间开销对十用户来说是十分巨大的，Ifn通常Princeton二维网格模型库中的模型多数都大十这个规模。对十同样的计算问题和数据规模，采用并行算法求解时，使用2个处理器的计算时间降到1小时左右，4个处理器的计算时间约为0.39小时。可见，采用并行算法大大降低了求解二角网格模型最短路径问题的计算时间。因此，设计并行算法优化求解二角网格模型最短路径问题的复杂度和计算时间是很有必要的。求解二角网格模型上的最短路径是进行聚类分割二维网格模型的前期准备工作，提供了在模型的网格表面定义测地距离，基十测地距离进行聚类的前期准备【‘]。由十并行最短路径算法能够有效减少二角网格模型上求解最短路径问题的时间，因此提高了二维网格模型测地距离意义下聚类分割的效率。
1.2研究现状最短路径是图论中的一个经典问题，其研究起源十20世纪50年代末期，这类问题来自实践并已经成为许多优化问题的子问题，如网络通信系统中的资源分配、交通网络中的路线分析设计等。对最短路径的研究已经出现大量的算法，如经典的Dijkstra算法、Floyd算法等。最短路径算法有不同的分类，按图中顶点距离被标记的方式分为标号设定和标号修改两类，这两种算法都是在每次循环迭代过程中给顶点指定距离标号，该标号是对源点到该顶点间最短路径的一种估计，不同之处在十二者每一步产生的标号是永久性的还是暂时性的按照计算方法的不同分为串行最短路径算法和并行最短路径算法。并行算法可以通过对串行算法并行化得到，也可以重新编写适合具体应用问题的并行算法。20世纪80年代以来，许多国外的专家学者研究探讨了最短路径并行算法的实现。最短路径并行算法的研究主要包括基十标号设定的并行算法和基十标号修正的并行算法【ia}等。标号设定并行算法将网络划分后分配到多个处理器上，每个处理器负责一个子网内的计算，如Paige和Kruskal提出了Dijkstra算法的同步并行化方法[[13]。对基十标号修正并行算法的研究也出现了多种算法，如Narayanan讨论了Floyd算法的两种数据并行实现方法[fl}l，但没有测试这两种并行算法的加速比;Adamson和Tick}ls]以及Bertsekas}l6]等在虚拟共享存储机器上实现了标号修正并行算法。国内对最短路径并行算法的研究不多，主要包括:智能交通系统的交通网络最短路径并行算法[yz,m-is}，主要为了快速、高效地进行交通网络分析;谭国真和隋春丽研究的PC机群上的最短路径并行算法[fl}l，文章介绍了SPMD模式下的算法实现过程，在非循环图网络模型和强连通随机网络模型上测试该并行算法;平晓慧和谭国真设计的最短路径并行算法[faol，用十解决时间依赖网络和大规模网络上的最短路径问题;周益民等在NOW上的MPI平台实现了一种所有点对间的最短路径并行算法[f211，该算法实质是采用二维网格结构的Floyd并行算法;李丹等介绍了机群系统中基十Dijkstra算法的一种并行化策略[f221，并讨论了最短路径并行算法的加速比。这些算法针对不同的应用需求和实验环境，在时空复杂度、实现难易程度及应用范围方面各具特色。
二角网格模型包含大量丰富的细节信息(几何信息和拓扑连接信息等)。如何对模型进行描述、表示，对空间曲面上两点间距离进行测量、求解等，这使得二角网格模型上最短路径问题的求解不完全同十其他领域，显然不能直接使用其他已有的最短路径并行算法来解决。然}fn，目前对二角网格模型最短路径并行算法的研究并不多。鉴十此，为降低求解二角网格模型上最短路径问题的计算时间、提高计算效率，本文在分析借鉴其他最短路径并行算法优点的基础上，研究了二角网格模型上最短路径问题的特点，结合已有的并行实验平台，充分利用并行处理快速高效的优点，提出并实现了适合十解决二角网格模型上最短路径问题的并行算法。1.3本文工作以降低求解二角网格模型最短路径问题的计算时间开销、提高计算效率为出发点，在对最短路径算法和并行计算进行研究和分析的基础上，本文主要做了以下工作:1,提出并实现一种基十多层k路划分任务分配策略的矩阵乘最短路径并行算法。
参考文献
[1]孙晓鹏.二维模型的分割及应用研究fD].中国科学院计算技术研究所博士论文，Zoos.
[2]周培德.计算几何一算法分析与设计【M].北京:清华大学出版社，2000:193-196.
[3]Sharir M,Schorr A.On shortest path in polyhedral spaces[J].SIAM Journal onComputing,1986,1 s(1):193-21 s.
[4]Kanai T,Suzuki H. Approximate shortest path on a polyhedral surface and itsapplications[J].Computer-Aided-Design,2001,33(11):801一811.
[5]Lanthier M, Mahestwari A, Stack J-R. Approximating weighted shortest paths onpolyhedral surface[A].In:Procceedings of the 13th ACM Symposium on ComputGeometry,Nice,France,1997.272-283.
[6]张丽艳，吴熹.二角网格模型上任意两点间的近似最短路径算法研究阴.计算机辅助设i}一与l冬}形学学报，2003(s): s92-s97.
[7]余晓荣，杨晓东，中长雨.曲面上任意两点的近似最短路径算法研究[J].中国}x}象}x}形学报，200s,10(7):900-904.
[8]童晶，陈正鸣.二角网格表面近似测地线的计算[[J].计算机辅助设计与图形学学报，2008,20(2):180-18s.
[9]孙晓鹏，李华.基十CSR存储的二维网格最短路径算法[[J].计算机工程与应用，200s,41(10): s-7.
[10]Barry Wilkinson,Michael Allen, Parallel Programming,China MachinePress,200s.
[11]Kuan-Ching Li,Hsun-Chang Chang.On construction of a visualization toolkit for MPIparallel programs in cluster environments.Advanced Information Networking andApplications,AINA 200s.19th In
[12]倪安宁，隽志才，高林杰.交通网络最短路径并行算法研究综述[[J].公路交通科技.2006,23(12):128一132.
[13]R C Paige, C P Kruskal. Parallel algorithms for shortest path problems[C]. Proceedingsof the International Conference on Parallel Processing.198s:14-20.
[14]P Narayanan. Single source shortest path problem on processor array [C].ProceedingsFrontiers of Massively Parallel Computation McLean, VA:1992.
[15]P Adamson, E Tick.Greedy partitioned algorithms for the shortest pathproblem[J].International Journal of Parallel Programming,1991，20(4):271-298.
[16]D P Bertsekas,F Guerriero,R Musmanno. Parallel asynchronous label-correcting methodsor shortest paths[J]. Journal of Optimization Theory and Applications.1996,88(1):297-320.
[17]倪安宁.交通网络分析中的最短路径并行算法研究与实现.吉林大学硕士论文.2004.4
[18]隽志才，倪安宁，贾洪飞，李杰.两种策略下的最短路径并行算法研究与实现田.系统工程理论方法应用，2006,15(2):123一127.
[19]谭国真，隋春丽.PC机群环境下最短路径并行算法的研究[J].小型微型计算机系
摘要 3-4
Abstract 4
1 绪论 7-10
1.1 研究背景及意义 7
1.2 研究现状 7-8
1.3 本文工作 8-9
1.4 本文组织结构 9-10
2 并行计算相关理论 10-19
2.1 并行计算概述 10-11
2.1.1 并行计算概念 10
2.1.2 物理问题的并行求解过程 10-11
2.2 并行计算机系统介绍 11-12
2.2.1 共享存储多处理机系统 11-12
2.2.2 分布存储多计算机系统 12
2.2.3 分布式共享内存计算机—机群系统 12
2.3 并行算法设计相关理论 12-14
2.3.1 并行算法的设计技术 12-13
2.3.2 并行算法的设计过程 13
2.3.3 并行算法的性能评测 13-14
2.4 并行程序设计模型 14-19
2.4.1 消息传递模型 14-16
2.4.1.1 MPI 编程简介 14-15
2.4.1.2 MPI 常用函数 15
2.4.1.3 MPI 通信模式 15-16
2.4.2 共享存储模型 16-19
2.4.2.1 OpenMP 概述 16-17
2.4.2.2 OpenMP 多线程编程 17-19
3 并行实验环境的构建与配置 19-23
3.1 SMP 机群 19-20
3.1.1 SMP 机群体系结构 19
3.1.2 SMP 机群特点 19
3.1.3 SMP 机群编程模型 19-20
3.2 基于Linux 的SMP 机群并行计算平台构建 20
3.3 MPI 并行程序设计环境 20-21
3.3.1 MPI 并行程序环境配置 20-21
3.3.2 MPI 并行程序的编译与运行 21
3.4 MPI+OpenMP 混合编程并行程序设计环境 21-23
3.4.1 MPI+OpenMP 混合编程并行环境的配置 22
3.4.2 MPI+OpenMP 混合编程并行程序的编译与运行 22-23
4 基于多层k 路划分任务分配策略的矩阵乘最短路径并行算法 23-33
4.1 问题描述 23
4.2 算法的设计与实现 23-30
4.2.1 利用矩阵乘思想求解所有点对间最短路径 23-24
4.2.2 采用行列划分任务分配策略的最短路径并行算法 24-27
4.2.3 采用多层k 路划分任务分配策略的最短路径并行算法 27-30
4.2.3.1 基于多层k 路划分算法的任务划分 27
4.2.3.2 基于划分结果的任务映射 27-30
4.2.4 采用两种任务分配策略的最短路径并行算法性能分析 30
4.3 实验测试及结果分析 30-33
5 基于MPI+OpenMP 多粒度混合编程的矩阵乘最短路径并行算法 33-38
5.1 MPI+OpenMP 多粒度混合编程模型 33-35
5.2 算法实现 35-36
5.3 实验测试 36-38
6 基于局部细分的三角网格模型最短路径并行算法 38-46
6.1 细分法思想 38
6.2 基于局部细分的所有点对间最短路径并行算法 38-42
6.2.1 并行算法设计 38-39
6.2.2 并行算法实现 39-42
6.2.2.1 数据结构及基本操作定义 39-40
6.2.2.2 算法步骤 40-42
6.2.2.3 算法说明 42
6.3 实验测试与结果分析 42-46
7 结论 46-47