A framework for scheduling multi-rate circuit simulation

ABSTRACT

This paper presents a theoretical framework for scheduling of subcircuit simulation in a multirate simulation environment. We show that event-driven simulation, selective-trace, and latency are subsumed by this framework. We assume that the circuit to be simulated is partitioned into subcircuits and that the dependency relations can be expressed as a directed acyclic graph. Each subcircuit predicts its own stepsize, and we assume that a subcircuit can be simulated over some step only when all its inputs are known over that step. It is possible to show that the problem of scheduling the subcircuits subject to these constraints to minimize the amount of memory used to store intermediate voltages is NP-Complete [NV88]. We therefore propose a greedy algorithm that at each step in the schedule, simulates the subcircuit that requires the minimal amount of memory. The algorithm has been implemented in the circuit simulator XPSim, and the performance improvement due to the scheduling technique is demonstrated on a number of circuits. Extensions of the approach to cyclic dependency graphs using the method of waveform relaxation are discussed in a section on future work.

REFERENCES

• AHU74: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• BFNB88: R.L. Bauer, J.Y. Fang, A. Ng, and R.K. Brayton. XPSIM: A MOS VLSI simulator. Proceedings of ICCAD 1988, pages 66-69, November 1988.
• CC88: R. Chadha and C.F. Chen. Extension of a transistor level digital timing simulator to include first ortder analog behavior. Proceedings of 1988 Int. Conference on Computer Design, pages 116-119, 1988.
• CGK75: B.R. Chalwa, H.K. Gummel, and P. Kozak. MOTIS- an MOS timing simulator. IEEE Transacations on Circuits and Systems, pages 901-909, Dec 1975.
• CS84: C.F. Chen and P. Subramaniam. The second generation MOTIS timing simulator- an efficient and accurate approach for general MOS circuits. Proceedings of 1984 IEEE Int. Syrup. Ckts. and Systems, pages 538-542, 1984.
• DOR87: P. Debefve, F. Odeh, and A.E. Ruehli. Circuit Analysis, Simulation, and Design. Part P. Elsevier Science. North-Holland, New York, 1987.
• Kar72: Richard M. Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, pages 85-103, 1972.
• Nag75: L.W. Nagel. SPICE2: A computer program to simulate semiconductor circuits. Technical Report ERL-M520, Electronic Research Laboratory, U.C. Berkeley, Berkeley, CA 94720, May 1975.
• Nag80: L.W. Nagel. ADVICE for circuit simulation. Proceedings of Int. Syrup. Ckts. and Systems, 1980.
• ND85: S.tL. Nassif and S.W. Director. WASIM: A waveform based simulator for VLSICs. Proc. International Conference on Compu~er A ided Design, pages 29-31~ 1985.
• NV88: Antony P-C Ng and V. Visvanathan. A framework for scheduling multi-rate circuit simulation. Technical report, ATg~T Bell Labs, 600 Mountain Ave, Murray Hill, NJ 07974, Nov 1988.
• RSVR80: A.E. Ruehli, A.L. Sangiovann!i-Vincentelll, and N.B. Guy Rabbat. Time analysis of large scale circuits containing one-way macromodules. Proc. 1980 1EEE Int. Syrup. Circuits and Systems, pages 766-770, 1980.
• Sal84: R.A. Saleh. Iterated timing analysis and SPLICE1. Technical Report M84/2, Electronic Research Laboratory, U.C. Berkeley, Berkeley, CA 94720, January 1984.
• WJM+73: W.T. Weeks, A.J. Jimenez, G.W. Mahoney, D. Mehta, H. Qassemzadeh, and T.R. Scott. Algorithms for ASTAP -- a network analysis prograin. IEEE Transactions on Circuit Theory, CT-20:628-634, November 1973.
• WSV84: J. White and A.L. Sangiovanni-Vincentelli. Relax2.1" A waveform relaxation based circuit simulation program. Proc. 198~ Custom Integrated Circuits Conference, pages 23"!-236, May 1984.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Theory, Verification