区域分配问题

Question

我正在使用povray将图像通过群集渲染。每个工人节点将呈现部分图像。这个问题的主题是找到合适的分裂算法。

Povray渲染像素的像素。但是每个像素都有独特的复杂性，因此渲染它需要不同的时间。

我将图像分为许多地区。例如，2x2像素区域。并渲染了其中一些地区。这些区域的复杂性会影响周围区域的复杂性，因此整个区域都充满了复杂的值。

我将图像分为区域。每个区域都定义：

• 启动列，结尾列。
• 开始行，结束行。
• 该区域的复杂性。

目的是创建一个工作列表，当合并覆盖所有区域时。工作应该具有类似的复杂性。

每个工作都定义：

• 启动列，结尾列。
• 开始行，结束行。

违反：

• 作业的有效宏观区域是矩形或正方形的形式。
• 工作的数量为N。

Answer 1

感谢您更新您的问题。

作为替代策略，您可以有一个主奴隶安排，工人从老板流程中要求工作，做工作，然后要求更多工作。老板分发了小小的工作碎片，直到没有工作。该策略的优点是，只要选择工作很小（例如2x2像素正方形），所有工人都会忙于忙碌，直到非常接近结束，并且您避免了需要预先计算出区域复杂性的明确估计。

Answer 2

我最终使用的算法非常复杂且效率低下，因此我为下一个答案开放。

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