Skip to content

Latest commit

 

History

History
86 lines (74 loc) · 2.69 KB

README.md

File metadata and controls

86 lines (74 loc) · 2.69 KB

SURF

BFS Direction-Optimizer utilizing workload state of frontiers on GPUs.

SURF is abbreviation of 'switching direction upon recent workload state'.

This project aims to support a high performance breadth-first graph traversal on GPUs.

Tested operating system

Ubuntu [18.04.5, 20.04.2] LTS

Tested software

g++ [7.5.0, 9.3.0], CUDA [11.2, 11.5]

Tested hardware

GTX970, RTX3080

Compile

make

Execute

./surf --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

Code specification

SURF implementation:

  • main.cu: load a graph as an input
  • bfs.cuh: traverse the graph
  • model.h: initialize a trained MLP model and predict a label of direction
  • 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

Auto labeler:

  • bfs_al.cu: generate train data as auto-labeled records
    • Compile: make
    • Execute: ./aula --csr <*_beg_pos.bin> <*_adj_list.bin> --data <train_data> [option1]
      • [option1]: --verylarge
        • set data type of vertices and edges to 'unsigned long long', default='unsigned int'

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 SURF)
        • 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'
    • 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

Publication

SURF: Direction-Optimizing Breadth-First Search Using Workload State on GPUs. Daegun Yoon, Sangyoon Oh. Sensors, Jun. 2022. [Paper]

Contact

If you have any questions about this project, contact me by one of the followings: