Skip to content

Latest commit

 

History

History
120 lines (85 loc) · 5.12 KB

README.md

File metadata and controls

120 lines (85 loc) · 5.12 KB
Raw

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

Algorithm Abbreviation Code Folder
Our Optimized TD OPT-CPU opt-truss-decomp
Our Optimized TD with GPU OPT-HPU opt-truss-decomp-offload
Our simplified OPT-CPU with Large Data support > 2G edges OPT-CPU-LD opt-cpu-large-data
Our simplified OPT-HPU with Large Data support > 2G edges OPT-HPU-LD opt-offload-large-data
Wang et al.'s work (VLDB'12) WC (sequential) opt-truss-decomp/related_work/wc_improved.cpp
Ross et al.'s work (PKDD'14) ROSS (sequential) opt-truss-decomp/related_work/ros_improved.cpp
Kabir et al.'s work (HiPC'17, HPEC'17) PKT opt-truss-decomp/pkt_serial, opt-truss-decomp/pkt_parallel_org
Smith el al.'s work (HPEC'17) MSP msp
Sariyuce el al.'s work (VLDB'19) H-IDX, H-IDX+ (our improved version) h-idx/pnd

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 /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

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

Folder Comment
dependencies/cub, dependencies/moderngpu GPU primitives
dependencies/libpopcnt popcnt primitive
dependencies/sparsepp, dependencies/sparsehash-yche sparse hash table implementation