Source code for the graph reordering technique, DBG, published in [Faldu et al., IISWC'19].

This repo integrates skew-aware lightweight reordering techniques with a widely popular shared-memory graph processing framework, Ligra. To make this repo standalone, it retains large chunk of the code from the original Ligra framework along with the changes from Balaji et al. [2]. For detailed information on the Ligra framework, please consult their original repository.

Specifically, we provide multi-threaded implementations of DBG[1], Hub Clustering[2], Hub Sorting[3], Sort and Random (in ligra/dbg.h), in addition to the original implementations of Hub Clustering and Hub Sorting provided by Balaji et al. (in ligra/IO.h). We also support aribtrary reordering based on an input MAP file (see LoadMappingFromFile() in ligra/dbg.h for more detail).

export DBG_ROOT='directory where this repo is cloned'
cd ${DBG_ROOT}/apps
make clean; make cleansrc; make -j

In addition to the Ligra's built-in support of graphs in adjacency format from the Problem Based Benchmark Suite, we also support graphs in binary CSR format used in Galois (enabled by setting VGR=1 in the Makefile, which is ON by default).

Workloads used in the paper can be downloaded from the links specified in ${DBG_ROOT}/graph-convert-utils/workload_links.info.

Directory ${DBG_ROOT}/datasets contains a small dataset called web-Google to get you started. The following set of commands shows how you could download and prepare it by yourself.

wget http://snap.stanford.edu/data/web-Google.txt.gz
gunzip web-Google.txt.gz
${DBG_ROOT}/graph-convert-utils/clean_edgelist.py ${DBG_ROOT}/datasets/web-Google.txt ${DBG_ROOT}/datasets/web-Google.el
${DBG_ROOT}/graph-convert-utils/convert.sh ${DBG_ROOT}/datasets/web-Google

The following command runs the PageRank application on the web-Google dataset with DBG reordering (specified by 5).

cd ${DBG_ROOT}/apps
make REORDERING_ALGO=5 DEGREE_USED_FOR_REORDERING=0 DATASET=web-Google run-PageRank

Total reordering time is printed as DBG Total Map Time: 0.032493 and Application runtime is printed as PageRank Run Time(sec) :0.437708. Addition of both would provide a net runtime of an application.

The following script runs all five graph applications on the web-Google dataset.

cd ${DBG_ROOT}/apps
./run.sh

This version is tested on x86 system with gcc 6.4.0 on Ubuntu 14.04.1 booted with Linux 4.4.0-96-lowlatency.

The repo also contains code from multiple other repositories (e.g., Ligra, Graph-Reordering-IISWC18, GAP) and the original copyright and license constraints apply to their code.

Please cite the following if you use the source code from this repository in your research.

@inproceedings{DBGFalduIISWC19,  
  author={Priyank Faldu and Jeff Diamond and Boris Grot},  
  booktitle={International Symposium on Workload Characterization (IISWC)},  
  title="{A Closer Look at Lightweight Graph Reordering}",  
  year={2019},  
  month=nov,  
}

[1] P. Faldu and J. Diamond and B. Grot, "A Closer Look at Lightweight Graph Reordering," in Proceedings of the International Symposium on Workload Characterization (IISWC), November 2019.

[2] V. Balaji and B. Lucia, "When is Graph Reordering an Optimization? Studying the Effect of Lightweight Graph Reordering Across Applications and Input Graphs," in Proceedings of the International Symposium on Workload Characterization (IISWC), September 2018.

[3] Y. Zhang, V. Kiriansky, C. Mendis, S. Amarasinghe and M. Zaharia, "Making Caches Work for Graph Analytics," in Proceedings of the International Conference on Big Data (Big Data), January 2018.