Multilevel cooperative search for the circuit/hypergraph partitioning problem

Min Ouyang, Michel Toulouse, Krishnaiyan Thulasiraman, Fred Glover, Jitender S. Deogun

Research output: Contribution to journalArticle

20 Scopus citations

Abstract

The objectives in this paper are twofold: design an approach for the netlist partitioning problem using the cooperative multilevel search paradigm introduced by Toulouse et al. and study the effectiveness of this paradigm for solving combinatorial optimization problems, in particular, those arising in the very large scale integration (VLSI) computer-aided design (CAD) area. The authors present a cooperative multilevel search algorithm CoMHP and describe a parallel implementation on the SGI O2000 system. Experiments on ISPD98 benchmark suite of circuits show, for four-way and eight-way partitioning, a reduction of 3% to 15% in the size of hyperedge cuts compared to those obtained by hMETIS. Bisections of hypergraphs based on the algorithm also outperform hMETIS, although more modestly. The authors present experimental results to demonstrate that the cooperation scheme plays a key role in the performance of CoMHP. In fact, the improvement in the quality of the solutions produced by CoMHP is to a large extent independent of the partitioners used in the implementation of CoMHP. The experimental results also demonstrate the effectiveness of the cooperative multilevel search paradigm for solving the netlist partitioning problem and show that the cooperative multilevel search strategy can be used as a paradigm for designing effective solution techniques for combinatorial optimization problems such as those arising in the VLSI CAD area.

Original languageEnglish (US)
Pages (from-to)685-693
Number of pages9
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume21
Issue number6
DOIs
StatePublished - Jun 2002

Keywords

  • Combinatorial optimization
  • Cooperative search
  • Graph partitioning
  • Multilevel algorithms
  • VLSI physical design

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Multilevel cooperative search for the circuit/hypergraph partitioning problem'. Together they form a unique fingerprint.

  • Cite this