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 |  |
| Windows | Windows Server 2019 |  |
C++20for linux (requiresgcc/g++-11or higher),C++23for windows.cmakeversion3.22.2.tbblibrary for execution policies (automatically fetched usingcmake).
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.
[&](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; };
[&](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]); };
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
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
}