Równoległe maszyny o dostępie swobodnym

Parallel Random Access Machines (PRAM)jest modelem, który jest brany pod uwagę dla większości algorytmów równoległych. W tym przypadku wiele procesorów jest podłączonych do jednego bloku pamięci. Model PRAM zawiera -

• Zestaw podobnego typu procesorów.

• Wszystkie procesory mają wspólną jednostkę pamięci. Procesory mogą komunikować się między sobą tylko za pośrednictwem pamięci współdzielonej.

• Jednostka dostępu do pamięci (MAU) łączy procesory z pojedynczą pamięcią współdzieloną.

Tutaj, n liczba procesorów może wykonywać niezależne operacje na nliczba danych w określonej jednostce czasu. Może to spowodować równoczesny dostęp do tej samej lokalizacji pamięci przez różne procesory.

Aby rozwiązać ten problem, w modelu PRAM narzucono następujące ograniczenia -

• Exclusive Read Exclusive Write (EREW) - Tutaj żadne dwa procesory nie mogą jednocześnie czytać z tej samej lokalizacji pamięci ani zapisywać do niej.

• Exclusive Read Concurrent Write (ERCW) - Tutaj żadne dwa procesory nie mogą czytać z tego samego miejsca w pamięci w tym samym czasie, ale mogą zapisywać w tym samym miejscu w tym samym czasie.

• Concurrent Read Exclusive Write (CREW) - Tutaj wszystkie procesory mogą czytać z tego samego miejsca pamięci w tym samym czasie, ale nie mogą zapisywać w tym samym miejscu pamięci w tym samym czasie.

• Concurrent Read Concurrent Write (CRCW) - Wszystkie procesory mogą w tym samym czasie odczytywać lub zapisywać w tym samym miejscu pamięci.

Istnieje wiele metod implementacji modelu PRAM, ale najważniejsze z nich to -

• Model pamięci współdzielonej
• Model przekazywania wiadomości
• Model równoległy danych

Model pamięci współdzielonej

Kładzie nacisk na pamięć współdzieloną control parallelism niż on data parallelism. W modelu pamięci współdzielonej wiele procesów jest wykonywanych niezależnie na różnych procesorach, ale mają one wspólną przestrzeń pamięci. Z powodu jakiejkolwiek aktywności procesora, jeśli nastąpi jakakolwiek zmiana w jakimkolwiek miejscu pamięci, jest to widoczne dla pozostałych procesorów.

Ponieważ wiele procesorów uzyskuje dostęp do tego samego miejsca w pamięci, może się zdarzyć, że w dowolnym momencie więcej niż jeden procesor uzyskuje dostęp do tego samego miejsca w pamięci. Załóżmy, że jeden czyta to miejsce, a drugi pisze w tym miejscu. Może to spowodować zamieszanie. Aby tego uniknąć, jakiś mechanizm kontrolny, taki jaklock / semaphore, jest wdrażana w celu zapewnienia wzajemnego wykluczenia.

Programowanie pamięci współdzielonej zostało zaimplementowane w następujących -

• Thread libraries- Biblioteka wątków zezwala na wiele wątków sterowania, które działają jednocześnie w tej samej lokalizacji pamięci. Biblioteka wątków zapewnia interfejs obsługujący wielowątkowość poprzez bibliotekę podprogramów. Zawiera podprogramy dla

  • Tworzenie i niszczenie wątków
  • Planowanie wykonania wątku
  • przekazywanie danych i wiadomości między wątkami
  • zapisywanie i przywracanie kontekstów wątków

Przykłady bibliotek wątków obejmują - wątki SolarisTM dla Solaris, wątki POSIX zaimplementowane w Linuksie, wątki Win32 dostępne w Windows NT i Windows 2000 oraz wątki JavaTM jako część standardowego zestawu JavaTM Development Kit (JDK).

• Distributed Shared Memory (DSM) Systems- Systemy DSM tworzą abstrakcję pamięci współdzielonej w luźno połączonej architekturze w celu implementacji programowania pamięci współdzielonej bez wsparcia sprzętowego. Wdrażają standardowe biblioteki i wykorzystują zaawansowane funkcje zarządzania pamięcią na poziomie użytkownika obecne w nowoczesnych systemach operacyjnych. Przykłady obejmują Tread Marks System, Munin, IVY, Shasta, Brazos i Cashmere.

• Program Annotation Packages- Jest to realizowane na architekturach o jednolitej charakterystyce dostępu do pamięci. Najbardziej godnym uwagi przykładem pakietów adnotacji programów jest OpenMP. OpenMP implementuje równoległość funkcjonalną. Skupia się głównie na zrównoleglaniu pętli.

Koncepcja pamięci współdzielonej zapewnia niskopoziomową kontrolę nad systemem pamięci współdzielonej, ale jest ona zwykle żmudna i błędna. Jest bardziej odpowiedni do programowania systemowego niż programowania aplikacji.

Zalety programowania w pamięci współdzielonej

• Globalna przestrzeń adresowa zapewnia przyjazne dla użytkownika podejście do programowania w zakresie pamięci.

• Ze względu na bliskość pamięci do procesora, udostępnianie danych między procesami jest szybkie i jednolite.

• Nie ma potrzeby wyraźnego określania sposobu przekazywania danych między procesami.

• Narzut komunikacji procesu jest znikomy.

• Bardzo łatwo się tego nauczyć.

Wady programowania w pamięci współdzielonej

• Nie jest przenośny.
• Zarządzanie lokalnością danych jest bardzo trudne.

Model przekazywania wiadomości

Przekazywanie komunikatów jest najczęściej stosowanym podejściem programowania równoległego w systemach pamięci rozproszonych. Tutaj programista musi określić równoległość. W tym modelu wszystkie procesory mają własną lokalną jednostkę pamięci i wymieniają dane za pośrednictwem sieci komunikacyjnej.

Procesory używają bibliotek przekazujących komunikaty do komunikacji między sobą. Wiadomość wraz z przesyłanymi danymi zawiera następujące elementy -

• Adres procesora, z którego wysyłana jest wiadomość;

• Początkowy adres lokalizacji pamięci danych w procesorze wysyłającym;

• Rodzaj wysyłanych danych;

• Rozmiar wysyłanych danych;

• Adres procesora, do którego wysyłana jest wiadomość;

• Początkowy adres lokalizacji pamięci dla danych w procesorze odbierającym.

Procesory mogą komunikować się ze sobą za pomocą dowolnej z następujących metod:

• Komunikacja punkt-punkt
• Komunikacja zbiorowa
• Interfejs przekazywania wiadomości

Komunikacja punkt-punkt

Komunikacja punkt-punkt to najprostsza forma przekazywania wiadomości. W tym przypadku wiadomość może zostać wysłana z procesora wysyłającego do procesora odbierającego za pomocą dowolnego z następujących trybów przesyłania -

• Synchronous mode - Następna wiadomość jest wysyłana dopiero po otrzymaniu potwierdzenia, że ​​jej poprzednia wiadomość została dostarczona, aby zachować kolejność wiadomości.

• Asynchronous mode - Aby wysłać kolejną wiadomość, nie jest wymagane otrzymanie potwierdzenia dostarczenia poprzedniej wiadomości.

Komunikacja zbiorowa

Komunikacja zbiorowa obejmuje więcej niż dwa procesory do przekazywania wiadomości. Następujące tryby umożliwiają komunikację zbiorową -

• Barrier - Tryb bariery jest możliwy, jeśli wszystkie procesory uczestniczące w komunikacji uruchamiają określony blok (znany jako barrier block) do przekazywania wiadomości.

• Broadcast - Nadawanie jest dwojakiego rodzaju -

  • One-to-all - Tutaj jeden procesor z pojedynczą operacją wysyła ten sam komunikat do wszystkich innych procesorów.

  • All-to-all - Tutaj wszystkie procesory wysyłają wiadomość do wszystkich innych procesorów.

Nadawane wiadomości mogą być trzech typów -

• Personalized - Unikalne komunikaty są wysyłane do wszystkich innych procesorów docelowych.

• Non-personalized - Wszystkie procesory docelowe otrzymują tę samą wiadomość.

• Reduction - W przypadku rozgłaszania redukcyjnego jeden procesor w grupie zbiera wszystkie komunikaty ze wszystkich innych procesorów w grupie i łączy je w jedną wiadomość, do której mają dostęp wszystkie inne procesory w grupie.

Zalety przekazywania wiadomości

• Zapewnia niskopoziomową kontrolę równoległości;
• Jest przenośny;
• Mniej podatne na błędy;
• Mniejszy narzut związany z równoległą synchronizacją i dystrybucją danych.

Wady przekazywania wiadomości

• W porównaniu z równoległym kodem pamięci współużytkowanej, kod przekazujący komunikaty generalnie wymaga większego narzutu oprogramowania.

Biblioteki przekazywania wiadomości

Istnieje wiele bibliotek przekazujących wiadomości. Tutaj omówimy dwie z najczęściej używanych bibliotek do przekazywania wiadomości -

• Interfejs przekazywania wiadomości (MPI)
• Równoległa maszyna wirtualna (PVM)

Interfejs przekazywania wiadomości (MPI)

Jest to uniwersalny standard zapewniający komunikację między wszystkimi współbieżnymi procesami w rozproszonym systemie pamięci. Większość powszechnie używanych równoległych platform obliczeniowych zapewnia co najmniej jedną implementację interfejsu przekazywania wiadomości. Został zaimplementowany jako zbiór predefiniowanych funkcji o nazwielibrary i mogą być wywoływane z języków takich jak C, C ++, Fortran, itp. MPI są zarówno szybkie, jak i przenośne w porównaniu z innymi bibliotekami przekazującymi komunikaty.

Merits of Message Passing Interface

• Działa tylko na architekturach pamięci współużytkowanej lub architekturach pamięci rozproszonej;

• Każdy procesor ma swoje własne zmienne lokalne;

• W porównaniu z dużymi komputerami z pamięcią współdzieloną, komputery z pamięcią rozproszoną są tańsze.

Demerits of Message Passing Interface

• W przypadku algorytmu równoległego potrzeba więcej zmian w programowaniu;
• Czasami trudne do debugowania; i
• Nie działa dobrze w sieci komunikacyjnej między węzłami.

Równoległa maszyna wirtualna (PVM)

PVM to przenośny system przekazywania wiadomości, przeznaczony do łączenia oddzielnych heterogenicznych maszyn hosta w jedną maszynę wirtualną. Jest to pojedynczy, zarządzalny, równoległy zasób obliczeniowy. Duże problemy obliczeniowe, takie jak badania nadprzewodnictwa, symulacje dynamiki molekularnej i algorytmy macierzowe, można rozwiązać bardziej efektywnie kosztowo, wykorzystując pamięć i łączną moc wielu komputerów. Zarządza wszystkimi trasami komunikatów, konwersją danych, harmonogramowaniem zadań w sieci o niekompatybilnych architekturach komputerowych.

Features of PVM

• Bardzo łatwy w instalacji i konfiguracji;
• Wielu użytkowników może korzystać z PVM w tym samym czasie;
• Jeden użytkownik może wykonywać wiele aplikacji;
• To mała paczka;
• Obsługuje C, C ++, Fortran;
• Dla danego uruchomienia programu PVM, użytkownicy mogą wybrać grupę maszyn;
• To model przekazywania wiadomości,
• Obliczenia oparte na procesach;
• Obsługuje heterogeniczną architekturę.

Programowanie równoległe danych

Głównym celem modelu programowania równoległego danych jest jednoczesne wykonywanie operacji na zbiorze danych. Zestaw danych jest zorganizowany w jakąś strukturę, taką jak tablica, hipersześcian itp. Procesory zbiorowo wykonują operacje na tej samej strukturze danych. Każde zadanie jest wykonywane na innej partycji o tej samej strukturze danych.

Jest to restrykcyjne, ponieważ nie wszystkie algorytmy można określić pod względem równoległości danych. To jest powód, dla którego równoległość danych nie jest uniwersalna.

Języki równoległe danych pomagają określić dekompozycję danych i mapowanie do procesorów. Obejmuje również instrukcje dotyczące dystrybucji danych, które pozwalają programiście mieć kontrolę nad danymi - na przykład, które dane trafią na który procesor - w celu zmniejszenia ilości komunikacji wewnątrz procesorów.