Comment la variance du temps d'exécution des tâches affecte-t-elle la durée?

16

Disons que nous avons une grande collection de tâches et une collection de processeurs identiques (en termes de performances) qui fonctionnent complètement dans parallèle. Pour les scénarios d'intérêt, nous pouvons supposer . Chaque prend un certain temps / cycles à terminer une fois qu'il est affecté à un processeur , et une fois qu'il est attribué, il ne peut pas être réaffecté jusqu'à ce qu'il soit terminé (les processeurs finissent toujours par terminer les tâches assignées). Supposons que chaque prenne une quantité de temps / cyclesτ1,τ2,...,τnρ1,ρ2,...,ρmmnτiρjτiXi, inconnue à l'avance, tirée d'une distribution aléatoire discrète. Pour cette question, nous pouvons même supposer une distribution simple: , et tous les sont indépendants par paire. Par conséquent et .P(Xi=1)=P(Xi=5)=1/2Xiμi=3σ2=4

Supposons que, statiquement, au temps / cycle 0, toutes les tâches soient assignées aussi uniformément que possible à tous les processeurs, uniformément au hasard; donc chaque processeur se voit attribuer tâches (on peut tout aussi bien supposer aux fins de la question). Nous appelons le makespan le temps / cycle auquel le dernier processeur ρ pour terminer son travail assigné, termine le travail qui lui a été assigné. Première question:ρjn/mm|nρ

En fonction de m , n et des Xi , quel est le makespan M ? Plus précisément, qu'est-ce que E[M] ? Var[M] ?

Deuxième question:

Supposons que P(Xi=2)=P(Xi=4)=1/2 , et tous les Xi sont indépendants deux à deux, de sorte que μi=3 et σ2=1 . En fonction de m , n et de ces nouveaux Xi , quelle est la durée? Plus intéressant, comment se compare-t-il à la réponse de la première partie?

Certaines expériences de pensée simples démontrent que la réponse à cette dernière est que la durée de fabrication est plus longue. Mais comment cela peut-il être quantifié? Je serai heureux de publier un exemple si cela est (a) controversé ou (b) pas clair. En fonction du succès de celui-ci, je posterai une question de suivi sur un schéma d'affectation dynamique sous ces mêmes hypothèses. Merci d'avance!

Analyse d'un cas facile: m=1

Si m=1 , toutes les n tâches sont planifiées sur le même processeur. Le makespan M est le moment idéal pour effectuer n tâches de manière séquentielle complète. Par conséquent, et V a r [ M ]

E[M]=E[X1+X2+...+Xn]=E[X1]+E[X2]+...+E[Xn]=μ+μ+...+μ=nμ
Var[M]=Var[X1+X2+...+Xn]=Var[X1]+Var[X2]+...+Var[Xn]=σ2+σ2+...+σ2=nσ2

Il semble qu'il soit possible d'utiliser ce résultat pour répondre à la question pour ; nous avons simplement besoin de trouver une expression (ou approximation) pour max ( Y 1 , Y 2 , . . . , Y m )Y i = X i nm>1max(Y1,Y2,...,Ym) , une variable aléatoire avecμY=nYi=Xinm+1+Xinm+2+...+Xinm+nmetσ 2 Y =nμY=nmμX . Cette direction va-t-elle dans la bonne direction?σY2=nmσX2

Patrick87
la source
Bonne question. Si seulement il n'y avait pas de date limite aujourd'hui ...
Dave Clarke

Réponses:

8

Comme , nous pouvons regarder cela en termes de k et n au lieu de n et m . Disons que T i est le temps nécessaire au i- ème processeur pour terminer son travail.m=k×nknnmTii

Au fur et à mesure que augmente, la probabilité que T i = 5 k (le processeur n'a été affecté qu'à T = 5 tâches) pour certains i s'approche de 1 , de sorte que la durée étant définie comme m a x ( T i ) , E [ M ] approche 5 k .nTi5kT=5i1max(Ti)E[M]5k

Pour le deuxième scénario, il s'agit de donc l'augmentation du nombre de processeurs améliore la répartition 4–2.4k

Qu'en est-il de - augmenter le nombre de tâches par processeur? Augmenter k a l'effet inverse, cela rend moins probable un processeur avec un ensemble malchanceux de tâches. Je rentre chez moi maintenant mais j'y reviendrai plus tard. Mon "pressentiment" est qu'à mesure que k augmente, la différence de E [ M ] entre la division 4–2 et la division 5–1 disparaît, E [ M ] devient la même pour les deux. Je suppose donc que 4–2 est toujours meilleur, sauf peut-être pour certains cas spéciaux (très petites valeurs spécifiques de k et n ), si ce n'est que cela.kkkE[M]E[M]kn

Donc, pour résumer:

  • Une variance plus faible est meilleure, toutes choses étant égales par ailleurs.
  • À mesure que le nombre de processeurs augmente, une variance plus faible devient plus importante.
  • À mesure que le nombre de tâches par processeur augmente, une variance plus faible devient moins importante.
svinja
la source
+1 Excellente intuition, et cela aide également à clarifier ma pensée. Ainsi, l'augmentation du nombre de processeurs a tendance à augmenter la durée de validité sous une hypothèse de mise à l'échelle faible; et l'augmentation du nombre de tâches a tendance à diminuer la durée de travail sous une forte hypothèse de mise à l'échelle (bien sûr, cela prend plus de temps; je veux dire que le rapport travail / durée de travail s'améliore). Ce sont des observations intéressantes, et elles semblent vraies;
Patrick87
la première est justifiée par le fait que tend vers 1 pour k fixe et n croissant ; ce dernier par le fait que V a r [ X + X ] = V a r [ X ] + V a r [ X ] = 2 σ 24 σ 2 = 41(1P(X=5)k)n1kn ... donc la variance n'augmente pas linéairement en fonction de k . Est-ce compatible avec votre pensée (c'est ainsi que j'interprète ce que vous avez jusqu'à présent)? Var[X+X]=Var[X]+Var[X]=2σ24σ2=4Var[X]=Var[2X]k
Patrick87
Je ne sais pas d'où vient le "pressentiment"; il n'est pas cohérent avec le reste du raisonnement heuristique.
András Salamon
2

Je trouve que les arguments heuristiques sont souvent assez trompeurs lorsque l'on considère la planification des tâches (et des problèmes étroitement liés comme le bin bin). Il peut arriver des choses contre-intuitives. Pour un cas aussi simple, cela vaut la peine de faire la théorie des probabilités.

Soit avec k un entier positif. Supposons que T i j est le temps nécessaire pour terminer la j- ième tâche donnée au processeur i . Il s'agit d'une variable aléatoire de moyenne μ et de variance σ 2 . Le makespan attendu dans le premier cas est E [ M ] = E [ max { k j = 1 T i ji = 1 , 2 , ,n=kmkTijjiμσ2 Les sommes sont toutes iid avec une moyenne k μ et une variance k σ 2 , en supposant que T i j sont toutes iid (c'est plus fort que l'indépendance par paire).

E[M]=E[max{j=1kTjejje=1,2,,m}].
kμkσ2Tjej

Maintenant, pour obtenir l'espérance d'un maximum, il faut soit avoir plus d'informations sur la distribution, soit se contenter de bornes sans distribution, telles que:

  • Peter J. Downey, Distribution-free bounds on the expectation of the maximum with scheduling applications , Operations Research Letters 9 , 189–201, 1990. doi: 10.1016 / 0167-6377 (90) 90018-Z

E[M]kμ+σkn-12n-1.
n

σ2nk

Pour votre deuxième question, le scénario de faible variance résultant en une durée de vie plus longue semble être le résultat improbable d'une expérience de pensée. LaisserX=maxje=1mXje indique la durée de la première distribution, et Oui=maxje=1mOuijepour le second (avec tous les autres paramètres identiques). IciXje et Ouije dénoter les sommes de k durées de tâche correspondant au processeur jesous les deux distributions. Pour tousXkμ, l'indépendance donne

Pr[XX]=je=1mPr[XjeX]je=1mPr[OuijeX]=Pr[OuiX].
Comme la majeure partie de la masse de la distribution de probabilité du maximum sera supérieure à sa moyenne, E[X] aura donc tendance à être plus grand que E[Oui]. Ce n'est pas une réponse complètement rigoureuse, mais en bref, le deuxième cas semble préférable.
András Salamon
la source