Crosstalk minimization in logic synthesis for PLAs

ABSTRACT

We propose a maximum crosstalk effect minimization algorithm that takes logic synthesis into consideration for PLA structures. To minimize the crosstalk effect, a technique for permuting wire is used which contains the following steps. First, product terms are partitioned into long and short sets, and then the product terms in the long and short sets are interleaved. After that, we take advantage of the crosstalk immunity of product terms in the long set to further reduce the maximum coupling capacitance of the PLA. Finally, synthesis techniques such as local and global transformations are taken into consideration to search for a better result. The experiments demonstrate that our algorithm can effectively minimize the maximum coupling capacitance of a circuit by 51% as compared with the original area-minimized PLA without crosstalk effect minimization.

REFERENCES

• 1: Blair, G. M. 1992. PLA design for single-clock CMOS. IEEE J. Solid-State Circ. 27, 1211--1213.
• 2: Cadence. 1999. Virtuoso---Layout Editor. http://www.cadence.com/.
• 3: Dhong, Y. B. and Tsang, C. P. 1992. High speed CMOS POS PLA using predischarged OR array and charge sharing AND array. IEEE Trans. Circ. Syst. II: Analog and Digital Signal Processing 39, 557--564.
• 4: Chunjie Duan , Sunil P. Khatri, Exploiting Crosstalk to Speed up On-Chip Buses, Proceedings of the conference on Design, automation and test in Europe, p.20778, February 16-20, 2004
• 5: Harris, D. and Grutkowski, T. 2004. Advanced domino circuit design. In Tutorial Note of the Design Automation and Test in Europe Conference. ACM Press, Paris, France.
• 6: Jiang, H. R., Chang, Y. W., and Jou, J. Y. 2000. Crosstalk-Driven interconnect optimization by simultaneous gate and wire sizing. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 19, 999--1010.
• 7: Sunil P. Khatri , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Cross-talk immune VLSI design using a network of PLAs embedded in a regular layout fabric, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 8: Khatri, S. P., Brayton, R. K., and Sangiovanni-Vincentelli, A. 2001. Cross-Talk Noise Immune VLSI Design Using Regular Layout Fabrics. Springer, New York.
• 9: Sunil P. Khatri , Amit Mehrotra , Robert K. Brayton , Ralf H. J. M. Otten , Alberto Sangiovanni-Vincentelli, A novel VLSI layout fabric for deep sub-micron applications, Proceedings of the 36th ACM/IEEE conference on Design automation, p.491-496, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309985]
• 10: Ki-Wook Kim , Unni Narayanan , Sung-Mo Kang, Domino logic synthesis minimizing crosstalk, Proceedings of the 37th conference on Design automation, p.280-285, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337419]
• 11: Lee, S. H., Kim, D. H., Kim, K. R., and Lee, J. D. 2002. A practical SPICE model based on the physics and characteristics of realistic single-electron transistors. IEEE Trans. Nanotechnol. 1, 226--232.
• 12: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 13: Fan Mo , Robert K. Brayton, River PLAs: a regular circuit structure, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513970]
• 14: D. LaPotin , H. Ngo , I. Vo, Design Methodology for a 1.0 GHz Microprocessor, Proceedings of the International Conference on Computer Design, p.17, October 05-05, 1998
• 15: Sakurai, T. and Tamaru, K. 1983. Simple formulas for two and three dimensional capacitance. IEEE Trans. Electron Devices ED-30, 183--185.
• 16: Sellers, F. F., Hsiao, M. Y., and Bearnson, L. W. 1968. Analyzing errors with the Boolean difference. IEEE Trans. Comput. C-17, 7 (July), 676--683.
• 17: Sentovich, E. M., Singh, K. J., Lavagno, L., Moon, C., Murgai, R., Saldanha, A., Savoj, H., Stephan, P. R., Brayton, R. K., and Sangiovanni-Vincentelli, A. 1992. SIS: A system for sequential circuit synthesis. Tech. Rep., Univ. of California Berkeley. May. Memorandum No. UCB/ERL M92/41.
• 18: Kenneth L. Shepard , Vinod Narayanan, Noise in deep submicron digital design, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.524-531, November 10-14, 1996, San Jose, California, United States
• 19: Synopsis. 2001. Star-Hspice. http://www.synopsis.com/.
• 20: Tien, T. K. 2003. Crosstalk alleviation, power minimization and timing optimization for dynamic PLAs. Ph.D. thesis, National Chung Cheng University, Chia-Yi, Taiwan, ROC.
• 21: Tien, T. K., Chang, S. C., and Tsai, T. K. 2002. Crosstalk alleviation for dynamic PLAs. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 21, 1416--1424.
• 22: Hsiao-Ping Tseng , Louis Scheffer , Carl Sechen, Timing and crosstalk driven area routing, Proceedings of the 35th annual conference on Design automation, p.378-381, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277148]
• 23: UCB Device Group. 2002. Berkeley Predictive Technology Model. http://www-device.eecs.berkeley.edu/~ptm/.
• 24: Vittal, A. and Marek-Sadowska, M. 1997. Crosstalk reduction for VLSI. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 16, 290--298.
• 25: Wang, C. C., Wu, C. F., Hwang, R. T., and Kao, C. H. 1999. A low-power and high-speed dynamic PLA circuit configuration for single-clock CMOS. IEEE Trans. Circ. Syst. I: Fundamental Theory and Applications 46, 857--861.
• 26: Wang, J. S., Chang, C. R., and Yeh, C. 2001. Analysis and design of high-speed and low-power CMOS PLAs. IEEE J. Solid-State Circ. 36, 1250--1262.
• 27: Zhao, H. and Wong, D. F. 1999. Global routing with crosstalk constraints. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 18, 1683--1688.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Combinational logic
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

General Terms:
Algorithms, Performance

Keywords:
Crosstalk, PLA, domino logic, synthesis