Ideas for Multithreaded Metropolis

[FarbigeWelt]

Multithreaded Metropolis
Given
-Metropolis, render_n+1 depends on result_n, except n=1 , means principally single core only
+Z cores (Z, Z=8*i, i=1,2,3,...)
Searched
:multithread render
Ideas
Idea 1
1 a generates Z new large mutations start conditions
1 b, each core renders one large mutation following small mutation with max cons. rejects
1 c result evaluation after all threads finished generates Z new large mutations start conditions.

EDIT: Read over next post with additional points for idea 1.


Idea 2
2 a define Z cameras, adjust each camera focus length in a way each camera covers 1/Z part of image, adjust camera angle and position i a way sub-image stiching leads to seamless 2D panorama of the size of image
2 b each core renders sub-image of one camera
2 c some cores reach max sample count earlier at the moment Z/(4*i) cores are done, the half number of cores with the lowest sample counts get stopped, their sub-image divided into 4 1/4 sized sub-images, then each of the Z/(4*i)+Z/(8*i) cores continue render. The remaining Z/(8*i) part-images get assigned to the next finishing cores.
2 d repeat 2 c until size of divided part-image falls below a defined limit. Render rest-images until all reach max count of samples.

Similar approaches could be used for network rendering too.

What do you think? Is one of these ideas feasible?

[Dade]

[...]
1 c result evaluation after all threads finished generates Z new large mutations start conditions
[...]

Samples can have a very variable cost and, in your scenario, all threads will be "hostages" of (i.e. will have to wait) the one with the more time consuming work: the CPU load will be well below the 100%.

[FarbigeWelt]

[...]
1 c result evaluation after all threads finished generates Z new large mutations start conditions
[...]

Samples can have a very variable cost and, in your scenario, all threads will be "hostages" of (i.e. will have to wait) the one with the more time consuming work: the CPU load will be well below the 100%.

Thank you for the feedback to idea 1.
This is exactly the part I did not like too, cores not busy until most demanding task is done.

EDIT: Additional points for idea 1
If small mutation rendering would not depend on previous results all start conditions of small mutations could be calculated first on a stack.
Core after core could take a start condition from the stack. After stack is empty evaluation of large and their related small mutations could calculate new start conditions and put them on stack.
This way cores only have to wait for stack preparations.

I guess a single render task from one start condition takes not much time and stack generation can be done quite fast.

This means overhead penalty should be outnumbered by the fact that most and computation intense work can be performed on multiple cores simultaneously.

[FarbigeWelt]

Addition to idea 2
Although each core has its own camera and sub-image it might be useful to create a central virtual image Z times larger as the sub-image. Assuming there are three possibilities:
a) path ends on sub-image
b) path ends outside sub-image but inside image
c) path ends outside image
It is obvious that c-paths are lost.
Less obvious is what to do with b-paths.
a-paths are evaluated as usual for core‘s sub-image.
a- and b-paths are sent to a special software layer. This layer adjusts offset and angle for the transfer to result image which is built from Z sub-images. The result image is updated steadily as final render.
Because a sub-image part contains samples from all cores, the layer calculates angle and offset corrected Z sub-images ready to be fed back to each related core.
Each core combines its sub-image with the one from the layer before evaluating its sub-image for the next start conditions.

What do you think about the points of idea 2?
Is idea 2 feasible over all?

[Fox]

Technically is this possible to make MLT safe for BiDirVM, even with huge speed penalty, would it still do caustics better than random?