Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Circuit simulation
Reexamination Certificate
1999-06-14
2002-11-12
Teska, Kevin J. (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Circuit simulation
C703S002000, C703S022000, C716S030000
Reexamination Certificate
active
06480816
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of integrated circuit (IC) design. More specifically, the present invention relates to circuit simulation.
2. Background Information
Circuit simulation involves taking a description of a circuit, usually called a netlist, and a description of the input stimulus and then solving certain mathematical equations to determine the response of the circuit to the given input stimulus over the simulation time period. An example of a circuit simulator is the SPICE simulator, originally developed by W. Nagel. See e.g. W. Nagel, “SPICE2, A computer program to simulate semiconductor circuits”, University of California, Berkeley, Memo No. ERL-M520, May 1975. Circuit simulators like SPICE represent a circuit as a set of coupled first order non-linear differential equations. Well-known techniques like Modified Nodal Analysis are used to perform this mathematical representation. The set of coupled non-linear equations are then solved using a sequence of steps, as illustrated in FIG.
10
. The steps involve determining the time-step of integration, linearising the differential equations, and solving the resulting set of linear algebraic equations. A test is performed to determine if convergence has been achieved. The process is repeated till convergence is reached. Once convergence has been achieved, time is advanced and the entire process is repeated.
This traditional method of circuit simulation has a time complexity of O(N
3
) in the worst case, and O(N
1.5
) in the average case. This is due to the step involving the solution of the linear algebraic equations. This solution requires solving a matrix which has the time complexity of O(N
3
). Due to this super-linear time complexity of the algorithm in circuit simulators like SPICE, they are incapable of solving large circuits. Usually the limits of such simulators are reached when circuit sizes reach 100,000 devices. Solving circuits larger than this size becomes impossible, since the time taken to find the solution becomes very large.
The need to solve large circuits is becoming ever more important due to the advances of silicon process technology. Integrated circuits or chips with multi-million transistors are quite common. In order to address this need, alternative algorithms have been developed. For example, algorithms developed by C. X Huang etc, as disclosed in C. X. Huang et al., “The design and implementation of Powermill”, Proceedings of the International Symposium on Low Power Design, pp. 105-120, 1995, by Y.-H. Shih etc as disclosed in Y. H. Shin et al., “ILLIADS: A new Fast MOS Timing Simulator Using Direct Equation Solving Approacg” Proceedings of 28
th
ACM/IEEE Design Automation Conference, 1991, and by A. Devgan as disclosed in A. Devgan, “Transient Simulation of Integrated Circuits in the Charge-Voltage Plane”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, VI. 15, No. 11, November 1996. These algorithms are characterized by a linear O(N) time complexity, thereby allowing them to handle large circuits.
The linear time complexity in these algorithms is achieved by partitioning the circuit into small partitions. To avoid the super-linear time of matrix solution, these algorithms use an approximate (i.e. inaccurate) solution instead. Under Huang's approach, an algorithm called one-step relaxation is used. This algorithm often has inaccuracies of up to 20% and has serious problems on stiff circuits. In common circuits, relaxation based algorithms do not obtain the correct results. Circuits characterized by tight feedback or coupling cause problems for this algorithms. Under Shih's approach, a direct equation solving technique is used. This works well in very limited situations where the device models can be accurately modeled by the second-order Shichman and Hodges model. This is rarely true with the latest silicon process technologies that require the very complex and highly non-linear BSIM3 models for accurate device models. Devgan uses an explicit integration technique but as evidenced from the waveforms in this paper, the accuracy is inadequate. The common problem with using any approximate algorithm for solving the matrix equations is that accuracy is usually not consistently good for all circuit design styles, especially for stiff circuits.
Standard matrix based algorithms do not suffer from the inaccuracy of relaxation and other approximate algorithms. Using matrix based algorithms along with partitioning can result in good accuracy; only the nodes at the boundaries of partitions can have degraded accuracy. However, use of single time-step for all partitions produces significantly reduced performance.
Thus, an improved approach to circuit simulation is desired.
SUMMARY OF THE INVENTION
An EDA tool is provided with a circuit simulator that simulates circuit operation using dynamic partitioning and on-demand evaluation. The circuit simulator includes a static partitioner, a dynamic partitioner and an evaluation scheduler. The static partitioner pre-forms a number of static partitions for the circuit. During simulation, the dynamic partitioner forms and re-forms a number of dynamic partitions, referencing the static partitions. At each simulation time step, the evaluation scheduler determines which, if any, of the dynamic partitions have to be evaluated, and evaluating on-demand only those where evaluations are necessary.
In one embodiment, the static partitioner forms the static partitions by organizing devices of the IC design into connected sets. The static partitioner also pre-processes the static partitions into a form tailored to the dynamic partitioner's needs. In one embodiment, the dynamic partitioner determines if the devices of the IC design are in an On or an Off state, and forms the dynamic partitions accordingly. In one embodiment, the evaluation scheduler determines whether any of the dynamic partitions are in steady state, and schedules the dynamic partitions for evaluation accordingly. In one embodiment, the evaluations, when performed, are performed through matrix solution when accuracy is needed.
REFERENCES:
patent: 5305229 (1994-04-01), Dhar
patent: 5553008 (1996-09-01), Huang et al.
patent: 6049662 (2000-04-01), Saha et al.
patent: 6112022 (2000-08-01), Wei
patent: WO 98/24039 (1998-06-01), None
Buch et al, “Symphony: A Fast Mixed Signal Simulator for BiMOS Analog/Digital Circuits”, IEEE Proceedings of the Tenth International Conference on VLSI Design, pp. 403-407 (Jan. 1997).*
International Search Report for PCT/US00/11508.*
Sangiovanni-Vincentelli, A., “Circuit Simulation,” in Computer Design Aids for VLSI Circuits, P. Antognetti, D.O. Pederson, and H. De Man, Eds. Groningen, The Netherlands: Sijthoff and Noordhoff, 1981, pp. 19-113.
Huang, C.X., et al., “The Design and Implementation of Powermill,” Proceedings of the International Symposium on Low Power Design, pp. 105-120, 1995.
Devgan, A., “Transient Simulation of Integrated Circuits in the Charge-Voltage Plane,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, No. 11, Nov. 1996, pp. 1379-1390.
Ho, C.W., et al., “The Modified Nodal Approach to Network Analysis,” IEEE Transactions on Circuits and Systems, vol. CAS-22, No. 6, Jun. 1975, pp. 504-509.
Hopcroft, J.E., “Dividing a Graph into Triconnected Components,” SIAM Journal on Computing, vol. 2, No. 3, Sep. 1973, pp. 135-158.
Newton, A.R., et al., “Relaxation-Based Electrical Simulation,” IEEE Transactions on Computer-Aided Design, vol. CAD-3, No. 4, Oct. 1984, pp. 308-331.
Shih, Y.H., et al., “Illiads: A New Fast MOS Timing Simulator Using Direct Equation-Solving Approach,” Proceedings of the 28thACM/IEEE Design Automation Conference, Jun. 1991, pp. 20-25.
Tarjan, R., “Depth-First Search and Linear Graph Algorithms,” SIAM Journal on Computing, vol. 1, No. 2, Jun. 1972, pp. 146-160.
Ackland, B. D., et al., “Event-EMU: An Event Driven Timing Simulator for MOS VLSI Circuits,” International Conference on Computer Aided D
Broda Samuel
Columbia IP Law Group, PC
Teska Kevin J.
LandOfFree
Circuit simulation using dynamic partitioning and on-demand... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Circuit simulation using dynamic partitioning and on-demand..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit simulation using dynamic partitioning and on-demand... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2973676