Performance-driven technology mapping with MSG partition and selective gate duplication

ABSTRACT

Traditionally, technology mapping is done by first partitioning a circuit into a forest of trees. Each individual tree is then mapped using dynamic programming. The links among the mappings of different trees are provided via propagating the essential mapping information along multiple fanout branches. While this approach may achieve optimality within each tree, the overall result is compromised from the very first treatment of fanouts. In this article, we propose a new scheme that greatly improves technology mapping. Instead of a forest of trees, we partition the circuit into a set of maximal super-gates (MSGs). These are used to transform the original circuit into trees. We then apply the dynamic programming technique to the trees and allow duplication of gates in the mapping of each individual MSG. Experimental results on ISCAS'85 benchmarks show that our approach delivers an average of 20.6% reduction in delay with only a 9.5% increase on area.

REFERENCES

• 1: Ali, Samia A. 1992. A partitioning technique of general combinational circuit into a tree type circuit. In Proceedings of the 24th Southeastern Symposium and 3rd Annual Symposium on Communications, Signal Processing Expert Systems and ASIC VLSI Design. 116--119.
• 2: Bhattacharya, B. B. and Seth, S. C. 1987. On the reconvergent structure of combinational circuits with applications to compact testing. In Proceedings of the Fault-Tolerant Computing Symposium. 264--269.
• 3: B. B. Bhattacharya , S. C. Seth, Design of Parity Testable Combinational Circuits, IEEE Transactions on Computers, v.38 n.11, p.1580-1584, November 1989 [doi>10.1109/12.42129]
• 4: U. K. Bhattacharyya , I. Sen Gupta , S. Shyama Nath , P. Dutta, PLA based synthesis and testing of hazard free logic, Proceedings of the 8th International Conference on VLSI Design, p.121, January 04-07, 1995
• 5: Brasen, D. R. and Saucier, G. 1998. Using cone structures for circuit partitioning into FPGA packages. IEEE Trans. Comput.-Aided Des. Integrated Circ. Syst. 17, 7, 592--600.
• 6: Sreejit Chakravarty , H. B. Hunt, On Computing Signal Probability and Detection Probability of Stuck-At Faults, IEEE Transactions on Computers, v.39 n.11, p.1369-1377, November 1990 [doi>10.1109/12.61046]
• 7: K. Chaudhary , M. Pedram, A near optimal algorithm for technology mapping minimizing area under delay constraints, Proceedings of the 29th ACM/IEEE conference on Design automation, p.492-498, June 08-12, 1992, Anaheim, California, United States
• 8: Chaudhary, K. and Pedram, M. 1995. Computing the area versus delay trade-off curves in technology mapping. IEEE Trans. Comput.-Aided Des. Integrated Circ. Syst. 14, 12, 1480--1489.
• 9: Cheng, D. I., Marek-Sadowska, M., and Cheng, K. T. 1995. Speeding up power estimation by topological analysis. In Proceedings of the IEEE International Conference on Custom Integrated Circuits. 623--626.
• 10: Jason Cong , Yuzheng Ding, On area/depth trade-off in LUT-based FPGA technology mapping, Proceedings of the 30th international conference on Design automation, p.213-218, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164675]
• 11: Jason Cong , Zheng Li , Rajive Bagrodia, Acyclic multi-way partitioning of Boolean networks, Proceedings of the 31st annual conference on Design automation, p.670-675, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196609]
• 12: Jason Cong , Dongmin Xu, Exploiting signal flow and logic dependency in standard cell placement, Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), p.63-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan [doi>10.1145/224818.224931]
• 13: Jason Cong , Songjie Xu, Technology mapping for FPGAs with embedded memory blocks, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.179-188, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275138]
• 14: Gary D. Hachtel , Fabio Somenzi, Logic Synthesis and Verification Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000
• 15: Bo Hu , Yosinori Watanabe , Alex Kondratyev , Malgorzata Marek-Sadowska, Gain-based technology mapping for discrete-size cell libraries, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775979]
• 16: K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
• 17: Yuji Kukimoto , Robert K. Brayton , Prashant Sawkar, Delay-optimal technology mapping by DAG covering, Proceedings of the 35th annual conference on Design automation, p.348-351, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277142]
• 18: Marhoefer, M. and McCluskey, E. J. 1988. An experimental study of supergates. CRC Tech. Rep. No. 88-6 Stanford University.
• 19: Min, H. B. and Park, E. S. 1996. Graph-Theoretic algorithm for finding maximal supergates in combinational logic circuits. IEE Proc. Circ. Devices Syst. 143, 6, 313--318.
• 20: Pan, Y., Li, Z., and Min, Y. 1991. Structural analysis of large digital circuits. In Proceedings of the Pacific Rim International Symposium on Fault Tolerant Systems. 121--124.
• 21: Richard L. Rudell , Alberto Sangiovanni-Vincentelli, Logic synthesis for vlsi design, 1989
• 22: Sentovich, E. M., Singh, K. J., Lavagno, L., Moon, C., Murgai, R., Saldanha, A., Savoj, H., Stephan, P. R., Brayton, R. K., and Sangiovanni-Vicentelli, A. 1992. SIS: A system for sequential circuit synthesis. Electronic Research Lab., Dept. of Electrical Engineering, Computer Science, University of California at Berkeley, Memo. UCB/ERL M92/41.
• 23: Seth, S. C., Pan, L., and Agrawal, V. D. 1985. PREDICT---Probabilistic estimation of digital circuit reliability. In Proceedings of the Fault-Tolerant Computing Symposium. 220--225.
• 24: Seth, S. C., Bhattacharya, B. B., and Agrawal, V. D. 1986. An exact analysis for efficient computation of random pattern testability in combinational circuits. In Proceedings of the Fault-Tolerant Computing Symposium.
• 25: Leon Stok , Mahesh A. Iyer , Andrew J. Sullivan, Wavefront technology mapping, Proceedings of the conference on Design, automation and test in Europe, p.108-es, January 1999, Munich, Germany [doi>10.1145/307418.307559]
• 26: Hervé J. Touati , Cho W. Moon , Robert K. Brayton , Albert Wang, Performance-oriented technology mapping, Proceedings of the sixth MIT conference on Advanced research in VLSI, p.79-97, March 1990, Boston, Massachusetts, United States
• 27: V. A. Vardanian, Exact probabilistic analysis of error detection for parity checkers, Proceedings of the 15th IEEE VLSI Test Symposium (VTS'97), p.222, April 27-May 01, 1997
• 28: Min Zhao , Sachin S. Sapatnekar, A new structural pattern matching algorithm for technology mapping, Proceedings of the 38th conference on Design automation, p.371-376, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378526]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Technology mapping, covering, directed acyclic graph, dynamic programming, gate duplication, logic synthesis, matching, maximal super-gate, partition, super-gate