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 $\tau_1, \tau_2, ..., \tau_n$ $\rho_1, \rho_2, ..., \rho_m$ $m \leq n$ $\tau_i$ $\rho_j$ $\tau_i$ $X_i$ , nieznane z góry, pochodzące z pewnego dyskretnego losowego rozkładu. W przypadku tego pytania możemy nawet przyjąć prosty rozkład: $P(X_i = 1) = P(X_i = 5) = 1/2$ , a wszystkie $X_i$ są niezależne parami. Dlatego $\mu_i = 3$ i $\sigma^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 $\rho_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 $\rho^*$ aby zakończyć przypisaną pracę, kończy pracę, do której została przypisana. Pierwsze pytanie:

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

Drugie Pytanie:

Załóżmy, że $P(X_i = 2) = P(X_i = 4) = 1/2$ , a wszystkie $X_i$ są niezależne parami, więc $\mu_i = 3$ i $\sigma^2 = 1$ . Jaka jest makespan w funkcji $m$ , $n$ i tych nowych $X_i$ ? 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 $m = 1$ $n$ $M$ $n$

\begin{aligned} E [M] & = E [X_{1} + X_{2} + . . . + X_{n}] \\ = E [X_{1}] + E [X_{2}] + . . . + E [X_{n}] \\ = μ + μ + . . . + μ \\ = n μ \end{aligned}

$\begin{align*} E[M] &= E[X_1 + X_2 + ... + X_n] \\ &= E[X_1] + E[X_2] + ... + E[X_n] \\ &= \mu + \mu + ... + \mu \\ &= n\mu \end{align*}$

\begin{aligned} V a r [M] & = V a r [X_{1} + X_{2} + . . . + X_{n}] \\ = V a r [X_{1}] + V a r [X_{2}] + . . . + V a r [X_{n}] \\ = σ^{2} + σ^{2} + . . . + σ^{2} \\ = n σ^{2} \end{aligned}

$\begin{align*} Var[M] &= Var[X_1 + X_2 + ... + X_n] \\ &= Var[X_1] + Var[X_2] + ... + Var[X_n] \\ &= \sigma^2 + \sigma^2 + ... + \sigma^2 \\ &= n\sigma^2 \\ \end{align*}$

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? $m > 1$ $\max(Y_1, Y_2, ..., Y_m)$ $Y_i = X_{i\frac{n}{m} + 1} + X_{i\frac{n}{m} + 2} + ... + X_{i\frac{n}{m} + \frac{n}{m}}$ $\mu_Y = \frac{n}{m}\mu_X$ $\sigma_Y^2 = \frac{n}{m}\sigma_X^2$

probability-theory scheduling parallel-computing

— Patrick87
źródło

Fajne pytanie. Gdyby dzisiaj nie było ostatecznego terminu ...

— Dave Clarke,

8

Ponieważ , możemy na to spojrzeć w kategoriach i zamiast i . Powiedzmy, że to czas, jaki zajmuje ty procesor do zakończenia pracy. $m = k \times n$ $k$ $n$ $n$ $m$ $T_i$ $i$

W miarę wzrostu prawdopodobieństwo, że = (procesorowi przypisano tylko zadań) dla niektórych podejść , więc makespan jest zdefiniowany jako , zbliża się do . $n$ $T_i$ $5k$ $T=5$ $i$ $1$ $\mathrm{max}(T_i)$ $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$ $k$ $E[M]$ $E[M]$ $k$ $n$

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 - (1 - P (X = 5)^{k})^{n}

$1 - (1 - P(X = 5)^k)^n$

1

$1$

k

$k$

n

$n$

V a r [X + X] = V a r [X] + V a r [X] = 2 σ^{2} \leq 4 σ^{2} = 4 V a r [X] = V a r [2 X]

$Var[X + X] = Var[X] + Var[X] = 2\sigma^2 \leq 4\sigma^2 = 4Var[X] = Var[2X]$

k

$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 dodatnią liczbą całkowitą. Załóżmy, że jest czasem wymaganym do wykonania zadania przydzielonego procesorowi . Jest to zmienna losowa o średniej i wariancji . Oczekiwany makespan w pierwszym przypadku to $n = km$ $k$ $T_{ij}$ $j$ $i$ $\mu$ $\sigma^2$ Wszystkie sumy są iid ze średnią i wariancją , przy założeniu, że wszystkie są wszystkie iid (jest to silniejsze niż niezależność parami).

E [M] = E [max {\sum_{j = 1}^{k} T_{i j} ∣ i = 1, 2, \dots, m}] .

$E[M] = E[\max \left\{\sum_{j=1}^k T_{ij} \mid i=1,2,\dots,m \right\}].$

k μ

$k\mu$

k σ^{2}

$k\sigma^2$

T_{i j}

$T_{ij}$

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

Peter J. Downey, Granice bez dystrybucji w oczekiwaniu maksimum z aplikacjami do planowania , Operations Research Letters 9 , 189–201, 1990. doi: 10.1016 / 0167-6377 (90) 90018-Z

E [M] \leq k μ + σ \sqrt{k} \frac{n - 1}{\sqrt{2 n - 1}} .

$E[M] \le k\mu + \sigma\sqrt{k}\frac{n-1}{\sqrt{2n-1}}.$

n

$n$

$\sigma^2$ $n$ $k$

$X = \max_{i=1}^m X_i$ $Y = \max_{i=1}^m Y_i$ $X_i$ $Y_i$ $k$ $i$ $x \ge k\mu$

P r [X \leq x] = \prod_{i = 1}^{m} P r [X_{i} \leq x] \leq \prod_{i = 1}^{m} P r [Y_{i} \leq x] = P r [Y \leq x] .

$Pr[X \le x] = \prod_{i=1}^m Pr[X_i \le x] \le \prod_{i=1}^m Pr[Y_i \le x] = Pr[Y \le x].$

E [X]

$E[X]$

E [Y]

$E[Y]$

— András Salamon
źródło