Earticle

초록

영어

Breadth-first search (BFS) is one of the most used graph kernels, and substantially affects the overall performance when processing various graphs. Since graph data are frequently used in real life for example road networks in navigation systems, high performance graph processing becomes more critical. In this study, we aim to process BFS algorithm efficiently on road network data. We propose BARON, a BFS algorithm that copes with road networks. To accelerate graph traversal, BARON reduce the occurrence of branch and memory divergences by exploiting warp-cooperative work sharing and atomic operations. With this design approach, BARON outperforms the other BFS kernels of state-of-the-art graph processing frameworks executed stably on the latest GPU architectures. For various graphs, BARON yields speedups of up to 2.88 and 5.43 over Gunrock and CuSha, respectively.

목차

Abstract
I. INTRODUCTION
II. RELATED WORK
III. BARON: BFS ALGORITHM FOR ROAD NETWORKS
IV. EVALUATION
A. Implementation and Hardware Specifications
B. Methodology and Graph Benchmarks
C. BFS Performance Comparison
V. CONCLUSION
ACKNOWLEDGMENT
REFERENCES

저자

• Daegun Yoon [ dept. of Artificial Intelligence Ajou University ]
• Sangyoon Oh [ dept. of Artificial Intelligence Ajou University ]

참고문헌