Fast and Adaptive List Intersections on the GPU

The repository provides the implementation of the Logarithmix Radix Binning GPU (LRB-GPU) triangle counting algorithm from the IEEE High Performance Extreme Computing Conference (HPEC) publication “Fast and Adaptive List Intersections on the GPU”, which was a 2018 HPEC Graph Challenge Finalist. This algorith was implemented on top of the Hornet data structure, and included as part of its library of high performance graph algorithms.

For questions regarding the LRB-GPU algorithm or implementation, please contact the primary author at (foxjas09@gmail.com). For additional information or questions concerning the Hornet data structure, its APIs, or other algorithms please refer to Hornet repository.

Requirements

• Nvidia Modern GPU (compute capability ≥ 3.0): Kerpler, Maxwell, Pascal, Volta architectures.
• CUDA toolkit 9 or greater.
• GCC or Clang host compiler with support for C++14. Note: the compiler must be compatible with the related CUDA toolkit version. For more information see CUDA Installation Guide.
• CMake v3.6 or greater.
• 64-bit Operating System (Ubuntu 16.04 or above suggested).

Quick Start

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).

---

License

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.