Thoughts on Multithreading...

[Cyberduke]

Numsgil, what are your current thoughts for implementing multithreading in Darwinbots?

The two approaches I can think of are:

Single step – sequential parts
So in one cycle; a DNA thread pool would run while the main thread waited for them to all finish and then kick of the physics and wait until that was done then render the result of one complete step.
The length of the cycle is the sum of all its parts, but the processing within each part is done in parallel.

Multistep – parallel parts
So in one cycle; one thread pool is processing the DNA of all the bots in the simulation
While at the same time another thread (pool) is processing the physics for the DNA results from the previous step, at the same time another thread is rendering the results from the physics for the step before. The length of a cycle is equal to its slowest part.

Does a multistep approach even work for this kind of simulation; I know it can for games.

[Numsgil]

The main issue from the multistep approach as I understand it is that each step adds latency.  So let's pretend we're making a game.  The user presses the jump button.  How long does it take before we see the character jump up?

First frame: the jump button is registered and a m_wantToJump flag is set somewhere
Second frame: the m_wantToJump flag is interpreted by the physics engine and an impulse is applied and the character moved (in the physics representation anyway)
Third frame: The jumping character is drawn so the user sees the character jump.

Suppose your game is running at 30 Hz.  There's basically a 100ms delay between action and reaction.  That's a very noticeable delay, and the game will feel "sluggish" to players even if they don't know why.  The game has increased throughput at the cost of making it feel less responsive.  Compare to a purely serial old school game (before graphics hardware) where the same frame the input is registered the character will react.

With the way modern graphics hardware works (a completely separate supercomputer your program talks to), almost every single game has to adopt at least a two step approach.  Otherwise you spend half the time with the CPU idle and the graphics card busy and half the time with the CPU busy and the graphics card idle.  With the two step approach the graphics is a frame delayed but you get massive improvements in your CPU and Graphics budgets, so it's usually worth it.

There was an article about this sort of thing in gamasutra where the developers got out a camcorder and recorded how many frames it took between button press and reaction of the character for different games.  I don't think I could dig it up, but if you find it it's a good read.

Darwinbots (and other simulations like this) are slightly different since the primary "user" is actually the AI.  The issue isn't "responsiveness", since the AI doesn't necessarily care, so in that regard you could implement a multistep approach.  The issue instead is reaction time.  In DB2, the sense->think->act cycle for bots occurs in a single cycle because it's a a single step.  We don't care about the affect of the graphics part of doing multistep (it doesn't affect the AI at all), so for our purposes doing multistep like that adds a single cycle of latency.  The sensory information a bot is acting on would be a cycle delayed from the actions it performs in response.

Which isn't necessarily a bad thing.  I haven't thought about it before, but adding in some cycles of latency between sense and action would make for less robotically precise bots, and something approaching more biological responses.  So even performance issues aside it might be worth playing with.

Also sorry if any of that rambled.  I'm about to go to bed and coherency is the first to go when I'm tired.

[Cyberduke]

In regards to the pitfalls of using this in a simulation I was more thinking along the lines of potential increases in memory usage depending on the implementation.

At its most fundamental each step would want its own copy of the simulation state to read from and write to for thread safety?
A particular copy of the DNA will want to process against a particular copy of the physical state of the simulation I.e. it would not be the same state the physics is currently solving, nor the same state that is being drawn.

What’s the current plan for doing stuff like finding out what a bot has the ability to sense?
I would start off looking at building a KD tree or something and then I can read from that while the original physical state is free to be written to safely in a different thread. But I gather you have some uber cool algorithm for this detection that doesn’t require spatial trees?

How is the physical state information going to be stored? Is it directly within a list of world entities (e.g. bots) that have properties such as location and rotation? or within some other separate data structure?

Obviously rather than storing actual duplicate copies of each state you could just have a single master and a set of deltas for each cycle I guess?

[abyaly]

Introducing a cycle delay between bot DNA execution and bot action would make writing a bot significantly more difficult. A bot would need to attempt to extrapolate the data once cycle forward before acting in order to reliably do the things it should be doing.

As far as threads, it seems like the main CPU eaters in DB2 were eye input and DNA execution. Both of these tasks seem parallelizable, since doing this for one bot isn't dependent on the results from another.

[Prsn828]

I know it may be a surprise that I would have an answer to some of this after disappearing for so long, but unless there have been drastic design plan changes in my absence, the entities are planned to be grouped as Islands of objects that are close to one another.  These objects are all shapes, including the bots, so a shape class will handle their physical attributes, while a brain and body class handle the bots' attributes.  Ideally, a single thread would be able to maintain the graphics by always drawing only the objects that have moved or changed shape, but I don't think this is realistic without a few bugs with the graphics, so something else will probably be done instead.

[Numsgil]

In regards to the pitfalls of using this in a simulation I was more thinking along the lines of potential increases in memory usage depending on the implementation.

At its most fundamental each step would want its own copy of the simulation state to read from and write to for thread safety?
A particular copy of the DNA will want to process against a particular copy of the physical state of the simulation I.e. it would not be the same state the physics is currently solving, nor the same state that is being drawn.

That's not too bad, though.  DNA doesn't change much from frame to frame, so that can be cached fairly effectively.  And it only interacts with the world through the sysvars, so there's at most maybe 2K per bot that would be duplicated.

What’s the current plan for doing stuff like finding out what a bot has the ability to sense?
I would start off looking at building a KD tree or something and then I can read from that while the original physical state is free to be written to safely in a different thread. But I gather you have some uber cool algorithm for this detection that doesn’t require spatial trees?

No, there's nothing really cool algorithm-wise I've thought of.  I want to do something that lets bots see other bots based only on apparent size of the distant bot (and some camouflage maybe).  And I want it to be additive, so that a single veggy halfway across the world is invisible, but a whole veggy island becomes very apparent (probably more as a smear of "something green".  I think there's a thread somewhere where I talk about rods and cones and the like).  Traditional spatial data structures don't necessarily work well for this sort of thing.  I'm going to brute force it for the first version then hammer on it some more later with some other sorts of algorithms.  Probably look in to raycasting structures since I think it has a lot in common with that.  A kd-tree might be the solution at the end of the day.

How is the physical state information going to be stored? Is it directly within a list of world entities (e.g. bots) that have properties such as location and rotation? or within some other separate data structure?

Probably how it will work is that there's a central bot array, and the bots themselves have instances of things like DNA and a physical body.  That was the plan in the past, and I think it makes the most sense.  Then for physics, there's probably another list of physical bodies inside the physics engine that's more agnostic about what the bodies are (ie: probably contain shots, bots, and static shapes).

Obviously rather than storing actual duplicate copies of each state you could just have a single master and a set of deltas for each cycle I guess?

Yeah, there's something like that in the DNA already.

Introducing a cycle delay between bot DNA execution and bot action would make writing a bot significantly more difficult. A bot would need to attempt to extrapolate the data once cycle forward before acting in order to reliably do the things it should be doing.

Haha, bot programmers always ruin my good ideas   I'll probably abandon the idea as a core feature, then.  I'm not a fan of "features" that bot programmers can work around, since it effectively works as just another hurdle to jump.  Kind of defeats the purpose.

As far as threads, it seems like the main CPU eaters in DB2 were eye input and DNA execution. Both of these tasks seem parallelizable, since doing this for one bot isn't dependent on the results from another.

Definitely.  It would be interesting to have access to something like the Larrabee (full disclosure: Intel owns the company I work for ), or the Cell processor (as in the PS3, though I somehow don't think .NET is going to get ported  ).  For any of the target platforms I'm aiming for (2-4 core PPUs) it just means it should be able to utilize a significant chunk of the available hardware.