Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to handle loops in a digital logic simulator?

I'm developing a digital logic simulator to build my own CPU in it later (so it's a long term project). Everything works great for circuits with no loops, for example a fulladder. Then there are circuits like an SR latch, where one of the inputs of a gate is connected to the output of another gate. So I'm in a loop, because both gates need the output of the other one, to compute their own output.
What is the best way to solve this? I implemented it in a way, that (when a loop is detected) it will return it's last output. Or, when this run is the first one (so there was no previous output) I will return zero (low). So I just assume that all the outputs were low/zero in the beginning. It works so far, but I'm sure that this is not a good way to solve the issue.

Any ideas?

like image 345
emre23 Avatar asked Jan 13 '13 00:01

emre23


1 Answers

In many cases, simply modeling each gate as having a unit propagation delay is a fine approach. A slightly more sophisticated alternative is to have the "simulation-step" routine for most component check whether the simulation time has advanced by a "full step", and only update its output if so; a few components could be omit that check but instead request that they be run again on the simulation step after other components have had a chance to update. That would allow some components to pretend to have zero propagation delay provided that they weren't nested too deeply (the simulation should limit how many times it will attempt to run each component's evaluate-state routine before it decides the components aren't going to reach a stable state).

Depending upon what exactly is being simulated, I would suggest having multiple output states for your components besides "high" and "low". Even adding an "indeterminate" state can be helpful, with the behavior that when a component's input changes in a way that could affect its output, the output will become "indeterminate" after the minimum propagation time, and assume a legitimate value after the maximum propagation time following the moment that the inputs become valid. Note that as signals pass through more levels of logic, the amount of time that they are "indeterminate" will increase. The only way to simulate anything meaningfully is to have a clock which is assumed stable, and ensure that clock periods are long enough that things can fully stabilize between them.

Simulating things in this way has the advantage that while simulation will "fail" (yield "indeterminate" values) on many circuits which would work in reality, the fact that such a simulation yields deterministic results would suggest that a real circuit that was built the same way would do so as well. Unfortunately, for circuits which rely upon edge-triggered latches, the most common simulation result would be "indeterminate", even for circuits which would have a 100% chance of actually working. To ease that problem, one would often want to 'jinx' a few gates so as not to stretch the 'indeterminate' interval. Doing this would be something of a "cheat", and create the possibility that a circuit might work in simulation but fail in reality. Nonetheless, if such cheats are applied carefully, they may make simulation much more useful than it would be otherwise.

like image 162
supercat Avatar answered Oct 03 '22 08:10

supercat