Manipulating the event queue is a considerable source of run-time overhead. Our approach to reducing this overhead is to have the compiler perform as much of the simulation as possible at compile time and completely eliminate the run-time event queue. We do this by collecting information about which events could be executed at any given point during the simulation and generating code for those events guarded by run-time tests. When possible, we track variable values during compilation so that more decisions about whether an event will execute can be made at compile time instead of run time.
As an example, consider Figure 1. At the start of simulation, the compiler finds the initial event E1 in the event graph and emits the corresponding code. On analyzing the code itself, the compiler determines that the value of clk is set to 0. Following the trigger edge from the start event to E2, the compiler emits code for E2 and similarly notes that the value of clk is changed to 1. The change of clk triggers E3, so the compiler emits the code for E3, and notes that E3 remains sensitive. At this point, the only possible transition to take corresponds to the delay edge from E2 back to itself. The compiler generates code to increment the time. It then repeats this same series with the clk value initially set to 1, and arrives at the same state it was in after E1 executed: E2 is ready to execute and clk is 0. The compiler simply wraps a loop around that section of code. As there are no other events waiting to be executed, the compilation is complete. The final code is:
E1 clk = 0 forever E2 clk = ~clk E3 $display("clk") time = time+1 E2 clk = ~clk E3 $display("clk") time = time+1 end
In an event-driven simulator this example would cause two events to be scheduled for each time step. Our approach completely eliminates all of the overhead; there is no run-time event queue and no conditional tests are performed at run time. The generated code is what one expects of a cycle-based compiled-code simulator; however, our technique does not require special treatment of clock signals and is thus more general.
The above example shows how variable values can be tracked at compile time. In general, not all variables have known values at compile time, and even if they do, the compiler cannot afford to track all of them. For example, it is intractable to record all the values generated by an increment to an initially known value within a loop. Our compiler only tracks values due to assignments of constants and simple boolean expressions. Without knowing the exact values, the compiler may not be able to determine if an event will definitely execute. For these cases, the compiler generates run-time tests to ensure that the simulation is correct.
We now discuss our static simulation technique in more detail.