Programowanie rozproszone i równoległe - PDF

# Programowanie rozproszone i równoległe ## Wykład I - Między innymi na podstawie książki: „Wprowadzenie do obliczeń równoległych" Z. J. Czech - Wydawnictwo Naukowe PWN - Wydanie z 2013 roku - ISBN: 978-83-17290-9 - Piotr Marek Oramus, Programowanie rozproszone i równoległe ## PLAN 1. Histo...

# Programowanie rozproszone i równoległe ## Wykład I - Między innymi na podstawie książki: „Wprowadzenie do obliczeń równoległych" Z. J. Czech - Wydawnictwo Naukowe PWN - Wydanie z 2013 roku - ISBN: 978-83-17290-9 - Piotr Marek Oramus, Programowanie rozproszone i równoległe ## PLAN 1. Historia 2. Przetwarzanie sekwencyjne, współbieżne, równoległe – definicje 3. Architektury systemów 4. Parametry i prawa rządzące tym światem 6. Niebezpieczeństwa! ## Trochę historii ### 1951 – UNIVAC I - Pierwszy na świecie komputer ogólnego przeznaczenia - 1 kflop/s (1000 operacji zmiennoprzecinkowych na sekundę) - The image is of a computer system, most likely UNIVAC I. This is a black and white image of a large server room, in the foreground a white tiled floor. An operator/engineer is stationed at a desk in the middle. The image showcases a number of servers with black and white screens and a number of connected keyboards. In the background, the image continues showcasing more servers and a long hallway or room that's difficult to see. On the right side of the document, there is a close-up image of what appears to be a unit of UNIVAC I in the background. It showcases a large metal cabinet, with the top part showing multiple lights and a panel with a prominent label "Bantingen Bant", likely the name of the manufacturer or a company, that also is written on the servers in the foreground. ### Praca z komputerem | Dekada | Lokalizacja | | :------ | :------------------------------------------------- | | 1960 | Pokój z komputerem | | 1970 | Pokój terminalowy | | 1980 | Własne biurko | | 1990 | Ruchoma | - The image showcases a selection of different types of computers and computer setups prevalent in different decades. On the left side of the image are images of early computers, like the IBM System/360 from 1964, and the Tektronix Terminal from 1972. The Tektronix Terminal is a setup of a CRT display, with a keyboard, both seated on a table. On the right side of the image are images of personal computer models, like ZX-81 and the Amiga 500 from 1987. ZX-81 is a small handheld computer on a table with a keypad. The Amiga 500 is a small desktop computer with a black exterior, on a white desk, with a keyboard and mouse. ### Zestawienie TOP 500 z roku 2024 (czerwiec) 1. **Frontier** - HPE Cray EX235a, AMD Optimized 3rd Generation EPYC 64C 2GHz, AMD Instinct MI250X, Slingshot-11, HPE DOE/SC/Oak Ridge National Laboratory United States – 8 699 904 rdzeni, 1206 Pflop/s, 22.8MW - The image showcases a selection of servers and computing systems that likely represent the Frontier supercomputer from Oak Ridge National Laboratory. The specific models are difficult to decipher. The image showcases a long row of servers, each one made from black metal, with some labels and lights, but no specific details are visible other than the AMD logo that is on the front of every cabinet. All of the servers are in a large room, most likely a server room, where many cables can be seen running on either side of the servers. On the front of every server, is a black-and-white sticker with a compass and text "FRONTIER". On the top of the server, there is a bright yellow beam, visible only in the first 2 servers. The label with a black and white compass has the text "FRONTIER" below it. Two of the servers have labels on it that read "ENERGY" and "AMDA". 2. **Aurora** - HPE Cray EX - Intel Exascale Compute Blade, Xeon CPU Max 9470 52C 2.4GHz, Intel Data Center GPU Max, Slingshot-11, Intel DOE/SC/Argonne National Laboratory United States – 9 264 128 rdzeni, 38.7MW 3. **Eagle** - Microsoft NDv5, Xeon Platinum 8480C 48C 2GHz, NVIDIA H100, NVIDIA Infiniband NDR, Microsoft Azure Microsoft Azure United States - 2 073 600 rdzeni 1997 – 1-2 TFlop/s; 2008 – 1.026 PFlop/s; ### Kraków A.D. 2024. - Akademickie Centrum Komputerowe Cyfronet AGH - The image showcases a computer system, likely one of the systems from the Akademickie Centrum Komputerowe Cyfronet AGH. It is a system with a light blue exterior, with the text "HPE Cray" written in white letters. The image showcases 5 racks, each one containing multiple servers, as the server is one or two shelves high. The servers also have a prominent label "HELIOS" with a background of a solar system and a hand with a pointing finger. The system is in a large room, most likely a server room with yellow lighting and grey tiles on the ground, only visible on the left side of the image. 1. **Helios**. 35 Pflop/s, 75 264 rdzeni CPU, 440 NVIDIA Grace Hopper GH200, 24 akceleratory NVIDIA H100 2. **Athena**. 7,7 Pflop/s 3. **Ares**. CPU: 3,5 Pflop/s + GPU 0,5 Pflop/s 4. **Prometheus**. 2,65 Pflop/s - Na liście TOP 500 (2024 czerwiec) - 55 Helios GPU 30440 TFlop/s - 177 Athena 7710 TFLop/s - 305 Helios CPU 3350 TFlop/s - 442 Ares 3510 Tflop/s - Podane są powyżej wartości Rpeak, a ranking jest wg Rmax. ### I na skalę „domową". - Od dawna każdy procesor zamontowany w PC ma wiele rdzeni. - The image showcases a computer chip. It has two parts. The top part is the zoomed-in view of the chip, with multiple transistors and lines. The bottom image is the complete device, which is a green circuit board, with a connector at the bottom. The green board has numerous components on it. The chip has a bright yellow sticker with the text "1" on it. It also has a text "2" written on the bottom right side of the board. On the top left side of the chip, a portion of text is visible, it seems to read "RP2040 dwurdzeniowy", likely the name of the chip or a brand. - Na obrazku obok: Six-core "Istanbul" Opteron. - Poniżej Raspberry Pi Pico W. - RP2040 dwurdzeniowy ARM Cortex M0+ @133MHz ## Po co przetwarzać z pomocą wielu procesorów? - Liczymy równolegle, bo czasami inaczej się nie da... - Przykład: - Pogoda(X, Y, Z) -> temperatura, ciśnienie, wilgotność, kierunek i siła wiatru - Siatka nad Polską ma 7 350 000 000 komórek elementarnych. - Złożoność obliczeń: 100 operacji zmiennoprzecinkowych / komórkę elementarną - Symulacja: 4 dni z krokiem czasowym 5 minut - Do wykonania: 84 700 000 000 000 operacji zmiennoprzecinkowych - Jeden CPU o wydajności 1GFlop/s wykona rachunki w 10 dni - Zakładamy, że dysponujemy CPU o wydajności 1TFlop/s - Rachunki można teoretycznie zakończyć po 15 minutach, ale: - Do wykonania rachunku potrzeba 350GB pamięci - Dane z RAM do CPU muszą być przesyłane około 1 000 000 000 000 razy/sek. - Biorąc pod uwagę prędkość światła odległość od CPU do RAM to maksymalnie 0.3mm - a dane trzeba by zapisywać w obszarze o rozmiarze jednego atomu.... ## Program sekwencyjny - Program sekwencyjny składa się z jednego ciągu instrukcji. - Przekształcają one dane wejściowe w wyjściowe. - Program taki uruchamiany jest jako proces (*) sekwencyjny i wykonywany jest przez jeden wirtualny, umowny procesor. - W programie sekwencyjnym operacje wykonywane są kolejno po sobie. Aby rozpocząć operację 0i+1 musimy poczekać na zakończenie operacji oi. - The image is of a simple graph, depicting a timeline with four operations. - Ten sam program, ale na innym (wolniejszym) procesorze: - The image is of another simple graph, depicting a timeline with four operations. - (*) aby nie robić zamieszania nie rozróżniamy tu wątków i procesów. ## Program współbieżny - Ze współbieżnością mamy do czynienia, gdy dwie (lub więcej) czynności mogą się dziać w tym samym czasie. Dwie operacje są współbieżne, gdy w trakcie trwania jednej rozpoczęto drugą. - Program współbieżny to taki, w którym problem potrafimy podzielić i realizować w postaci wielu zadań (obliczeniowych), które mogą być realizowane współbieżnie. - Pojedyncze zadanie wykonywane jest sekwencyjne. - The image is of a simple graph, depicting a timeline with three tasks and their operations. ## Program współbieżny a synchronizacja - Generalnie, w programie współbieżnym nie sposób ustalić kiedy operacje należące do różnych zadań będą wykonane. Nie wiadomo, która operacja jednego zadania poprzedzi rozpoczęcie realizacji operacji z innego zadania. - Procesy współbieżne działają asynchronicznie. - Jeśli nam to przeszkadza, to do programu trzeba dodać instrukcje synchronizacji. Synchronizacja jednak kosztuje! - The image is of a simple graph, depicting a timeline and the three tasks. ## Koszt synchronizacji - Synchronizacja wykonania programu współbieżnego oznacza jakąś formę komunikacji pomiędzy zadaniami. Jakie będą tego skutki? - Załóżmy, że operacja trzecia może się zacząć dopiero, gdy w każdym zadaniu dwie wcześniejsze już się zakończyły: - Asynchronicznie: The image is of a simple graph, depicting a timeline and the three tasks. - Z synchronizacją: The image is of a simple graph, depicting a timeline and the three tasks. - Piotr Marek Oramus, Programowanie rozproszone i równolegle - Czas ## Program współbieżny a zasoby - Program współbieżny może zostać uruchomiony w środowisku, w którym liczba rzeczywistych procesorów(*) jest mniejsza od liczby potrzebnych procesorów wirtualnych (liczby procesów sekwencyjnych do wykonania). - W szczególności, komputer, który może w danej chwili wykonywać tylko jeden proces nazywany jest maszyną sekwencyjną. - Braki zasobów sprzętowych pokrywamy poprzez przeplot: - The image is of a simple graph, depicting a timeline and the three tasks. - (*) - rdzeni rzeczywistych czy wirtualnych ## Program współbieżny, równoległy i rozproszony - Program współbieżny (concurrent program) - napisany jest tak, że jego procesy mogą być wykonywane w tym samym czasie. Dodatkowo program ten musi rozwiązać problemy synchronizacji i komunikacji pomiędzy procesami. Wynik działania powinien być taki sam jak dla programu sekwencyjnego. - Program równoległy (parallel program) to program współbieżny plus zasoby sprzętowe, które umożliwiają równoległe (jednoczesne) wykonywanie procesów współbieżnych. - Program rozproszony (distributed program) to program współbieżny, który używa zasobów wielu komputerów, czyli procesory są w tym przypadku rozproszone. ## Wykonanie programu współbieżnego - Przeplot rozwiązuje problem braku zasobów, ale sam z siebie generuje dodatkowe koszty związane z przełączeniem kontekstu. - Aby zminimalizować liczbę przełączeń kontekstu systemy operacyjne przeplot wykonują co pewien czas (podział czasu). Procesy otrzymują dostęp do procesora na pewien czas. W trakcie trwania jednego takiego okresu, proces wykonuje wiele operacji. - System operacyjny musi szeregować zadania różnych programów, obsługiwać przerwania i uwzględniać priorytety procesów. ## Procesy a wątki - Proces to działający program. - Proces otrzymuje od systemu operacyjnego zasoby: pamięć, uchwyty do plików, gniazda sieciowe... - Instrukcje procesu wykonuje co najmniej jeden wątek. - Wątki procesu mają dostęp do zasobów procesu. ## Architektury maszyn równoległych ### Taksonomia Flynna [1966] | Strumień Instrukcji\Strumień danych | Single data | Multiple data | | :--------------------------------- | :------------------ | :-------------------- | | Single instruction | SISD | SIMD | | | Architektura Von Neumann | Procesor wektorowy | | | | Procesor macierzowy | | Multiple instruction | MISD | MIMD | | | sf: systemy uczące się | Multikomputer | | | | Sieć komputerowa | - The image showcases a table with a breakdown of different types of computer architectures. Each column represents the number of data streams, the number of instruction streams, and each row represents the type of architecture based on the data stream and instruction stream. The image also showcases the architecture of the computer, like a single-core computer, multiple-core computer, etc. ``` for ( i = 0; i < size; i++ ) C[ i ] = A[ i ] + B[ i ]; for (j = 0; j < size; j++ ) D[j] = E[ j ] / F[j]; ``` ### Maszyny typu Multiple Instractions Multiple Data (MIMD) | | Shared Memory (SM) | Distributed Memory (DM) | | :----------------------------------------------------------------------------- | :--------------------------------------------------------------------------------------------------------------------------------------- | :---------------------------------------------------------------------------------------------------------------------------------- | | | Pamięć wspólna, współdzielona, globalna | Pamięć lokalna, rozproszona | | | Wszystkie procesory mają dostęp do wspólnej przestrzeni adresowej. | To programista musi podzielić dane. Aby oczytać daną z pamięci trzeba znać adres komórki pamięci i wiedzieć gdzie ta pamięć jest... | | | Od dawna każdy PC jest maszyną tego typu. | | | | Typowo: komputer z wielordzeniowym (i) procesorem(ami) | Rozwój sieci komputerowych w latach 90-tych XX wieku wyprzedził rozwój procesorów. | | | | Typowo: klaster obliczeniowy. | - The image showcases a table with a comparison of MIMD architectures. Different characteristics of the architectures are described. - Są jeszcze rozproszone maszyny z pamięcią wspólną. Rozwiązania sprzętowe (np. SGI Origin 2000) lub programowe (vSMP) - The image showcases a diagram of a computer cluster with multiple processors connected to a shared memory. The diagram features 6 CPUs, each one with its own memory space, connected to shared memory. - Hierarchiczna Pamięć Współdzielona – czas dostępu do pamięci zależy od lokalizacji pamięci. - Problem dostępu do danych. Tak naprawdę, to już jeden węzeł (komputer) stanowi problem, bo to: - The image showcases a diagram of a computer with 4 CPUs and one shared memory. - w środku wygląda jakoś tak: - The image showcases a diagram with 10 CPUs, each one with its own level 1 cache (iL1 & dL1), level 2 cache (L2) and level 3 cache (L3). All level 3 caches are connected to one shared memory. ## WNIOSKI 1. Przetwarzamy równolegle, bo czasami inaczej się nie da 2. To co robił jeden procesor ma teraz robić ich wiele - ale to oznacza konieczność wymiany informacji, a to z kolei trwa. W sumie, w przypadku równoległym potrzeba większej mocy obliczeniowej niż w przypadku sekwencyjnym aby „odrobić" czas zajmowany na komunikację. Przetwarzanie równoległe zawsze generuje narzuty. Im mniejsze tym lepiej. 3. Zwiększenie udziału kodu równoległego oznacza często zmianę algorytmu. ## Definicje - **Równoległość procesowa** – np. supermarket/bank i wiele kas – wykonywanie niezależnych zadań z kolejki przez wiele procesorów - **Równoległość tablicowa (array parallelism)** – musztra wojskowa – przetwarzanie multimediów - **Równoległość potokowa (pipelining)** – taśma produkcyjna, budowa i zespoły pracowników - **Przetwarzanie rozproszone** – dziedzina wiedzy o systemach zawierających więcej niż jeden element przetwarzający, element przechowujący, proces współbieżny lub działający program, które są ściśle lub luźno ze sobą powiązane - **System równoległy** – to ściśle powiązany system rozproszony. - W przetwarzaniu równoległym zasoby systemu są podporządkowane celowi w postaci rozwiązania jednego problemu - System rozproszony może pracować nad kilkoma problemami równocześnie. - System rozproszony -> sieć telefoniczna - System równoległy -> orkiestra ## Niebezpieczeństwa - The image showcases a diagram with two CPUs with a shared memory. The CPUs perform an operation with the same variable, but in different orders. The result is that the value of the variable is incorrect. - The image showcases a diagram with two CPUs with a shared memory. The CPUs perform an operation with the same variable, but in different orders and read and write to a local register. The result is that the value of the variable is incorrect. - The image showcases a diagram with two CPUs with a shared memory. The CPUs perform an operation with the same variable, but in different orders and read and write to a local register. The result is that the value of the variable is incorrect. ## Poprawność programu współbieżnego - Poprawność programu współbieżnego = poprawność programu sekwencyjnego + bezpieczeństwo + żywotność - Poprawność programu sekwencyjnego: - {p}S{q} - S - to program, transformuje dane wejściowe w wyjściowe - p - warunek wstępny (precondition) - ten warunek określa poprawność danych wejściowych - q - warunek końcowy (postcondition) – ten warunek określa poprawność wyniku. - Poprawność częściowa (partial correctness) – każde kończące się wykonanie programu S z danymi zgodnymi z p prowadzi do danych spełniających q. - Warunek stopu (stop condition) – każde wykonanie programu S dla dowolnych danych zgodnych z p, się kończy. Generalnie, trzeba udowodnić, że iteracje (pętle) w programie się skończą. - Poprawność pełna (total correctness) - poprawność częściowa + warunek stopu. - Program współbieżny składa się z zadań, które realizowane są sekwencyjnie. Każde z zadań musi być w pełni poprawne (1). - Zadania się ze sobą komunikują. Komunikacja nigdy (przy dowolnej realizacji współbieżnych zadań) nie może złamać warunków dotyczących bezpieczeństwa (2). Jednocześnie, dowolne wykonanie współbieżnych zadań musi „w końcu" doprowadzić do spełnienia warunków żywotności (3). - Przykłady warunków bezpieczeństwa: stan konta w danej chwili zmienia tylko jedno zadanie; w trakcie używania konta przez jedno zadanie, inne do stanu konta nie mają dostępu - Przykład warunku żywotności: każde zadanie się zakończy - Poprawność programu współbieżnego = (1) + (2) + (3) - (1) - pełna poprawność zadań - (2) - bezpieczeństwo - (3) - żywotność - Problemy z (2) i (3) wynikają z komunikacji pomiędzy zadaniami. - Bezpieczeństwo chroni przed czymś złym. - Żywotność obiecuje, że stanie się coś dobrego. ## Sekcja krytyczna - Aby zagwarantować bezpieczeństwo aplikacji współbieżnej, działającej na maszynie z pamięcią wspólną, muszą istnieć mechanizmy wzajemnego wykluczania się zadań w dostępie do zasobów. - Zasób to np.: zmienna, plik, terminal, połączenie sieciowe... - Wykluczanie oznacza, że danego zasobu(ów) może jednocześnie używać tylko jedno zadanie. - Sekcja krytyczna to fragment zadania, w którym używamy problematycznego zasobu(ów). - Tylko jedno zadanie może realizować sekcję krytyczną. - UWAGA: to jest pewne uproszenie, bo różne zasoby mogą być chronione niezależnymi od siebie sekcjami krytycznymi. Dużo zależy od tego co musimy chronić. ## Semafor - Semafor s to struktura danych posiadająca (co najmniej) pola - s.w - nieujemna liczba całkowita - s. q - zbiór zadań (kolejka) - The image showcases a code snippet with a description of the semafor data structure in Ada. ``` type semafor is record w: natural q: kolejka end record; ``` - Opuszczenie semafora binarnego s przez zadanie z: ``` if s.w > 0 then s.w := s.w - 1 else zatrzymaj zadanie z do s.q dodaj z end if ``` - Podniesienie semafora s o wartość n przez zadanie z: ``` if s.q zawiera zadanie then zz := pobierz i usuń zadanie z s.q wznów zadanie zz else s.w := s.w + 1 end if ``` - Można jeszcze spotkać operacje oczekiwania na zero. Zadania są przez nią zatrzymywane do chwili osiągnięcia przez s.w wartości zero. - Poza semaforami binarnymi są i uogólnione. s.w może przyjmować wartości nie większe od N, gdzie (N>1). Operacje podniesienia/opuszczenia semafora mogą żądać zmiany s.w o wartości z przedziału od 1 do N. - Oznaczenia: - Opuszczenie semafora o n: s.down( n ) - Podniesienie semafora o n:s.up ( n ) - Ustawienie wartości początkowej licznika s.w na n: s.set( n ) - Liczba s.w nazywana jest także liczbą pozwoleń. ## Sekcja krytyczna - przykład - The image showcases a code snippet with a description of use cases semafor. ``` s: semafor stankonta: int s.set( 1 ) stankonta := 200 task Z1, Z2; task body Z1 is begin cena: int cena := 100 s.down( 1 ) if (stankonta >= cena) then stanKonta := stanKonta - cena end if s.up( 1 ) end Z1 ---- task body Z2 is begin cena: int cena := 150 s.down( 1 ) if (stankonta >= cena) then stankonta := stankonta - cena end if s.up( 1 ) end Z2 ``` ## Sekcja krytyczna - problemy - Nieumiejętne stosowanie sekcji krytycznych może doprowadzić do problemów z programem współbieżnym: - **Blokada** - zadanie zostało wstrzymane, ale nigdy nie obudzone, czyli się nie zakończy. - **Zakleszczenie** - blokada, która jest wynikiem tego, że zadanie, które może inne obudzić, samo zostało wstrzymane. Zakleszczenie to blokada wielu zadań. - **Zagłodzenie** - brak dostępu do wymaganego zasobu. Generalnie, zasób jest wprawdzie przydzielany, ale polityka przydziału nie gwarantuje, że każdemu z zadań dostęp ostatecznie zostanie przyznany. ## Uczciwość - Aby zadanie doczekało się szczęśliwie dostępu do wymaganego zasobu potrzebna jest uczciwość w zarządzaniu dostępem. - Uczciwość słaba: proces, który nieprzerwanie zgłasza żądanie zostanie kiedyś obsłużony. - Uczciwość silna: proces, który nieskończenie wiele razy zgłasza żądanie zostanie kiedyś obsłużony. - Różnica jest subtelna. Niech przykładowe zadanie zgłasza żądanie dostępu, ale zamiast się zatrzymać w przypadku odmowy, podejmuje inne działania. W przypadku uczciwości słabej nawet nieskończona liczba powtórzeń takiego działania nie gwarantuje, że zadanie otrzyma dostęp. W przypadku uczciwości silnej sukces kiedyś jednak będzie. ## Monitor - Monitor to konstrukcja wyższego poziomu od semafora. - Monitor podobnie jak semafor gwarantuje wzajemne wykluczanie: tylko jeden proces może być aktywny wewnątrz procedury monitora. - Dodatkowo monitor posiada zmienne warunków, na których operuje się za pomocą: - wait(a) – wstrzymuje proces, który wykonywał procedurę monitora i odblokowuje monitor. Proces trafia do kolejki związanej z warunkiem a, który jeszcze nie nastąpił i to spowodowało wykonanie wait. - signal(a) – inny proces tą operacją uwalnia proces z kolejki powiązanej z warunkiem a. Operacja signal wywoływana jest, gdy warunek jest już spełniony. Uwaga: uwolniony proces nie może rozpocząć pracy tak długo jak inny proces jest wciąż aktywny wewnątrz monitora. ## Monitor luzem - The image showcases an example of a monitor system. It features 2 procedures, a print operation and an update operation. ``` monitor wyświetlaj_dane is liczba: int liczba_dostępna: bool liczba_dostępna := false procedure wyświetl_raz() is begin loop if ! liczba_dostępna then ; else break loop end if end loop print liczba liczba_dostępna := false end procedure ustaw( v: int ) is begin liczba := v liczba_dostępna := true end ``` ## Monitor z warunkiem - The image showcases an example of a monitor system that uses a condition. The monitor contains two procedures: "wyświetl_raz()" that prints the current value of an integer variable, and "ustaw()" that sets the value of the variable to a new value. The monitor also has a condition called "brak danych" that is used to indicate when the variable has not been set yet. ``` monitor wyświetlaj_dane is liczba: int liczba_dostępna: bool brak_danych: warunek liczba_dostępna := false procedure wyświetl_raz() is begin loop if ! liczba_dostępna then wait( brak_danych ) else break loop end if end loop print liczba liczba_dostępna := false end procedure ustaw( v: int ) is begin liczba := v liczba_dostępna := true signal( brak_danych ) end ``` ## Parametry - Lokalność - Granulacja (program grubo/drobno-ziarnisty) - Niezbalansowanie obciążenia systemu w procentach: ``` L = 100 Σ(Tmax - T) / Рттах ``` - Determinizm - Przyspieszenie: ``` S(n, P) = T(n, 1) / T(n, P) ``` - Podając przyspieszenie trzeba uwzględniać algorytm !!!! - Czy przyspieszenie może spełniać nierówność ? ``` S(n, P) = T(n, 1) / T(n, P) > P ``` - czyli, czy przyspieszenie może być większe od ilości użytych procesorów? - Efektywność / sprawność programu równoległego ``` η(η, P) = S(n, P) / P = T(n, 1) / PT(n, P) ``` - Lub uwzględniając czas obliczeń i dodatkowy czas (narzut!) potrzebny na komunikację w wersji równoległej ``` η(η, P) = Tc(n) / (Tc(n) + Ta(n, P)) = 1 / (1 + Ta(n,P) / Tc(n)) ``` ## Prawa - Program składa się z części, która musi być sekwencyjna i równoległej. - The image showcases an equation for the execution time of a program, that contains a sequential part and a parallel part. ``` T(n, P) = β(n)T(n, 1) + (1 – β(η))T(η, 1) / P ``` - **Prawo Amdahla** (przyspieszenie): ``` S(n, P) = T(n, 1) / T(n, P) = β(n) + 1-β(n) / P ``` - czyli: ``` limp→∞S(n, P) = 1 / β(η) ``` - Czy jest tragicznie czy tylko źle ? ``` limp→∞S(n,P) = 1 / β(n) ``` - Często część sekwencyjna jest stała i nie zależy od n lub rośnie z n wolniej niż część, którą można już zrównoleglać. - **Wniosek: duże maszyny są dla dużych obliczeń!** - **Prawo Gustafson-a [1988]** ``` S(n, P) = (To + Tr(n, 1)) / (To + Tr(n, P)) ``` - Jeśli Tr(n, P) rośnie z n a maleje z P to każdą efektywność można uzyskać poprzez zwiększenie problemu - Czas wykonywania części sekwencyjnej nie zależy od rozmiaru problemu (n) i jest stały - **Prawo Gustafson-a inaczej** ``` S(n, P) ≤ P + (1 − P)s ``` - S – udział sekwencyjnego czasu w całym czasie wykonania aplikacji równoległej - **Porównanie praw Amdahl'a i Gustawson'a** - The image showcases a diagram with two timelines and three different configurations of the program. - **Porównanie praw Amdahl'a i Gustawson'a** - The image showcases a diagram with two timelines and six different configurations of the program. ## WNIOSKI 1. Przetwarzamy równolegle, bo czasami inaczej się nie da 2. To co robił jeden procesor ma teraz robić ich wiele - ale to oznacza konieczność wymiany informacji , a to z kolei trwa. W sumie, w przypadku równoległym potrzeba większej mocy obliczeniowej niż w przypadku sekwencyjnym aby „odrobić" czas zajmowany na komunikację. Przetwarzanie równoległe zawsze generuje narzuty. Im mniejsze tym lepiej. 3. Zwiększenie udziału kodu równoległego oznacza często zmianę algorytmu. 4. Nie ma ucieczki przed przetwarzaniem równoległym 5. Istnieje wiele technologii, ale efektywne ich użycie wymaga zastosowania odpowiedniego sposobu pisania programu. ## Maksymalizacja wydajności - Dlaczego producenci sprzedają nam procesory z wieloma rdzeniami zamiast szybkich jednostek o jednym rdzeniu ? - P = C f V^2 - gdzie: - P - wydzielana moc przez pewien typ procesora - C - współczynnik proporcjonalności (tam siedzi liczba tranzystorów) - f - częstotliwość taktowania - V - napięcie - tylko, że: V = F(f) i gdy częstotliwość rośnie to napięcie także musi ## WNIOSKI 1. Przetwarzamy równolegle, bo czasami inaczej się nie da 2. To co robił jeden procesor ma teraz robić ich wiele - ale to oznacza konieczność wymiany informacji, a to z kolei trwa. W sumie, w przypadku równoległym potrzeba większej mocy obliczeniowej niż w przypadku sekwencyjnym aby „odrobić" czas zajmowany na komunikację. Przetwarzanie równoległe zawsze generuje narzuty. Im mniejsze tym lepiej. 3. Zwiększenie udziału kodu równoległego oznacza czesto zmianę algorytmu. 4. Nie ma ucieczki przed przetwarzaniem równoległym 5. Istnieje wiele technologii, ale efektywne ich użycie wymaga zastosowania odpowiedniego sposobu pisania programu. ## Niebezpieczeństwa - The image showcases a film strip with the words "FIN" showing the end.