《并行广度优先搜索算法研究》由会员分享，可在线阅读，更多相关《并行广度优先搜索算法研究（52页珍藏版）》请在金锄头文库上搜索。
1、 摘要 随着计算机科学的不断发展，图的搜索技术已经渗透到语言学、逻辑学、物理、化学、电子、通信、数学等诸多学科领域，特别是网络技术的快速发展和并行计算机的出现，并行处理进入了前所未有的繁荣期，图的遍历也显得越来越重要。广度优先搜索算法是图论的一个基本问题，也是一个热点问题。广度优先搜索算法的并行化已经成为目前亟待解决的问题。 本文首先介绍了广度优先搜索并行算法的研究现状。然后，在 Cilk+运行时系统上，实现了用“bag”的数据结构代替共享队列的一种优化方法，该算法是基于层同步思想的一个细粒度并行算法，能够更容易的并行代码。其次，在分布式系统上，实现了基于邻接矩阵一维划分的并行广度优先搜索算法
2、。最后，在分析和研究现有的广度优先搜索并行算法的基础上，结合现有的并行计算环境，提出了一种新的广度优先搜索并行算法。该算法是在分布式系统上提出来的，结合了层同步的思想和邻接矩阵二维划分的思想。通过大量实验证明，我们提出的新算法在时间复杂度上达到了更好的性能，在分布式系统上具有更好的适用性。 关键字：广度优先搜索算法关键字：广度优先搜索算法 分布式系统分布式系统 层同步层同步 邻接矩阵二维划分邻接矩阵二维划分 Abstract With the development of computer science, the search technology of graphs has emerged
3、 in linguistics, logic, physics, chemistry, electronics, communication, mathematics and some other fields of science. Especially with the fast progress of internet technology and the appearance of parallel computer systems , parallel manage has in an unprecedented boom period and the problem of trav
4、ersing graphs is more and more important. Breadth-First search algorithm is a basic problem of graph theory and also a hot problem. The parallelism of Breadth-First search algorithm has been an urgent problem. First of all, this paper introduces the status about parallel breadth-first search algorit
5、hms. Secondly, we replace the shared queue with a new “bag” data structure which is more amenable for code parallelization with the cilk+ run-time model, and this is a fine-grained parallel algorithms based on layer synchronization theory. Thirdly, we achieve a parallel breadth-first search algorith
6、ms based on one-dimensional decomposition of the adjacency matrix corresponding to the graph. Finally, analyzing the methods present of parallel breadth-first search and combining with the current parallel system conditions we have, this paper proposes a new method of parallel breadth-first algorith
7、m. This algorithm combines the level-synchronous theory and two-dimension partition thought of the adjacency matrix. Plenty of experiments prove that this new algorithm reaches a better performance of time complexity, and more suitable for distributed memory systems. Keywords: Breadth-First search a
8、lgorithm Distributed memory system Layer synchronization Two-Dimension partition of the adjacency matrix 目录 第一章 绪论 . 1 1.1 引言 . 1 1.2 广度优先搜索算法简介 . 2 1.2.1 图的表示方法 . 2 1.2.2 串行广度优先搜索 . 3 1.3 广度优先搜索并行算法研究现状 . 4 1.3.1 多线程系统上的 PBFS 算法 . 4 1.3.2 多核系统上的 PBFS 算法 . 5 1.3.3 分布式系统上的 PBFS 算法 . 6 1.3.4 外存上的 PBFS
9、 算法 . 7 1.3.5 其他 PBFS 算法 . 7 1.3.6 其他相关工作 . 7 1.4 本文所做的工作 . 7 1.5 本文的组织结构 . 8 第二章 多核并行处理技术简介 . 9 2.1 并行编程模式 . 9 2.1.1MPI 编程模型 . 9 2.1.2OpenMP 编程模型 . 10 2.1.3Cilk+编程模型 . 10 2.2 共享内存和分布式内存层次结构 . 15 2.3 并行系统的性能度量标准 . 16 2.3.1 并行程序中的开销来源 . 16 2.3.2 并行系统的性能度量 . 17 2.3 本章小结 . 18 第三章 基于层同步策略的并行广度优先搜索算法 . 19 3.1 并行广度优先搜索 . 19 3.1.1PBFS 算法描述 . 19 3.1.2 数据结构分析 . 21 3.2 实验结果与分析 . 24 3.3 本章小结 .
