Sr-4-wyk-2.0-Slajd31
Algorytm A* (1)
Algorytm A* jest algorytmem, który może posłużyć m.in. do statycznego równoważenia obciążenia. Poniżej opiszemy politykę wyboru miejsca, w którym ma być uruchomiony dany proces, gdyż cały algorytm polega na odpowiednim przypisaniu procesów do procesorów.
Zakładamy, że system składa się z n procesorów i m procesów. Dla każdego procesu mamy podany koszt jego uruchomienia na każdym procesorze (macierz kosztów na slajdzie). Algorytm używa struktury drzewa do znalezienia najlepszego rozwiązania. Proces poszukiwania rozwiązania zaczyna się od korzenia drzewa, miejsca w którym jeszcze żaden proces nie jest przypisany do procesora. Każdy poziom w drzewie oznacza przypisanie jednego procesu do określonego procesora. Liście drzewa oznaczają kompletne rozwiązanie, czyli przypisanie wszystkich procesów do procesorów. Podczas schodzenia w głąb drzewa dla każdego węzła n w drzewie obliczany jest koszt C(n ). Ta wartość jest oceną najtańszego rozwiązania zawierającego dany węzeł, biorąc pod uwagę koszt komunikacji i uruchomienia. Koszt C(n ) tworzy suma dwóch składników: f(n ) – koszt bieżącego, częściowego rozwiązania z pierwszymi k zadaniami przypisanymi do procesorów; g(n ) – dolne ograniczenie szacowanego kosztu ścieżki w drzewie, poczynając od węzła n do liścia, który reprezentuje pełne rozwiązanie. Za każdym razem algorytm wybiera węzeł z dołu bieżącego drzewa o minimalnym koszcie i rozpatruje przypisanie kolejnego procesu. Algorytm zatrzymuje się gdy dotrze do rozwiązania. Do obliczenia f(n ) jest brany procesor z największym obciążeniem komunikacyjnym (koszt komunikacji podany jest na grafie procesów) i obliczeniowym. Wartość g(n ) jest kosztem komunikacji pomiędzy najbardziej obciążonym węzłem, a węzłami, którym nie przypisano do tej pory zadań. Dla uproszczenia wszystkie procesy reprezentowane są jako graf nieskierowany, gdzie każdy węzeł oznacza proces, a krawędź wymagania komunikacyjne. Poza tym zakłada się, że każdy procesor może komunikować się ze wszystkimi innymi procesorami w systemie i nie muszą one być połączone koniecznie bezpośrednio ze sobą.
