To tylko jedna z 4 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Problem szeregowania zadań
1.Opis problemu
Problemem jest uszeregowanie zadań, gdy znamy:
Ilość zadań
termin zakończenia zadania (deadline)
czas wykonywania zadania
Zadania mogą zostać wykonane tylko sekwencyjnie, jeden po drugim. W związku ze specyfikąproblemu zadanie sprowadza się do posortowania dostępnej puli zadań, po czasie zakończenia (deadline'ie), co też w niniejszym rozwiązaniu zostało uczynione. Do sortowania został użyty algorytm mergesort, w wersji bitonicznej, która określa sieć wymian pomiędzy procesorami następująco:
2.Rozwiązanie
2.1 Dla 2 procesorów
Rozwiązanie problemu dla dwóch procesorów prezentuje się następująco:
2.2 Dla 4 procesorów
2.3 Dla 8 procesorów
2.4 Porównanie
Jak widać z porównania wydajności, algorytm cechuje się dobrą skalowalnością, i widzimy zdecydowanie przyspieszenie wraz ze wzrostem ilości procesorów rozwiązujących problem.
... zobacz całą notatkę
Komentarze użytkowników (0)