next up previous contents
Next: Projekt implementacji pamięci dzielonej Up: Projekt implementacji maszyny typu Previous: Przyjęte założenia o środowisku   Spis rzeczy


Synchronizacja procesorów

Przyjęty do implementacji model jest maszyną typu MIMD (konkretnie SPMD). Oznacza to, że procesory mogą w danej chwili wykonywać różny kod. Zaimplementowany sposób synchronizacji jest podejściem łączącym rozwiązania opisane w p. 2.1.2 z koncepcją pełnej synchronizacji. Procesory w momencie uruchomienia na nich programu wykonują dokładnie te same instrukcje korzystając jednak z różnych danych (w szczególności na początku odróżnia je jedynie ich indeks). Można wyróżnić tutaj pojęcie grupy procesorów. Na początku istnieje jedna grupa, do której należą wszystkie procesory. Podział grupy na podgrupy jest niejawny i następuje po napotkaniu instrukcji if... then... else... (p. 3.3.4), case... (p. 3.3.5) lub pętli (p. 3.3.6 i 3.3.7). Przykładowo po napotkaniu if... then... else... i sprawdzeniu warunku, do jednej grupy zostaną przydzielone procesory, dla których warunek został spełniony, a do drugiej te, dla których był fałszywy. Obie podgrupy wykonują następnie kod dla nich przeznaczony. Po jego zakończeniu następuje synchronizacja oraz ponowne połączenie obu podgrup w jedną. Wykonanie case... jest analogiczne, jednakże tutaj podział może nastąpić na większą liczbę podgrup. W przypadku pętli następuje przydzielenie wszystkich procesorów do jednej podgrupy. Jest to konieczne ponieważ należy zapewnić synchronizację procesorów po zakończeniu pętli (niektóre procesory mogą ją zakończyć wcześniej, a inne później).

Uwaga: Należy zauważyć, że dla poprawności wykonania programu nie jest konieczna synchronizacja wykonania fragmentów kodu, w których nie ma odwołań do pamięci dzielonej. Oto przykład:

shared x;

local y;

local z;

...

y := x;

if y<>z then

begin

// tutaj następują obliczenia nie odwołujące się

// do pamięci globalnej

end;

else
begin

// tutaj również nie ma odwołań do pamięci globalnej

end;

x := z;

...

Mamy tutaj dwie instrukcje odwołujące się do pamięci dzielonej przedzielone instrukcją warunkową. Z punktu widzenia poprawności wykonania kodu istotne jest jedynie zsynchronizowanie procesorów na tych instrukcjach przypisania, kod zawarty w instrukcji warunkowej może się natomiast wykonywać niezależnie. Analogicznie nie nastąpi podział na grupy przy wykonywaniu pętli, jeśli nie występują w niej instrukcje dostępu do pamięci globalnej. Daje to możliwość tworzenia szybkich algorytmów, które nie odwołują się do pamięci dzielonej (te operacje są bardzo kosztowne jeśli chodzi o czas ich wykonania), ponieważ można przekopiować dane do pamięci podręcznej procesora (o ile algorytm na to pozwala).


next up previous contents
Next: Projekt implementacji pamięci dzielonej Up: Projekt implementacji maszyny typu Previous: Przyjęte założenia o środowisku   Spis rzeczy
Łukasz Maśko
2000-04-17