Coder Social home page Coder Social logo

puzzlef / graph-csr-openmp Goto Github PK

View Code? Open in Web Editor NEW
0.0 1.0 0.0 89 KB

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

Home Page: https://arxiv.org/abs/2311.14650

License: MIT License

C++ 95.56% Shell 2.03% JavaScript 2.41%
csr edgelist graph load openmp parallel gvel algorithm parser

graph-csr-openmp's Introduction

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

graph-csr-openmp's People

Contributors

wolfram77 avatar

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.