Trust: Triangle Counting Reloaded on GPUs
This is the code for TRUST: Triangle Counting Reloaded on GPUs.
The code of TRUST has two version: without graph partition for small graph and without graph partition for large graph. Preprocess include the code for preprocessing. Following the step to test the TRUST.
CUDA Toolkit 10.2;
g++ 7.4.0;
MPICH-3.3
In Preprocessing step, use
$ cd Preprocess
$ ./compile.sh
compile the code and we will get three files: fromDirectToUndirece, preprocess and partition.
This corresponds to following three step:
fromDirectToUndirect transform the directed graph to undirected graph, delete the duplicate edges and self loops and remove orphan vertices. It take file name as input and will generate undirected graph 1.mmio
.
For example:
$ ./fromDirectToUndirect cit-Patents.txt
The format of cit-Patents.txt
should be edge list.
preprocess will do the orientation and reordering and generate the CSR format of graph. It will take 1.mmio
as input and generate two file begin.bin
and adjacent.bin
partition use hash to partition the graph. To see detail of partition usage, you can read the Dataset/Cit-Patents/partition.sh
In folder Dataset/Cit-Patents/
we give a example of download Cit-Patents graph and preprocessing it.
Run it by
$ cd Dataset/Cit-Patents/
$ ./get+preprocess.sh
For the large graph and input file only include edge list, we recommend use preprocess code in Preprocess/speedupIO
.
For partition, run
$./partition.sh 2
There are one input arguments n
, it represent the partition number, we will partition graph into n*n
pieces
Before compile the code, you should modify the Makefile
to match your architecture.
The current settings, --gpu-architecture=compute_70 --gpu-code=sm_70
, are tailored for the V100 environment used in the paper.
For small graph, we don’t partition the graph.
Compile the code:
$ cd Without-graph-partition/
$ make
Run the code:
$ mpirun -n 1 ./trianglecounting.bin ../Dataset/Cit-Patents/ 1 1024 1024 1
The input arguments is
The output arguments is
For the large graph, partition is required.
Compile the code:
$ cd With-graph-partition/
$ make
Run the code:
$ mpirun -n 8 ./trianglecounting.bin ../Dataset/Cit-Patents/ 8 1024 1024 1 2
The input arguments is
n
The output arguments is
@article{pandey2021trust,
title={TRUST: Triangle Counting Reloaded on GPUs},
author={Pandey, Santosh and Wang, Zhibin and Zhong, Sheng and Tian, Chen and Zheng, Bolong and Li, Xiaoye and Li, Lingda and Hoisie, Adolfy and Ding, Caiwen and Li, Dong and others},
journal={IEEE Transactions on Parallel and Distributed Systems},
volume={32},
number={11},
pages={2646--2660},
year={2021},
publisher={IEEE}
}