simulator (Re: [Icfp04-discuss] three liberal arts) (fwd)

[Olaf Doschke]

> Just for information (and fun:-)...
> 
> There are _many_ different ways to implement an ant simulator.  For
> example, one could compile ant code into C and thereby remove
> interpretive overheads.

After the contest was over, I thought about that, mainly
because my simulator (interpreter style) in foxpro was too
slow. I also read from someone, that he focused on writing
a compiler from a higher level state language (allowing
something like 'Turn Right 3') to ant code. Then I thought,
if he likes compiler problems so much, he could do the
simulator as a compile of the ant scripts...

For example compile optimizations:
Because ants cannot sense directions of other ants, you could
also do some optimizations. I think everybody has done something
like 'Turn Right 3':
 
n  : turn n+1
n+1: turn n+2
n+2: turn m

you could output code that only once changes the direction
d+3%6 and also sets the resting value to 2. That would make
the complete dump output of the simulation different (for those
two rounds), but would produce the same result again after the 
two resting rounds.

Not all determinsitic instructions, that only lead to one
next state can be optimized this way, because they change
the world, which could be sensed or lead to failure of
pickup or something else. Let's see: There are these deter-
ministic instructions:

Mark i st 
Unmark i st 
Drop st 
Turn lr st

But:
A Mark could be sensed by another ant, so you shouldn't put
it too early. For Unmark the same argument goes. Drop could
also influence another ants Sense and later, after a move
another ants PickUp. So Turn is the only instruction that 
can safely be summed up to one round with the trick of mis-
using 'resting'...

Although Flip is not deterministic in a way, in another way
it is: Even though consuming Xi in wrong order, when calling
a randomint, that would normally only be done next round:
It's intended to be a random number! So only if you are
concerned about getting a similar simulation dump you need
to do all Flip instructions in the right processing order. 
If you don't mind, you could also execute a Flip after a 
Turn in one round and change to the overall resultstate. In
this way not only Flip 1 s1 s2 is deterministic...

Other instructions could be programmed deterministic when
setting s1 = s2. Although this is not very useful: A
Sense ... s1 s1 ... makes no sense, it's just a 'Goto s1'. 
A Move s1 s1 perhaps makes sense, if the ant knows, Food
or Home is in front of it, but that may lead to deadlock
situations if an ant in front in opposite direction does
the same...

Even more advanced would be branch prediction: If an ant in
the next state want's to pickup food and it stands on food,
it will surely pickup the food next round. and if no ant is
around, then it will have no influence on any Senses of other
ants. You could PickUp the Food, alter the world and change 
the ants state to s1 of the PickUp at once, instead of wait-
ing with the PickUp for the next round.

Branch prediction is a thing processors do, and a processor is 
again an interpreter of the ant assembler! A compiler cannot 
predict the world when compiling the ant, so a compiler could
not do this optimizations. The last word in compiler speed vs
interpreter speed is not told! Perhaps a combination of both 
will be good.

You can think of each ant as a task for one processor. Then
you simulate a 182 parallel processor machine all accessing 
the same ram: the worlds cells. Most of the ants are loosely 
coupled when looking at a small amount of rounds, most of them
even won't meet throughout the whole simulation. So I think 
you could speed up things with branch prediction very much.

Of course it's not very easy to do. You'd need a fallback
position at least for some small portion of the world if your 
prediction was wrong. Is some hardware expert designing CPUs
among us? Flushing an instruction pipeline when a predicted
branch has not occured, is that how you do branch predic-
tion? And profitting of pipelined instructions to be processed
(partly) in parallel? A start would be to differentiate two
parts of each instruction: One that alters the worlds cells
and one that alters the ant. The latter could be called ALU 
(Ant logical Unit) ;-). Those two parts of the instruction
could also be processed in parallel.

Of course: a processor has real parallel processing in hardware
with instruction pipelines and states of fetch, decode and
execute can be processed parallel. Code which simulates this
cpu like behaviour could even run slower than a normal inter-
pretation of code.

Nevertheless I think the "one second limit" (concerning those
1133MHz PIII machine you mentiones) could be beat by far, because
the ants and cells are mostly loosely coupled.

But no chance of programming something as sophisticated in three
days!? Has anybody at least thought of that?

Bye, Olaf.