• Libraries
    • Log in to:
    View Item 
    •   MSpace Home
    • University of Manitoba Researchers
    • University of Manitoba Scholarship (login required)
    • View Item
    •   MSpace Home
    • University of Manitoba Researchers
    • University of Manitoba Scholarship (login required)
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Multilevel cooperative search for the circuit/hypergraph partitioning problem

    View/Open
    Ouyang_Multilevel_cooperative_search.pdf (329.2Kb)
    Date
    2002-06-30
    Author
    Ouyang, M
    Toulouse, M
    Thulasiraman, K
    Glover, F
    Deogun, JS
    Metadata
    Show full item record
    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.
    URI
    http://hdl.handle.net/1993/2924
    DOI
    10.1109/TCAD.2002.1004312
    Collections
    • University of Manitoba Scholarship (login required) [171]

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Browse

    All of MSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Login

    Statistics

    View Usage Statistics

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV