Paralelní výpočtyMiloslav Pekař

Co je paralelní počítání?‡ Software tradičně psán pro sériové

počítání – na jednom počítači s jedním CPU

‡ Problém se rozloží na sérii diskrétních instrukcí

‡ Instrukce prováděny postupně a může být v daný moment prováděna pouze jedna

‡ Paralelní počítání je současné využití více výpočetních prostředků k řešení výpočetního problému – aby mohl být řešen pomocí více CPU

‡ Problém je rozložen do diskrétních částí, které mohou být řešeny současně

‡ Každá další část je rozložena do série instrukcí

‡ Instrukce z každé části jsou prováděny současně na různých CPU

‡ Použití jednoho počítače s více procesory nebo více sesíťovaných počítačů

‡ Dříve považováno za high-end počítání, dnes běžné všude kde je třeba zpracovat velké objemy dat sofistikovanou cestou

Proč?‡ Úspora času a peněz

‡ Paralelní clustery mohou být postaveny z levných součástí

‡ Řešení velkých problémů‡ Množství problémů velkých a komplexních,

neefektivní řešit na jednom počítači, zvláště kvůli omezené paměti

‡ „Grand Challenge“ problémy vyžadující petaflopy výkonu

‡ http://en.wikipedia.org/wiki/Grand_Challenge‡ Webové vyhledávače / databáze vyřizující milióny

operací za vteřinu‡ Současnost

‡ Jeden počítač – jeden úkol, více strojů – více úkolů současně

‡ Např. Access Grid (http://accessgrid.org) poskytuje globální síť pro spolupráci

‡ Využití nemístních prostředků‡ SETI@home – přes 330 000 PC, přes 528

teraflopů‡ Folding@home - přes 340 000 PC, přes 4,2

petaflopů

† Limity sériového počítání‡ Přenosová rychlost

‡ Rychlost sériového počítače je přímo závislá na tom, jak rychle se data pohybují hardwarem

‡ Absolutní limita je rychlost světla (30cm/ns) a měděný drát (9 cm/ns)

‡ Zvyšování rychlosti nezbytně zahrnuje snižování vzdáleností výpočetních elementů

‡ Miniaturizace‡ Limitou je velikost atomu

‡ Ekonomický faktor‡ Je drahé urychlovat jeden počítač,

levnější je spojit více pomalejších počítačů

Klasifikace

‡ Flynn‘s Classical Taxonomy‡ Rozlišuje architektury

multiprocesorových systémů podle toho, jak mohou být klasifikovány ve dvou nezávislých oblastech: instrukce a data

‡ Každá z těchto oblastí může mít pouze dva možné stavy: single nebo multiple

SISD SIMD

MISD MIMD

Single instructionSingle data Single instruction

multiple data

Multiple instructionSingle data

Multiple instructionMultiple data

SISD

‡ Sériový (neparalelní) počítač‡ Single Instruction: pouze jedna

instrukce je zpracovávána na CPU během jednoho cyklu

‡ Single Data: pouze jeden stream dat se využívá jako vstup během jednoho cyklu

‡ Nejstarší a i dnes nejběžnější typ počítače

•Load A

•Load B

Čas •C = A + B

•Store C

•A = B * 2

•Store A

SIMD

‡ Paralelní počítač‡ Single Instruction: všechny CPU

provádí stejnou instrukci během jednoho cyklu

‡ Multiple Data: každá výpočetní jednotka může operovat s jiným datovým elementem

‡ Nejvhodnější pro speciální problémy s vysokým stupněm pravidelnosti – processing obrázků a grafiky

‡ Dva druhy: procesorová pole a vektorové pipelines

•Previous instruction

•Load A(1)

Čas •Load B(1)

•C(1) = A(1) + B(1)

•Store C(1)

•Next instruction

•Previous instruction

•Load A(2)

Čas •Load B(2)

•C(2) = A(2) + B(2)

•Store C(2)

•Next instruction

•P revio us instr uctio n

•Lo ad A(n )

Čas •Lo ad B (n )

•C (n ) = A( n) + B( n)

•St or e C (n )

•Next in str uction

P1 P2 Pn

SIMD

+ = +

MISD

‡ Jeden stream dat je odesílán do více počítacích jednotek

‡ Každá jednotka pracuje nezávisle, podle nezávislých instrukcí

‡ Existovalo jen velmi málo počítačů tohoto typu

‡ Vhodné využití:‡ Vícenásobné filtry operující na jednom

signálu‡ Vícenásobné kryptografické algoritmy

pokoušející se cracknout jednu zakódovanou zprávu

•Previous instruction

•Load A(1)

Čas •C(1) = A(1) * 1

•Store C(1)

•Next instruction

P1 P2 Pn

•Previous instruction

•Load A(2)

Čas •C(2) = A(1) * 2

•Store C(2)

•Next instruction

•Previous instruction

•Load A(n)

Čas •C(n) = A(1) * n

•Store C(n)

•Next instruction

MIMD

‡ Nejběžnější typ paralelního počítače

‡ Multiple Instruction: každý procesor může provádět nezávislý stream instrukcí

‡ Multiple Data: každý procesor může pracovat na svých vlastních datech

‡ Provádění instrukcí může být synchronní ale nemusí, stejně tak deterministické nebo ne

‡ Pozn.: hodně MIMD architektur používá SIMD počítací sub-komponenty

•Previous instruction

•Load A(1)

Čas •Load B(1)

•C(1) = A(1) * B (1)

•Store C(1)

•Next instruction

P1 P2 Pn

•Previous instruction

•Call funcD

Čas •X = Y * Z

•Sum = X^2

•Call sub1(i,j)

•Next instruction

•P revio us instr uctio n

•Do i = 1 :N

Čas •Alph a = w * 3

•Zeta = C (i )

•1 0 con tinu e

•Next in st ruction

Vybrané pojmy‡ Pipelining: rozložení úkolu do kroků

prováděných různými výpočetními jednotkami, vstupy tečou skrz, víceméně jako montážní linka

‡ Synchronizace: koordinace paralelních příkazů v reálném čase, úzce spojeno s komunikací

‡ Často je implementován synchronizační bod, výpočet nemůže pokročit dále, dokud jiný výpočet nedosáhne stejný nebo logicky ekvivalentní bod

‡ Většinou zahrnuje čekání alespoň jednoho výpočtu, proto brzdí a zvyšuje celkovou dobu řešení

‡ Hrubost: poměr počítání a komunikace‡ Hrubý – relativně velké kusy práce jsou

provedeny mezi komunikačními událostmi‡ Jemný – relativně málo výpočetní práce je

provedeno mezi komunikačními událostmi

‡ Zrychlení: poměr sériový čas / paralelní čas

‡ Paralelní overhead: čas potřebný ke koordinaci paralelních výpočtů v kontrastu s konáním užitečné práce

‡ Čas pro nastartování výpočtu‡ Synchronizace‡ Datová komunikace‡ Softwarový overhead – kompilátory, knihovny,

nástroje, OS‡ Čas pro ukončení výpočtu

‡ Massively Parallel: vztahuje se k hardwaru, stroj má mnoho procesorů

‡ Embarrassingly Parallel: řešení mnoha nezávislých úkolů zaráz, malá nebo žádná nutnost komunikace mezi úkoly

‡ Scalability: schopnost paralelního systému dodat vyšší výkon v závislosti na přidaných procesorech

‡ Hardware – paměť – CPU přenos a síťová komunikace

‡ Algoritmus aplikace‡ Paralelní overhead

Sdílená pam읇 Více procesorů může operovat

nezávisle, ale sdílí pam읇 Změny od jednoho CPU na dané

adrese v paměti jsou viditelné pro ostatní CPU

‡ Rozdělení podle času přístupu k paměti na UMA a NUMA

† Výhody‡ Globální adresování nabízí

uživatelsky přívětivou perspektivu k programování

‡ Sdílení dat mezi úkoly je rychlé a uniformní díky vzdálenosti paměť – CPU

† Nevýhody‡ Nedostatek škálovatelnosti mezi

pamětí a CPU, přidání více CPU geometricky zvýší provoz na sdílené cestě CPU – paměť a pro Cache Coherent systémy též provoz kvůli cache – paměť managementu

‡ Programátor musí zajistit korektní přístup do globální paměti

‡ Náklady – je velmi nákladné postavit stroje se sdílenou pamětí se stále se zvyšujícím počtem CPU

Sdílená paměť UMA‡ Uniform Memory Access (UMA)

‡ Dnes v Symmetric Multiprocessor (SMP) strojích

‡ Identické procesory‡ Stejný přístup a přístupová doba k

paměti‡ Někdy také CC-UMA = Cache Coherent

UMA‡ Cache Coherent značí, že pokud jeden

CPU updatuje lokaci v paměti, ostatní procesory o tomto updatu ví, realizováno na hardwarové úrovni

PaměťCPU

CPU

CPU

CPU

Sdílená paměť NUMA‡ Non-Uniform Memory Access‡ Často realizován spojením dvou a

více SMP‡ Jeden SMP může přímo

přistupovat k paměti dalšího SMP‡ Ne všechny procesory mají stejné

přístupové časy ke všem pamětím – přístup přes Bus je pomalejší

‡ Pokud se zachovává Cache Coherency, používáme označení CC-NUMA = Cache Coherent NUMA

CPU

CPU

CPU

CPU

Paměť

CPU

CPU

CPU

CPU

Paměť

CPU

CPU

CPU

CPU

Paměť

CPU

CPU

CPU

CPU

Paměť

Bus Interconnect

Distribuovaná pam읇 Je vyžadována komunikační síť ke spojení

pamětí procesorů‡ Procesory mají vlastní paměť, adresování

paměti jednoho CPU se nemapuje do ostatních procesorů, tudíž zde není koncept globálního adresování

‡ Protože CPU operují samostatně s vlastní pamětí a její změny ostatní CPU nevidí; není zachovávána cache coherency

‡ Pokud CPU potřebuje přístup k datům jiného CPU, je na programátorovi, aby explicitně definoval potřebnou komunikaci, stejně tak synchronizaci

† Výhody‡ Škálovatelnost: přidání dalšího CPU zvýší i

pam읇 Každý CPU může velmi rychle přistupovat do

své paměti, bez overheadu kvůli zachovávání Cache Coherency

‡ Efektivní cena: možnost použít CPU „z police“ a síť

† Nevýhody‡ Programátor je zodpovědný za mnoho detailů

spojených s datovou komunikací mezi procesory

‡ Může být obtížné přemapovat stávající datové struktury založené globálním adresování na tento systém

‡ NUMA přístupové doby

CPU

Paměť

CPU

Paměť

CPU

Paměť

CPU

Paměť

Hybridní distribuovaná paměť

‡ Největší a nejrychlejší počítače na světě používají tuto architekturu paměti

‡ Komponenta sdílené paměti je většinou cache coherent SMP stroj

‡ Procesory na daném SMP mohou adresovat paměť stroje globálně

‡ Komponenta distribuované paměti je sesíťování více SMP

‡ SMP ví pouze o svojí vlastní paměti, proto je třeba síťová komunikace k přesunu dat z jednoho SMP k dalšímu

‡ Dnešní trendy ukazují, že tato architektura je vhodná pro budoucnost high end počítání

‡ Výhody a nevýhody jsou společné s těmi sdílené / rozdělované paměti

CPU

CPU

CPU

CPU

Paměť

CPU

CPU

CPU

CPU

Paměť

CPU

CPU

CPU

CPU

Paměť

CPU

CPU

CPU

CPU

Paměť

Programovací modely‡ Shared Memory (sdílená paměť)‡ Threads (vlákna)‡ Message Passing (předávání zpráv)‡ Data Parallel‡ Hybrid‡ Paralelní modely jsou abstraktní

analogie k architektuře hardwaru a paměti

‡ Modely nejsou specifické pro ten který typ stroje / paměti

‡ Volba modelu závisí na dostupných zdrojích a programátorovi

‡ Neexistuje „nejlepší“ model, ačkoli některé jsou vhodnější pro ten či onen problém

Shared Memory‡ Výpočetní úkoly používají společný

prostor adres, na které zapisují nebo ze kterých čtou asynchronně

‡ Není třeba explicitně definovat komunikaci dat mezi úkoly – výhoda

‡ Nevýhodou je (co se výkonu týče), že se stává dosti obtížným porozumět a spravovat umístění dat

‡ Udržovat data lokální pro CPU, který na nich pracuje, snižuje počty přístupů, obnovování cache a provoz na sběrnici, které vznikají, pokud více CPU používá stejná data

Threads‡ Jeden proces může mít více

současných prováděcích cest‡ „jeden program zahrnující několik

podprogramů“‡ Hlavní a.out je spuštěn OS, načte se a

alokuje všechny potřebné prostředky‡ a.out provede nějakou sériovou práci

a vytvoří několik vláken, které mohou být naplánovány a spouštěny OS zároveň

‡ Každé vlákno má lokální data, ale také sdílí veškeré prostředky a.out

‡ Vlákna spolu komunikují skrz sdílenou paměť, což vyžaduje, aby synchronizace zabránila updatování jedné adresy více vlákny

‡ Vlákna mohou být spouštěna a ukončována, ale a.out a poskytuje potřebné sdílené prostředky, dokud není výpočet hotov

a.outCall sub1Call sub2Do i = 1:N

A(i) = fnc(i ** 2)B(i) = A(i) * psi

End doCall sub3Call sub 4

…T1 T2

T3

T4 Čas

Message Passing‡ Set úkolů používá jejich vlastní

lokální paměť během výpočtu‡ Vícero úkolů může být jak na

jednom stroji tak napříč spektrem strojů

‡ Úkoly si vyměňují data skrze komunikaci – posílání a přijímání zpráv

‡ Transfer dat obyčejně požaduje kooperativní operace, např. operace odeslání musí mít odpovídající operaci přijetí

Stroj A

Úkol 0Data

Send()Úkol 2Data

Recv()

Stroj B

Úkol 1Data

Recv()Úkol 3Data

Send()

Data Parallel‡ Většina paralelní práce se soustředí na

provedení operací na kusu dat‡ Kus dat je typicky organizovaný, např.

pole nebo krychle‡ Skupina úkolů pracuje společně na

stejné datové struktuře, avšak každý úkol na jiné části

‡ Úkoly provádí stejnou operaci na svém kusu dat, např. „+4 ke každému prvku pole

‡ Na architektuře sdílené paměti – všechny úkoly přístup k datům skrze globální paměť

‡ Na architektuře rozdělované paměti je datová struktura rozdělena a zůstává jako úlomek v lokální paměti každého úkolu

Pole A

Úkol 1 Úkol 2 Úkol n

Tvorba programu‡ Problém konverze sériového programu na

paralelní‡ Automatická konverze (většinou cykly) nebo

manuální (programátor přidává direktivy pro kompilátor)

‡ Identifikace hotspotů – místa v programu, kde je provedeno nejvíce práce

‡ Identifikace bottlenecků – místa kde je zpomalen program

‡ Dekompozice pracovních dat na kusy – buď na stejné kusy (domain decomposition) nebo podle toho, kolik je třeba vykonat práce na daném kusu, kusy nejsou stejně velké, časově stejně náročné (functional decomposition)

‡ Komunikace mezi úkoly‡ Synchronizace‡ Distribuce zatížení jednotlivých úkolů, tak aby

byly všechny vytíženy

‡ Hrubost ‡ I/O operace – obecně zpomalují paralelní

program

Limity‡ Amdahlův zákon – zrychlení programu je

ůměrné zlomku paralelního kódu: 1 / (1 – P)‡ Přidáním více procesorů: 1 / (P/N + S), kde P

je zlomek paralelního kódu, N počet CPU a S zlomek sériového kódu

‡ Paralelní programy jsou komplexnější než sériové

‡ Portabilita – operační systémy mohou způsobit těžkosti

‡ Zdroje – celkový čas výpočtu je kratší, ovšem je třeba více CPU atd.

‡ Škálovatelnost – nakonec přidání dalšího stroje / CPU zvýší dobu výpočtu

Příklad programu‡ Jednoduchá tepelná rovnice‡ Většina problémů v paralelním počítání

vyžaduje komunikaci mezi úkoly‡ Hodně obyčejných problémů vyžaduje

komunikaci mezi „sousedními“ úkoly‡ Tepelná rovnice popisuje časovou výměnu

tepla za dané počáteční teploty a podmínek na hranici

‡ Finitní diferenciální schéma je použito k numerickému řešení rovnice na čtvercové oblasti

‡ Počáteční teplota je nulová (stále) na okrajích a vysoká na středu

‡ Elementy 2D pole reprezentují teplotu v bodě čtverce

‡ Výpočet elementu je závislý na hodnotě sousedního elementu

‡ Ux,y = Ux,y + Cx * (Ux+1,y + Ux-1,y – 2 * Ux,y) + Cy * (Ux,y+1 + Ux,y-1 – 2 * Ux,y)

‡ Sériový program:Do iy = 2:ny-1Do ix = 2:nx-1

u2(ix,iy) = u1(ix,iy) + cx * (u1(ix+1,iy) + u1(ix-1,y) – 2 * u1(ix,iy)) cy * (u1(ix,iy+1) + u1(ix,y-1) – 2 * u1(ix,iy))

End doEnd do

Ux,y+1Ux-1,y Ux,y

Ux+1,y

Ux,y-1

y

x

Řešení‡ Implementace jako SPMD model‡ Celé pole je rozděleno na sub-pole a tato jsou

rozdělena mezi úkoly‡ Určí se závislost dat, vnitřní data úkolu jsou

nezávislá na ostatních úkolech, hraniční data jsou závislá na datech sousedního úkolu, je třeba komunikace

‡ Master proces pošle počáteční info worker procesům, zajistí konvergenci a sbírá výsledky

‡ Worker proces kalkuluje výsledky a komunikuje se sousedy, je-li třeba

Program v pseudokódufind out if I am MASTER or WORKER if I am MASTER initialize array send each WORKER starting info and subarray do until all WORKERS converge gather from all WORKERS convergence data broadcast to all WORKERS convergence signal end do

receive results from each WORKER

else if I am WORKER receive from MASTER starting info and subarray do until solution converged update time send neighbors my border info receive from neighbors their border info update my portion of solution array determine if my solution has converged send MASTER convergence data receive from MASTER convergence signal end do send MASTER results endif

Řešení‡ V předchozím programu bylo předpokládáno,

že úkoly využívají blokování komunikace‡ Blokování komunikace znamená, že se čeká

než komunikační proces skončí a pak se přikročí k další instrukci programu

‡ Úkoly komunikují sousední data a potom se updatují své části pole

‡ Vyloučením blokování se většinou zrychlí program

‡ Každý úkol může updatovat vnitřek svého pole zatímco probíhá komunikace, až skončí updatují se hranice

Program v pseudokódufind out if I am MASTER or WORKER if I am MASTER initialize array send each WORKER starting info and subarray do until all WORKERS converge gather from all WORKERS convergence data broadcast to all WORKERS convergence signal end do

receive results from each WORKER

else if I am WORKER receive from MASTER starting info and subarray do until solution converged update time non-blocking send neighbors my border info non-blocking receive neighbors border info update interior of my portion of solution array wait for non-blocking communication complete update border of my portion of solution array determine if my solution has converged send MASTER convergence data receive from MASTER convergence signal end do send MASTER results endif

+++ Děkuji za pozornost +++