Architektury równoległe

architektura równoległa: architektura składająca się z wielu procesorów wykonujących jednocześnie (równoległe) obliczenia, np. systemy wielordzeniowe, wieloprocesorowe. Cel: zwiększenie wydajności (wykonywanie wielu zadań na raz), funkcjonalności, wysoka dostępność (awaria jednego węzła nie ma wpływu na pozostałe).

Podział architektur równoległych:

• ze względu na mechanizm sterowania:

  • SIMD (Single Instruction, Multiple Data): przetwarzanie wielu strumieni danych w oparciu o jeden strumień rozkazów. (ten sam rozkaz może być wykonany jednocześnie wiele razy w krótkim czasie)

  • MIMD (Multiple Instruction, Multiple Data): przetwarzanie równoległe zachodzi zarówno na poziomie danych, jak I instrukcji. Procesory pracują niezależnie i asynchronicznie: mogą wykonywać różne instrukcje na różnych danych. (metoda standardowa)

• ze względu na organizację przestrzeni adresowej:

  • message-passing: każdy procesor ma własną pamięć, do której dostęp ma tylko on. Procesory komunikują się ze sobą, wymieniając wiadomości, w których wysyłają dane potrzebne do wykonania obliczeń. (wady: mała efektywność, skalowalność, utrudnienie programowania – trzeba zaprogramować komunikację między procesorami

  • architektura ze współdzieloną pamięcią:

    • UMA: architektury jednorodnego dostępu do pamięci (z punktu widzenia węzła obliczeniowego dostęp do każdego bloku pamięci zabiera średnio identyczną ilość czasu)

    • NUMA: dostęp do pamięci jest zhierarchizowany (pamięć bliska i daleka, nowocześniejszy sposób)

• ze względu na charakter sieci połączeniowej:

  • statyczne

    • sieć pełna (każdy z każdym)
      zalety: niezawodna, brak kolizji, przesył wieloma ścieżkami
      wady: wysoki koszt, duża ilość kabla

    • typu gwiazda (wszystkie z jednym)
      zalety: duża przepustowość, wydajność, łatwa lokalizacja uszkodzeń, łatwa rozbudowa
      wady: duża ilość kabli (więc drogo), uszkodzenie elementu centralnego blokuje całą sieć

    • typu magistrala (o----o----o----o----o)
      zalety: mała ilość kabla, brak dodatkowych urządzeń, niska cena, łatwość instalacji, awaria jednego nie pogrąża całej sieci
      wady: trudna lokalizacja usterek, jedna transmisja w momencie, dużo kolizji, mała skalowalność

    • typu ring (jak magistrala, plus ostatni z pierwszym)
      zalety: mało kabla
      wady: usterka jednego pogrąża całą sieć, trudne dołączenie nowych elementów, skomplikowana diagnostyka

    • typu drzewo binarne
      zalety: łatwa konfiguracja, łatwa rozbudowa
      wady: dużo kabli i urządzeń, trudne odszukiwanie błędów

    • typu mesh – krata (urządzenie komunikuje się z urządzeniami sąsiadującymi)
      zalety: łatwa do poszerzania, samo-naprawialna, elastyczna
      wady: niska skalowalność, opóźnienia

    • typu hypercube (jak mesh, ale w większej ilości wymiarów)

  • dynamiczne

    • system z przełącznicą krzyżową (cross bar switch)
      najbardziej kosztowny sposób, wykorzystujący sieć elementów przełączających i szyn.
      
      
      
      Przykład sieci bez blokad – połączenie dowolnego procesora z dowolnym modułem pamięci nie blokuje połączeń innych procesorów z innymi modułami. Ilość przełączników jest proporcjonalna do iloczynu ilości procesorów z ilością modułów pamięci. Zwykle ilość modułów jest większa od ilości procesorów, gdyż w przeciwnym przypadku mogłyby się pojawić procesory bez pamięci. Przełącznica krzyżowa jest nieopłacalna przy dużej ilości procesów w systemie.
      Wysoka przepustowość, wysokie koszty.

    • architektura szynowa
      Proste rozwiązanie – procesory podłączone do magistrali, magistrala podłączona do jednej pamięci globalnej. Spadek wydajności może nastąpić przy podłączeniu wielu procesorów – zwiększa się czas oczekiwania na dostęp pamięci. Rozwiązanie – podłączenie do każdego procesora pamięci podręcznej typu cache.
      
      
      
      Niskie koszty, ograniczenia na przepustowość.

    • wielostanowa sieć połączeń
      Kompromis: większa przepustowość niż przy wspólnej magistrali, niższe koszty niż przy przełącznicy krzyżowej.
      Składa się z log(procesorów) stopni. Każdy stopień ma pocesorów/2 elementów przełączających, które mogą działać w trybie prostym lub odwrotnym (zależnie od zmiany bitu).
      
      Sieć omega:
      
      
      
      

• ze względu na ziarnistość procesora (wielkość porcji przetwarzania danych)
  ziarnistość – stosunek obliczeń do przesłań

  • coarse-grain (wiele obliczeń, po nich rzadkie przesłania – ‘load inbalance’)

  • medium-grain

  • fine-grain (niewielkie zadania pod względem kodu i czasu, wiele przesłań – może doprowadzić do nadmiaru przesłań)

Miary Wydajności

• czas wykonania równoległego (Tpar)
  czas pomiędzy momentem rozpoczęcia obliczeń a momentem, w którym ostatni procesor zakończy obliczenia

• przyśpieszenie (S)
  stosunek czasu niezbędnego do rozwiązana procesu z użyciem jednego procesora (Tseq) do czasu potrzebnego do rozwiązania tego samego problemu z wykorzystaniem systemu równoległego o „p” procesorach (Tpar)

  • względne – Tseq jest czasem wykonania algorytmu równoległego na jednym z procesorów systemu wieloprocesowego

  • rzeczywiste – Tseq jest czasem wykonania „najlepszego” algorytmu sekwencyjnego na jednym z procesorów systemu równoległego

  • bezwzględne – Tseq jest czasem wykonania „najlepszego” algorytmu sekwencyjnego na „najlepszym” komputerze sekwencyjnym

• efektywność programu równoległego (E)
  stosunek przyśpieszenie do liczby procesorów

• koszt
  iloczyn równoległego czasu przetwarzania i liczby procesorów

• skalowalność systemu równoległego
  miara zdolności do zwiększenia przyśpieszenia proporcjonalnie do liczby procesorów
  
  System równoległy jest skalowany, jeśli utrzymuje się stalą efektywność przy jednoczesnym zwiększaniu się liczby procesorów oraz rozmiaru problemu. Skalowalność jest miara zdolności do zwiększenia przyspieszenia ze zwiększeniem ilości procesorów. Odzwierciedla ona zdolność systemu równoległego do efektywnego wykorzystania zwiększającej się liczby procesorów.

Amdahl’s Law

Dwie części programu równoległego:

• część sekwencyjna (Pseq), która musi się wykonywać na tylko jednym procesorze

• część równoległa (1-Pseq), która jest wykonywana niezależnie na wielu procesorach

(t1 – czas wykonania sekwencyjnego)

Gustafson Speedup

• czas wykonania program równoległego: Pseq + Ppar = 1, gdzie Pseq to sekwencyjna część programu, a Ppar – równoległa

• czas wykonania sekwencyjnego: Pseq + p*Ppar

• przyśpieszenie: