Pr-1st-1.1-m09-Slajd06

Sortowanie rozproszone – przykład

Każdy zprocesów $P_{i+1}$ ma za zadanie uporządkować (posortować) przypisany mu na wstępie zbiór <math<\mathcal{X}_{i+1}</math> i wyznaczyć element $mi{n}_{i+1}$.

Następnie procesy wysyłają elementy $mi{n}_{i+1}$ do swoich lewych sąsiadów ioczekują na odpowiedź zawierającą $ma{x}_i$. Po otrzymaniu wiadomości zwartością $mi{n}_{i+1}$, a przed wysłaniem odpowiedzi, proces $P_i$ wyznacza nowy element $ma{x}_i$.

W ogólności, nowo wyznaczony $ma{x}_i$ może być równy otrzymanemu ostatnio $mi{n}_{i+1}$. Następnie każdy z procesów wysyła odpowiedź ze swoim elementem maksymalnym do prawego sąsiada. Po otrzymaniu odpowiedzi, procesy znów sortują zbiory <math<\mathcal{X}_{i+1}</math> i jeśli wwyniku tego sortowania wartość $mi{n}_{i+1}$ różnić się będzie od poprzednio wysłanego elementu minimalnego, to proces wysyła ten nowy element $mi{n}_{i+1}$ do lewego sąsiada.

Cel sortowania rozproszonego zostaje osiągnięty, gdy uporządkowany zostanie każdy zbiór <math<\mathcal{X}_{i}</math>, a ponadto dla każdego $i:1\le i\le n-1,ma{x}_i<mi{n}_{i+1}$.

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