Design and implementation of move-based heuristics for VLSI hypergraph partitioning
- 31 December 2000
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Journal of Experimental Algorithmics
Abstract
We summarize the techniques of implementing move-based hypergraph partitioning heuristics and evaluating their performance in the context of VLSI design applications. Our first contribution is a detailed software architecture, consisting of seven reusable components, that allows flexible, efficient and accurate assessment of the practical implications of new move-based algorithms and partitioning formulations. Our second contribution is an assessment of the modern context for hypergraph partitioning research for VLSI design applications. In particular, we discuss the current level of sophistication in implementation know-how and experimental evaluation, and we note how requirements for real-world partitioners - if used as motivation for research - should affect the evaluation of prospective contributions. Two "implicit decisions" in the implementation of the Fiduccia-Mattheyses heuristic are used to illustrate the difficulty of achieving meaningful experimental evaluation of new algorithmic ideas.Keywords
This publication has 18 references indexed in Scilit:
- Cut Size Statistics of Graph Bisection HeuristicsSIAM Journal on Optimization, 1999
- Partitioning using second-order information and stochastic-gain functionsPublished by Association for Computing Machinery (ACM) ,1998
- Two novel multiway circuit partitioning algorithms using relaxed lockingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1997
- Partitioning-based standard-cell global placement with an exact objectivePublished by Association for Computing Machinery (ACM) ,1997
- An evaluation of bipartitioning techniquesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1997
- A method for generating random circuits and its application to routability measurementPublished by Association for Computing Machinery (ACM) ,1996
- Recent directions in netlist partitioning: a surveyIntegration, 1995
- Multiple-way network partitioning with different cost functionsIEEE Transactions on Computers, 1993
- Graph bisection algorithms with good average case behaviorCombinatorica, 1987
- A Procedure for Placement of Standard-Cell VLSI CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1985