DocumentCode :
3395668
Title :
Accelerating finding euler circuit on CPU-GPGPU heterogeneous architecture
Author :
Jiachun Ye ; Songnian Yu
Author_Institution :
Sch. of Comput. Eng. & Sci., Shanghai Univ., Shanghai, China
fYear :
2011
fDate :
19-22 Aug. 2011
Firstpage :
1649
Lastpage :
1652
Abstract :
GPU (Graphic Processing Unit) provides a large computational performance at a very low price. Algorithms with regular data access map well to the SIMD architecture of current GPU, while irregular algorithms on discrete data structures like graphs are hard to map. In this paper, we transform the prior algorithm, design special data structures, and present an optimized CPU-GPU implementation for finding Euler circuit on a randomly generated Eulerian graph. It can deal with a graph of 4096 vertices and 1.7 million edges in about 1 second, which has a speed up of about 50 times over the best sequential CPU implementation.
Keywords :
computer graphic equipment; coprocessors; data structures; graphs; parallel architectures; CPU-GPGPU heterogeneous architecture; SIMD architecture; accelerating finding Euler circuit; design special data structure; discrete data structure; graphic processing unit; irregular algorithm; randomly generated Eulerian graph; regular data access; Algorithm design and analysis; Complexity theory; Graphics processing unit; Heuristic algorithms; IEL; Partitioning algorithms; Synchronization; Euler circuit; GPGPU; graph; parallel;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Mechatronic Science, Electric Engineering and Computer (MEC), 2011 International Conference on
Conference_Location :
Jilin
Print_ISBN :
978-1-61284-719-1
Type :
conf
DOI :
10.1109/MEC.2011.6025795
Filename :
6025795
Link To Document :
بازگشت