In the applicant's experience, there are two basic techniques for improving the performance of digital simulation. One technique seeks to improve the performance of gate simulations; the other seeks to reduce the number of gate simulations performed. Until now, these two techniques have worked at cross-purposes to one another. Techniques that use complex scheduling techniques to reduce the number of gate simulations require large amounts of time per gate simulation. Techniques which improve the speed of gate simulations by reducing or eliminating scheduling code simulate more gates than necessary. In the past several years there has been much research in improving simulation performance. Two basic approaches to simulation have evolved, which are termed Oblivious and Event-Driven. Oblivious simulators eliminate scheduling code to improve the performance of gate simulations, but provide no performance improvements for circuits that require few gate simulations. Event-Driven simulators use scheduling techniques to reduce the number of gates simulated, but perform poorly when the number of gate simulations is large.
Although traditional event-driven simulation eliminates a significant number of gate simulations, it does not eliminate all useless gate simulations. A gate simulation can be considered useless if it does not produce a change in any monitored net (i.e. a net whose value is visible to the user). In traditional event-driven simulation, a gate is simulated if and only if its inputs change value. There is a non-traditional approach to event-driven simulation which differs significantly from the usual event driven technique. With the non-traditional approach, if the inputs of a gate change, this change may not propagate to a monitored net. This can occur in two ways. First, when the gate is simulated, the output may not change. Consider, for example, the gate AND pictured in FIG. 1. Since all three inputs are zero, the change from zero to one in net A will not cause a change in net Q. The simulation of this AND gate could be eliminated without affecting the results of the simulation. The second way that a gate simulation could fail to affect a monitored net is for the output of the gate to change, but the change to be "absorbed" by some other gate before reaching the monitored net. This situation is illustrated in FIG. 2.
USPTO Backgrounds
USPTO Backgrounds