Alghamdi, Mohammed (2020) Developing the parallelization techniques for finding the all-pairs shortest paths in graphs. PhD thesis, University of Warwick.

Preview

PDF WRAP_Theses_Alghamdi_2020.pdf - Submitted Version - Requires a PDF viewer. Download (2086Kb) | Preview

Request Changes to record.

Abstract

Finding the All-Pairs Shortest Paths (APSP) is a fundamental graph problem aiming to find the shortest path between any two nodes in a graph. Solving the APSP problem in parallel is an active research area. Many algorithms have been proposed. In this thesis, a new approach are presented to solve the APSP problem for big graphs on shared and distributed systems. In this approach, a graph is partitioned judiciously and then processed in parallel. In particular, the graph is first pre-processed to prepare the partition in the computation stages. After the graph is partitioned into smaller sub-graphs, a traditional shortest path algorithm, such as the Floyd-Warshall algorithm or the Dijkstra’s algorithm, can be used to find the APSP in each sub-graph. Finally, through the common nodes between the sub-graphs, the local results in each sub-graph are combined to establish the APSP for the entire graph. Our method are implemented using OpenMP for the shared memory architecture and MPI for the distributed memory architecture. In order to improve the scalability of the method, we proposed two different communication patterns among partitions (and processes) to achieve the parallelization and the combination of the local results. Further, we develop a hybrid CPU-GPU parallelization method, which can be run in a single multicore CPU and further be distributed across multiple GPUs to aggregate the results. We also developed two load-balancing schemes for this hybrid method. We have conducted extensive experiments on a high-performance cluster with both simulated and real-world graphs. The experimental results show that comparing with the existing solution, our method is able to accelerate the solving of the APSP problem significantly.

Item Type:	Thesis (PhD)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Library of Congress Subject Headings (LCSH):	Parallel processing (Electronic computers), Electronic data processing -- Distributed processing, Graphics processing units, Graph theory, Multiprocessors
Official Date:	July 2020
Dates:	Date Event July 2020 UNSPECIFIED
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Thesis Type:	PhD
Publication Status:	Unpublished
Supervisor(s)/Advisor:	He, Ligang
Sponsors:	Jāmiʻat al-Malik Khālid ; Saudi Arabian Cultural Bureau in the U.K.
Format of File:	pdf
Extent:	xv, 120 leaves : illustrations (some colour)
Language:	eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads