Change in multithreading behavior on calculation

[Dreamora]

Would it be possible to alter the multi threaded calculation so that a thread when it is done with the calculation of its current block goes to the next block and calculates this one instead of waiting until the other running calculations of "partner blocks" are finished?

Currently this raises the calculation time dramatically, because the slowest block is setting the time needed to calculate X blocks parallel.
With small blocks the issue is not really important, but with 4096x4096+ it gets a serious problem, if the slowest block takes 3-4 mins to finish while the fastest took 30 second.
I currently have a Core Duo but plan to get a desktop system later this year with a Q6400 where this problem would cause even more wasted time as still the slowest of the 4 threads would force the other 3 cores and thus threads to wait.

[Aaron]

Hi Dreamora,

The current multithreading behaviour was a compromise to accommodate a limitation in the tile memory management system. If the active tiles wander too far apart, they will request additional non-shared tiles and the map cache might be exhausted. This would lead to massive disk I/O, and would really slow things down. Keeping all the tiles in the same area maximises the shared cache, and so allows the calculation to stay within the preset memory envelope.

So, in addition to desynchronising the tiles, I'll need to improve the tile manager to allow it to grow in accordance with the needs of each thread. I can't say exactly when this will be done, but it's also something I require for my new 3D renderer, so it's fairly high on my to-do list right now.

Best regards,
Aaron.

[Dreamora]

Thanks for sharing that insight.

Didn't think of cases were blocks actually get that large that without paging nothing would be possible anymore.

Any chance that in a case as described above a thread that has finished his block could go to the next "block in work" and starts to work on it from back to front at least on textures where this is possible?
Don't know if this is possible at all or would make sense for later usage thought, so just an idea ...
I don't know how hard it would be preventing the threads from getting in each others way (I assume thats why each thread has its own block?)

[Aaron]

Hi Dreamora,

Didn't think of cases were blocks actually get that large that without paging nothing would be possible anymore.

Whoa, hang on a minute. Are you running these calculations without mosaic tiling enabled? If mosaic tiling is disabled, and you still see a big difference in tile processing speed, then I have a more serous problem on my hands. If all the maps are in RAM, the threads should all run at approximately the same speed. Oops…wait a minute. The light map calculation uses a temporary mosaic map to hold the shadow state, so that calculation will always have the tiling problem I described earlier.

Anyway, regarding the tile cache problem, which certainly won’t help the matter even if you’re using non-mosaic maps, I’ve updated the tile management code to allow the cache size to grow as required. This would mean that you could theoretically throw hundreds of threads at the map and process all the tiles at once without overloading the cache (though you’d fry your RAM). However, I still need to modify each of the tile calculations to ‘lock’ the required mosaic tiles. The next release may not have these changes applied since we’re so late in the dev cycle (RC1 right now), but this change will be one of the first cabs of the rank for v2.5a.

Just FYI: When changing the tile manager, I was horrified to find that cache size was still hard-coded at 9 tiles per map, just as it was when I first wrote the mosaic algorithm some time at the start of the millennium. This means that if you have enough threads running that they need more than nine tiles at any one time, the least frequently used tiles will be loaded/saved to disk very often, which is probably why your fourth thread is running really slowly. Anyway, this sort of problem will be fixed when I update the tile calculations.

Any chance that in a case as described above a thread that has finished his block could go to the next "block in work" and starts to work on it from back to front at least on textures where this is possible?...
I assume thats why each thread has its own block.

Yep, each thread gets its own tile so that I don’t have to check whether the threads are running over one another (this requires thread synch, and it’s slow). However, what I can do is assign the threads to sub-tiles in each tile (say, split a tile into 2x2 sub-tiles), and this would mean that each core is substantially calling on the same tile cache. That would certainly be more memory-efficient, and I’ll put it on the to-do list as well. Thanks for the suggestion!

Cheers,
Aaron.

[Aaron]

Hi Dreamora,

I've just uploaded L3DT Pro v2.5 RC2, which revises the thread management to allow them to run independently (I.e. they don't wait for the slowest any more). This works for the terrain normals algorithm and the per-pixel texture algorithm. The light mapping algo is still running with the old method, but I'll upgrade that - and multi-thread many other calcs - in L3DT v2.5a.

Cheers,
Aaron.

[Dreamora]

Just realized that when doing the tests to see if the thread initialisation bug is still present. The time remaining calculation were consistent. With RC1 they went up and down due to the waiting threads.

Thank you very much for this addition.


EDIT:

I found a little problem.
Its no show breaking error but if the user cancels the operation on the "modified threading calculation" it will bring up on cancel warning to the console per block that was not calculated yet.
I assume thats because the thread manager tries to start the thread on the next unused block when one block is cancelled.

[Aaron]

Hi Dreamora,

Thanks for the bug report. I'll fix that problem for v2.5a, which is going to have multithreading enabled by default. At the moment, multithreading is still somewhat 'unofficial', so the odd bug is to be expected.

Cheers,
Aaron.