Citation
Jason Cong, Sung Kyu Lim. "Edge Separability based Circuit Clustering With Application to Circuit Partitioning". Asia South Pacific Design Automation Conference, 429-434, January, 2000.

Abstract
In this paper, we introduce a new efficient O(nlogn) 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 [NI92] 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 [SS93], Density [CS93, HK95], Rent Parameter [NOP87], Ratio Cut [WC92], Closeness [SK93], and Connectivity [SU82] method. In addition, our ESC based multiway partitioning algorithm LR/ESC-PM provides comparable results to state-of-the-art hMetis [KA+97] and hMetis-Kway [KK99].

Electronic downloads

• asp00a.ps · application/postscript · 506 kbytes

Citation formats

• HTML

  Jason Cong, Sung Kyu Lim. <a
  href="http://www.gigascale.org/pubs/31.html">Edge
  Separability based Circuit Clustering With Application to
  Circuit Partitioning</a>, Asia South Pacific Design
  Automation Conference, 429-434, January, 2000.

• Plain text

  Jason Cong, Sung Kyu Lim. "Edge Separability based Circuit
  Clustering With Application to Circuit Partitioning". Asia
  South Pacific Design Automation Conference, 429-434,
  January, 2000.

• BibTeX

  @inproceedings{CongLim00_EdgeSeparabilityBasedCircuitClusteringWithApplication,
      author = {Jason Cong and Sung Kyu Lim},
      title = {Edge Separability based Circuit Clustering With
                Application to Circuit Partitioning},
      booktitle = {Asia South Pacific Design Automation Conference},
      pages = {429-434},
      month = {January},
      year = {2000},
      abstract = {In this paper, we introduce a new efficient
                O(nlogn) 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 [NI92] 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 [SS93], Density [CS93, HK95], Rent
                Parameter [NOP87], Ratio Cut [WC92], Closeness
                [SK93], and Connectivity [SU82] method. In
                addition, our ESC based multiway partitioning
                algorithm LR/ESC-PM provides comparable results to
                state-of-the-art hMetis [KA+97] and hMetis-Kway
                [KK99].},
      URL = {http://www.gigascale.org/pubs/31.html}
  }
  

Posted by Sung Kyu Lim on 28 Aug 2000..

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.