Edge separability-based circuit clustering with application to multilevel circuit partitioning

In this paper, we propose a new efficient O(nlogn) connectivity-based bottom-up clustering algorithm called edge separability-based clustering (ESC). Unlike existing bottom-up algorithms that are based on local connectivity information of the netlist, ESC exploits more global connectivity information using edge separability to guide the clustering process, while carefully monitoring cluster area balance. Exact computation of the edge separability λ(e) for a given edge e=(x,y) in an edge-weighted undirected graph G is equivalent to finding the maximum flow between x and y. Since the currently best known time bounds for solving the maximum flow problem is O(mnlog(n²/m)), due to Goldberg and Tarjan (Goldberg and Tarjan, 1988), the computation of λ(e) for all edges in G requires O(m²nlog(n²/m)) time. However, we show that a simple and efficient algorithm CAPFOREST (Nagamochi and Ibaraki, 1992) can be used to provide a good approximation of edge separability (within 9.1% empirical error bound) for all edges in G without using any network flow computation in O(nlogn) time. Our experimental results based on large-scale benchmark circuits demonstrate the effectiveness of using edge separability in the context of multilevel partitioning framework for cutsize minimization. We observe that exploiting edge separability yields better quality partitioning solution compared to existing clustering algorithms (Sun and Sechen, 1993), (Cong and Smith, 1993), (Huang and Kahng, 1995), (Ng et al., 1987), (Wei and Cheng, 1991), (Shin and Kim, 1993), (Schuler and Ulrich, 1972), (Karypis et al., 1997), that rely on local connectivity information. In addition, our ESC-based iterative improvement based multilevel partitioning algorithm LR/ESC-PM provides comparable results to state-of-the-art hMetis package (Karypis et al., 1997), (Karypis and Kumar, 1999).