Logic synthesis for large pass transistor circuits

ABSTRACT

Pass transistor logic (PTL) can be a promising alternative to static CMOS for deep sub-micron design. In this work, we motivate the need for CAD algorithms for PTL circuit design and propose decomposed BDDs as a suitable logic level representation for synthesis of PTL networks. Decomposed BDDs can represent large, arbitrary functions as a multi-stage circuit and can exploit the natural, efficient mapping of a BDD to PTL. A comprehensive synthesis flow based on decomposed BDDs is outlined for PTL design. We show that the proposed approach allows us to make logic-level optimizations similar to the traditional multi- level network based synthesis flow for static CMOS, and also makes possible optimizations with a direct impact on area, delay and power of the final circuit implementation which do not have any equivalent in the traditional approach. We also present a set of heuristical algorithms to synthesize PTL circuits optimized for area, delay and power which are key to the proposed synthesis flow. Experimental results on ISCAS benchmark circuits show that our technique yields PTL circuits with substantial improvements over static CMOS designs. In addition, to the best of our knowledge this is the first time PTL circuits have been synthesized for the entire ISCAS benchmark set.

REFERENCES

• 1: S. Akers, "Binary decision diagrams," IEEE Trans. on Computers, vol. C-27, no. 6, June 1978.
• 2: Pranav Ashar , Abhijit Ghosh , Srinivas Devadas, Boolean Satisfiability and Equivalence Checking Using General Binary Decision Diagrams, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.259-264, October 14-16, 1991
• 3: W. A1-Assadi, A.E Jayasumana, and Y.K. Malaiya, "Pass-transistor logic design," Int'l J. Electronics, vol. 70, no. 4, 1991.
• 4: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 5: A. E Chandrakasan, S. Sheng, and R.W. Brodersen, "Low Power CMOS Digital Design," IEEE JSSC, vol. SC-20, 1985.
• 6: R. Hossain, M. Zheng, and A. Albicki, "Reducing power dissipation in CMOS circuits by signal probability based transistor reordering," IEEE Trans. CAD, vol. 15, no. 3, March 1996.
• 7: A. Jaekel , G. A. Jullien , S. Bandyopadhyay, Multilevel Factorization Technique for Pass Transistor Logic, Proceedings of the 9th International Conference on VLSI Design: VLSI in Mobile Communication, p.339, January 03-06, 1996
• 8: Jawahar Jain , Amit Narayan , C. Coelho , Sunil P. Khatri , Alberto L. Sangiovanni-Vincentelli , Robert K. Brayton , Masahiro Fujita, Decomposition Techniques for Efficient ROBDD Construction, Proceedings of the First International Conference on Formal Methods in Computer-Aided Design, p.419-434, November 06-08, 1996
• 9: Patrick C. McGeer , Kenneth L. McMillan , Alexander Saldanha , Alberto L. Sangiovanni-Vincentelli , Patrick Scaglia, Fast discrete function evaluation using decision diagrams, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.402-407, November 05-09, 1995, San Jose, California, United States
• 10: J.L. Neves, and A. Albicki, "A pass transistor regular structure for implementing multi-level combinational circuits," 7th Int'l ASIC Conf. and Exhibit, 1994.
• 11: Shipra Panda , Fabio Somenzi, Who are the variables in your neighborhood, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.74-77, November 05-09, 1995, San Jose, California, United States
• 12: Jan M. Rabaey, Digital integrated circuits: a design perspective, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 13: D. Radhakrishnan, S.R. Whitaker, and G.K. Maki, "Formal design procedures for pass transistor switching circuits," IEEE JSSC, vol. SC-20, no. 2, April 1985.
• 14: Richard Rudell, Dynamic variable ordering for ordered binary decision diagrams, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.42-47, November 07-11, 1993, Santa Clara, California, United States
• 15: Takayasu Sakurai , Bill Lin , A. R Newton, Multiple-Output Shared Transistor Logic (MOSTL), University of California at Berkeley, Berkeley, CA, 1990
• 16: F. Salice, "Automatic synthesis of logic functions using transmission gates," J. Microelectronic Systems Integration, vol. 3, no. 1, 1995.
• 17: Y. Sasaki, K. Yano, S. Yamashita, H. Chikata, K. Rikino, K. Uchiyama, and K. Seki, "Multi-level pass-transistor logic for lowpower ULSIs," Int'l Symp. on Low Power Electronics, Oct. 1995.
• 18: Hamid Savoj, Don't cares in multi-level network optimization, University of California at Berkeley, Berkeley, CA, 1992
• 19: M. Shamanna, K. Cameron, S.R. Whitaker, "Multiple-input, multiple-output pass transistor logic," Int'l J. Elect., vol.79, no.l, 1995.
• 20: Thomas R. Shiple , Ramin Hojati , Alberto L. Sangiovanni-Vincentelli , Robert K. Brayton, Heuristic minimization of BDDs using don't cares, Proceedings of the 31st annual conference on Design automation, p.225-231, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196360]
• 21: K. Yano, T. Yamanaka, T. Nishida, M. Saito, K. Shimohigashi, and A. Shimizu, "A 3.8-ns CMOS 16x 16-b multiplier using complementary pass-transistor logic," IEEE JSSC, vol. 25, no. 2, April 1990.
• 22: K. Yano, Y. Sasaki, K. Rikino, and K. Seki, "Top-down pass-transistor logic design," IEEE JSSC, vol. 31, no. 6, June 1996.

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: Memory technologies

  J. Computer Applications

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
Pass transistor logic, logic synthesis, BDD