n Równoległy system komputerowy – zbiór co najmniej dwóch procesorów zdolnych do wspólnego rozwiązywania złożonego zadania obliczeniowego, na ogół o tej samej architekturze i pod kontrolą tego samego SO.
n Rozproszony system komputerowy – zbiór samodzielnych komputerów połączonych za pomocą sieci, z rozproszonym oprogramowaniem systemowym, często o różnych architekturach i systemach operacyjnych.
n pamięć współdzielona- wszzystkie procesory mają dostęp do tej sąmej pamięci, która jest współdzielona – dysponują tą samą przestrzenią adresową. Komunikacja między procesorami może odbywać się poprzez pamięć, w konsekwencji jest łatwa i szybka.- Co jeśli dwa procesory chcą jednocześnie pisać w to samo miejsce pamięci? Co jeśli jeden pisze, a drugi w tej samej chwili czyta? Trudności z synchronizacją.- Problemy natury technologicznej – potrzebne specjalne układy (krosownice) pozwalające łączyć jednocześnie wiele procesorów z jedną pamięcią. Trudności te rosną drastycznie dla nproc>8. Dla nproc>20 niewykonalne praktycznie.- Przy większej liczbie procesorów pogarsza się też wydajność ze względu na konieczność synchronizacji. Dostęp do pamięci nie może być prawdziwie jednoczesny, zawsze wszystkie procesory oprócz jednego muszą chwilę poczekać.- Bardzo wygodne dla programisty, koszmar dla inżyniera projektującego komputer.Droga
n pamięć rozproszona - każdy procesor dysponuje swoją własną pamięcią (przestrzenią adresową).- Procesor n „nie wie” co dzieje się w pamięci procesora m, dla m ≠ n.- Względnie łatwe do zbudowania dla inżyniera – bierze się oddzielne komputery, każdy ze swoją pamięcią i łączy się razem szybkim łączem. -Trudne dla programisty – jak sprawić, żeby procesory mogły się komunikować, wymieniać dane? Potrzebny jest sposób na wymianęwiadomości.
n Skoro nie mogą zajrzeć do nieswojej pamięci, procesory muszą wymieniać wiadomości za pośrednictwem łącza (sieci), którym są połączone.- Programista musi to uwzględnić w sposób jawny w programie.- N procesorów, gdyby połączyć każdy z każdym, to mamy N(N-1)/2 ≈ N2/2 połączeń– niepraktyczne dla większych N, dlatego łączymy tylko wybrane procesory – topologie.
n rozproszona pamięć współdzielona- Próbuje połączyć zalety obydwu modeli pamięci (łatwość budowy DM i łatwość oprogramowania SM).n Fizycznie mamy do czynienia z pamięcią rozproszoną, a pamięć współdzieloną emuluje się, najczęściej na poziomie systemu operacyjnego, jako uogólnienie pamięci wirtualnej.n Wszystkie procesory widzą jedną logiczną przestrzeń adresową, dostęp do tych jej części, które są nielokalne ("leżą na innych procesorach") realizowany jest za pomocą sieci, w sposób niejawny, tj. program nie wie, że transmisja taka ma miejsce.-Wada: wydajność drastycznie spada, jeśli lokalność jest słaba.
n Dekompozycja problemu - rozdzielić zadanie obliczeniowe tak, aby nadawało się do przetwarzania równoległego.
dekompozycja trywialna,dekompozycja funkcjonalna,dekompozycja danych:
• geometryczna,• rozproszona przestrzenna (ssd),• farma zadań.
Dekompozycja trywialna - występuje, gdy da się podzielić dane na niezależne
od siebie części, z których każdą da się potraktować tym samym algorytmem.
n Każdy procesor dostaje porcję danych do przetworzenia i zajmuje się nią.
Brak zależności brak komunikacji (chyba że rozesłanie i zebraniedanych).
n Przykład: zwiększanie jasności bitmapy, obliczanie sił działających między
atomami z podziałem składowe-sił-naprocesory. numeryczne obliczanie całki.
Dekompozycja funkcjonalna - Nie dzielimy danych, tylko algorytm.
n Dzielimy zadanie na niezależne sekcje, każdy procesor zajmuje się jedną sekcją,wyniki z sekcji n idą do sekcji n +1, a sekcja n może zajmować się kolejnymi danymi.n Przetwarzanie taśmowe (pipelining), n Nie da się bardziej zrównoleglić niż wynosiliczba sekcji.n Ale można bardziej pracochłonne sekcje podzielić na podsekcje albo przydzielić kilka procesorów do jednej sekcji (jeśli np. samą sekcjęmożna zdekomponować trywialnie
Dekompozycja danych - Dzielimy dane na procesory, podobnie jak w dekompozycji trywialnej, ale tym razem mogą występować zależności między danymi przypisanymi różnym procesorom.n Zależności potrzeba komunikacji.n Bardzo często występująca dekompozycja.n Trzy często spotykane odmiany:
-->Dekompozycja danych-geometryczna - n Każdy procesor dostaje porcję danych do przetworzenia, porcje określamy dokonując geometrycznego podziału dziedziny. n Mogą występować problemy z bilansowaniem pracy – trzeba pilnować, żeby żaden procesor nie został bez pracy .
-->Rozproszona dekompozycja przestrzenna - Dzielimy dane na małe ziarna ("kawałki pracy").n Każdemu CPU przydzielamy losowo trochę ziaren do obliczeń.n ziarna muszą być bardzo małe tak by każdy CPU dostał wiele ziaren.
-->Task-farm - Blisko związane z koncepcją master-slave. n Dzielimy procesory na dwie grupy: nadzorców i robotników, w najprostszym przypadku jest tylko jeden nadzorca (master) i robotnicy (slaves). n Nadzorca dzieli zadanie na ziarna i wrzuca je do puli ziaren do przetworzenia. n Każdy z robotników, do skutku: • prosi o przydzielenie ziarna ,• otrzymuje ziarno,• przetwarza ziarno,• wysyła do dobiorcy n Odbiorca składa wyniki w całość. Odbiorcą często jest nadzorca, żeby nie nudził się n Przestojów nie ma w ogóle, najwyżej na końcu pracy, gdy brakuje ziaren.n Niestety nie może być zależności między ziarnami – robotnicy nie mogą się komunikować.
n Przyspieszenie, S(N), mówi nam ile razy szybciej program równoległy działa na N rocesorach w porównaniu z wersją szeregową. Oczywiście przyspieszenie rośnie wraz z N (poza przypadkami patologicznymi). Wgląd w to, w jakim stopniu zrównoleglony jest program daje efektywność, E(N). - "przyspieszeniem odniesionym do liczby procesorów, na których to przyspieszenie uzyskano".
n Prawo Amdahla - Jeśli można zrównoleglić F-tą część programu, pozostawiając (1- F)-tą część szeregową, to maksymalne przyspieszenie wyniesie 1/(1- F). Prawo Amdahla po cichu zakłada, że ułamek zrównoleglenia, F, nie zależy od N i jest stały. W rzeczywistości często jest tak, że im więcej procesorów, tym większą część programu można zrównoleglić, czyli F rośnie z N.: najczęściej ułamek zrównoleglenia, F, zależy od rozmiaru problemu, x, tj. F rośnie wraz z x ("duże problemy lepiej się zrównoleglają")...
inf4