Parallel Subgraph Enumeration on GPUs and CPUs

This project provides a framework for parallel subgraph enumeration utilizing GPUs and multi-core CPUs on a single machine [1,2].

File organization

• scripts: provide some useful scripts to preprocess the data graphs and run the programs.
• lib: the library used in this project.
• src/cpu: the implementation on multi-core CPUs.
• src/gpu: the implementation on GPUs.
• src/preprocess: the utils to preprocess the data graphs.

Prerequisites

Common dependency

• gtest (optional): needed to compile the src/test folder.

CPU dependency

• g++ 5.4.0

GPU dependency

You need the following deps only if you want to run GPU solutions.

• CUDA 10.0
• moderngpu 1.0
• cnmem
• cudpp (optional)
• cub 1.8
• METIS (optional)

Build GPU dependency

The GPU deps except for CUDA are configured as submodule in the lib folder. You can easily fetch the respositories by the following command.

git submodule init
git submodule update

To compile moderngpu

cd lib/moderngpu; make -j

To compile cnmem

cd lib/cnmem 
mkdir build 
cmake -DCMAKE_INSTALL_PREFIX={your_path_to_cnmem} ..
make -j
make install

Add the path to the libcnmem.so to your LD_LIBRARY_PATH.

To compile cudpp, refer to this guide and this guide.

cd lib/cudpp 
git submodule init
git submodule update
mkdir build
cmake -DCMAKE_INSTALL_PREFIX={your_path_to_cudpp} ..
make -j
make install

Compile

After configuring the dependencies, simply go to the folder src/cpu, src/gpu, src/preprocess, and make -j.

Note that the solutions for CPUs and GPUs are separated. So you can still compile and run the CPU solutions even if you don't have CUDA on your machine.

GPU gencode

Depending on your GPU architecture, you may need to

• In src/gpu/Makefile, add -gencode arch=compute_61,code=sm_xx to ARCH.
• In src/gpu/utils/context/MGPUContext.cuh, add mgpu::arch_xx_cta<128,8,8> to MGPULaunchBox and mgpu::arch_xx_cta<128,1> to MGPULaunchBoxVT1.

If your arch is not in lib/moderngpu/src/moderngpu/launch_box.hxx, you need to configure there also.

Run

Getting started

scripts/demo.sh shows an example of how to run the preprocessing, CPU and GPU solutions.

Data formats

Our framework supports two formats of data graphs.

• SNAP: the edge list input. The datasets downloaded from SNAP website adopt this format.
• BIN: our preprocessed binary format. The BIN format reorganizes the vertex ids into the continous integer starting from 0. It removes any self loops and parallel edges if needed. The BIN file is written in binary to improve read/write speed.

Queries

The set of queries supported can be seen in doc/queries.pdf.

Register new queries

1. In src/query/common/Query.h, add a new function specifying the structure of a new pattern. Refer to other patterns in the same file as examples.
2. In src/Meta.h, add your new query under QueryType.
3. Recompile.

Preprocess

See src/preprocess/README.md for details.

scripts/preprocess.h provide some example runs.

Run GPU solutions

See src/gpu/README.md.

Run CPU solutions

See src/cpu/README.md.

References

[1]. GPU-Accelerated Subgraph Enumeration on Partitioned Graphs. SIGMOD 2020. [Paper] [Bib entry] [Slides] [Video]

[2]. Exploiting Reuse for GPU Subgraph Enumeration. Under submission. TKDE 2020.