Post on 23-Feb-2016
description
transcript
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 +++