New algorithms for min-cut replication in partitioned circuits

ABSTRACT

Abstract: Hwang and El Gamal (1992, 1995) formulated the min-cut replication problem, which is to determine min-cut replication sets for the components of a k-way partition such that the cut size of the partition is minimized after the replication. They gave an optimal algorithm for finding min-cut replication sets for a k-way partitioned digraph. However, their optimal min-cut replication algorithm does not guarantee min-cut replication sets of minimum sizes. Furthermore, their algorithm is not optimal for hypergraphs. In this paper, we optimally solve the min-area min-cut replication problem on digraphs, which is to find min-cut replication sets with the minimum sizes. More importantly, we give an optimal solution to the hypergraph min-area min-cut replication problem using a much smaller flow network model. We implemented our algorithms in a package called Hyper-MAMC, and interfaced Hyper-MAMC to the TAPIR package. On average, Hyper-MAMC produces 57.3% fewer cut nets and runs much faster than MO-Rep in the TAPIR package, on the same initial partitions of a set of MCNC Partition93 benchmark circuits.

REFERENCES

• CHK92: J. Cong , L. Hagen , A. Kahng, Net partitions yield better module partitions, Proceedings of the 29th ACM/IEEE conference on Design automation, p.47-52, June 08-12, 1992, Anaheim, California, United States
• FF62: J.R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.
• FM82: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• HE92: James Hwang , Abbas El Gamal, Optimal replication for min-cut partitioning, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.432-435, November 1992, Santa Clara, California, United States
• HE95: J. Hwang and A. E1 Gamal. Min-Cut Replication in Partitioned Networks. IEEE Trans. on CAD, 14(1):96-106, Jan. 1995.
• HK91: L. Hagen and A. B. Kahng. Fast Spectral Methods for Ratio Cut Partitioning and Clustering. In Proc. of the IEEE Int'l Conf. on Computer- Aided Design, pages 10-13, Nov. 1991.
• KGV83: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by Simulated Annealing. Science, pages 671-680, May 1983.
• KL70: B. Kernighan and S. Lin. An Efficient Heuristic Procedure for Partitioning of Electrical Circuits. Bell System Technical Journal, pages 291-307, Feb. 1970.
• KN91: C. Kring and A. R. Newton. A Cell-Replicating Approach to Mincut-Based Circuit Partitioning. In Proc. of the IEEE Int'l Conf. on Computer- Aided Design, pages 2-5, Nov. 1991.
• LKCH95: L.-T. Liu, M.-T. Kuo, C.-K. Cheng, and T. C. Hu. A Replication Cut for Two-Way Partitioning. IEEE Trans. on CAD, 14(5):623-630, May 1995.
• MBSV91: R. Murgai, R. K. Brayton, and A. Sangiovanni- Vincentelli. On Clustering for Minimum Delay/Area. In Proc. of the IEEE Int'l Conf. on Computer-Aided Design, pages 6-9, 1991.
• PL88: B. Preas and M. Lorenzetti. Physical Design Automation of VLSI Systems. Benjamin/Cummings, 1988.
• RW93: Rajmohan Rajaraman , D. F. Wong, Optimal clustering for delay minimization, Proceedings of the 30th international conference on Design automation, p.309-314, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164907]
• WC89: Y.C. Wei and C. K. Cheng. Towards Efficient Hierarchical Designs by Ratio Cut Partitioning. In Proc. of the IEEE Int'l Conf. on Computer- Aided Design, pages 298-301, Nov. 1989.
• YW94: Honghua Yang , D. F. Wong, Efficient network flow based min-cut balanced partitioning, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.50-55, November 06-10, 1994, San Jose, California, United States

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Measurement, Performance, Theory

Keywords:
Hyper-MAMC, VLSI, VLSI circuit partitioning, VLSI layout, circuit layout, circuit layout CAD, digraphs, hypergraphs, k-way partition, k-way partitioned digraph, min-cut replication, optimal algorithm, partitioned circuits