Make simulator responsive when displaying long simulations

[tomcl]

Is your feature request related to a problem? Please describe.

Curently, after simulating a very long simulation, moving backwards to examine the history beyond the 1000 clock cycle buffer requires resimulation from start

Describe the solution you'd like
Simulation keeps checkpoint state at regular intervals so that after simulating up to N - regenerating 1000 contiguous clock cycles of data in any range < N will be fast

Describe alternatives you've considered

See below.

Additional context

Currently we have a supposed circular array which holds the last N simulation samples. Going forward from this in time is fine - the simulator restarts from the latest sample. Going back is problematic because the only way to go back is to resimulate from 0. The circular array is not used properly as a circular array but is filled up so that the waveform simulator can be guaranteed to have a available the last MaxArraySize samples in the array.

The solution is to keep an array of records of checkpoint simulation state every 1000 clocks or whatever, and to make the circular array keep track of the time of its starting sample as well as its last sample (making only the assumption that between these two times we have data correctly stored in the array).

To add the additional data it will be necessary to add a field to fc: FastComponent:

HistoricState: StepData<SimulationComponentState> option // this is exactly like State field

// we define HistoricState data so that (if data exists)
(Option.get fc.HistoricState.StepData).Step[clockNum] = 
     (Option.get fc.State.StepData).Step[clockNum*fc.CheckPointInterval]

Where CheckPointInterval is a new field of FastComponent. Any value for this can be chosen.

We could assume that HistoricState exists up to ClockTick although see below for a more scalable solution

Also the "circular arrays" of simulation data are not currently used properly as circular arrays. We would need a new mutable field FirstClockTick of FastSimulation.

Then at top-level when running a simulation: fastSim:fastSimulation to clock t we would implement:

if t < fastSim.FirstClockTick then // in this case we have gone beyond circular array
      // find largest stored checkpoint < t  (= t / fastSim.CheckPointInterval
      // restart simulation at checkpoint time
// do whatever was done before to simulate.

to restart a simulation at some checkpoint time:

• Set FirstClockTick to the relevant checkpoint time
• Set ClockTick = FirstClockTick (or possibly FirstClockTick - 1)
• For each FastComponent with state, set its State at array index (FirstClockTick/ MaxarraySize) equal to the corresponding stored HistoricState containing the historic state data

When running the simulation:

• set FirstClockTick to be min 0 (ClockTick-MaxArraySize)

Then resimulating any time that has been previously simulated requires at most 1000 cycles of simulation.

When making this (overdue, really) change to the simulation to handle long simulations properly it would also be possible to use HistoricState (if it exists) to go forward in time. The procedure would restart the simulation and some future checkpoint time (the largest less than the time required) and be identical to when going back in time.

Adding this to the simulator would be pretty easy, and would actually make the simulation have a more uniform user interface where at top level you simply ask for a time range of simulated data (containing no more than MaxArraySize steps) and the simulator will do the work necessary to give you that.

Note on scalability

It is entirely possible to simulate small designs for 100,000,000 or more clock cycles. See #445.
That presents a challenge because then the amount of HistoricState stored will be too large

The solution is to prune the checkpoints so that the HistoricState array uses a new field of FastSimulation: FirstHistoricClockTick. if no historic data is found - too bad - we must simulate from start.

A fully scalable solution would use a Map for HistoricState instead of an array.

\\\ the key of the map is the actual clockTick stored
\\\ there is no restriction on how often clock ticks are stored
\\\ Map.Keys is sorted by key value and can be used to find the largest key smaller than a given time
HistoricState: Map<int32,SimulationComponentState>

• Note that now working out how to restart the simulation requires finding a clocked component - the FastSimulation has a Map of these - and then extracting is HistoricData map and checking keys.
• The maps obviously must not get too large. They can be pruned by extracting the list of keys and deleting items.
• Pruning could be simple (remove anything too far away from current clock tick) or complex: keep more elements at times close to the current clock tick (backward and forward) to make navigation by small amounts always fast.
• Possibly clockTick and all clock numbers should be int64 not int32. I'm not sure this is needed. I don't see much use case for simulating beyond 1,000,000,000 cycles but we should probably check for any attempt to do this (we do not at the moment).
• I am torn between using a Map, and using an Array, for this data. What I like about the Map is that there are no assumptions made about what is the data currently stored - each item specified its clock tick as key. It is only a little more work to implement, and allows much more general strategies for what data to keep stored. The cost of storing or deleting data is admittedly quite high because every stateful component has a map which must have an item deleted or added. But we only need to do this every (2000?) cycles or so. This is just on the edge of where I worry it could be a performance hit

[samuelpswang]

Waveform simulator is responsive no matter the length of simulation after partial SVG generation was implemented in PR #456. Closing issue pending verification by @tomcl.