|
Published Articles >> Table of Contents >> Abstract
Asia and South Pacific Design Automation Conference 2000 (ASP-DAC'00)
p. 429
Edge Separability Based Circuit Clustering with Application to Circuit Partitioning
Jason Cong, UCLA Department of Computer Science, Los Angeles, CA
Sung Kyu Lim, UCLA Department of Computer Science, Los Angeles, CA
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ASPDAC.2000.835138
Send link to a friend
| Abstract |
|
In this paper, we introduce a new efficient
O(n log n) graph search based bottom-up clustering
algorithm named ESC (Edge Separability based
Clustering). Unlike existing bottom-up algorithms
that are based on local connectivity information of the
netlist, ESC exploits more global connectivity information
"edge separability" to guide clustering process
while carefully monitoring cluster area balance. Computing
the edge separability for a given edge e = (x,y)
in an edge weighted undirected graph G(V, E, s, w) is
equivalent to finding the x-y mincut. Then, we show
that a simple and efficient algorithm CAPFOREST
can be used to provide a good estimation of edge
separability for all edges in G without using any network
flow computation. Related experiments based on
large scale ISPD98 benchmark circuits confirm that
exploiting edge separability yields better quality partitioning
solution compared to various bottom-up clustering
algorithms proposed in the literature including
Absorption, Density, Rent Parameter,
Ratio Cut, Closeness, and Connectivity method.
In addition, our ESC based multiway partitioning
algorithm LR/ESC-PM provides comparable
results to state-of-the-art hMetis and hMetis-Kway.
|
 Additional Information
|
Citation:
Jason Cong, Sung Kyu Lim,
"Edge Separability Based Circuit Clustering with Application to Circuit Partitioning,"
asp-dac,
p. 429,
Asia and South Pacific Design Automation Conference 2000 (ASP-DAC'00),
2000
|
|
