Systemy wieloprocesorowe z pamiecia dzieloną - Bartłomiej Zieliński(1).pdf - elekronika i nie tylko - kormoran55

Jarosław Krupa

Radosław Kozłowski

4FDS - systemy i sieci komputerowe

POLITECHNIKA RZESZOWSKA

Systemy wieloprocesorowe z

pamięcią dzieloną

Streszczenie

W opracowaniu tym znaleźć można informacje z szerokiej dziedziny dotyczącej systemów

rozproszonych z pamięcią dzieloną. Przestudiowane zostaną różne kategorie

wieloprocesorów. Z opracowania tego dowiedzieć można się także, czym w istocie jest

pamięć dzielona i jak naprawdę działają wieloprocesory z pamięcią dzieloną.

Przeanalizowana zostaje semantyka dzielenia oraz przestudiowane zostają różne modele

spójności stosowane w systemach z pamięcią dzieloną. Opracowanie to zawiera także

uproszczone informacje na temat projektowania systemów rozproszonej pamięci

dzielonej. Ponieważ rozproszona pamięć dzielona może być ściśle powiązana z

architekturą komputera, systemami operacyjnymi, systemami wsparcia wykonywania

programów, a nawet z językami programowania, wszystkie te zagadnienia odegrają

również znaczącą rolę w niniejszym opracowaniu. W ostatnim rozdziale przedstawione

zostaną tendencje rozwojowe oraz kierunki rozwoju systemów wieloprocesorowych z

pamięcią dzieloną.

Wprowadzenie

Systemy komputerowe przeżywają rewolucję. Od 1945 roku, kiedy to rozpoczęła się era

nowoczesnych komputerów, aż do roku 1985 komputery były wielkie i drogie. Nawet

minikomputery z reguły kosztowały dziesiątki tysięcy dolarów. Wskutek tego większość

instytucji dysponowała skromną liczbą komputerów, które - z braku sposobów ich

łączenia - działały niezależnie jeden od drugiego.

Od połowy lat osiemdziesiątych sytuacja ta zaczęła się zmieniać dzięki dwu osiągnięciom

w technologii. Pierwszym było opracowanie mikroprocesorów o dużej mocy obliczeniowej.

Z początku były to maszyny ośmiobitowe, lecz wkrótce upowszechniły się procesory

szesnastobitowe, trzydziestodwubitowe, a nawet sześćdziesięcioczterobitowe. Wiele z

nich miało moc obliczeniową porównywalną z mocą całkiem porządnego komputera

głównego (tj. wielkiego) - a przy tym za ułamek ceny. Postęp w technologii

komputerowej, jaki dokonał się w minionym półwieczu, jest oszałamiający i nie ma sobie

równego w innych dziedzinach przemysłu. Od maszyny, która kosztowała 10 milionów

dolarów i wykonywała jedną instrukcję na sekundę, technologia doszła do maszyn

kosztujących 1000 dolarów i wykonujących 10 milionów instrukcji na sekundę, osiągając

ponad tysiąc razy lepszy współczynnik cena/wydajność.

Drugim osiągnięciem było wynalezienie szybkich sieci komputerowych. Lokalne sieci

komputerowe, czyli sieci LAN (ang. Local Area Network ), umożliwiają łączenie w obrębie

budynków nawet setek komputerów w taki sposób, że niewielkie ilości informacji mogą

być przesyłane między maszynami w czasie tysięcznych części sekundy. Większe ilości

danych mogą przemieszczać się między maszynami z szybkościami od 10 do 100

milionów bitów na sekundę, a niekiedy nawet szybciej . Rozległe sieci komputerowe, czyli

sieci WAN (ang. Wide Area Networks ), pozwalają łączyć miliony maszyn na całej kuli

ziemskiej i przesyłać informacje z szybkościami od 64 kb/s do gigabitów na sekundę.

Dzięki tym technologiom wzajemne połączenie ze sobą - za pomocą szybkiej sieci -

systemów komputerowych złożonych z wielu jednostek centralnych (CPU - ang. Central

Processor Unit ) jest obecnie nie tylko wykonalne, ale i łatwe. Nazywa się je zwykle

systemami rozproszonymi (ang. distributed systems ) w przeciwieństwie do poprzednich

systemów scentralizowanych (ang. centralized systems ), czyli jednoprocesorowych (ang.

single-processor systems ), złożonych z jednego procesora centralnego, jego pamięci,

urządzeń zewnętrznych i pewnej liczby terminali. Systemy rozproszone wymagają jednak

zupełnie odmiennego oprogramowania niż systemy scentralizowane. Co więcej -

niezbędne dla nich systemy operacyjne zaczynają dopiero powstawać. Uczyniono już

kilka kroków, lecz droga do przebycia jest jeszcze długa.

Chociaż wszystkie systemy rozproszone składają się z wielu jednostek centralnych, sprzęt

ten można zorganizować na kilka sposobów, zwłaszcza pod względem wzajemnych

połączeń i rodzajów komunikacji. W ciągu wielu lat proponowano rozmaite schematy

klasyfikacji wieloprocesorowych systemów komputerowych, lecz w rzeczywistości żaden z

nich nie przyjął się na dobre i nie wszedł do powszechnego użycia. Istotne w tym

przypadku są dwie cechy: liczba strumieni instrukcji oraz liczba strumieni danych.

Komputer z jednym strumieniem instrukcji i jednym strumieniem danych nosi nazwę

SISD. Wszystkie tradycyjne komputery jednoprocesorowe (tj. mające tylko jedną

jednostkę centralną) mieszczą się w tej kategorii - od komputerów osobistych aż po

wielkie komputery główne.

Następną kategorią jest SIMD - jeden strumień instrukcji i zwielokrotniony strumień

danych. Ten typ odnosi się do procesorów macierzowych z jedną jednostką wykonywania

instrukcji, która pobiera instrukcję, a następnie zarządza wieloma jednostkami danych w

sposób równoległy - każda z nich operuje na własnych danych. Maszyny tego rodzaju są

użyteczne do obliczeń, w których powtarza się te same operacje na wielu zbiorach

danych, na przykład przy dodawaniu wszystkich składowych 64 niezależnych wektorów.

Niektóre superkomputery zalicza się do typu SIMD.

Kolejna kategoria zwie się MISD - zwielokrotniony strumień instrukcji i jeden strumień

danych. Modelowi temu nie odpowiada żaden ze znanych komputerów. Ostatnią z

kategorii stanowi MIMD, która w istocie oznacza grupę niezależnych komputerów

zaopatrzonych we własne liczniki rozkazów, programy i dane. Wszystkie systemy

rozproszone należą do kategorii MIMD, tym samym ta klasyfikacja nie jest nazbyt

użyteczna do naszych celów.

Wszystkie komputery MIMD dzielą się na dwie grupy ( RYS.1. ): komputery wyposażone we

wspólną pamięć, zazwyczaj nazywane wieloprocesorami (ang. multiprocessors ) i

komputery, które jej nie mają, czasami nazywane multikomputerami (ang.

multicomputers ). Zasadnicza różnica przedstawia się następująco: w wieloprocesorze

istnieje jedna wirtualna przestrzeń adresowa dzielona przez wszystkie procesory

centralne. Jeśli którakolwiek jednostka centralna zapisuje na przykład wartość 44 pod

adresem 1000, to każda inna jednostka centralna, czytająca następnie spod swojego

adresu 1000, otrzyma wartość 44. Wszystkie maszyny dzielą tę samą pamięć. Na odwrót,

w multikomputerach każda z maszyn ma własną, prywatną pamięć. Jeśli jakaś jednostka

centralna zapisuje wartość 44 pod adresem 1000, podczas gdy inna jednostka centralna

czyta spod adresu 1000, to ta ostatnia dostanie wartość pamiętaną tam poprzednio.

Zapisywanie wartości 44 zupełnie nie wpływa na zawartość jej własnej pamięci. Typowym

przykładem multikomputera jest zbiór komputerów osobistych połączonych za pomocą

sieci.

Rys. 1. Podział równoległych i rozproszonych systemów komputerowych.

Każdą z tych kategorii komputerów można dalej podzielić na podstawie architektury sieci

wzajemnych połączeń. Kategorie te opisane zostały jako szynowe (ang. bus ) i

przełączane (ang. switched ). Przez kategorię szynową rozumiemy istnienie pojedynczej

sieci, tablicy połączeń, szyny, kabla lub innego nośnika łączącego wszystkie maszyny.

Schematu takiego używa telewizja kablowa - firma okablowująca układa przewód wzdłuż

ulicy, a wszyscy subskrybenci mają doprowadzenia biegnące do niego od ich odbiorników

telewizyjnych. Systemy przełączane nie mają jednego szkieletu jak telewizja kablowa.

Zamiast niego od maszyny do maszyny biegną pojedyncze przewody; stosuje się przy

tym wiele różnych schematów okablowania. Komunikaty biegną po drutach, a

przełączenia jawnie określane przy każdym kroku wytyczają ich trasę wzdłuż jednego z

wyprowadzeń. Na tej zasadzie jest zorganizowany system światowej telefonii.

Odmiennym wymiarem tej taksonomii jest to, że w niektórych systemach maszyny są

ściśle powiązane (ang. tightly coupled ), a w innych są luźno powiązane (ang. loosely

coupled ). W ściśle powiązanym systemie obserwowane opóźnienie komunikatu wysłanego

od jednego komputera do drugiego jest małe, a szybkość przesyłania danych jest duża,

tzn. liczba bitów przesyłanych w ciągu sekundy jest wielka. W systemie luźno

powiązanym zachodzi odwrotna sytuacja: międzymaszynowe opóźnienia komunikatów są

duże, a szybkość przesyłania danych jest mała. Na przykład dwa jednoukładowe

procesory centralne znajdujące się na tej samej płytce drukowanej i połączone

wytrawionymi na niej ścieżkami są ściśle powiązane, podczas gdy dwa komputery

połączone za pomocą modemu o szybkości 2400 bitów na sekundę poprzez system

telefoniczny są luźno powiązane. Systemy ściśle powiązane są zazwyczaj używane jako

systemy równoległe (do rozwiązywania pojedynczych problemów), systemy luźno

powiązane stosuje się głównie w systemach rozproszonych (do prac nad wieloma

osobnymi problemami), aczkolwiek nie zawsze musi to być prawdą. Słynnym

kontrprzykładem jest projekt, w którym setki komputerów rozmieszczonych po całym

świecie pracowały wspólnie nad rozłożeniem na czynniki olbrzymiej liczby (około

stucyfrowej). Każdy komputer miał przydzielony inny zakres podzielników do

wypróbowania i pracował nad zadaniem w swoim wolnym czasie, przesyłając gotowe

wyniki za pomocą poczty elektronicznej. Ogólnie rzecz biorąc, wieloprocesory wykazują

więcej ścisłych powiązań aniżeli multikomputery, ponieważ mogą wymieniać dane z

szybkością działania pamięci, wszakże niektóre multikomputery zbudowane na

światłowodach mogą też pracować z szybkościami działania pamięci.

Czym jest pamięć dzielona

W początkowym okresie wprowadzania obliczeń rozproszonych, było niejawnie

zakładane, że programy na maszynach, które nie mają żadnej fizycznej pamięci dzielonej

(tj. multikomputerach), w sposób oczywisty przebiegają w różnych przestrzeniach

adresowych. Przy takim nastawieniu komunikację pojmowano w kategoriach

przekazywania komunikatów między rozłącznymi przestrzeniami adresowymi. W roku

1986 zaproponowane zostało inne rozwiązanie, obecnie znane pod nazwą rozproszonej

pamięci dzielonej (ang. distributed shared memory - DSM). Zaproponowane zostało

użycie zbioru stacji roboczych połączonych za pomocą sieci lokalnej i mających jedną,

stronicowaną, wirtualną przestrzeń adresową. W najprostszym wariancie każda strona

występuje w dokładnie jednej maszynie. Odwołania do stron lokalnych są wykonywane

sprzętowo z pełną szybkości pamięci. Próba odwołania do strony na innej maszynie

powoduje zasygnalizowanie braku strony przez sprzęt i przejście do systemu

operacyjnego. System operacyjny wysyła wówczas komunikat do zdalnej maszyny, która

znajduje potrzebną stronę i wysyła ją zamawiającemu procesowi. Nieudana instrukcja

zostaje wtedy ponowiona i może być wykonana do końca.

Projekt ten jest w istocie podobny do tradycyjnych systemów pamięci wirtualnej: gdy

proces odwołuje się do strony nieobecnej, następuje przejście do systemu operacyjnego,

który sprowadza stronę i umieszcza w pamięci. Różnica polega tu na tym, że system

operacyjny zamiast pobierać stronę z dysku, pobiera ją od innego procesora za

pośrednictwem sieci. Jednak dla procesów użytkowych system ten wygląda jak

tradycyjny wieloprocesor z wieloma procesami, które mają swobodę czytania i

zapisywania pamięci dzielonej. Cała komunikacja i synchronizacja może odbywać się

przez pamięć, przy czym komunikacja jest niewidoczna dla procesów użytkowych.

Opracowany został w rezultacie system łatwy zarówno do programowania (logicznie

dzielona pamięć), jak i do zbudowania (brak fizycznie dzielonej pamięci). Chociaż ten

system jest rzeczywiście łatwy do programowania i budowy, to jednak w wielu

zastosowaniach marnie działa wskutek miotania się stron tam i z powrotem po sieci.

Zachowanie to jest podobne do szamotania w jednoprocesorowych systemach z pamięcią

wirtualną. W ostatnich latach prowadzono intensywne badania nad zwiększeniem

wydajności takich systemów o rozproszonej pamięci dzielonej. Odkryto przy tym wiele

nowych technik. Wszystkie one mają na celu zminimalizowanie ruchu w sieci i

zredukowanie zwłoki między chwilą wykonania zamówienia pamięci a chwilą, w której

zostaje ono spełnione.

Jedno z podejść polega na zrezygnowaniu z dzielenia całej przestrzeni adresowej na rzecz

dzielenia wybranej jej części, a mianowicie tych zmiennych i struktur danych, które

muszą być używane przez więcej niż jeden proces. W tym modelu zamiast myśleć o

każdej maszynie, jako o mającej bezpośredni dostęp do zwykłej pamięci, rozważa się

użycie przez nią zbioru dzielonych zmiennych, co daje wyższy poziom abstrakcji.

Strategia ta nie tylko znacznie redukuje ilość danych do dzielenia, lecz również w

większości przypadków udostępnia znaczne ilości informacji o dzielonych danych, takich

jak ich typy, co może pomagać w optymalizowaniu implementacji. Jedną z możliwych

optymalizacji jest zwielokrotnienie zmiennych dzielonych na wielu maszynach. Stosując

dzielenie zwielokrotnionych zmiennych zamiast całych stron, problem symulacji

multiprocesora zredukowano do zagadnienia utrzymywania spójności wielu kopii zbioru

danych strukturalnych typów. Czytanie może się odbywać lokalnie, bez ruchu w sieci, a

do zapisywania można wykorzystać protokół aktualizacji wielu kopii. Protokoły takie są w

powszechnym użyciu w systemach rozproszonych baz danych, więc pomysły z tamtego

obszaru mogą znaleźć tu zastosowanie.

Dalszym krokiem w kierunku strukturalizacji przestrzeni adresowej jest dzielenie

obudowanych typów danych, nazywanych często obiektami (ang. objects ). Różnią się one

od zmiennych dzielonych tym, że każdy obiekt ma nie tylko dane, lecz również działające

na nich procedury zwane metodami (ang. methods ). Programy mogą manipulować

danymi obiektu tylko za pomocą jego metod. Nie jest dozwolony bezpośredni dostęp do

danych. Taki sposób ograniczania dostępu umożliwia nowe optymalizacje. Wykonywanie

wszystkiego środkami programowymi ma inne zalety i wady niż wykonywanie tego za

pomocą sprzętu stronicującego. Na ogół bardziej ogranicza to programistę, lecz może też

polepszać działanie. Wiele z tych ograniczeń (np. działania na obiektach) uważa się za

dobre obyczaje inżynierii programowania, pożądane jako wewnętrznie poprawne.

W pierwszej kolejności należy przeanalizować kilka rodzajów wieloprocesorów z pamięcią

dzieloną, rozpoczynając od najprostszych, działających na pojedynczej szynie, a kończąc

na zaawansowanych, o bardzo pomysłowych rozwiązaniach pamięci podręcznych.

Poznanie tych maszyn jest ważne dla zrozumienia rozproszonej pamięci dzielonej (DSM),

ponieważ większość prac nad pamięcią DSM było inspirowanych postępami w

architekturze wieloprocesorów. Co więcej, wiele z tych algorytmów jest tak do siebie

podobnych, że czasami trudno jest powiedzieć, czy zaawansowana maszyna jest

wieloprocesorem, czy multikomputerem używającym sprzętowej realizacji rozproszonej

pamięci dzielonej.

2.1. Pamięć układowa

Chociaż większość komputerów ma pamięć zewnętrzna, istnieją również

samowystarczalne układy zawierające jednostkę centralną wraz z cały pamięcią.

Produkuje się miliony takich układów i montuje się je w samochodach, w przyrządach, a

nawet w zabawkach. W projekcie tego rodzaju część układu stanowiąca jednostkę

centralną (CPU) jest bezpośrednio połączona liniami adresów i liniami danych z częścią

stanowiącą pamięć ( RYS.2a. ).

Rys. 2. Pamięć układowa: a) komputer jednoukładowy, b) hipotetyczny wieloprocesor z

pamięcią dzieloną.

Możliwe jest do wyobrażenia proste rozwinięcie tego układu z wieloma jednostkami

centralnymi bezpośrednio dzielącymi tę samą pamięć ( RYS.2b. ). Choć zbudowanie takiego

układu jest możliwe, byłby on skomplikowany, drogi i bardzo nietypowy. Skonstruowanie

w ten sposób jednoukładowego wieloprocesora zawierającego np. 100 jednostek

centralnych mających dostęp do tej samej pamięci byłoby z kolei niemożliwe z przyczyn

inżynierskich. Konieczne było więc znalezienie innego podejścia do dzielenia pamięci.

2.2. Wieloprocesory szynowe

W przypadku pamięci układowej połączenie między jednostką centralną a pamięcią jest

wiązką równoległych przewodów, z których część służy do przenoszenia adresu, pod

którym jednostka centralna chce czytać lub pisać, inne są wykorzystywane do wysyłania

lub odbierania danych, a reszta - do nadzorowania przesłań. Tego rodzaju zbiór

przewodów zwie się szyną (ang. bus ). Tutaj szyna jest wewnątrz układu, lecz w wielu

systemach występują szyny zewnętrzne, które służą do łączenia płyt obwodów

drukowanych zawierających jednostki centralne, pamięci oraz kontrolery wejścia-wyjścia.

W komputerze stołowym szyna jest zazwyczaj wytrawiona na płycie głównej (płycie

macierzystej), na której jest zamocowana jednostka centralna i część pamięci, i do której

Systemy wieloprocesorowe z pamiecia dzieloną - Bartłomiej Zieliński(1).pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: