W jaki sposób wariancja czasu wykonania zadania wpływa na makespan?

16

Powiedzmy, że mamy duży zbiór zadań i zbiór identycznych (pod względem wydajności) procesorów które działają całkowicie w równolegle. W przypadku interesujących scenariuszy możemy założyć . Każde zajmuje pewną ilość czasu / cykli, gdy jest przypisane do procesora , a po przypisaniu nie można go ponownie przypisać, dopóki nie zostanie zakończone (procesory zawsze ostatecznie wykonują przypisane zadania). Załóżmy, że każdy zajmuje określoną ilość czasu / cykliτ1,τ2,...,τnρ1,ρ2,...,ρmmnτiρjτiXi, nieznane z góry, pochodzące z pewnego dyskretnego losowego rozkładu. W przypadku tego pytania możemy nawet przyjąć prosty rozkład: P(Xi=1)=P(Xi=5)=1/2 , a wszystkie Xi są niezależne parami. Dlatego μi=3 i σ2=4 .

Załóżmy, że statycznie w czasie / cyklu 0 wszystkie zadania są przydzielane możliwie równomiernie wszystkim procesorom, jednakowo losowo; więc każdemu procesorowi ρj przypisano n/m zadań (równie dobrze możemy założyć m|n dla celów pytania). Makespan nazywamy czasem / cyklem, w którym ostatni procesor ρ aby zakończyć przypisaną pracę, kończy pracę, do której została przypisana. Pierwsze pytanie:

W funkcji m , n i Xi , jaki jest makespan M ? W szczególności czym jest E[M] ? Var[M] ?

Drugie Pytanie:

Załóżmy, że P(Xi=2)=P(Xi=4)=1/2 , a wszystkie Xi są niezależne parami, więc μi=3 i σ2=1 . Jaka jest makespan w funkcji m , n i tych nowych Xi ? Co ciekawsze, jak to porównać do odpowiedzi z pierwszej części?

Niektóre proste eksperymenty myślowe pokazują, że odpowiedź na to drugie pytanie jest taka, że ​​okres makespan jest dłuższy. Ale jak można to określić ilościowo? Z przyjemnością opublikuję przykład, jeśli jest to (a) kontrowersyjne lub (b) niejasne. W zależności od powodzenia tego zadania, pod tymi samymi założeniami opublikuję kolejne pytanie dotyczące dynamicznego schematu przydziału. Z góry dziękuję!

Analiza łatwego przypadku: m=1

Jeśli , wszystkie zadań jest przypisanych do tego samego procesora. Makespan to czas na wykonanie zadań w całkowicie sekwencyjny sposób. Dlatego i n M n E [ M ]m=1nMnV 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

Wydaje się, że można użyć tego wyniku, aby odpowiedzieć na pytanie dla ; musimy po prostu znaleźć wyrażenie (lub ścisłe przybliżenie) dla gdzie , zmienna losowa z and . Czy to zmierza we właściwym kierunku?max ( Y 1 , Y 2 , . . . , T m ), Y i = X i nm>1max(Y1,Y2,...,Ym) μY=nYi=Xinm+1+Xinm+2+...+Xinm+nmσ 2 Y =nμY=nmμXσY2=nmσX2

Patrick87
źródło
Fajne pytanie. Gdyby dzisiaj nie było ostatecznego terminu ...
Dave Clarke,

Odpowiedzi:

8

Ponieważ , możemy na to spojrzeć w kategoriach i zamiast i . Powiedzmy, że to czas, jaki zajmuje ty procesor do zakończenia pracy.k n n m T i im=k×nknnmTii

W miarę wzrostu prawdopodobieństwo, że = (procesorowi przypisano tylko zadań) dla niektórych podejść , więc makespan jest zdefiniowany jako , zbliża się do .T i 5 k T = 5 i 1 m a x ( T i ) E [ M ] 5 knTi5kT=5i1max(Ti)E[M]5k

W drugim scenariuszu jest to więc zwiększenie liczby procesorów poprawia podział 4–2.4k

Co powiesz na - zwiększenie liczby zadań na procesor? Zwiększenie ma odwrotny efekt, zmniejsza prawdopodobieństwo posiadania procesora z pechowym zestawem zadań. Idę teraz do domu, ale wrócę do tego później. Moje „przeczucie” polega na tym, że wraz ze wzrostem różnica między podziałem 4–2 i podziałem 5–1 znika, staje się takie samo dla obu. Zakładam więc, że 4–2 jest zawsze lepsze, z wyjątkiem może niektórych szczególnych przypadków (bardzo małe określone wartości i ), jeśli nawet to.k k E [ M ] E [ M ] k nkkkE[M]E[M]kn

Podsumowując:

  • Niższa wariancja jest lepsza, wszystkie pozostałe są równe.
  • W miarę wzrostu liczby procesorów ważniejsza staje się mniejsza wariancja.
  • Wraz ze wzrostem liczby zadań na procesor, mniejsza wariancja staje się mniej ważna.
svinja
źródło
+1 Doskonała intuicja, a to pomaga również wyjaśnić moje myślenie. Tak więc wzrost liczby procesorów ma tendencję do zwiększania makespan przy słabym założeniu skalowania; a zwiększenie liczby zadań ma tendencję do zmniejszania makespan przy silnym założeniu skalowania (oczywiście trwa to dłużej; mam na myśli poprawę stosunku pracy do makespan). Są to interesujące spostrzeżenia i wydają się prawdziwe;
Patrick87
pierwszy jest uzasadniony faktem, że dąży do dla ustalonego i wzrostu ; ten ostatni przez fakt, że ... więc wariancja nie wzrasta liniowo w funkcji . Czy jest to zgodne z twoim myśleniem (tak interpretuję to, co do tej pory masz)? 1(1P(X=5)k)n1knVar[X+X]=Var[X]+Var[X]=2σ24σ2=4Var[X]=Var[2X]k
Patrick87
Nie wiem skąd się wzięło „przeczucie”; nie jest to spójne z resztą heurystycznego rozumowania.
András Salamon,
2

Uważam, że argumenty heurystyczne są często dość mylące przy rozważaniu planowania zadań (i ściśle powiązanych problemów, takich jak pakowanie bin). Mogą się zdarzyć rzeczy sprzeczne z intuicją. W tak prostym przypadku warto faktycznie wykonać teorię prawdopodobieństwa.

Niech z k dodatnią liczbą całkowitą. Załóżmy, że T i j jest czasem wymaganym do wykonania j-tego zadania przydzielonego procesorowi i . Jest to zmienna losowa o średniej μ i wariancji σ 2 . Oczekiwany makespan w pierwszym przypadku to E [ M ] = E [ max { k j = 1 T i ji = 1 , 2 , ,n=kmkTijjiμσ2 Wszystkie sumy są iid ze średnią k μ i wariancją k σ 2 , przy założeniu, że wszystkie T i j są wszystkie iid (jest to silniejsze niż niezależność parami).

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

Teraz, aby uzyskać oczekiwane maksimum, albo potrzebujemy więcej informacji na temat dystrybucji, albo musimy zadowolić się granicami bez dystrybucji, takimi jak:

E[M]kμ+σkn12n1.
n

σ2nk

X=maxi=1mXiY=maxi=1mYiXiYikixkμ

Pr[Xx]=i=1mPr[Xix]i=1mPr[Yix]=Pr[Yx].
E[X]E[Y]
András Salamon
źródło