Biography
Enrollment Date: 2012
Graduation Date：2015
Degree：M.S.
Defense Date：2015.06.02
Advisors：Yangdong Deng
Department：Institute of Microelectronics，Tsinghua University
Title of Dissertation/Thesis：Parallel Algorithm of All-Pairs Shortest Paths and its Applications
Abstract:
As an essential graph algorithmic pattern, the All-Pairs Shortest Paths Problem (APSP) plays an important role in many crucial applications such as bioinformatics, social network, logistics planning, geographic information systems, power grid system, studying the spread of some epidemic disease, GPS, computer-aided design of integrated circuits and traffic planning. With the advent of the big data era, as a basic analysis tool of various graphs, APSP has become a bottleneck for critical applications. Currently, APSP for large-scale graph generally require multi-core machine or distributed computing nodes. It need to be considered not only the performance inside a computing node but also the communication between the computing nodes. Due to the structure of graph is different in different application, the algorithm must be automatically suitable to various kinds of structure.To solve these problems, we propose two main APSP parallel algorithm. They are Communication Optimized P-Toueg algorithm under the Pregel framework on distributed computing platform and sampling hybrid algorithm based on Graphics Processing Units (GPUs). Firstly, This work investigates efficient APSP algorithms and implementations under the Pregel framework. On the basis of designing a Pregel based Toueg algorithm (P-Toueg algorithm), we propose an improved algorithm, so-called Communication Optimized P-Toueg algorithm, which reduces the upper bound of communication complexity from O(N^2) to O(PN), where N is the number of vertices in the graph and P is the number of parallel processes. Both P-Toueg algorithm and Communication Optimized P-Toueg algorithm were evaluated on a supercomputer. The results proved that the acceleration ratio of the Communication Optimized P-Toueg algorithm over the original P-Toueg algorithm increases with the scale of graphs. The Communication Optimized P-Toueg algorithm also delivers excellent scalabilities on both the size of dataset and the number of computational nodes. Secondly, this work investigates GPU-based APSP parallel algorithms that adapt to varying graph structures. We propose an improved vertex-parallel algorithm, so-called optimized vertex-parallel algorithm, which performs best on graphs with a large diameter. We also proposed a hybrid algorithm integrating the optimized vertex-parallel algorithm vertex- and an edge-parallel algorithm that can efficiently handle graphs with arbitrary structure. Furtherly, we proposed a sampling heuristic to further improve the performance of the hybrid algorithm. Experimental results prove that the sampling hybrid algorithm achieves a speedup of up to 7.2x on high-diameter graphs and 1.7x on other graphs. The sampling hybrid algorithm also has a better scalability on large graphs. Finally, in order to verify the efficiency of the algorithm, we used APSP solving the problem of Betweenness Centrality and diameter. Experiments showed that efficiency can be greatly enhanced.