Transistor placement for noncomplementary digital VLSI cell synthesis

ABSTRACT

There is an increasing need in modern VLSI designs for circuits implemented in high-performance logic families such as Cascode Voltage Switch Logic (CVSL), Pass Transistor Logic (PTL), and domino CMOS. Circuits designed in these noncomplementary ratioed logic families can be highly irregular, with complex diffusion sharing and nontrivial routing. Traditional digital cell layout synthesis tools derived from the highly stylized "functional cell" style break down when confronted with such circuit topologies. These cells require a full-custom, two-dimensional layout style which currently requires skilled manual design. In this work we propose a methodology for the synthesis of such complex noncomplementary digital cell layouts. We describe a new algorithm which permits the concurrent optimization of transistor chain placement and the ordering of the transistors within these diffusion-sharing chains. The primary mechanism for supporting this concurrent optimization is the placement of transistor subchains, diffusion-break-free components of the full transistor chains. When a chain is reordered, transistors may move from one subchain (and therefore one placement component) to another. We will demonstrate how this permits the chain ordering to be optimized for both intra-chain and inter-chain routing. We combine our placement algorithms with third-party routing and compaction tools, and present the results of a series of experiments which compare our technique with a commercial cell synthesis tool. These experiments make use of a new set of benchmark circuits which provide a rich sample of representative examples in several noncomplementary digital logic families.

REFERENCES

• 1: Serkan Askar , Maciej Ciesielski, Analytical approach to custom datapath design, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.98-101, November 07-11, 1999, San Jose, California, United States
• 2: Bulent Basaran, Optimal diffusion sharing in digital and analog CMOS layout, Carnegie Mellon University, Pittsburgh, PA, 1998
• 3: Bernhardt, B. et al. 1995. Complementary GaAs (CGaAsTM): A high performance BiCMOS alternative. In Proceedings of the 1995 GaAs IC Symposium. 18--21.
• 4: Blair, G. 1997. Comments on "New single-clock CMOS latches and flip-flops with improved speed and power savings." IEEE J. Solid State Circ. 32, 10 (Oct.), 1611.
• 5: Burns, J. and Feldman, J. 1988. C5M---a control logic layout synthesis system for high-performance microprocessors. IEEE Trans. CAD 17, 1 (Jan.), 14--23.
• 6: Burns, J. and Nowka, K. 1998. Parallel condition-code generation for high-frequency powerPC microprocessors. In Proceedings of the 1998 Symposiums on VLSI Circuits. 115.
• 7: Chow, S., Chang, H., Lam, J., and Liao, Y. 1992. The layout synthesizer: An automatic block generation system. In Proceedings of the 1992 CICC. 11.1.1--11.1.4.
• 8: Cohn, J. 1992. Automatic device placement for analog cells in KOAN. Ph.D. dissertation, Carnegie Mellon University, Pittsburgh, PA; also, CMU Report No. CMUCAD-92-07, Carnegie Mellon University, Pittsburgh, PA.
• 9: John M. Cohn, Analog Device-Level Layout Automation, Kluwer Academic Publishers, Norwell, MA, 2000
• 10: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 11: 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
• 12: Friedman, V. and Liu, S. 1984. Dynamic logic CMOS circuits. IEEE J. Solid State Circ. 19, 2 (Apr.), 265.
• 13: Masahiro Fukui , Noriko Shinomiya , Toshiro Akino, A new layout synthesis for leaf cell design, Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), p.40-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan [doi>10.1145/224818.224907]
• 14: Avaneendra Gupta , John P. Hayes, CLIP: an optimizing layout generator for two-dimensional CMOS cells, Proceedings of the 34th annual conference on Design automation, p.452-455, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266198]
• 15: Hanawa, M., Kaneko, K., Kawashimo, T., and Maruyama, H. 1996. A 4.3ns 0.3mm CMOS 54x54b multiplier using precharged pass-transistor logic. In Proceedings of the 1996 International Solid-State Circuits Conference. 265.
• 16: Heller, L., Griffin, W., Davis J., and Thomas, N. 1984. Cascode voltage switch logic: A differential CMOS logic family. In Proceedings of the 1984 International Solid-State Circuits Conference. 17.
• 17: Hsieh, Y., Huang, C., Lin, Y., and Hsu, Y. 1991. LiB: A CMOS cell compiler. IEEE Trans. Comput.-Aided Des. 10, 8 (Aug.), 994--1005.
• 18: Klass, F. 1998. "Semi-dynamic and dynamic flip-flops with embedded logic. In Proceedings of the 1998 Symposium VLSI Ciruits. 109.
• 19: Kowaleski, J., Wolrich, G., Fischer, T., Dupcak, R., Kroesen, P., Pham, T., and Olesin, A. 1996. A dual-execution pipelined floating-point CMOS processor. In Proceedings of the 1996 International Solid-State Circuits Conference. 359.
• 20: Lefebvre, M. and Skoll, D. 1992. PicassoII: A CMOS leaf cell synthesis system. In Proceedings of the 1992 MCNC International Workshop on Layout Synthesis, vol. 2. 207--219.
• 21: Martin Lefebvre , David Marple , Carl Sechen, The future of custom cell generation in physical synthesis, Proceedings of the 34th annual conference on Design automation, p.446-451, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266196]
• 22: Lu, F. and Samueli, H. 1993. A 200-MHz CMOS pipelined multiplier-accumulator using a quasi-domino dynamic full-adder cell design. IEEE J. Solid State Circ. 28, 2 (Feb.), 125.
• 23: Makino, H., Suzuki, H., Morinaka, H., Nakase, Y., Mashiko, K., and Sumi, T. 1996. A 286 MHz 64-b floating point multiplier with enhanced CG operation. IEEE J. Solid State Circ. 31, 4 (April), 510.
• 24: Matsui, M., Hara, H., Uetani, Y., Kim, L.-S., Nagamatsu, T., Watanabi, Y., Chiba, A., Matsuda, K., and Sakurai, T. 1994. A 200 MHz 13 mm2 2-D DCT macrocell using sense-amplifying pipeline flip-flop scheme. IEEE J. Solid State Circ. 29, 12 (Dec.), 1484.
• 25: Maziasz, R. L. and Hayes, J. P. 1992. Layout Minimization of CMOS Cells. Kluwer Academic Publishers, Boston, MA.
• 26: Montanero, J., Witek, R., Anne, K., Black, A., Cooper, E., Dobberpuhl, D., Donahue, P., Eno, J., Farell, A., Hoeppner, G., Kruckemyer, D., Lee, T., Lin, P., Madden, L., Murray, D., Pearce, M., Santhanam, S., Snyder, K., Stephany, R., and Thierauf, S. 1996. A 160 MHz 32b 0.5 W CMOS RISC microprocessor. In Proceedings of the 1996 International Solid-State Circuits Conference. 215.
• 27: Hiroshi Murata , Kunihiro Fujiyoshi , Shigetoshi Nakatake , Yoji Kajitani, Rectangle-packing-based module placement, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.472-479, November 05-09, 1995, San Jose, California, United States
• 28: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 29: Poirier, C. 1989. Excellerator: Custom CMOS leaf cell layout generator. IEEE Trans. Comput.-Aided Des. 8 (July), 744--755.
• 30: Michael A. Riepe , Karem A. Sakallah, Transistor level micro-placement and routing for two-dimensional digital VLSI cell synthesis, Proceedings of the 1999 international symposium on Physical design, p.74-81, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300028]
• 31: Riepe, M. 1999. Transistor-level micro-placement and routing for two-dimensional digital VLSI cell synthesis. Ph.D dissertation, The University of Michigan, Ann Arbor, MI.
• 32: Rogenmoser, R. and Huang, Q. 1996. An 800-MHz 1-μm CMOS pipelined 8-b adder using true single-phase clocked logic-flip-flops. IEEE J. Solid State Circ. 31, 3 (Mar.), 405.
• 33: Rutenbar, R. 1989. Simulated annealing algorithms: An overview. IEEE Circ. Dev. 5, 1 (Jan.) 19--26.
• 34: Saika, S., Fukui, M., Shinomiya, N., and Akino, T. 1997. A two-dimensional transistor placement algorithm for cell synthesis and its application to standard cells. IEICE Trans. Fund., E80--A, 10 (Oct.), 1883--1891.
• 35: Sechen, C. and Sangiovanni-Vincentelli, A. 1985. The TimberWolf placement and routing package. IEEE J. Solid State Circ. SC-20, 2 (Apr.), 510--522.
• 36: Tatjana Serdar , Carl Sechen, AKORD: transistor level and mixed transistor/gate level placement tool for digital data paths, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.91-97, November 07-11, 1999, San Jose, California, United States
• 37: A. M. Shams , M. A. Bayoumi, A New Full Adder Cell for Low-Power Applications, Proceedings of the Great Lakes Symposium on VLSI '98, p.45, February 19-24, 1998
• 38: Shimazu, Y., Kengaku, T., Fujiyama, T., Teraoka, E., Ohno, T., Tokuda, T., Tomisawa, O., and Tsujimichi, S. 1989. A 50MHz 24b floating-point DSP. In Proceedings of the 1996 International Solid-State Circuits Conference. 45.
• 39: Silberman, J., Aoki, N., Boerstler, D., Burns, J., Dhong, S., Essbaum, A., Ghosal, U., Heidel, D., Hofstee, P., Lee, K., Meltzer, D., Ngo, H., Nowka, K., Posluszny, S., Takahashi, O., Vo, I., and Zoric, B. 1998. A 1.0GHz single-issue 64b PowerPC integer processor. In Proceedings of the 1998 International Solid-State Circuits Conference. p. 231.
• 40: Somasekhar, D. and Roy, K. 1996. Differential current switch logic: A low power DCVS logic family. IEEE J. Solid State Circ. 31, 7 (July), 987.
• 41: Stephany, R., Anne, K., Bell, J., Cheney, G., Eno, J., Hoeppner, G., Joe, G., Kaye, R., Lear, J., Litch, T., Meyer, J., Montanaro, J., Patton, K., Pham, T., Reis, R., Silla, M., Slaton, J., Snyder, K., and Witek, R. 1998. A 200 MHz 32b 0.5 W CMOS RISC microprocessor. In Proceedings of the 1998 International Solid-State Circuits Conference. 239.
• 42: Stetson, S. 1997. University of Michigan, Ann Arbor, MI. Private communication.
• 43: Suzuki, M., Ohkubo, N., Yamanaka, T., Shimizu, A., and Sasaki, K. 1993. A 1.5ns 32b CMOS ALU in double pass-transistor logic. In Proceedings of the 1993 International Solid-State Circuits Conference. 91.
• 44: Tani, K. et al. 1991. Two-dimensional layout synthesis for large-scale CMOS circuits. In Proceedings of the 1991 International Conference on Computer-Aided Design. 490--493.
• 45: Uehara, T. and VanCleemput, W. M. 1981. Optimal layout of CMOS functional arrays. IEEE Trans. Comput. C-30, 5 (May), 305--312.
• 46: Durgam Vahia , Maciej Ciesielski, Transistor level placement for full custom datapath cell design, Proceedings of the 1999 international symposium on Physical design, p.158-163, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300049]
• 47: Wang, Z., Jullien, G., Miller, W., Wang, J., and Bizzan, S. 1997. Fast Adders Using Enhanced Multiple-Out-put Domino Logic. IEEE J. Solid State Circ. 32, 2 (Feb.), 209.
• 48: Xia, H., Lefebvre, M., and Vinke, D. 1994. Optimization-based placement algorithm for BiCMOS leaf cell generation. IEEE J. Solid State Circ. 29, 10 (Oct.), 1227--1237.
• 49: Yano, K., Sasaki, Y., Rikino, K., and Seki, K. 1996. Top-down pass-transistor logic design. IEEE J. Solid State Circ. 31, 6 (June), 797.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout; Placement and routing

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
Cell Synthesis, Euler graphs, benchmark circuits, digital circuits, noncomplementary circuits, sequence pair optimization, transistor chaining, transistor placement