Research And Implement Of Parallel Shortest Path Algorithms On Triangular Mesh Model

In recent years, as triangular mesh model is widely used in geometric modeling, computer graphics and partition mesh model etc, people start to focus on research of shortest path problem on triangular mesh model. Finding shortest path between two points is a basic computing problem of triangular mesh model. Many existing shortest path algorithms on triangular mesh model are mostly serial now. However, with the mesh scale increasing, computing time have a sharp increase too. Parallel computing can rapidly and effectively solve large scale complex problem. It spends less time in solving the same problem, so computing efficiency has increased greatly. In order to reduce computing time and make further research, this paper do some research of parallel shortest path algorithms on triangular mesh model, main content includes:(1) A matrix-multiplication parallel shortest path algorithm base on multilevel k-way partitioning task mapping strategy is presented. This parallel algorithm adopt matrix-multiplication algorithm to solve all pairs shortest path problem, and innovatively use graph partition method to map computing task. Compared with traditional task mapping strategy, this algorithm effectively reduces communication cost between processors, and the whole computing time is decreased too.(2) A matrix-multiplication parallel shortest path algorithm base on MPI+OpenMP multi-granularity mix programming mode is presented. Because of fully utilizing two-level parallelization of SMP Cluster, the experiment results show that this algorithm has better parallel performance and execution efficiency than MPI matrix-multiplication parallel shortest path algorithm.(3) A local-subdivision parallel shortest path algorithm is presented. Local-subdivision method create a new subdivision graph by subdividing edges of initial shortest path neighborhood triangular faces,then obtain a new shortest path base on this subdivision graph. So the shortest path of two points can be obtained from triangular mesh faces.Parallel algorithm take source-partition strategy to map graph points to every processor, all processors do local-subdivision algorithm concurrently. The experiment results indicate that this algorithm can greatly reduce computing time, obtain better parallel performance, and get more approximate shortest path results.A SMP Cluster parallel computing platform base on Linux is constructed; MPI and MPI+OpenMP parallel programming design environment are provided. Three algorithms are tested on this parallel computing platform. Running time, speedup and performance analysis is given. The experiment results show that the parallel algorithms mentioned in this paper not only solve shortest path problem on triangular mesh model accurately and effectively, but also reach the target of reducing computing time and improving execution efficiency.