An improved circuit-partitioning algorithm based on min-cut equivalence relation

✍ Scribed by Xianyang Jiang; Xubang Shen; Tianxu Zhang; Huayu Liu

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 330 KB
• Volume: 36
• Category: Article
• ISSN: 0167-9260
• DOI: 10.1016/s0167-9260(03)00032-4

✦ Synopsis

Network flow is an excellent approach to finding min-cuts in network because of the celebrated maxflow/min-cut theorem. For a long time, however, it has not been a practical circuit partitioning method for its relatively high computational complexity. Algorithm FBB is the first one to apply network flow to solve two-way balanced circuit partitioning successfully. Later, its improved version DMC efficiently solved the problem of multi-way circuit partitioning. In this paper, an improved circuit-partitioning algorithm MCER is presented. MCER is based on a min-cut equivalence relation. The algorithm not only inherits to take advantage of flow theory, but also incorporates a subsets movement-based method to utilize internal equivalent topological structure of circuit. Based on the equivalence relation and subsets movement between initial min-cuts, MCER will find more min-cuts. A series of experiments demonstrate that searching space of MCER is bigger than that of former algorithms and MCER outperforms FBB or DMC in terms of the size of min-cuts. Furthermore, MCER will degrade to DMC or FBB under special conditions.