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 result...[ Read more ]

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.