30000字硕士毕业论文三角形网格模型最短路径并行算法的讨论与实现
论文类型：硕士毕业论文
论文字数：30000字
论点：并行,算法,最短
论文概述：
该算法借用矩阵乘思想求解所有点对间最短路径,创新性地引入图划分方法进行并行任务分配。实验表明,相比采用传统任务分配策略,该并行算法能够有效降低处理器间的通信开销,从而减少整个
论文正文：
1导言
1.1研究背景和意义最短路径问题是计算机科学、计算机网络通信、计算机图形学、地理信息系统和智能交通系统等许多学科中常见且研究广泛的问题。近年来，十二边形网格模型在几何建模、计算机图形学等地方的广泛应用，使得人们开始关注十二边形网格模型中最短路径问题的研究。在二维网格模型上找到任意两个顶点之间的最短路径是几何模型计算的基本问题，也是网格模型有意义分割、机器视觉和模式识别等热点研究工作必须面对的基本问题。如果fll将二面角网格模型石视为一个加权点，那么网格中的顶点就是点的顶点，两点之间的距离长度就是权值，那么在二面角网格模型上寻找两点之间的最短路径就是加权图中两点之间的最短路径。采用经典的最短路径算法如Dijkstra算法[f2l]来解决这个问题，结果是二面角网格模型中首尾相连的边集:如果对可行路径进行细分，就可以得到沿二面角网格表面行走的最短路径结果，现有算法分为两类:精确算法和近似算法f=}-51。
尽管通过不断发展和改进的训练和计算机器的数据结构和算法的有效结合，在两角网格模型上出现了大量的最短路径算法f}-}l，但这些算法都是通过基本的十串行方法解决的。随着网格规模的不断增加，串行最短路径算法的计算时间和存储要求也急剧增加。有时，即使是单机也无法解决问题，[并行计算为快速解决大量计算任务提供了有效途径。并行计算和并行算法是[大规模科学计算的理论基础和支持工具。并行处理不仅可以为解决大规模复杂问题提供强大的计算和存储能力，而且可以大大节省计算时间，提高计算效率。对于有1104个顶点和2104个补丁的网格模型，在正版英特尔(R) CPUT 1400 @ 1.83 GHz处理器和1G内存的计算环境下，使用迪克斯特拉算法(Dijkstra algorithm)的计算时间超过8小时，这对十个用户来说是非常巨大的。Ifn通常在普林斯顿2D网格模型库中有十个尺度的模型。对于同样的计算问题和数据规模，当使用并行算法解决问题时，使用2个处理器的计算时间减少到约1小时，使用4个处理器的计算时间约为0.39小时。可以看出，并行算法大大减少了求解两角网格模型最短路径问题的计算时间。因此，有必要设计并行算法来优化求解两角网格模型最短路径问题的复杂性和计算时间。在二面角网格模型上求解最短路径是对二维网格模型进行聚类和分割的准备工作，这为在模型网格表面上定义大地距离和基于大地距离[’进行聚类提供了准备工作。十条并行最短路径算法能够有效减少在两角网格模型上求解最短路径问题的时间，从而提高二维网格模型测地线距离意义下的聚类分割效率。
1.2现状研究最短路径是图论中的经典问题。它的研究起源于20世纪50年代末。这类问题源于实践，已成为网络通信系统资源分配、交通网络路由分析与设计等诸多优化问题的子问题。在最短路径的研究中出现了大量的算法，如经典的迪克斯特拉算法和弗洛伊德算法。最短路径算法有不同的分类。根据图中顶点之间的距离被标记的方式，它们被分为标签设置和标签修改。在每个循环迭代过程中，这两种算法都为顶点分配距离标签。标签是对源点和顶点之间最短路径的估计。不同之处在于，在十二个步骤中的每一步中生成的标签是永久的还是临时的。根据计算方法的不同，将两种算法分为串行最短路径算法和并行最短路径算法。并行算法可以通过并行化串行算法或重写适合特定应用问题的并行算法来获得。自20世纪80年代以来，许多国外专家学者对最短路径并行算法的实现进行了研究和探讨。最短路径并行算法的研究主要包括由base 10标签设置的并行算法和由base 10标签修改的并行算法[IA]。标签设置并行算法划分网络并将其分配给多个处理器。每个处理器负责子网内的计算。例如，佩奇和克鲁斯卡尔提出了迪杰斯特拉算法的同步并行方法[·[13]。在对十进制标签校正并行算法的研究中，也出现了多种算法。例如，纳拉亚南讨论了弗洛伊德算法的两种数据并行实现方法，但没有测试两种并行算法的加速比。阿达姆松、提克和贝尔瑟卡斯·L6在虚拟共享存储机器上实现了标签校正并行算法。我国对最短路径并行算法的研究很少，主要包括:智能交通系统交通网络的最短路径并行算法[yz，m-is]，主要用于快速高效的交通网络分析；摘要:谭国珍和隋春丽研究了PC机集群上的最短路径并行算法[1，介绍了该算法在SPMD模式下的实现过程，并在无环图网络模型和强连通随机网络模型上对并行算法进行了测试。由平小惠和谭国珍设计的最短路径并行算法[法奥十次解决了时变网络和大规模网络上的最短路径问题。周一民等人在NOW [f211平台上实现了MPI平台上所有点对之间的最短路径并行算法，本质上是二维网格结构的弗洛伊德并行算法；李丹等人介绍了集群系统[f221中基本Dijkstra算法的并行化策略，并讨论了最短路径并行化算法的加速比。这些算法根据不同的应用需求和实验环境，在时间空复杂度、实现难度和应用范围上有各自的特点。
二面角网格模型包含大量详细信息(几何信息、拓扑连接信息等)。)。如何描述和表达模型，测量和求解曲面上两点之间的距离空，等等。这使得两角网格模型上的最短路径问题与其他10个领域中的最短路径问题不完全相同，并且显然不能被其他现有的最短路径并行算法直接解决。然而，目前对于两角网格模型中最短路径并行算法的研究还不多。有鉴于此，为了减少二面角网格模型求解最短路径问题的计算时间，提高计算效率，在分析和借鉴其他最短路径并行算法优点的基础上，结合现有并行实验平台，充分利用快速高效并行处理的优势，提出并实现了一种适用于二面角网格模型求解最短路径问题的并行算法。1.3在研究和分析最短路径算法和并行计算的基础上，本文主要做了以下工作:1 .提出并实现了一种基于10层K路径划分任务分配策略的矩阵倍最短路径并行算法。
参考
[1]肖鹏太阳报。二维模型分割与应用的功能展开研究。中国科学院计算技术研究所博士论文，动物园。
[2]周培德。计算几何算法的分析与设计[。北京:清华大学出版社。2000年:193-196年。
[3]沙里尔·M，朔尔·阿.多面体空间中的最短路径[[]。暹罗计算机杂志，1986，1 s(1):193-21 s.
[4]Kanai T，铃木h .多面体表面上的近似最短路径及其应用[J]。计算机辅助设计，2001，33(11):801-811。
[5] lanthier m，mahestwaria，Stack J-R .多面曲面上加权最短路径的逼近[A]。1997.272-283年在法国尼斯举行的第十三届计算机几何学术研讨会的主持人。
[6]张丽艳，吴Xi。两角网格模型中任意两点间近似最短路径算法的研究。《计算机辅助设计》，第一版和第一版，《地貌学杂志》，2003年:s92-s97。
杨晓东于晓荣，中雨。曲面上任意两点的近似最短路径算法研究[[]。《中国期刊》x}图像X}，200年代，10(7):900-904。
摘要3-4[/BR/]摘要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.2.3分布式共享内存计算机-集群系统12 [/BR/] 2.3并行算法设计理论12-14
2.3.1并行算法设计技术12-13 [/BR/] 2.3.2并行算法设计过程13 [/BR/] 2.3.3并行算法性能评估13-14 [/BR/] 2.4并行编程模型14-19
2.4.1消息传递模型14-16
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 3.4.1 MPI+OpenMP混合编程并行环境配置22
3.4.2 MPI+OpenMP混合编程并行编程编译和运行22-23
4矩阵乘法最短路径并行算法23-33 [/BR/] 4.1问题描述23 [/BR/] 4.2算法设计和实现23-30 [/BR/] 4.2.1使用矩阵乘法求解所有点对之间的最短路径23-24
4.2.3.1任务划分27 [/BR/]基于多层K路径划分算法4.2.3.2任务映射基于划分结果27-30 [/BR/] 4.2.4最短路径并行算法使用两种任务分配策略的性能分析30 [/BR/] 4.3实验测试和结果分析30-33
5矩阵乘法最短路径并行算法33-38
5.1 MPI+OpenMP多粒度混合编程模型33-35
5.2基于MPI的算法 基于局部细分的6三角网格模型最短路径并行算法38-46 [/BR/] 6.1细分思想38 [/BR/] 6.2基于局部细分的全点对最短路径并行算法38-42 [/BR/] 6.2.1并行算法设计38-39
6.2.2并行算法实现39-42[/BR/]6.2.2.1数据结构和基本运算定义39-40[/BR/]6.2.2.2算法步骤40-42[/BR/]6.2.2.3算法陈争鸣通经。引用该论文[[。计算机辅助设计与图形杂志，2008，20(2):180-18s。
[9]肖鹏·孙。李华。[·[著《二维网格最短路径算法》。计算机工程与应用，200S，41 (10): S-7。[/比尔/] [10]巴里·威尔金森，迈克尔·艾伦，并行编程，中国机械出版社。200年代。
[11]宽井莉，张顺昌。集群环境下MPIparallel程序可视化工具包的构建。高级信息网络与应用，aina200s.19thin
[12]倪安宁，军之才，高林杰。交通网络中最短路径并行算法研究综述[[。公路交通技术。2006年，23(12):128-132。
[13]佩奇。克鲁斯卡。最短路径问题的并行算法。《并行处理国际会议录》，198s:14-20。
[14]纳拉亚南。处理器阵列上的单源最短路径问题。《大规模并行计算前沿》，弗吉尼亚:1992年。
[15]P阿达姆松，E Tick。最短路径问题的贪婪分区算法[。《国际并行程序设计杂志》，1991，20(4):271-298。
[16]德·贝尔塞卡斯，弗·格雷罗，罗·穆萨诺。引用该论文[。最优化理论与应用杂志。1996，88(1):297-320。
[17]倪安宁。交通网络分析中最短路径并行算法的研究与实现。吉林大学硕士论文。2004.4
[18]军之才，倪安宁，贾洪飞，李杰。两种策略下最短路径并行算法的研究与实现。系统工程理论和方法的应用，2006，15(2):123-127。
[19]谭国珍，隋春丽。计算机集群环境下最短路径并行算法的研究[。小型计算机系统
[7]
[8]