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

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

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

• g++ 5.4.0

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)

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

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.

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.

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

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.

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

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.

See src/preprocess/README.md for details.

scripts/preprocess.h provide some example runs.

See src/gpu/README.md.

See src/cpu/README.md.

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