Skip to content

Single-Source Shortest Path (SSSP) implementation in modern C++ for 2022 IPDPS workshop on Graphs, Architectures, Programming, and Learning (GrAPL 2022) submission.

License

Notifications You must be signed in to change notification settings

gunrock/essentials-cpp

Folders and files

NameName
Last commit message
Last commit date

Latest commit

e6a9186 · Mar 31, 2022

History

30 Commits
Mar 16, 2022
Mar 16, 2022
Mar 16, 2022
Mar 15, 2022
Mar 16, 2022
Mar 16, 2022
Mar 15, 2022
Mar 16, 2022
Mar 16, 2022
Mar 16, 2022
Mar 31, 2022

Repository files navigation

Essentials of Parallel Graph Analytics

Single-Source Shortest Path (SSSP) implementation in modern C++ for 2022 IPDPS workshop on Graphs, Architectures, Programming, and Learning (GrAPL 2022) submission. For a more complete implementation of the ideas presented in the paper, please refer to the on-going work of graph analytics on GPUs at gunrock/essentials.

System Version Status
Ubuntu Ubuntu 20.04 Ubuntu
Windows Windows Server 2019 Windows

Dependencies

  • C++20 for linux (requires gcc/g++-11 or higher), C++23 for windows.
  • cmake version 3.22.2.
  • tbb library for execution policies (automatically fetched using cmake).

Implementation Detail

This code base makes use of modern C++ features such as ranges, execution_policy, and lambda expressions to implement the essential components for parallel graph analytics. We focus on a simple implementation of Single-Source Shortest Path (SSSP), but the concepts can easily be extended to support other graph algorithms such as Breadth-First Search with minor changes to the lambda expression during traversal.

SSSP Traversal Condition

[&](vertex_t const& src,    // source
    vertex_t const& dst,    // destination
    edge_t const& edge,     // edge
    weight_t const& weight  // weight
   ) {
     weight_t new_d = distances[src] + weight;
     weight_t curr_d = atomic::min(&distances[dst], new_d, m_locks[dst]);
     return new_d < curr_d;
};

BFS Traversal Condition

[&](vertex_t const& src,    // source
    vertex_t const& dst,    // destination
    edge_t const& edge,     // edge
    weight_t const& weight  // weight
   ) {
     // If the neighbor is not visited, update the distance. Returning false
     // here means that the neighbor is not added to the output frontier, and
     // instead an invalid vertex is added in its place. These invalides (-1 in
     // most cases) can be removed using a filter operator or uniquify.
     if (distances[dst] != std::numeric_limits<vertex_t>::max())
       return false;
     else
       return (atomic::cas(
                   &distances[dst], std::numeric_limits<vertex_t>::max(),
                   iteration + 1) == std::numeric_limits<vertex_t>::max(), m_locks[dst]);
};

Quick Start Guide

Before building this project, make sure your system/compiler supports C++20 and cmake.

git clone https://github.com/gunrock/essentials-cpp.git
cd essentials-cpp
mkdir build && cd build
cmake .. 
make
bin/sssp ../datasets/chesapeake/chesapeake.mtx

How to Cite

Thank you for citing our work.

@InProceedings{   Osama:2022:EOP,
  author        = {Muhammad Osama and Serban D. Porumbescu and John D.
                  Owens},
  title         = {Essentials of Parallel Graph Analytics},
  booktitle     = {Proceedings of the Workshop on Graphs, Architectures,
                  Programming, and Learning},
  year          = 2022,
  series        = {GrAPL 2022},
  month         = may
}

About

Single-Source Shortest Path (SSSP) implementation in modern C++ for 2022 IPDPS workshop on Graphs, Architectures, Programming, and Learning (GrAPL 2022) submission.

Topics

Resources

License

Stars

Watchers

Forks