Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/70862

Parallel implementation of finding Euler circuit in digraph using CUDA and OpenMP

Authors Zhang, Junkang
Issue Date 2014
Summary Finding Euler circuit has been a fundamental problem in graph theory. Several serial solutions have been presented, but no detailed parallel implementations have been developed. As general purpose computing on graphics processing units (GPGPU) has arisen to harness the powerful parallel computation capability of the GPU, we design a parallel Euler circuit finding solution for digraphs, and implement the solution on both the CUDA CPU-GPU heterogeneous programming framework and the OpenMP shared memory many-core CPU programming model. Specifically, we divide the Euler circuit finding algorithm in five steps and study the feasibility and performance of parallelizing each step. We also compare the overall performance between our CUDA, OpenMP and serial implementations. Our results show that parallelizing Euler circuit finding on a laptop computer with an Intel i7 quad-core CPU and an NVIDIA GT640M GPU yields a 4X speedup with OpenMP and a 24X speedup with CUDA over the serial version.
Note Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2014
Subjects
Language English
Format Thesis
Access View full-text via DOI
Files in this item:
File Description Size Format
th_redirect.html 346 B HTML