Skip to content

Latest commit

 

History

History
64 lines (57 loc) · 3.22 KB

README.md

File metadata and controls

64 lines (57 loc) · 3.22 KB
Raw

Geodesic Distance-based Spectral Graph Partitioner (GDSP)

This repo contains the code used for our paper

Y. Futamura, R. Wakaki and T. Sakurai, "Spectral Graph Partitioning Using Geodesic Distance-based Projection," 2021 IEEE High Performance Extreme Computing Conference (HPEC), 2021, pp. 1-7, doi: 10.1109/HPEC49654.2021.9622831.

If you use our code in your published work, please cite the paper.

BibTeX entry:

@INPROCEEDINGS{9622831,
  author={Futamura, Yasunori and Wakaki, Ryota and Sakurai, Tetsuya},
  booktitle={2021 IEEE High Performance Extreme Computing Conference (HPEC)}, 
  title={Spectral Graph Partitioning Using Geodesic Distance-based Projection}, 
  year={2021},
  volume={},
  number={},
  pages={1-7},
  doi={10.1109/HPEC49654.2021.9622831}}

Requirement

  • C and C++11 compiler (e.g. gcc/g++)
  • Fortran compiler supporting ISO_C_BINDING (e.g. gfortran)
  • CMake 3.1+
  • Julia 1.3.1+ with MAT.jl package (used to read MATLAB .mat files)
  • BLAS/LAPACK library (e.g. those in Intel MKL)

Installation

$ # assume that the path to a Julia executable is in $PATH
$ mkdir build && cd build
$ cmake .. -DCMAKE_C_COMPILER=gcc -DCMAKE_CXX_COMPILER=g++ -DCMAKE_C_FLAGS="-O3 -DNDEBUG" -DCMAKE_CXX_FLAGS="-O3 -DNDEBUG"
$ make

Usage

$ cd build
# Run GDSP
$ OMP_NUM_THREADS=4 ./sppart_test --mat=/path/to/graph.mat --npart=2 --ub=1.03
# See help message
$ ./bin/sppart_test --help

Note

  • --npart > 2 is experimental. Do not use for performance evaluation. It may violate the balance constraint.
  • sppart_test options used for parallel performance evaluation in the paper: --npart=2 --ub=1.03 --dims=8 (or --dims=4) --limit=1000 --bfsalg=0 --dobfstd --orthalg=1 --roundalg=1 --seed=0 --srcalg=1 --xtyalg=1

Authors

  • Yasunori Futamura, Ryota Wakaki, Tetsuya Sakurai
    • University of Tsukuba
    • futamura (at) cs.tsukuba.ac.jp

License

Most parts of this repo are under the MIT license, except for the following

  • external directory contains following third party programs
    • CLI11 by H. Schreiner et al., BSD 3-Clause license
    • METIS v5.1.0 by Univ. Minnesota, Apache 2.0 license (CMakeLists.txt is modifined so that it can be built as a submodule)
    • MT-METIS v0.7.2 by Univ. Minnesota, Apache 2.0 license (CMakeLists.txt is modifined so that it can be built as a submodule)
    • nlohmann/json by N. Lohmann, MIT license
  • include/gapbs contains GAP Benchmark Suite by Univ. California, BSD 3-Clause (modified by us)
  • include/maxflow contains Maxflow by J. Groschaft, MIT license (modified by us)
  • ./FindJulia.cmake is from xtensor-julia-cookiecutter by J. Mabille et al., BSD 3-Clause
  • ./FindMKL.cmake is from PyTorch by Facebook Inc., BSD-style license