iG-kway: Incremental k-way Graph Partitioning on GPU
Recent advances in GPU-accelerated graph partitioning have achieved significant performance gains but remain limited to full graph partitioning, lacking support for incremental updates. This limitation is critical in CAD applications, where circuit graphs undergo iterative, incremental modifications during optimization. We present iG-kway, the first GPU-based incremental k-way graph partitioner. iG-kway features an incrementality-aware data structure and a refinement kernel that efficiently updates only affected vertices with minimal quality loss. Experiments show that iG-kway delivers up to $84 \times$ speedup over the state-of-the-art G-kway with comparable partitioning quality.
Authors
- Wan Luan Lee (ORCID: https://orcid.org/0009-0007-2156-2765)
- Ulf Schlichtmann (ORCID: https://orcid.org/0000-0003-4431-7619)
- Boyang Zhang (ORCID: https://orcid.org/0009-0007-2008-7915)
- Dian-Lun Lin (ORCID: https://orcid.org/0000-0003-3075-7437)
- Tsung-Yi Ho (ORCID: https://orcid.org/0000-0001-7348-5625)
- Yi-Hua Chung
- Tsung‐Wei Huang (ORCID: https://orcid.org/0000-0001-9768-3378)
- Shui Jiang (ORCID: https://orcid.org/0000-0003-0718-1003)
- Che Chang (ORCID: https://orcid.org/0009-0001-5455-037X)
Institutions
- University of Wisconsin–Madison (US)
- Chinese University of Hong Kong (HK)
- Technical University of Munich (DE)
Publication Details
- Published
- 2025-06-22
- DOI
- https://doi.org/10.1109/dac63849.2025.11132904
- Citations
- 6
- Primary Topic
- Graph Theory and Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 7.66