High-Performance Streaming Graph Analytics on GPUs
The repository provides the graph algorithms implemented on top Hornet data structure.
For additional information concerning the data structure and its APIs please refer to Hornet repository.
The document is organized as follows:
The following basic steps are required to build and execute the Hornet algorithms:
git clone --recursive https://github.com/hornet-gt/hornetsnest
cd hornetsnest/build
cmake ..
make p
By default, the CUDA compiler nvcc
uses gcc/g++
found in the current
execution search path as host compiler
(cc --version
to get the default compiler on the actual system).
To force a different host compiler for compiling C++ files (*.cpp
)
you need to set the following environment variables:
CC=<path_to_host_C_compiler>
CXX=<path_to_host_C++_compiler>
To force a different host compiler for compiling host side code (*.cu
)
substitute cmake ..
with
cmake -DCUDAHC=<path_to_host_C++_compiler> ..
Note: host .cpp
compiler and host side .cu
compiler may be different.
The host side compiler must be compatible with the current CUDA Toolkit
version installed on the system
(see CUDA Installation Guide).
Algorithm | Static | Dynamic |
---|---|---|
(BFS) Breadth-first Search | yes | on-going |
(SSSP) Single-Source Shortest Path | yes | on-going |
(CC) Connected Components | yes | on-going |
(SCC) Strongly Connected Components | to-do | to-do |
(MST) Minimum Spanning Tree | on-going | to-do |
(BC) Betweeness Centrality | on-going | on-going |
(PG) Page Rank | yes | on-going |
(TC) Triangle Counting | yes | yes |
(KC) Katz Centrality | yes | yes |
(MIS) Maximal Independent Set | on-going | to-do |
(MF) Maximum Flow | to-do | to-do |
(CC) Clustering Coeffient | on-going | to-do |
(ST) St-Connectivity | to-do | to-do |
(TC) Transitive Closure | to-do | to-do |
Community Detection | to-do | to-do |
Temporal Motif Finding | on-going | to-do |
Sparse Vector-Matrix Multiplication | yes | to-do |
Jaccard indices | on-going | to-do |
Energy/Parity Game | on-going | to-do |
Algorithm | CPU1 | GPU 2 | Speedup |
---|---|---|---|
(BFS) Breadth-first Search | |||
(SSSP) Single-Source Shortest Path | |||
(CC) Connected Components | |||
(MST) Minimum Spanning Tree | |||
(BC) Betweenness Centrality | |||
(PG) Page Rank | |||
(TC) Triangle Counting | |||
(KC) Katz Centrality |
1 Intel ...
2 NVidia Tesla P100 ..
Algorithm | Static | Dynamic | Speedup |
---|---|---|---|
(BFS) Breadth-first Search | |||
(SSSP) Single-Source Shortest Path | |||
(CC) Connected Components | |||
(MST) Minimum Spanning Tree | |||
(BC) Betweenness Centrality | |||
(PG) Page Rank | |||
(TC) Triangle Counting | |||
(KC) Katz Centrality |
Algorithm | Static (A) | Static (B) | Dynamic (A) |
---|---|---|---|
(BFS) Breadth-first Search | 4 | 6 | |
(SSSP) Single-Source Shortest Path | |||
(CC) Connected Components | |||
(MST) Minimum Spanning Tree | |||
(BC) Betweenness Centrality | |||
(PG) Page Rank | |||
(TC) Triangle Counting | |||
(KC) Katz Centrality |
(A) lines of code required for the algorithm
(B) lines of code required for the operators
The code documentation is located in the docs
directory of Hornet data
structure directory (doxygen html format).
The documentation is also accessible online here.
If you find any bugs please report them by using the repository (github issues panel). We are also ready to engage in improving and extending the framework if you request new features.
Federico Busato
, Ph.D. Student, University of Verona (Italy)Oded Green
, Researcher, Georgia Institute of TechnologyFederico Busato
, Ph.D. Student, University of Verona (Italy)Oded Green
, Researcher, Georgia Institute of TechnologyJames Fox
, Ph.D. Student, Georgia Institute of Technology : Maximal Independent Set, Temporal Motif Finding
Devavret Makkar
, Ph.D. Student, Georgia Institute of Technology : Triangle Counting
Elisabetta Bergamini
, Ph.D. Student, Karlsruhe Institute of Technology (Germany) : Katz Centrality
Euna Kim
, Ph.D. Student, Georgia Institute of Technology : Dynamic PageRank
BSD 3-Clause License
Copyright (c) 2017, Hornet All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.