Min-cut partitioning with functional replication for technology mapped circuits using minimum area overhead

ABSTRACT

Logic replication is known to be an effective technique to reduce the number of cut nets in partitioned circuits. A new replication model calledfunctional replicationis particularly useful for partitioning technology mapped circuits [7]. Functional replication differs from traditional replication because it considers the functional dependency of the different output signals of a logic cell on its input signals. Functional replication can lead to a higher reduction in the number of cut nets than traditional replication. In this paper, we give the first theoretical treatment of the min-cut partitioning problem with functional replication. We present a novel two-phase algorithm to compute a min-cut bipartition of a technology mapped circuit with functional replication using minimum amount of area overhead. And we show that our algorithm can be applied to improve the solution produced by any area-constrained functional replication partitioning heuristic.

REFERENCES

• 1: Partitioning93 benchmark. available at http://www.cbl.ncsu.edu/CBL Docs/partn93.html.
• 2: M. Enos, S. Hauck, and M. Sarrafzadeh. Evaluation and optimization of replication algorithms for logic bipartitioning. IEEE Transactions on CAD, 18(9):1237-1248, September 1999.
• 3: 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
• 4: J. Hwang and A. El Gamal. Min-cut replication in partitioned networks. IEEE Transactions on CAD, 14(1):96-106, January 1995.
• 5: S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, pages 671-680, May 1983.
• 6: C. Kring and A. R. Newton. A cell-replicating approach to mincut-based circuit partitioning. In Proceedings of IEEE Int'l Conf. on Computer-Aided Design, pages 2-5, 1991.
• 7: Roman Kužnar , Franc Brglez , Baldomir Zajc, Multi-way netlist partitioning into heterogeneous FPGAs and minimization of total device cost and interconnect, Proceedings of the 31st annual conference on Design automation, p.238-243, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196364]
• 8: L. T. Liu, M. T. Kuo, C. K. Cheng, and T. C. Hu. A replication cut for two-way partitioning. IEEE Transactions on CAD, 14(5):623-630, May 1995.
• 9: W. K. Mak and D. F. Wong. Minimum replication min-cut partitioning. IEEE Transactions on CAD, 16(10):1221-1227, October 1997.
• 10: Kalapi Roy-Neogi , Carl Sechen, Multiple FPGA partitioning with performance optimization, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.146-152, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201333]
• 11: Xilinx Inc. The Programmable Logic Data Book, 1996.
• 12: 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
• 13: Hannah Honghua Yang , D. F. Wong, New algorithms for min-cut replication in partitioned circuits, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.216-222, November 05-09, 1995, San Jose, California, United States

INDEX TERMS

General Terms:
Algorithms

Keywords:
circuit partitioning, logic replication, minimum cut