Record Details

An efficient practical heuristic for good ratio-cut partitioning

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title An efficient practical heuristic for good ratio-cut partitioning
 
Creator PATKAR, SACHIN
NARAYANAN, H
 
Subject circuit optimisation
graph theory
logic cad
logic partitioning
 
Description We present an efficient heuristic for finding good bipartitions of the vertex set of a graph in the sense of the well-known measure of ratioCut (essentially the ratio between weight of cut edges and the product of weights of the nodesets of the bipartition). The widely accepted ratioCut bipartitioning algorithm of Wei and Cheng is similar in spirit to the Fiduccia-Mattheyeses algorithm (F-M algorithm). Our approach makes use of F-M algorithm as the first phase that takes in as an input, random bipartitions. In the later phase of our algorithm we make use of a new coarsening strategy and follow it up with a submodular function optimization algorithm on the coarsened graph. We also present the comparison of results of this approach applied to benchmark circuits with the well-established algorithms such as the Wei-Cheng algorithm for ratioCut bipartitioning and pmetis of Metis package. The comparative study not only shows that this new approach indeed produces good quality ratioCut bipartitions, but also the fact that this approach has the potential of finding a large number of such good partitions in comparison with other approaches. The key subroutine in our heuristic strategies is based on the recent finding about the role of submodular functions in designing new heuristics and approximate algorithms to some NP-hard problems.
 
Publisher IEEE
 
Date 2008-12-10T12:47:34Z
2011-11-27T12:06:14Z
2011-12-15T09:56:31Z
2008-12-10T12:47:34Z
2011-11-27T12:06:14Z
2011-12-15T09:56:31Z
2003
 
Type Article
 
Identifier Proceedings of the 16th International Conference on VLSI Design, New Delhi, India, 4-8 January 2003, 64-69
0-7695-1868-0
10.1109/ICVD.2003.1183116
http://hdl.handle.net/10054/282
http://dspace.library.iitb.ac.in/xmlui/handle/10054/282
 
Language en