Font Size: a A A

Design And Implementation Of Graph Algorithms On GPU And Performance Analysis

Posted on:2012-02-02Degree:MasterType:Thesis
Country:ChinaCandidate:W WangFull Text:PDF
GTID:2218330371462550Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
General Purpose Computation on Graphics Processor Units (GPGPU) is a popular research direction in high performance computation nowadays. There is not much research about graph algorithms on GPU at present, and an important reason is that graph algorithms have some features such as irregular memory access and dynamic data processing. It is hard to predict memory address and allocate tasks when executing a graph algorithm, increasing difficulties in parallelizing graph algorithms. On the other hand, data size is increasing rapidly in many new arising applications like Web information processing. Graph algorithms are more and more important in these fields, and performance of graph algorithms hinders the performance of data processing. Exploring general techniques for designing and implementing graph algorithms on GPU can effectively improve performance of graph algorithms in new arising applications. Besides, it can provide reference for design and implementation of other algorithms which have these similar features.The thesis analyzes current research situation of designing and implementing graph algorithms on GPU, and summarizes two problems when designing graph algorithms on GPU, i.e. irregular memory access and dynamic data processing. Aiming at irregular memory access, GPU-based Min Reduction data parallel primitive is designed which uses techniques including successive address, unrolling loop and template compilation, reduction results can be obtained quickly through two primitive modules, i.e. global memory reduction and shared memory reduction. The GPU primitive is applied to design and implement Prim's minimum spanning tree algorithm on GPU. Aiming at dynamic data processing, three techniques including hierarchical task allocation, hierarchical work queue and hierarchical Kernel are designed, and idle thread cost, memory access cost and synchronizing cost are greatly reduced. These methods are applied in design and implementation of Moore's Single Source Shortest Paths algorithm.The performance of these algorithms is analyzed across theoretical analysis and experiment test finally. A GPU program performance model is proposed and used to evaluate performance of GPU Prim algorithm and GPU Moore algorithm. The result validates the rationality of applying GPU to accelerating graph algorithms. The performance of these algorithms is tested with multiple kinds of graph data. GPU Prim algorithm and GPU Moore algorithm achieves speedup of 1.86 and 4.22 at most respectively, compared to contrast algorithms. These proposed methods can help design and implement graph algorithms on GPU.
Keywords/Search Tags:graphics processor units (GPU), graph algorithm, minimum spanning tree, single source shortest paths, irregular memory access, dynamic data
PDF Full Text Request
Related items