Le problème d'affectation de région

Question

J'utilise Povray pour rendre les images sur un cluster. Chaque noeud de travail va rendre une image partielle. Le sujet de cette question est de trouver un algorithme de fractionnement approprié.

Povray rendu pixel par pixel. Mais chaque pixel a une complexité unique et donc il faut une quantité différente de temps pour le rendre.

Je divise l'image dans de nombreuses régions. Par exemple, 2x2 pixels régions. Et rendu certaines de ces régions. La complexité de ces régions affecte la complexité des régions environnantes et ainsi toute la gamme des régions est rempli d'une valeur de complexité.

I diviser une image en régions. Chaque région définit:

• colonne de départ, la colonne de fin.
• Démarrage ligne, se terminant ligne.
• La complexité de cette zone.

L'objectif est de créer une liste des emplois qui lors de la fusion couvre toutes les régions. Les emplois devraient avoir des complexités similaires.

Chaque Job définit:

• colonne de départ, la colonne de fin.
• Démarrage ligne, se terminant ligne.

contrains:

• Une macro-région valable pour un emploi se présente sous la forme d'un rectangle ou un carré.
• Le nombre d'emplois est N.

Answer 1

Merci pour la mise à jour de votre question.

En tant que stratégie alternative, vous pourriez avoir un arrangement maître-esclave dans lequel les travailleurs demandent un travail d'un processus de patron, faire le travail, puis demander plus de travail. Les mains de patron des petits fragments de travail jusqu'à ce qu'il ne reste de travail. L'avantage de cette stratégie est que à condition que les emplois sont choisis assez petit (par exemple 2x2 carrés de pixels) tous les travailleurs seront tenus occupés jusqu'à très près de la fin, et vous éviter la nécessité de calculer les estimations explicites de la complexité de la région au préalable.

Answer 2

L'algorithme que j'ai finalement utilisé est assez complexe et inefficace, donc je suis ouvert pour les réponses suivantes.

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