Sr-4-wyk-1.0-Slajd32
Algorytm A* (2)
Prześledzimy teraz działanie algorytmu A* dla sieci procesów i procesorów zaprezentowanych na poprzednim slajdzie. Macierz kosztów M również bierzemy z poprzedniego slajdu.
Dla uproszczenia prezentacji przykładu, zakładamy następującą notację przypisania procesów do procesorów: procesy uporządkowane są w ciąg według swoich identyfikatorów (t0 , t1 , t2 , …, tn ), a każdemu procesowi z ciągu, który ma być wykonany na pewnym procesorze, odpowiada identyfikator tego procesora. W ten sposób uzyskujemy ciąg identyfikatorów (na slajdzie numerów) procesorów przypisanych do kolejnych procesów. Dodatkowo jeżeli proces nie ma przypisanego żadnego procesora oznaczamy to w ciągu literą „X”.
Dany mamy ciąg (2 0 2 X X) przypisania procesów do procesorów (proces t0 przypisany do procesora p2 , t1 do p0 , t2 do p2 ). Chcemy teraz obliczyć koszt takiego przypisania C(2 0 2 X X). Musimy więc obliczyć dwie wartości: koszt f(2 0 2 X X) oraz koszt g(2 0 2 X X). Na slajdzie podano koszt wykonania poszczególnych procesów na odpowiednich procesorach (np. M(t1 , p0 ) = 14 ). Obciążenie procesora (oznaczone jako funkcja Ob(identyfikator_procesora )) obliczane jest poprzez zsumowanie kosztów wykonania przypisanych mu procesów i kosztów komunikacji z innymi przypisanymi już procesami. Po obliczeniu obciążenia procesorów p0 oraz p2 widzimy, że procesor p2 jest bardziej obciążony, dlatego to p2 jest brane pod uwagę przy obliczaniu kosztu f . f(2 0 2 X X) liczymy sumując koszty wykonania procesów na tym procesorze (M(t0 , p2 ) + M(t2 , p2 )) oraz maksymalny koszt komunikacyjny tego procesora (dla procesora p2 i ciągu przypisań (2 0 2 X X) będzie to 8). Koszt g(2 0 2 X X) liczymy z kolei sumując koszty komunikacji pomiędzy procesami na najbardziej obciążonym procesorze p2 (są to procesy t0 i t2 ), z nieprzypisanymi dotąd procesami czyli t3 i t4 . Po zsumowaniu kosztów f(2 0 2 X X) = 23 oraz g(2 0 2 X X) = 16 uzyskujemy całkowity koszt przypisania C(2 0 2 X X) = 39.
