[Ktechlab-devel] Simulators.

Alan Grimes agrimes at speakeasy.net
Fri Mar 12 15:03:01 UTC 2010


The time has come to talk about simulators and test the limits of my
pathetic little intellect.

We use simulators to explore the evolution of complex systems that are
not easily modeled by a set of equations alone and to observe and learn
through watching how they evolve over time.

Even though I've been playing video games when I should have been
sleeping, I'll see if I can write a somewhat coherent explanation of how
simulators work.


Lets start with the simplest possible simulator.

############################
void simulate() {
	while(!halt_condition) {
		run_object1();
		run_object2();
		run_object3();
		run_objecy4();
	}
}
############################

This simulator allocates CPU time to four objects. It has two obvious
problems, it only simulates exactly four objects and it doesn't have a
concept of time.

Lets fix that with simulator mark II

############################
static ourClockT clock;

collection objects;

ourClockT readClock() { return clock; }

void simulate() {
	clock.reset();
	
	while(!halt_condition) {

		[iterate over objects]

		clock++;
	}
}
############################

This is basically the simulator ktechlab has now. It should also be
noted that objects are added and removed from the collection when they
need to be simulated.

Now the problems get a bit more subtle. The first problem is that there
is nondeterminism inherent in the simulation depending on what order
objects in the collection are iterated over. This may or may not be a
"don't care" situation. Another problem is that we don't have much
control over time in the simulation, we are only able to look at NOW.
(save for what variables we might be recording as in with the chart
recorder). Lets see how we can fix that.

############################
static ourClockT clock;

collection objects;
SystemStateT oldState;

ourClockT readClock() { return clock; }

void simulate() {
	clock.reset();
	
	while(!halt_condition) {

		[iterate over objects]

		oldState.save(get_system_state(), clock);
		clock++;
	}
}
############################

If our objects only look at oldState for their input then this removes
the nondeterminism problem and gives us the opportunity to move
backwards in time.

Now the issues become performance issues. Since there should not be any
"out of band" interactions between the objects, we can run them in
parallel using OpenMP or something. If we need more performance still
then the problems become interesting again. First we need a graph of the
interactions between objects. When a circuit is not a connected graph
(Ie, when there are two independent circuits), it is trivial, we simply
move the sub-graphs to different computational nodes in a beowulf
cluster. The rule is that each node may advance its clock as much as it
likes because its independent of the other circuits.

It gets interesting again when we try to partition a single circuit.
There the rule is that any node may advance its clock if all of the
nodes which it is connected to have also advanced their clocks. This is
a general approach but it doesn't apply to ktechlab because we're not
really dealing with objects but rather a representation and controller
for a system of linear equations. Our matrices are currently quite small
but they still dominate our CPU time. There are opportunities to enhance
our linear algebra engine by using libOil. It is also possible that an
existing library can be made to work. -- they tend to be written in C
and are difficult to integrate.

In a circuit that mixes analog and digital components it might be
possible to partition it between digital components that do act as
independent components and separate domains of analog simulation.

The art of solving linear algebra fast is also well understood, there
are many books and articles on the subject.

-- 
DO NOT USE OBAMACARE.
DO NOT BUY OBAMACARE.
Powers are not rights.





More information about the Ktechlab-devel mailing list