Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Keldor]

I've thought of a very simple way to distribute worldgen across multiple threads.   Simply generate separate worlds on each thread.

This works because worldgen typically produces perhaps 60 rejects.  With a single thread, that means 60 rejects, then a proper world.  With two threads running worldgen, each thread likely only ends up with 30 rejects before one or the other produces a non-rejected world (still 60 rejects total, but split up between the threads).  With three threads, only 20 rejects, four would have around 15 each, and so forth.  Each thread simply generates worlds, and we pick whichever one passes the rejection tests first.

Basically, the process works like this:

Mainthread spawns several worldgen threads.

Each worldgen thread has its own RNG seed, and runs in a separate memory space.  No interaction with the other worldgen threads.

When one of the threads produces a world that passes the rejection tests, it writes its index to a global int slot and goes into idle.  This is completely thread safe since because writing an integer is an atomic operation (make sure #pragma pack 4 is on, so there's no chance that the global integer strides a 4 byte boundary!  Your compiler most likely makes sure of this anyway, though...  It also needs to have the volatile keyword), also, if another thread happens to also write its index over it, it's only because it also has finished a good world.  Thus, it doesn't matter, since either way we have a good world.

Meanwhile, the main thread periodically checks the global index word to see if it's been changed by a finished thread (make sure that the index is volatile - i.e.

code:

volatile int index = -1;

).  Once it sees a index to one of the threads, it kills all the other threads, and reads back the finished world from the indexed thread.

Now the main thread just goes on as normal.

The nice thing about this approach is that it requires very little code change.  Simply bind the worldgen function to a thread pointer, ensure that it creates its own set of working variables, and it's good to go!  

The only other things to watch out for are displaying the world in progress (since there's only one screen to display to!  Ah well, I guess we'll have to pick just one thread to display), and readback of the finished world (which might not be a concern if we use invoke() from the main thread to make the finisher thread save the world to disc, export bitmaps, and so forth until we return to the main menu)

[ April 23, 2008: Message edited by: Keldor ]

[Capntastic]

Since worldgen already sucks down as much processing power as it can use, and each worldgen thread running would reduce the available processing power, I don't think this would be overly beneficial.   There's a chance it could complete a world faster; but there's also a chance that you'd have three threads each taking forever to burn through 40 or so rejects each.   It's dicey, I think.

[Align]

Yeah, unless this can be made to take advantage of multi-cores, it seems fruitless.

[Keldor]

Multithreading DOES take advantage of multiple cores - this is the typical method of using them.  Each thread can run on a separate core, since a thread is in essence a separate program.

[ April 23, 2008: Message edited by: Keldor ]

[thvaz]

The real problem with this suggestion is the ammount of memory used - a single world generation can use up to 512 mb of RAM.

[Align]

quote:Originally posted by Keldor:
<STRONG>Multithreading DOES take advantage of multiple cores - this is the typical method of using them.</STRONG>

Automatically, without further code?

quote:Originally posted by thvaz:
<STRONG>The real problem with this suggestion is the ammount of memory used - a single world generation can use up to 512 mb of RAM.</STRONG>

That might just be when it's gotten past the part where rejects most commonly occur, like hist. fig. generation.

[Derakon]

quote:Originally posted by Align:
<STRONG>Automatically, without further code?</STRONG>

The code written to make things multithreaded is the "further code" you need to make a multithreaded app.  

[briktal]

The problem would be ensuring that the same seed results in the same world.

[Derakon]

quote:Originally posted by briktal:
<STRONG>The problem would be ensuring that the same seed results in the same world.</STRONG>

Each thread would have its own RNG; they don't interfere with each other. And since this solution wouldn't actually touch the worldgen code (it more wraps around it), the process of generating a given world would be identical to what's currently happening. You'd just be making two (or more, depending on how many cores you have) in parallel.

[Align]

quote:Originally posted by Derakon:
<STRONG>The code written to make things multithreaded is the "further code" you need to make a multithreaded app.</STRONG>

I assume you meant multicore app?

[Ralgor]

quote:Originally posted by Derakon:
<STRONG>Each thread would have its own RNG; they don't interfere with each other. And since this solution wouldn't actually touch the worldgen code (it more wraps around it), the process of generating a given world would be identical to what's currently happening. You'd just be making two (or more, depending on how many cores you have) in parallel.</STRONG>

Actually, it wouldn't.  Getting a random number out of a pseudo-RNG changes the state of the RNG, so that the next number out of it will be different.  This means that later worlds are dependent on the rejects that came before.  Generating multiple worlds at once would drastically change the worlds generated, except in the case of a world with no rejects.

Not that I'm against it, but it's probably not worth the trouble right now.  World gen is something that can be left to work while you're doing something else.  On more recent computers, it doesn't take more than 10 minutes (and probably less, I haven't exactly timed it) to generate a world with over one hundred rejects.

What I would like to see is the A* path AI done on multiple separate threads.  That could dramatically speed up the actual game for people with multi-core processors (at least if that is the major performance bottleneck, like I've heard).  You could probably also put temperature on its own thread.

[Derakon]

quote:Originally posted by Ralgor:
<STRONG>Actually, it wouldn't.  Getting a random number out of a pseudo-RNG changes the state of the RNG, so that the next number out of it will be different.  This means that later worlds are dependent on the rejects that came before.  Generating multiple worlds at once would drastically change the worlds generated, except in the case of a world with no rejects.</STRONG>

Presumably when you use this method for worldgen, each thread starts with its own RNG seed, which gets recorded along with the world when the thread successfully finds a world. This approach thus wouldn't work for when you want to generate a specific world, since that'd have to run on a single thread, but it would work for all other worldgen.

Though agreed, this isn't the most important place to be optimizing.

[Ralgor]

quote:Originally posted by Derakon:
<STRONG>Presumably when you use this method for worldgen, each thread starts with its own RNG seed, which gets recorded along with the world when the thread successfully finds a world. This approach thus wouldn't work for when you want to generate a specific world, since that'd have to run on a single thread, but it would work for all other worldgen.

Though agreed, this isn't the most important place to be optimizing.</STRONG>

I see what you mean.  Instead of taking one seed and going with it, you take multiple seeds (all potentially created at the 'design a world' screen) and it just accepts whatever succeeds first.  If you're generating a specific world, then it only uses one thread, and you get to wait.

[Thassa]

If that's the case some seeds would never really get used since they would result in plenty of reject worlds before something usable would come out.

[Derakon]

Given the available space for world seeds, I doubt that would be a problem. But I do see one situation in which they would get used: offline worldgen. That is, you tell DF "I want 100 medium-sized worlds; go make them." Under such a scheme, the threads wouldn't stop when one thread successfully makes a world; they'd keep going until the required number of worlds is made. That could be each of four threads making 25 worlds, or it could be one thread making 50 and three making 10, 15, and 25 each...but it'd reduce the amount of "unused" seeds.