WAVE is abbreviation of 'working as versatile and efficient'.
This project aims to support a high performance breadth-first graph traversal on GPUs.
Ubuntu [16.04.5, 18.04.5, 20.04.2] LTS
g++ [5.4.0, 7.5.0, 9.3.0], CUDA [11.2, 11.3, 11.4]
GTX970, RTX3080
make
./wave --csr <*_beg_pos.bin> <*_adj_list.bin> [option1] [option2]
- [option1]: --verylarge
- set data type of vertices and edges to 'unsigned long long', default='unsigned int'
- [option2]: --verbose
- print breakdown of frontier processing techniques
WAVE implementation:
- main.cu: load a graph as an input
- bfs.cuh: traverse the graph
- fqg.cuh: implementation of push and pull phases
- mcpy.cuh: functions for initializing data structures
- alloc.cuh: memory allocation for data structures
- comm.cuh: global variables and functions shared by all files
CSR Generator provided by https://github.com/kljp/vCSR/:
- vcsr.cpp: generate CSR
- Compile: make
- Execute: ./vcsr --input <*.mtx> [option1] [option2] [option3] [option4]
- [option1]: --virtual <max_degree> (not available for WAVE)
- set maximum degree of a vertex to <max_degree>
- [option2]: --undirected
- add reverse edges
- [option3]: --sorted
- sort intra-neighbor lists
- [option4]: --verylarge
- set data type of vertices and edges to 'unsigned long long', default='unsigned int'
- [option1]: --virtual <max_degree> (not available for WAVE)
- Graph source: https://sparse.tamu.edu/
- Please make sure that the format of input graph should be Matrix Market.
Headers Provided by https://github.com/iHeartGraph/Enterprise/:
- graph.h: graph data structure
- graph.hpp: implementation of graph data structure
- wtime.h: get current time for measuring the consumed time
WAVE: designing a heuristics-based three-way breadth-first search on GPUs. Daegun Yoon, Minjoong Jeong, Sangyoon Oh. The Journal of Supercomputing, Nov. 2022. [Paper]
If you have any questions about this project, contact me by one of the followings: