Record Details

A new partitioning strategy based on supermodular functions

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title A new partitioning strategy based on supermodular functions
 
Creator PATKAR, SACHIN
BATTERYWALA, SH
CHANDRAMOULI, M
NARAYANAN, H
 
Subject vlsi
circuit layout cad
circuit optimisation
graph theory
integrated circuit layout
logic partitioning
 
Description r-way partitioning is an NP-hard problem. In this paper we present a few heuristics for clustering, which are motivated by the theory of sub/supermodular functions. The implementation based on this heuristic justifies some already published results about the approximability of the optimal solutions to this NP-hard problem using the ideas from the theory of sub/supermodular-functions. We also suggest a hypergraph model which is more natural and more suitable for modeling this problem. We give some experimental results which indicate that our methods hold promise. Our experimental results are comparable, and in some cases better than the best to date spectral partitioning methods on the standard benchmark circuits. Finally we suggest some multilevel strategies for partitioning, where in each level we employ a supermodular function based strategy which gives a suboptimal partitioning on the fused supergraph.
 
Publisher IEEE
 
Date 2008-12-10T12:47:15Z
2011-11-27T11:56:25Z
2011-12-15T09:56:30Z
2008-12-10T12:47:15Z
2011-11-27T11:56:25Z
2011-12-15T09:56:30Z
1997
 
Type Article
 
Identifier Proceedings of the Tenth International Conference on VLSI Design, Hyderabad, India, 4-7 January 1997, 32-37
0-8186-7755-4
10.1109/ICVD.1997.567957
http://hdl.handle.net/10054/281
http://dspace.library.iitb.ac.in/xmlui/handle/10054/281
 
Language en