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, nieznane z góry, pochodzące z pewnego dyskretnego losowego rozkładu. W przypadku tego pytania możemy nawet przyjąć prosty rozkład: , a wszystkie są niezależne parami. Dlatego i .
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 przypisano zadań (równie dobrze możemy założyć 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 , i , jaki jest makespan ? W szczególności czym jest ? ?
Drugie Pytanie:
Załóżmy, że , a wszystkie są niezależne parami, więc i . Jaka jest makespan w funkcji , i tych nowych ? 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:
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 ]V a r [ M ]
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 n μY=nσ 2 Y =n
źródło
Odpowiedzi:
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×n k n n m Ti 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 .T i 5 k T = 5 i 1 m a x ( T i ) E [ M ] 5 kn Ti 5k T=5 i 1 max(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 nk k k E[M] E[M] k n
Podsumowując:
źródło
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 j ∣ i = 1 , 2 , … ,n=km k Tij j i μ σ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).
Teraz, aby uzyskać oczekiwane maksimum, albo potrzebujemy więcej informacji na temat dystrybucji, albo musimy zadowolić się granicami bez dystrybucji, takimi jak:
źródło