Skip to content

KaHIP/FREIGHT

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

9 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

FREIGHT: Fast stREamInG Hypergraph parTitioning

FOSSA StatusLicense: MIT

FREIGHT is a streaming algorithm for hypergraph partitioning which is based on the widely-known graph-based algorithm Fennel. By using an efficient data structure, we make the overall running of FREIGHT linearly dependent on the pin-count of the hypergraph and the memory consumption linearly dependent on the numbers of nets and blocks. The results of our extensive experimentation showcase the promising performance of FREIGHT as a highly efficient and effective solution for streaming hypergraph partitioning. Our algorithm demonstrates competitive running time with the Hashing algorithm, with a difference of a maximum factor of four observed on three fourths of the instances. Significantly, our findings highlight the superiority of FREIGHT over all existing (buffered) streaming algorithms and even the in-memory algorithm HYPE, with respect to both cut-net and connectivity measures. This indicates that our proposed algorithm is a promising hypergraph partitioning tool to tackle the challenge posed by large-scale and dynamic data processing.

This repository is associated with the following paper:

  • "FREIGHT: Fast Streaming Hypergraph Partitioning", which has been published as a full paper at SEA 2023. This paper was the recipient of the SEA 2023 best paper award. Additionally, you can find a technical report and our SEA 2023 slides.

If you publish results using our algorithms, please acknowledge our work by citing our paper:

@InProceedings{FREIGHT2023,
  author ={Kamal Eyubov and Marcelo Fonseca Faraj and Christian Schulz},
  title ={{FREIGHT: Fast Streaming Hypergraph Partitioning}},
  booktitle ={21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages ={15:1--15:16},
  series ={Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN ={978-3-95977-279-2},
  ISSN ={1868-8969},
  year ={2023},
  volume ={265},
  editor ={Georgiadis, Loukas},
  publisher ={Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address ={Dagstuhl, Germany},
  URL ={https://drops.dagstuhl.de/opus/volltexte/2023/18365},
  URN ={urn:nbn:de:0030-drops-183657},
  doi ={10.4230/LIPIcs.SEA.2023.15},
}

Detailed experimental results published in our paper are available here.

Repository Structure

This repository contains the following folders:

Installation Notes

Requirements

Building FREIGHT

To build the software, clone this repository, enter the intended code base and run

./compile.sh

Alternatively, you can use the standard CMake build process.

The resulting binary is located in the deploy/ subdirectory within the appropriate code base.
The executables freight_cut and freight_con optimize for cut-net and connectivity, respectively. For partitioning graphs, the corresponding executable is named freight_graphs.

Running FREIGHT for hypergraphs

To partition a hypergraph in net-list format using FREIGHT, run

./freight_con <hypergraph filename> --k=<number of blocks> 
./freight_cut <hypergraph filename> --k=<number of blocks> 

For a complete list of parameters alongside with descriptions, run:

./freight_con --help
./freight_cut --help

For a characterization of the used hypergraph format, please see this page.

Running FREIGHT for graphs

To partition a graph in METIS format using FREIGHT, run

./freight_graphs <graph filename> --k=<number of blocks> 

For a complete list of parameters alongside with descriptions, run:

./freight_graphs --help

For a description of the graph format, please have a look at the KaHiP manual.

Licensing

FREIGHT is free software provided under the MIT License.

About

Streaming Hypergraph Partitioning

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published