Come fa varianza compito tempo di completamento influisce makespan?

Question

diciamo di lasciare che abbiamo una grande collezione di compiti $ \ tau_1, \ tau_2, ..., \ tau_n $ e una collezione di identici (in termini di prestazioni) processori $ \ rho_1, \ rho_2, ..., \ rho_m $ che operano completamente in parallelo. Per gli scenari di interesse, possiamo supporre $ m \ leq n $. Ogni $ \ tau_i $ richiede una certa quantità di tempo / cicli per completare una volta che è assegnata a un processore $ \ rho_j $, e, una volta assegnato, non può essere riassegnato fino completati (processori sempre compiti assegnati casualmente complete). Supponiamo che ogni $ \ tau_i $ prende una quantità di tempo / cicli $ x_i $, non nota in anticipo, tratto da una qualche distribuzione casuale discreta. Per questa domanda, possiamo anche ipotizzare una semplice distribuzione: $ P (x_i = 1) = P (x_i = 5) = 1/2 $, e tutto $ x_i $ sono indipendenti a due a due. Quindi $ \ mu_i = 3 $ e $ \ sigma ^ 2 = 4 $.

Supponiamo che staticamente, al tempo / ciclo 0, tutti i compiti vengono assegnati nel modo più uniforme possibile tutti i processori, uniformemente a caso; così ogni processore $ \ rho_j $ viene assegnato $ N / m $ compiti (possiamo altrettanto bene assumere $ m | n $ ai fini della questione). Chiamiamo il makespan il tempo / ciclo in cui l'ultimo processore di $ \ rho ^ * $ per terminare il suo lavoro assegnato, finisce il lavoro è stato assegnato. Prima domanda:

In funzione di $ m $, $ n $, e il $ x_i $ 's, qual è il $ makespan M $? In particolare, ciò che è di $ E [M] $? $ Var [M] $?

Seconda domanda:

Si supponga che $ P (x_i = 2) = P (x_i = 4) = 1/2 $, e tutto $ x_i $ sono indipendenti a due a due, in modo da $ \ mu_i = 3 $ e $ \ sigma ^ 2 = 1 $. In funzione di $ m $, $ n $, e questi nuovi $ x_i $ 's, qual è il makespan? Più interessante, come ci si confronta con la risposta della prima parte?

Alcune semplici pensato esperimenti dimostrano la risposta a questi ultimi è che il makespan è più lungo. Ma come può essere quantificato? Sarò felice di pubblicare un esempio, se questo è o (a), controversi o (b) poco chiaro. A seconda del successo con questo, mi post una domanda di follow-up su uno schema di assegnazione dinamica in queste stesse ipotesi. Grazie in anticipo!

Analisi di un caso semplice: $ m = 1 $

Se $ m = 1 $, allora tutto $ n $ compiti è prevista per lo stesso processore. Il $ makespan M $ è solo il tempo per completare $ n $ compiti in maniera sequenziale completa. Perciò, $$ \ 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} $$ e $$ \ 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 *} $$

Sembra che potrebbe essere possibile utilizzare questo risultato a rispondere alla domanda per $ m> 1 $; abbiamo semplicemente bisogno di trovare un'espressione (o approssimazione) per $ \ max (Y_1, Y_2, ..., Y_m) $ dove $ y_i = X_ {i \ frac {n} {} m + 1} + {i X_ \ frac {n} {} m + 2} + ... + X_ {i \ frac {n} {m} + \ frac {n} {m}} $, una variabile casuale con $ \ mu_Y = \ frac { n} {m} \ mu_X $ e $ \ sigma_Y ^ 2 = \ frac {n} {m} \ sigma_X ^ 2 $. È questa rubrica nella giusta direzione?

Answer 1

$ m = K \ n volte $, possiamo guardare a questo in termini di $ k $ e $ n $ invece di $ n $ e $ m $. Diciamo $ t_i $ è il tempo che impiega il $ i $ -esimo processore per completare il suo lavoro.

$ n $ cresce, la probabilità che $ t_i $ = $ 5k $ (il processore è stato assegnato solo $ T = 5 $ compiti) per un po '$ i $ avvicina $ 1 $, essere così makespan definita come $ \ mathrm { max} (t_i) $, $ E [M] $ avvicina $ 5k $.

Per il secondo scenario è $ 4k $ in modo da aumentare il numero di processori rende il 4-2 scissione meglio.

Che dire di $ k $ - l'aumento del numero di compiti per processore? L'aumento $ k $ ha l'effetto opposto, lo rende meno probabilità di avere un processore con una serie sfortunata di compiti. Sto andando a casa ora, ma tornerò più avanti su questo. Il mio "sospetto" è che da $ k $ cresce, la differenza di $ E [M] $ tra il 4-2 scomposto e le 5-1 scompare spaccati, $ E [M] $ diventa la stessa per entrambi. Quindi presumo che 4-2 è sempre meglio tranne forse per alcuni casi particolari (valori specifici molto piccolo di $ k $ e $ n $), se anche questo.

Quindi, per riassumere:

• Bassa varianza è meglio, tutto l'essere parità di altre condizioni.
• Poiché il numero di processori cresce, differenza inferiore diventa più importante.
• Poiché il numero di compiti per processore cresce, differenza inferiore diventa meno importante.

Answer 2

Trovo che gli argomenti euristici sono spesso del tutto fuorviante se si considera pianificazione delle attività (e problemi come bin packing strettamente correlati). Le cose possono accadere che sono contro-intuitivo. Per un caso così semplice, vale la pena effettivamente facendo la teoria della probabilità.

Sia $ n = km $ con $ k $ un intero positivo. Supponiamo $ T_ {ij} $ è il tempo impiegato per completare il $ j $ -esimo compito dato al processore $ i $. Questa è una variabile casuale con media $ \ mu $ e varianza $ \ sigma ^ 2 $. Il makespan previsto nel primo caso è $$ E [M] = E [\ max \ lasciato \ {\ sum_ {j = 1} ^ k T_ {ij} \ metà i = 1,2, \ dots, m \ right \}]. $$ Le somme sono tutti IID con media $ k \ mu $ e varianza $ k \ sigma ^ 2 $, supponendo che $ T_ {ij} $ sono tutti iid (questo è più forte di indipendenza a due a due).

Ora per ottenere l'aspettativa di un numero massimo, uno o ha bisogno di più informazioni sulla distribuzione, o uno deve accontentarsi limiti senza distribuzione, come ad esempio:

• Peter J. Downey, limiti senza distribuzione sul aspettativa del massimo con applicazioni di programmazione , Letters Ricerca Operativa 9 , 189-201, 1990. doi: 10.1016 / 0167-6377 (90) 90018-Z

che può essere applicato se le somme processori saggio sono IID. Questo non sarebbe necessariamente il caso se i tempi sottostanti erano semplicemente coppie indipendenti. In particolare, dal Teorema 1 makespan attesa è limitato superiormente da $$ E [M] \ Le K \ mu + \ sigma \ sqrt {k} \ frac {n-1} {\ sqrt {2n-1}}. $$ Downey dà anche una particolare distribuzione raggiungimento di questo legato, anche se la distribuzione cambia da $ n $ fa, e non è esattamente naturale.

Si noti che il limite dice che il makespan atteso può aumentare come uno qualsiasi dei parametri aumentano: la varianza $ \ sigma ^ 2 $, il numero di processori $ n $, o il numero di attività per processore $ k $ <. / p>

Per la seconda domanda, lo scenario a bassa varianza risultante in un più makespan sembra essere un risultato improbabile di un esperimento mentale. Sia $ X = \ Max_ {i = 1} ^ m x_i $ denotano il makespan per la prima distribuzione, e $ Y = \ Max_ {i = 1} ^ m y_i $ per il secondo (con tutti gli altri parametri uguali). Qui $ x_i $ e $ y_i $ denotano le somme di $ k $ durate delle attività corrispondenti al processore $ i $ sotto le due distribuzioni. Per tutti i $ x \ ge K \ mu $, rese indipendenza $$ 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] . $$ Poiché la maggior parte della massa della distribuzione di probabilità del massimo sarà sopra la sua media, $ E [X] $ tenderà quindi a essere più grande di $ E [Y] $. Questa non è una risposta del tutto rigoroso, ma in breve, secondo caso sembra preferibile.