MSpace - DSpace at UofM >
Research Publications from University of Manitoba Researchers >
Research Publications (UofM Student, Faculty and Staff only access) >

Please use this identifier to cite or link to this item:

Title: Multilevel cooperative search for the circuit/hypergraph partitioning problem
Authors: Ouyang, M
Toulouse, M
Thulasiraman, K
Glover, F
Deogun, JS
Keywords: combinatorial optimization
cooperative search
graph partitioning
multilevel algorithms
VLSI physical design
Issue Date: 30-Jun-2002
Citation: 0278-0070; IEEE TRANS COMPUT AID DES INT, JUN 2002, vol. 21, no. 6, p.685 to 693.
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.
Appears in Collection(s):Research Publications (UofM Student, Faculty and Staff only access)

Files in This Item:

File Description SizeFormat
Ouyang_Multilevel_cooperative_search.pdf329.26 kBAdobe PDFView/Open
View Statistics

Items in MSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! MSpace Software Copyright © 2002-2010  Duraspace - Feedback