Multilevel cooperative search: Application to the circuit/hypergraph partitioning problem

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

Research output: Contribution to conferencePaperpeer-review

9 Scopus citations

Abstract

In this paper, we present an adaptation for hypergraph partitioning of the multilevel cooperative search paradigm first introduced by Toulouse, Thulasiraman, and Glover. We also introduce a new approach for coarsening hypergraphs, and describe a parallel implementation of this algorithm on the SGI 02000 system. Experiments on ISPD98 benchmark suite of circuits show, for 4-way and 8-way partitioning, a reduction of 3% to 15% on hyperedge-cut compared to h-METIS. Bisections of hypergraphs based on our algorithm also outperforms hMETIS, although more modestly.

Original languageEnglish (US)
Pages192-198
Number of pages7
StatePublished - 2000
EventISPD-2000: International Symposium on Physical Design - San Diego, CA, USA
Duration: Apr 9 2000Apr 12 2000

Other

OtherISPD-2000: International Symposium on Physical Design
CitySan Diego, CA, USA
Period4/9/004/12/00

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

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

Cite this