Skip to content

Design of high-performance OpenMP-based parallel Graph Edgelist and Compressed Sparse Row (CSR) loader, aka GVEL.

License

Notifications You must be signed in to change notification settings

puzzlef/graph-csr-openmp

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

38 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Design of high-performance OpenMP-based parallel Graph CSR loader.

High-performance graph processing frameworks like Gunrock, Hornet, Ligra, and Galois help accelerate graph analytics tasks. However, graph loading is a major bottleneck in these frameworks. Fast graph loading is crucial for improving response time and reducing system/cloud usage charges. To address this, we introduce GVEL, a highly optimized method for reading Edgelists from text files and converting them into Compressed Sparse Row (CSR) format.

Below we plot the time taken by Hornet, Gunrock, PIGO, and GVEL for reading Edgelist and converting it to CSR on 13 different graphs. PIGO and GVEL are not visible on this scale - they are significantly faster than Hornet and Gunrock. The graph loading time for Hornet is not shown for uk-2002, it-2004, and sk-2005 graphs as it crashed while loading. GVEL surpasses Hornet, Gunrock, and PIGO in CSR reading by 78×, 112×, and 1.8×, respectively.

Below we plot only the time taken by PIGO and GVEL for reading Edgelist and converting it to CSR.

Next, we plot the time taken by PIGO and GVEL for reading Edgelist. Here, GVEL outperforms PIGO by 2.6×, achieving a read rate of 1.9 billion edges/s with 64 threads.

Finally, we plot the strong scaling behaviour of GVEL for reading Edgelist, and for reading CSR.

Refer to our technical report for more details:
GVEL: Fast Graph Loading in Edgelist and Compressed Sparse Row (CSR) formats.


Note

You can just copy main.sh to your system and run it.
For the code, refer to main.cxx.



Code structure

The code structure of GVEL is as follows:

- inc/_cctype.hxx: Character classification/conversion
- inc/debug.hxx: Debugging macros (LOG, ASSERT, ...)
- inc/exception.hxx: Custom exception class (FormatError)
- inc/_mman.hxx: Memory mapping/allcation functions
- inc/_openmp.hxx: OpenMP utility functions
- inc/_string.hxx: Number parsing/string tokenization
- inc/_utility.hxx: Runtime measurement functions
- inc/_vector.hxx: Vector utility functions
- inc/io.hxx: COO/MTX file reading functions
- main.cxx: Experimentation code
- process.js: Node.js script for processing output logs

Note that each branch in this repository contains code for a specific experiment. The main branch contains code for the final experiment. If the intention of a branch in unclear, or if you have comments on our technical report, feel free to open an issue.



References

Graph formats

Graph frameworks

Memory mapping

String tokenization

Parsing numbers

Parsing numbers (SIMD)

Stringifying numbers

Performance optimization

Smart pointers

Exception handling

Basics

Testing




ORG DOI

About

Design of high-performance OpenMP-based parallel Graph Edgelist and Compressed Sparse Row (CSR) loader, aka GVEL.

Topics

Resources

License

Stars

Watchers

Forks