Sr-4-wyk-1.0-Slajd36

Algorytm Baraka i Shiloha — przykład

W przykładzie zaprezentowanym na ilustracji przedstawiono schemat wymiany informacji w algorytmie Baraka i Shiloha. Zakładamy istnienie sieci 4 komputerów: KA , KB , KC oraz KD . Każdy z nich przechowuje wektor obciążenia o rozmiarze 4. Wartość wektora należy odczytywać z tabel pionowo, kolejne wiersze odpowiadają kolejnym pozycjom wektora. Każdy komputer posiada kilka wartości swojego wektora obciążenia dla różnych momentów w czasie, co widoczne jest w postaci kolumn w tabeli. Np. trzecia kolumna w tabeli na komputerze KA ([8, 3, 6, 4]) oznacza wektor obciążenia uzyskany w wyniku wymiany informacji z innym komputerem. Strzałka skierowana od wektora na jednym komputerze do wektora na drugim komputerze oznacza, że ten pierwszy wybrał drugiego w celu wymiany informacji.

Prześledźmy teraz przykład wymiany informacji o obciążeniu. Wartości oznaczone jako X na rysunku są wartościami obciążenia, które nie są dla nas istotne i oznaczają dowolną liczbę. Posłużymy się w tym celu komputerem KA. Obciążenie komputera KA wynosi 12. W pewnym momencie działania algorytmu równoważenia obciążenia komputera KA wybrał losowo komputer KB w celu wymiany z nim informacji. Wektor Lr , który zostanie przekazany z komputera KB do KA ma postać [6 X]. Po połączeniu lokalnego wektora z otrzymanym od KB wektorem Lr , na komputerze KA uzyskujemy nowy wektor [10 6 X X]. W kolejnym kroku komputer KA wybiera do wymiany komputer KD . W międzyczasie aktualizowana jest również informacja o wartość lokalnego obciążenia, która teraz dla KA wynosi 8. Z komputera KD KA otrzymuje wektor Lr równy [3, 4]. Ostatecznie wektor obciążenia L na KA wynosi [8, 3, 6, 4].

<< Poprzedni slajd | Spis treści | Następny slajd >>