地域の割り当ての問題

Question

Povrayを使用して、クラスター上で画像をレンダリングしています。各ワーカーノードは部分的な画像をレンダリングします。この質問の主題は、適切な分割アルゴリズムを見つけることです。

povrayはピクセルでピクセルをレンダリングします。しかし、各ピクセルにはユニークな複雑さがあるため、レンダリングするのに異なる時間がかかります。

多くの地域で画像を分割しました。たとえば、2x2ピクセル領域。これらの地域のいくつかをレンダリングしました。これらの領域の複雑さは、周囲の地域の複雑さに影響を与えるため、一連の領域が複雑さの値で満たされています。

地域で画像を分割します。各地域が定義しています：

• 開始列、終了列。
• 開始行、終了行。
• そのゾーンの複雑さ。

目的は、マージされたときにすべての地域をカバーするジョブのリストを作成することです。ジョブには同様の複雑さが必要です。

各ジョブが定義します：

• 開始列、終了列。
• 開始行、終了行。

反論：

• ジョブで有効なマクロ領域は、長方形または正方形の形です。
• ジョブの数はnです。

Answer 1

あなたの質問を更新してくれてありがとう。

別の戦略として、労働者が上司のプロセスから仕事を求め、仕事をしてから、より多くの仕事を求めるマスタースレーブの取り決めをすることができます。ボスは、作業が残るまで小さな仕事の断片を渡します。この戦略の利点は、ジョブが十分に小さく選択されている場合（例：2x2ピクセルの正方形）、すべての労働者が非常に近くまで忙しくなり、地域の複雑さの明示的な推定値を事前に計算する必要性を避けることです。

Answer 2

私が最終的に使用したアルゴリズムは非常に複雑で非効率的であるため、次の答えに開かれています。

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