Multilevel cooperative search for the circuit/hypergraph partitioning problem

Simple item page
dc.contributor.authorOuyang, M
dc.contributor.authorToulouse, M
dc.contributor.authorThulasiraman, K
dc.contributor.authorGlover, F
dc.contributor.authorDeogun, JS
dc.date.accessioned2007-10-10T12:14:08Z
dc.date.available2007-10-10T12:14:08Z
dc.date.issued2002-06-30
dc.description.abstractThe 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.en
dc.format.extent337164 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.citation0278-0070; IEEE TRANS COMPUT AID DES INT, JUN 2002, vol. 21, no. 6, p.685 to 693.en
dc.identifier.doihttp://dx.doi.org/10.1109/TCAD.2002.1004312
dc.identifier.urihttp://hdl.handle.net/1993/2924
dc.language.isoengen_US
dc.rights©2002 IEEE. This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of the University of Manitoba's products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to pubs-permissions@ieee.org. By choosing to view this document, you agree to all provisions of the copyright laws protecting it.en
dc.rightsrestricted accessen_US
dc.statusPeer revieweden
dc.subjectcombinatorial optimizationen
dc.subjectcooperative searchen
dc.subjectgraph partitioningen
dc.subjectmultilevel algorithmsen
dc.subjectVLSI physical designen
dc.subjectALGORITHMSen
dc.titleMultilevel cooperative search for the circuit/hypergraph partitioning problemen
Files
Collections
University of Manitoba Scholarship (login required)