Lightweight discrete event simulation software

scootermaster

Platinum Member
Nov 29, 2005
2,411
0
0
Heya!

So, I've written this software that simulates a simple processor with instruction scheduling and resources (functional units, registers, etc). It works just fine, but I would like more control over the state, or, better put, I'd like more control over roll-back. I.e. I'd like to be able to save the state at each clock tick, and then be able to go back to a specific tick and and restart things from there (perhaps changing the configuration). I could write all the code to save and reload the state, but I figured it might just be simpler to build the whole thing on top of some pre-existing library.

The setup isn't really that complicated: Just a graph, nodes are picked off and put in to a ready list (when ready), scheduled (in the presence of resources), repeat.

Anyone have any ideas? C++ is essential (do to external stuff written in C++ that can't be ported to Java or Python or whatever)

Thanks!
 

Cogman

Lifer
Sep 19, 2000
10,277
125
106
It what you do depends on how fast your simulations are running and how many "states" they have.

If you have all the state data in some nice state structure, then the solution is as simple as pushing that data into a stack/vector object and nulling the rest of the data if one of the points is changed. This could, however, be potentially costly for memory if you have a lot of states or a lot of data with each state (It may not even be feasible if you have lots of local variables / different data types.

The next solution, if the simulation runs sufficiently fast enough, is to just run it up to the point in question, let them change stuff, and then continue running. Of course, the problem here is the fact that changing stuff at a given state makes repeatability a problem. You would essentially have to save all the changes they make, and for which state they make it for and check each time you run the simulation "Is this a state that has been tinkered with?"

Either way, this will be easiest if you keep all data that is related to a state in one place via a struct or class.
 

Kirby

Lifer
Apr 10, 2006
12,032
2
0
You could possibly only the save the state every so many instructions, and then execute from there to the desired instruction. It'd keep it from having to store the state every every instruction.
 

slugg

Diamond Member
Feb 17, 2002
4,722
73
91
I'm assuming that your data is always the same size for each "tick."

Why not manage a linked list of some kind of state struct? When you "roll back and change things," just traverse back however many ticks you'd like to go, free the rest of the linked list from memory, then apply your changes and keep executing as desired.

If you combine this with your own memory management techniques, as opposed to using systems calls (i.e. avoid using malloc/new and free/delete), then it should be pretty fast. System calls will slow you down, so if you can just allocate a giant chunk of memory before the algorithm runs, then that makes it cheaper in execution time. You could implement a simple, minimalistic memory management scheme for speed, or you could use one of many open source libraries for reliability. For your purposes, I think you'd be better off writing your own, especially since it seems that each "tick" of information has an exact size, so you shouldn't have any fragmentation issues to deal with. Some multiple of the sizeof(your_struct) and you should be good to go without any fragmentation.

If we're talking a lot of data, you could make a separate thread for streaming to/from the hard disk and caching recent links in immediate memory. I'm not sure how well that'd work, but it's just an idea.

edit: Question... when you say you want to save the state... is that only the state of the processor (registers), or are you also including the memory?