Technology mapping algorithms for domino logic

ABSTRACT

We present an efficient algorithm for technology mapping of domino logic to a parameterized library. The algorithm is optimal for mapping trees consisting of two-input AND/OR nodes, and has a computation time that is polynomial in terms of constraint size. The mapping method is then extended to DAG covering that permits the implicit duplication of logic nodes. Our synthesis procedure maps the complementary logic cones independently when AND/OR logic is to be implemented, and together using dual-monotonic gates in the case of XOR/XNOR logic. The mapping procedure solves the output phase assignment problem as a preprocessing step. Based on a key observation that the output phase assignment could reduce the implementation cost due to the possible large cost difference between two polarities, a 0--1 integer linear programming formulation was designed to minimize the implementation cost. Our experimental results show the effectiveness of the proposed techniques.

REFERENCES

• 1: Luca Benini , Giovanni De Micheli, A survey of Boolean matching techniques for library binding, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.3, p.193-226, July 1997 [doi>10.1145/264995.264996]
• 2: Berkelaar, M. R. C. M. 1998. LP SOLVE 2.3 Users' Manual.
• 3: Berkelaar, M. R. C. M. and Jess, J. A. G. 1988. Technology mapping for standard-cell generators. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, 470--473.
• 4: Brayton, R. K., Chen, C. L., McMullen, C. T., Otten, R. H. J. M., and Yamour, Y. J. 1984. Automated implementation of switching functions as dynamic CMOS circuits. In Proceedings of the IEEE Custom Integrated Circuits Conference, 346--350.
• 5: Burns, J. L. and Feldman, J. A. 1998. C5M---A control-logic layout synthesis system for high-performance microprocessors. IEEE Trans. Comput. Aided Des. 17, 1 (Jan.), 14--23.
• 6: Campenhout, D. V., Mudge, T., and Sakallah, K. 1996. Modeling domino logic for static timing analysis. Tech. Rep. CSE-TR-295-96, The University of Michigan.
• 7: Chaudhary, K. and Pedram, M. 1995. Computing the area versus delay trade-off curves in technology mapping. IEEE Trans. Comput. Aided Des. 14, 12 (Dec.), 1480--1489.
• 8: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 9: Detjens, E., Gannot, G., Rudell, R., Sangiovanni-Vincentelli, A., and Wang, A. 1987. Technology mapping in MIS. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, 116--119.
• 10: Fishburn, J. P. and Dunlop, A. E. 1985. TILOS: A posynomial programming approach to transistor sizing. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, 326--328.
• 11: Harris, D. and Horowitz, M. A. 1997. Skew-tolerant domino circuits. IEEE J. Solid-State Circ. 32, 11 (Nov.), 1702--1711.
• 12: Christoph M. Hoffmann , Michael J. O'Donnell, Pattern Matching in Trees, Journal of the ACM (JACM), v.29 n.1, p.68-95, Jan. 1982 [doi>10.1145/322290.322295]
• 13: Dirk-Jan Jongeneel , Yosinori Watanbe , Robert K. Brayton , Ralph Otten, Area and search space control for technology mapping, Proceedings of the 37th conference on Design automation, p.86-91, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337321]
• 14: 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]
• 15: Ki-Wook Kim , C. L. Liu , Sung-Mo Kang, Implication graph based domino logic synthesis, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.111-114, November 07-11, 1999, San Jose, California, United States
• 16: 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]
• 17: Lehman, E., Watanabe, Y., Grodstein, J., and Harkness, H. 1997. Logic decomposition during technology mapping. J. ACM 16, 8 (Aug.), 813--834.
• 18: Yusuke Matsunaga, On accelerating pattern matching for technology mapping, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.118-122, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288587]
• 19: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 20: Ortiz, R. R. and Lefebvre, M. C. 1993. Technology mapping for NORA dynamic logic circuits. In Proceedings of the European Design Automation Conference, 310--314.
• 21: Priyadarshan Patra , Unni Narayanan, Automated phase assignment for the synthesis of low power domino circuits, Proceedings of the 36th ACM/IEEE conference on Design automation, p.379-384, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309964]
• 22: Prasad, M. R., Kirkpatrick, D., and Brayton, R. K. 1997. Domino logic synthesis and technology mapping. In Workshop Notes, International Workshop on Logic Synthesis.
• 23: Design Issues in Mixed Static-Domino Circuit Implementations, Proceedings of the International Conference on Computer Design, p.270, October 05-05, 1998
• 24: Ruchir Puri , Andrew Bjorksten , Thomas E. Rosser, Logic optimization by output phase assignment in dynamic logic synthesis, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.2-7, November 10-14, 1996, San Jose, California, United States
• 25: Sachin S. Sapatnekar , Sung-Mo Kang, Design Automation for Timing-Driven Layout Synthesis, Kluwer Academic Publishers, Norwell, MA, 1992
• 26: Tyler Thorp , Gin Yee , Carl Sechen, Domino logic synthesis using complex static gates, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.242-247, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288620]
• 27: 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
• 28: Venkat, K., Chen, L., Lin, I., Mistry, P., and Madhani, P. 1996. Timing verification of dynamic circuits. IEEE J. Solid-State Circ. 31, 3 (Mar.), 452--455.
• 29: Wang, J., Wang, Z. D., Jullien, G. A., and Miller, W. C. 1994. Area-time analysis of carry lookahead adders using enhanced multiple output domino logic. In Proceedings of the IEEE International Symposium on Circuits and Systems, 59--62.
• 30: Wang, Z., Jullien, G. A., Miller, W. C., Wang, J., and Bizzan, S. S. 1997. Fast adders using enhanced multiple-output domino logic. IEEE J. Solid-State Circ. 32, 2 (Feb.), 206--213.
• 31: Williams, T. 1996. Dynamic logic: Clocked and asynchronous. In Tutorial Notes at the International Solid State Circuits Conference.
• 32: Yee, G. and Sechen, C. 1997. Dynamic logic synthesis. In Proceedings of the IEEE Custom Integrated Circuits Conference, 345--348.
• 33: Min Zhao , Sachin S. Sapatnekar, Technology mapping for domino logic, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.248-251, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288621]
• 34: Zhao, M. and Sapatnekar, S. S. 2000. Timing-driven partitioning and timing optimization of mixed static-domino implementations. J. ACM 19, 11 (Nov.), 1322--1336.

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
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration); Standard cells**; Advanced technologies

General Terms:
Algorithms, Design, Theory

Keywords:
Domino logic, XOR/XNOR logic, dual-monotonic gates, parameterized library, phase assignment, synthesis, technology mapping