Algorithms for MIS vector generation and pruning

ABSTRACT

Ignoring the effect of simultaneous switching for logic gates causes silicon failures for high performance microprocessor designs. The main reason to omit this effect is the run time penalty and potential over-conservatism. Run times are directly proportional to the vector sizes. Efficient algorithms are presented that prune the multiple input switching (MIS) vector set to a worst-case covering using a boolean logic abstraction of the gate. This non-physical representation reduces the vector size to approximately n vectors for an n-input gate. This is effectively the same vector set size as the optimal single input switching vector set. There are no errors for 88% the simulations using a Monty-Carlo coverage on a 90nm static library, and the magnitude of the errors are less than 5% on average.

REFERENCES

• 1: V. Chandramouli , Karem A. Sakallah, Modeling the effects of temporal proximity of input transitions on gate propagation delay and transition time, Proceedings of the 33rd annual conference on Design automation, p.617-622, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240635]
• 2: Liang-Chi Chen , Sandeep K. Gupta , Melvin A. Breuer, A new gate delay model for simultaneous switching and its applications, Proceedings of the 38th conference on Design automation, p.289-294, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378488]
• 3: Y.-H. Jun, K. Jun, and S.-B. Park. An Accurate and Efficient Delay Time Modeling for MOS Logic Circuits Using Polynomial Approximation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 8(9):1027--1032, Sept. 1989.
• 4: Larry McMurchie , Carl Sechen, WTA: waveform-based timing analysis for deep submicron circuits, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.625-631, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774665]
• 5: C. E. Molnar, I. W. Jones, W. S. Coates, J. K. Lexau, S. M. Fairbanks, and I. E. Sutherland. Two FIFO Ring Performance Experiments. Proceedings of the IEEE, 87(2):297--307, February 1999.
• 6: K. T. Tang and E. G. Friedman. Delay Uncertainty Due To On-Chip Simultaneous Switching Noise in High Performance CMOS Integrated circuits. In IEEE Workshop on Signal Processing Systems, pages 633--642. IEEE, Oct. 2000.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Switching theory

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Logic arrays
      B.6.3 Design Aids
          Subjects: Simulation; Optimization
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Design, Performance