The region assignment problem

Question

I am using Povray to render images over a cluster. Each worker node is going to render a partial image. The subject of this question is to find a suitable splitting algorithm.

Povray render pixel by pixel. But each pixel has a unique complexity and so it takes a different amount of time to render it.

I divided the image in many regions. For example, 2x2 pixels regions. And rendered some of these regions. The complexity of those regions affects the complexity of the surrounding regions and so the whole array of regions is filled with a complexity value.

I divide an image in regions. Each region defines:

• Starting column, ending column.
• Starting row, ending row.
• Complexity of that zone.

The objective is to create a list of Jobs that when merged covers all the regions. The jobs should have similar complexities.

Each Job defines:

• Starting column, ending column.
• Starting row, ending row.

Contrains:

• A valid macro-region for a job is in the form of a rectangle or square.
• The number of Jobs is N.

Answer 1

Thanks for updating your question.

As an alternative strategy, you could have a master-slave arrangement in which workers ask for a job from a boss process, do the work, and then ask for more work. The boss hands out small fragments of work until no work remains. The advantage of this strategy is that provided the jobs are chosen small enough (e.g. 2x2 pixel squares) all workers will be kept busy until very near the end, and you avoid the need to calculate explicit estimates of region complexity beforehand.

Answer 2

The algorithm that I finally used is quite complex and inefficient, so I am open for next answers.

https://gist.github.com/gists/729677