AccTD

This repository contains the source code of the paper "Accelerating Truss Decomposition on Heterogeneous Processors" by Yulin Che, Zhuohang Lai, Dr. Shixuan Sun, Dr. Yue Wang and Prof.Qiong Luo.

Overview

We provide source codes of OPT-CPU, OPT-HPU, WC, ROSS, PKT, MSP, H-IDX, H-IDX+ for truss decomposition, and experimental scripts. The codes are organized in four cmake projects - h-idx, msp, opt-truss-decomp and opt-truss-decomp-offload. We give the code organization in the following "Algorithms" section.

Algorithms

Datasets (Input) Pre-Processing

• Real-World Graph

We use the converter in ppSCAN-release to transform an edge list txt file into our format (two binary files b_degree.bin and b_adj.bin under a folder). These two binary files contain the information for the reconstruction of the Compressed Sparse Row (CSR) format. Please see Lijun's datasets format for more details.

• Synthetic-Graph

Please see doc/RapidsSyntheticGraphGen.md to install graph generators and format converters (GT Graph Generator (3 types), Random, RMAT, Clique; Kronecker Model (RMAT) Graph; Parallel Graph Pre-Processing and Conversion).

• Statistics

The statistics (|V|, |E|, |TC|, avg-deg, max-deg, dodg-max-deg, max-core-val, core-histogram) can be collected using our tool in KroneckerBinEdgeListToCSR

Build

We build the four cmake project h-idx, msp, opt-truss-decomp and opt-truss-decomp-offload separately. In each build, we can give cmake options specified in the cmake list. For details, please see the corresponding project folder.

• build steps:

mkdir -p build
cd build
cmake .. ${cmake options}
make -j

• example cmake options for OPT-CPU: -DBUILD_SERIAL=ON -DPLAYGROUND=OFF -DLEGACY_PKT_ALL=ON

Run

Suppose we already have two binary files b_degree.bin and b_adj.bin under a folder folder_path as our input. Then we run as follows

WC/ROS/PKT/OPT-CPU/OPT-HPU

see python_experiments/run_experiments/run_k_truss_reorderd_graph.py , where org denotes the graph ordering.

• WC (in opt-truss-decomp)
• ROS (in opt-truss-decomp)
• PKT (in opt-truss-decomp)
• OPT-CPU (in opt-truss-decomp)
• OPT-HPU (in opt-truss-decomp-offload)

./wc /mnt/nvme-ssd/yche/datasets/snap_livejournal org
./ros /mnt/nvme-ssd/yche/datasets/snap_livejournal org
./pkt-inter-legacy /mnt/nvme-ssd/yche/datasets/snap_livejournal org
./pkt-inter-shrink /mnt/nvme-ssd/yche/datasets/snap_livejournal org
./cuda-pkt-offload-opt /mnt/nvme-ssd/yche/datasets/snap_livejournal org

MSP

• MSP (in msp)

see python_experiments/run_experiments/run_k_truss_karypis.py

./ktruss -kttype msp -iftype bin /mnt/nvme-ssd/yche/datasets/snap_livejournal

H-IDX and H-IDX+

• H-IDX, H-IDX+ (in h-idx)

see python_experiments/run_experiments/run_necleus_decomposition.py

./pnd /mnt/storage1/yche/datasets/snap_livejournal 2300
./hidx-org /mnt/storage1/yche/datasets/snap_livejournal 2300

More Experiments

see python_experiments/run_experiments

Dependencies