Hypergraph Partitioning for VLSI: Benchmarks, Code and Leaderboard

Hypergraph Partitioning Leaderboard: Leaderboard of minimum hyperedge cut values for different testcases with multiple imbalance factors.

SpecPart: A Supervised Spectral Framework for Hypergraph Partitioning Solution Improvement
K-SpecPart: A Supervised Spectral Framework for Multi-way Hypergraph Partitioning Solution Improvement

🔴 Note (Jan 10, 2026):
The golden evaluator (see golden_evaluator/utils.py) was patched on Jan 10, 2026. Prior to this fix, the evaluator only enforced the maximum balance constraint (i.e., it flagged a partition only when a part’s total weight exceeded the allowed upper bound) and did not check the minimum balance constraint (lower bound) for each part. This has now been corrected, and the evaluator enforces both minimum and maximum balance constraints. All solutions submitted prior to Jan 10 were generated and verified using the earlier evaluator. All solutions currently reported in the leaderboard have been evaluated using the updated evaluator and only include legally balanced partitions. We wanted to take this opportunity to apologize for the error and alert researchers that previous entries may not have satisfied balance constraints.

---

Description

This repository supports "Data, Benchmarking and Roadmapping" goals for the balanced hypergraph min-cut partitioning problem, which is central to chip design and the divide-and-conquer paradigm. The repository is a one-stop shop" that serves the following purposes.

1. We provide the ISPD98 benchmarks (with unit vertex weights and actual vertex weights) and Titan23 benchmarks in hMETIS format. To understand this format please refer to the hMETIS manual.
2. We provde open source code for the Julia implementation of a recent hypergraph partitioning code, SpecPart. We also provide the implementation of CMG (Combinatorial Multigrid) preconditioner with this package.
3. We provide open source code for the Julia implementation of K-SpecPart which is an enhancement over SpecPart, and can handle multi-way partitions. Comparison of cutsizes and runtimes are available here.
4. We provide the best known partitioning solutions (for number of partitions 2,3, and 4) for the ISPD98 benchmarks (both with unit vertex weights and actual vertex weights) and the Titan Benchmarks.
5. We provide a "Golden Evaluator" which processes a partition file to report the cutsize and the block balances.
6. We provide a leaderboard of minimum hyperedge cutsize values found on the ISPD98 benchmarks and the Titan23 benchmarks. We encourage fellow researchers to update the leaderboard if better solutions are found.

We hope to see pull requests with new solutions and optimization codes, and will continue to update the repository and leaderboard as this happens.

Table of Contents

• Current file/directory tree and description
• (SpecPart-specific) installation and run instructions
• (K-SpecPart-specific) installation and run instructions
• MedPart 2-way partitioning solutions
• Leaderboard of minimum hyperedge cutsize values
  • Leaderboard for number of partitions = 2
  • Leaderboard for number of partitions = 3
  • Leaderboard for number of partitions = 4
• Authors

---

Current File/Directory Tree and Description

.
├── benchmark                                 # hypergraph files for each benchmark 
│   ├── ISPD_benchmark                        # ISPD98 VLSI Circuit Benchmark Suite with unit vertex weights
│   ├── ISPD_weight_benchmark                 # ISPD98 VLSI Circuit Benchmark Suite with actual vertex weights
│   └── Titan23_benchmark                     # Titan23 Benchmark Suite
├── golden_evaluator                          # script for evaluating partitioning solutions
│   ├── markdown_leaderboard_generator.py
│   ├── README.md
│   └── utils.py
├── K_SpecPart                                # K-SpecPart implementation
│   ├── cmg                                   # Combinatorial Multigrid Implementation
│   ├── README.md                             # Guidelines to run K-SpecPart
│   ├── rmq
├── K_specpart_solutions                      # K-SpecPart partitioning solutions
│   ├── ISPD_benchmarks
│   ├── ISPD_weight_benchmarks
│   └── Titan23_benchmarks
├── LICENSE
├── medpart_solutions                         # MedPart partitioning solutions 
│   └── 2_way
├── README.md
├── solutions_2way                            # 2-way solutions for all the benchmarks with different imbalance factors
│   ├── TritonPart_solutions                  # TritonPart solutions (best of 20 seeds) for various imbalance factors
│   ├── ISPD_benchmark_solutions              # solutions on ISPD98 testcases with unit vertex weights
│   |   ├── hMetis                            # solutions using hMETIS
│   |   |   ├── UBfactor_2                    # solutions with imbalance factor 2
│   |   |   └── UBfactor_10                   # solutions with imbalance factor 10
│   |   |   
│   |   ├── KaHyPar                           # solutions with KaHyPar
│   |   |   ├── UBfactor_2                    # solutions with imbalance factor 2
│   |   |   └── UBfactor_10                   # solutions with imbalance factor 10
│   |   |   
|   |   ├── SpecPart                          # solutions with SpecPart
│   |   |   ├── hMetis_SpecPart               # SpecPart with initial solution generated from hMETIS
|   │   |   |   ├── UBfactor_2                # solutions with imbalance factor 2
│   |   |   |   └── UBfactor_10               # solutions with imbalance factor 10
│   |   |   |
│   |   |   └── KaHyPar_SpecPart              # SpecPart with initial solution generated from KaHyPar
|   │   |       ├── UBfactor_2                # solutions with imbalance factor 2
│   |   |       └── UBfactor_10               # solutions with imbalance factor 10
│   |   |
|   |   └── HyperEF_2.0                       # solutions with HyperEF 2.0
│   |       ├── UBfactor_2                    # solutions with imbalance factor 2
│   |       └── UBfactor_10                   # solutions with imbalance factor 10
│   |
│   ├── ISPD_weight_benchmark_solutions       # solutions on ISPD98 testcases with actual vertex weights
│   |   ├── hMetis                            # solutions with hMETIS
│   |   |   ├── UBfactor_2                    # solutions with imbalance factor 2
│   |   |   └── UBfactor_10                   # solutions with imbalance factor 10
│   |   |   
│   |   ├── KaHyPar                           # solutions with KaHyPar
│   |   |   ├── UBfactor_2                    # solutions with imbalance factor 2
│   |   |   └── UBfactor_10                   # solutions with imbalance factor 10
│   |   |   
│   |   └── SpecPart                          # solutions with SpecPart
│   |       ├── hMetis_SpecPart               # SpecPart with initial solution generated from hMETIS
|   │       |   ├── UBfactor_2                # solutions with imbalance factor 2
│   |       |   └── UBfactor_10               # solutions with imbalance factor 10
│   |       |   
│   |       └── KaHyPar_SpecPart              # SpecPart with initial solution generated from KaHyPar
|   │           ├── UBfactor_2                # solutions with imbalance factor 2
│   |           └── UBfactor_10               # solutions with imbalance factor 10
│   |       
└── └── Titan23_benchmark_solutions           # solutions on Titan23 testcases
│        ├── hMetis                           # solutions with hMETIS
│        |   ├── UBfactor_2                   # solutions with imbalance factor 2
│        |   └── UBfactor_20                  # solutions with imbalance factor 20
│        |   
│        ├── hMetis_Autotune                  # solutions with Autotuned hMETIS
│        |   └── UBfactor_10                  # solutions with imbalance factor 10
│        |   
│        ├── hMetis_Autotune_SpecPart         # SpecPart with initial solution generated from Autotuned hMETIS   
│        |   └── UBfactor_10                  # solutions with imbalance factor 10
│        |   
│        ├── hMetis_SpecPart                  # SpecPart with initial solution generated from hMETIS   
│        |   ├── UBfactor_2                   # solutions with imbalance factor 2
│        |   └── UBfactor_20                  # solutions with imbalance factor 20
│        └── HyperEF_2.0                   # solutions with HyperEF 2.0
│            ├── UBfactor_2                   # solutions with imbalance factor 2
│            └── UBfactor_20                  # solutions with imbalance factor 20
└── SpecPart                                  # SpecPart Implementation
│   ├── SpectralCommunityDetection
│       └── cmg                               # Combinatorial Multigrid Implementation

---

Installation and Run Instructions

Open Julia REPL and do the following:

include("SpectralRefinement.jl")
using Main.SpecPart
SpecPart.SpectralRefinement(hg = "Hypergraph file", pfile = "Partition file", Nparts = "Number of partitions", cycles = ζ, hyperedges_threshold = γ, ub = ε, nev = m, refine_iters = β, best_solns = δ)

ζ is the number of graph cycles (we recommend ζ=2)
γ is the threshold number of hyperedges to run ILP (we recommend γ=600)
ε is the imbalance factor (ε=1-49)
m is the number of eigenvectors (we recommend m=2)
β is the number of SpecPart iterations (we recommend β=2)
δ is the number of solutions picked from candidate solutions for overlay based clustering (we recommend δ=5)

A user guide is available here.

---

Leaderboards of minimum hyperedge cut values

Number of partitions 2

Current Leaderboard of minimum hyperedge cut values on ISPD98 testcases with unit vertex weights and actual vertex weights, with different imbalance factors (ε):

Testcase	Statistics		Cutsize
	# Vertices	# Hyperedges	ε = 1	ε = 2	ε = 5	ε = 10
IBM01	12752	14111	203	203	180	169
IBM01_wt	12752	14111	216	216	215	215
IBM02	19601	19584	349	326	262	262
IBM02_wt	19601	19584	266	266	258	258
IBM03	23136	27401	963	963	954	954
IBM03_wt	23136	27401	960	956	902	666
IBM04	27507	31970	600	592	523	388
IBM04_wt	27507	31970	506	502	440	393
IBM05	29347	28446	1728	1728	1713	1671
IBM05_wt	29347	28446	1720	1720	1715	1659
IBM06	32498	34826	977	977	904	741
IBM06_wt	32498	34826	795	791	487	470
IBM07	45926	48117	960	952	861	796
IBM07_wt	45926	48117	726	726	715	665
IBM08	51309	50513	1143	1143	1143	1143
IBM08_wt	51309	50513	1202	1201	1166	1124
IBM09	53395	60902	626	621	621	521
IBM09_wt	53395	60902	519	519	519	519
IBM10	69429	75196	1305	1283	1263	1263
IBM10_wt	69429	75196	1303	1258	1213	733
IBM11	70558	81454	1075	1054	1007	768
IBM11_wt	70558	81454	776	770	706	657
IBM12	71076	77240	2075	2063	1885	1885
IBM12_wt	71076	77240	2250	2113	2009	2009
IBM13	84199	99666	852	848	848	671
IBM13_wt	84199	99666	895	869	851	849
IBM14	147605	152772	1905	1905	1826	1665
IBM14_wt	147605	152772	1967	1820	1598	1318
IBM15	161570	186608	2800	2800	2622	2169
IBM15_wt	161570	186608	2243	2164	2049	1708
IBM16	183484	190048	2248	2121	1753	1653
IBM16_wt	183484	190048	1647	1645	1645	1645
IBM17	185495	189581	2454	2343	2202	2202
IBM17_wt	185495	189581	2458	2438	2258	2069
IBM18	210613	201920	1618	1527	1522	1522
IBM18_wt	210613	201920	1663	1607	1524	1524

---

Current Leaderboard of minimum hyperedge cut values on Titan23 testcases with different imbalance factors (ε):

	Statistics		Cutsize
Testcase	#Vertices	#Hyperedges	ε = 1	ε = 2	ε = 5	ε = 10	ε = 20
sparcT1_core	91976	92827	1088	978	978	978	903
neuron	92290	125305	244	243	243	243	206
stereovision	94050	127085	181	181	179	91	91
des90	111221	139557	374	371	365	345	345
SLAM_spheric	113115	142408	1061	1061	1061	1061	1061
cholesky_mc	113250	144948	305	285	281	281	281
segmentation	138295	179051	132	107	107	85	78
bitonic_mesh	192064	235328	581	581	581	543	483
dart	202354	223301	835	828	828	719	582
openCV	217453	284108	451	435	434	434	434
stap_qrd	240240	290123	378	376	376	296	275
minres	261359	320540	239	215	215	199	189
cholesky_bdti	266422	342688	1213	1156	1156	1156	848
denoise	275638	356848	456	416	416	416	224
sparcT2_core	300109	302663	1198	1198	1198	1198	930
gsm_switch	493260	507821	1517	1485	1485	1460	1407
mes_noc	547544	577664	703	634	628	628	617
LU230	574372	669477	3362	3273	3273	3262	2677
LU_Network	635456	726999	623	525	524	524	524
sparcT1_chip2	820886	821274	1037	899	899	815	783
directrf	931275	1374742	673	574	441	378	295
bitcoin_miner	1089284	1448151	1512	1489	1232	1232	1225

Number of partitions 3

Current Leaderboard of minimum hyperedge cut values on Titan23 testcases with imbalance factor (ε) = 2:

	Statistics		Cutsize
Testcase	#Vertices	#Hyperedges	ε = 2
sparcT1_core	91976	92827	1889
neuron	92290	125305	396
stereovision	94050	127085	331
des90	111221	139557	535
SLAM_spheric	113115	142408	2720
cholesky_mc	113250	144948	864
segmentation	138295	179051	453
bitonic_mesh	192064	235328	895
dart	202354	223301	1243
openCV	217453	284108	525
stap_qrd	240240	290123	497
minres	261359	320540	309
cholesky_bdti	266422	342688	1652
denoise	275638	356848	915
sparcT2_core	300109	302663	2249
gsm_switch	493260	507821	3694
mes_noc	547544	577664	1125
LU230	574372	669477	4548
LU_Network	635456	726999	786
sparcT1_chip2	820886	821274	1404
directrf	931275	1374742	762
bitcoin_miner	1089284	1448151	1917

Number of partitions 4

Current Leaderboard of minimum hyperedge cut values on Titan23 testcases with different imbalance factors (ε):

	Statistics		Cutsize
Testcase	#Vertices	#Hyperedges	ε = 2
sparcT1_core	91976	92827	2517
neuron	92290	125305	431
stereovision	94050	127085	407
des90	111221	139557	747
SLAM_spheric	113115	142408	3241
cholesky_mc	113250	144948	984
segmentation	138295	179051	490
bitonic_mesh	192064	235328	1311
dart	202354	223301	1401
openCV	217453	284108	522
stap_qrd	240240	290123	695
minres	261359	320540	407
cholesky_bdti	266422	342688	1865
denoise	275638	356848	1001
sparcT2_core	300109	302663	3558
gsm_switch	493260	507821	4404
mes_noc	547544	577664	1346
LU230	574372	669477	6310
LU_Network	635456	726999	1417
sparcT1_chip2	820886	821274	1601
directrf	931275	1374742	1092
bitcoin_miner	1089284	1448151	2737

---

Authors

Ismail Bustany, Andrew Kahng, Yiannis Koutis, Bodhisatta Pramanik, Zhiang Wang

References

To reference SpecPart, please cite:

I. Bustany, A. B. Kahng, Y. Koutis, B. Pramanik and Z. Wang, "SpecPart: A Supervised Spectral Framework for Hypergraph Partitioning Solution Improvement", (pdf), Proc. ACM/IEEE International Conference on Computer-Aided Design, 2022.

Acknowledgments

This work was partially supported by NSF CCF-2112665, CCF-2039863, CCF-1813374, DARPA HR0011-18-0-2-0032.