|
Abstract : |
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 [14] 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 [1] benchmark circuits confirm that exploiting edge separability yields better quality partitioning solution compared to various bottom-up clustering algorithms proposed in the literature including, |
