Je travaille sur un programme multi-threadé où j'ai un certain nombre de threads de travailleurs effectuant des tâches de longueur inégale. Je tiens à bien équilibrer les tâches pour vous assurer qu'ils font à peu près la même quantité de travail. Pour chaque tâche, T I J'ai un numéro C I , qui fournit une bonne approximation à la quantité de travail requise pour cette tâche.
Je cherche un (O (N) n = nombre de tâches ou meilleur) algorithme qui me donnera "à peu près" un bon équilibre de charge étant donné les valeurs de C i . Il n'est pas nécessaire d'être optimal, mais j'aimerais pouvoir avoir des limites théoriques sur la taille des allocations résultantes.
Des idées?
6 Réponses :
in O (n) cela semble facile.
donner à chaque fil de "points". Laissez Pour un fonctionnement continu, il n'y a pas de minimum dans edit: J'ai eu la mauvaise n. ci-dessus, n est le nombre de threads, contrairement à la question posée. Avec n = nombre de tâches, et t = nombre de fils, cela conduit à O (n * log T). Si T est "petit", ceci est proche de O (n).
p_i les points alloués au thread t_i . Pour chaque tâche, choisissez le thread avec le fichier P_I p_i . Vous devez alors simplement garder une trace des threads commandés par score, qui est trivial dans le temps O (n) et peut facilement être effectué dans O (log n) avec un arbre équilibré.
p_i . Si vous voulez éviter les scores qui allaient voyagez vers -inf, ajoutez régulièrement une quantité arbitraire p à tous les scores (le même montant pour tous les scores).
Cela semble intéressant et étonnamment trivial. J'y penserai et je reviendrai vers vous.
J'aurais un coup d'œil aux algorithmes pour l'équilibrage de la charge par exemple.
Le moyen le plus simple est de trier les travaux descendant par p_i (mais ceci est O (n log n)) et faites ceci:
Cet algorithme devrait vous donner de meilleurs résultats, mais avec O (N m) du temps où n est un nombre de tâches et de M Nombre de threads. Le coût total de la solution est O (n journal n + n m), donc pour m << n est O (n log n) et pour M près de N est O (n ^ 2).
Mon inclination n'est pas d'essayer de comprendre à l'avance sur la manière d'attribuer les tâches, mais de les jeter dans une file d'attente de travail courante. Tout fil de travail avec rien d'autre à accrocher la tâche suivante de la file d'attente du travail et vérifie la file d'attente de la prochaine tâche.
+1 Mais vous pourriez avoir de lourdes affirmations sur le pool de tâches partagées si vous avez de nombreux threads. Le système doit être réglé pour s'assurer que les threads n'attendent pas constamment à une serrure pour saisir une nouvelle tâche. Cela peut être atteint en rendant les tâches assez grandes ou en laissant des threads saisir plus d'une tâche à la fois. La bibliothèque de ParallelfX va encore plus loin en ayant des piscines de travail globales et locales et en ajoutant des "travaux volants" dans le mélange:
C'est exactement ce que je fais maintenant, mais avoir une exécution de fil par tâche entraînerait des frais généraux non triviaux causés par les threads terminant et étant des tâches à nouveau attribuées. Si je ne trouve aucune solution plus rapide, c'est ce que je vais aller avec, mais j'essaie essentiellement de trouver un moyen d'affecter> 1 tâche à chaque fil à l'avance
@WIM: si vous avez de la conflit dépend, en partie, sur les primitives de verrouillage que vous utilisez (et reste moins chère que d'essayer de planifier des tâches à des threads particuliers). Si vous utilisez un sémaphore dont le nombre est le nombre de tâches de la file d'attente, vous vous réveillez juste assez de threads. Vous pouvez également utiliser une file d'attente sans verrouillage. Si vous avez beaucoup de threads et de nombreuses tâches, vous pouvez utiliser n files d'attente pour réduire la conflit et attribuer simplement des tâches aux files d'attente de la manière ronde.
@ Il-Bhima: Démarrer un fil pour chaque tâche est certainement beaucoup de frais généraux. C'est pourquoi j'ai un pool fixe de threads qui redeviennent à la file d'attente pour une autre tâche.
Oui, ce que je voulais dire, c'est que j'ai une piscine de fil qui bloque sur un sémaphore de comptage et que chaque threads reprend un autre travail dès qu'il se termine. Vous me faites vraiment me demander si un algorithme de planification sera bien meilleur que de faire ce que vous dites.
Alors que la suggestion concernant le problème du knapack est utile, vous avez dit que vous essayez de minimiser le temps d'exécution net. Prendre l'approche de Knapsack vous obligerait à continuer à augmenter la taille de vos sacs à dos jusqu'à obtenir une solution réalisable - pas très efficace.
Si l'heure de l'exécution nette est limitée par le temps d'achèvement le plus long entre tous les threads travaillant en parallèle, je souhaite affecter des tâches afin de minimiser le temps de travail maximal sur toutes les threads. Cela peut entraîner un ou plusieurs fils qui ne font pas beaucoup de travail, nous ne «équilibrer» le travail. Si vous souhaitez équilibrer le travail, c'est une fonction objective différente. Par exemple, vous voudrez peut-être minimiser la variance du travail entre les threads.
Regardez dans la zone de planification de la boutique d'emploi. Si vous ne faites cela que rarement, je suggérerais d'utiliser un algorithme génétique - si vous devez le faire fréquemment et de manière plus automatisée, je suggérerais de faire une petite littérature de recherches sur des algorithmes déterministes. J'espère que cela t'aides.
Vous souhaitez implémenter un Travail d'exploitation d'algorithme . Chaque fil de travail a une file d'attente à double extrémité, de nouvelles tâches sont ajoutées au fond de la plus petite file d'attente. Les travailleurs suppriment les tâches du haut de leur propre file d'attente (la séparation supérieure / bas réduit la conflit), lorsqu'un travailleur n'a plus de travail à faire, il vole un emploi au bas de la plus grande file d'attente. C'est simple et fonctionne bien, il s'agit de l'algorithme que le système parallèle Microsoft à .NET4.0 est basé sur je crois.
L'allocation résultante est très bonne, les threads de travailleurs ne seront laissés qu'aucun travail ne fonctionnera que s'il n'y a plus d'emplois disponibles dans l'ensemble du système.
nb. Si vous voulez un exemple de code à déchirer, mon ami a écrit un système de vol de travail pour C #, que vous pouvez trouver ici
C'est la solution que je suis allé. Je envisage actuellement de migrer mon code vers Cilk, ce qui fournit un planificateur de vol de travail.
Wow, cela ressemble à une langue assez intéressante. Heureux d'avoir pu aider :)
L'ensemble des tâches est-elle connue à l'avance ou des tâches supplémentaires sont-elles ajoutées au fur et à mesure? Avez-vous à vous inquiéter de la famine (par exemple, une tâche avec High C_I ne jamais être exécutée si les tâches de faible C_I continuent d'être ajoutée)?
@David: Le nombre de tâches sera connu à l'avance, ainsi que des estimations de leur durée. La famine n'est pas un problème ici. Fondamentalement, mon objectif est de minimiser la période nette d'exécution