Recent work has illustrated the promise ofmultilevel approaches for partitioning large circuits. Multilevel partitioningrecursively clusters the instance until its size is smallerthan a given threshold, then unclusters the instance while applyinga partitioning refinement algorithm. Our multilevel partitioner usesa new technique to control the number of levels in the matching-basedclustering phase and also exploits recent innovations in classiciterative partitioning. Our heuristic outperforms numerousexisting bipartitioning heuristics, with improvements rangingfrom 6.9 to 27.9% for 100 runs and 3.0 to 20.6% for just 10 runs(while also using less CPU time).
No takes yet. Share an insight, caveat, or question.
Alpert et al. (1997) studied this question.