Základní komunikaˇcní operace Úvod Operace send a recieve Blokující a neblokující posílání zpráv Blokující posílání zpráv Neblokující posílání zpráv
One-to-all broadcast/All-to-one reduction All-to-all broadcast/All-to-all reduction All-reduce a Prefix-sum Scatter/Gather All-to-all personalized communication Circular shift
Základní komunikaˇcní operace mezi procesy
I
jde o komunikaˇcní vzory, které se v paralelním programování vyskytují velice cˇ asto
I
ˇ komunikující procesy mohou bežet na jednom nebo i na více výpoˇcetních uzlech jejich speciální implemetace má následující výhody
I
I I
I
zjednodušuje práci programátora mohou využívat hardwarovou podporu dané paralelní architektury udržují aktivní sít’ové spojení komunikaˇcní síteˇ I
I
ˇ tím vlastneˇ nekolik malých zpráv "shlukuje do jedné"
ˇ ˇ k vetšin eˇ techto operací existují i operace duální, které ˇ v opaˇcném smeru" ˇ "beží
Operace send a recieve
Jde o základní operace pro odeslání a pˇrijetí jedné zprávy. I
send( void *sendbuf, int nelems, int dest) I I I
I
sendbuf - ukazatel na pole dat, jež mají být odeslána nelems - poˇcet prvku˚ pole dest - ID procesu/uzlu, kterému mají být data zaslána
receive( void *recvbuf, int nelems, int source) I
I I
ˇ mají být pˇrijatá data recvbuf - ukazatel na pole, do nejž uložena nelems - poˇcet prvku, ˚ které budou pˇrijaty source - ID procesu/uzlu, od kterého mají být data naˇctena
Operace send a recieve
Pˇríklad: P1 a=100; send(&a,1,1); a=0;
P2 receive( &a,1,0); printf("%d",a);
Jaký výsledek vypíše proces P2 ?
Operace send a recieve
Pˇríklad: P1 a=100; send(&a,1,1); a=0;
P2 receive( &a,1,0); printf("%d",a);
Jaký výsledek vypíše proces P2 ? Výsledek je 100 nebo 0.
Operace send a recieve
I
sít’ové rozhraní muže ˚ využívat DMA a pracovat nezávisle na CPU
I
ˇ ve zpracování kódu, mohou být pokud má P2 zpoždení data z P1 odeslána až po provedení pˇríkazu a=0; na P1
I
tím pádem bude procesu P2 odesláno cˇ íslo 0
Blokující a neblokující posílání zpráv
Existují dva zpusoby ˚ posílání zpráv: I
blokující I
I
funkce send nevrátí ˇrízení programu, dokud to není sémanticky bezpeˇcné
neblokující I
komunikaˇcní funkce vrací ˇrízení programu dˇríve, než je to sémanticky bezpeˇcné
Blokující posílání zpráv
ˇ Blokující posílání zpráv je možné provést dvema zpusoby: ˚ I
bez bufferu
I
s bufferem
Blokující posílání zpráv bez bufferu
I
odesílatel pošle požadavek k pˇríjemci
I
odesílatel potvrdí ve chvíli, kdy ve zpracování kódu ˇ k místu pro pˇríjetí zprávy dospeje
I
následneˇ dojde k pˇrenosu dat
Blokující posílání zpráv bez bufferu
ˇcas
P1 (send)
P2 (receive)
Blokující posílání zpráv bez bufferu P1 (send)
ˇcas
send
P2 (receive)
SEND REQUEST
Blokující posílání zpráv bez bufferu P1 (send)
ˇcas
send
P2 (receive)
SEND REQUEST
SEND OK
receive
Blokující posílání zpráv bez bufferu P1 (send)
send
P2 (receive)
SEND REQUEST
ˇcas
IDLE
SEND OK TRANSFER
receive
Blokující posílání zpráv bez bufferu
ˇcas
P1 (send)
P2 (receive)
Blokující posílání zpráv bez bufferu P1 (send)
ˇcas
send
P2 (receive)
SEND REQUEST
Blokující posílání zpráv bez bufferu P1 (send)
ˇcas
send
P2 (receive)
SEND REQUEST SEND OK
receive
Blokující posílání zpráv bez bufferu P1 (send)
ˇcas
send
P2 (receive)
SEND REQUEST SEND OK TRANSFER
receive
Blokující posílání zpráv bez bufferu
ˇcas
P1 (send)
P2 (receive)
Blokující posílání zpráv bez bufferu P1 (send)
P2 (receive)
ˇcas
receive
Blokující posílání zpráv bez bufferu P1 (send)
P2 (receive)
receive
ˇcas
send
SEND REQUEST
Blokující posílání zpráv bez bufferu P1 (send)
P2 (receive)
receive IDLE
ˇcas
send
SEND REQUEST SEND OK TRANSFER
Blokující posílání zpráv bez bufferu
Možnost deadlocku: P1 send(&a,1,2); receive(&b,1,2); I
P2 send( &a,1,1); receive( &b,1,1 );
oba procesy posílají send request a oba pak cˇ ekají na potvrzení send ok
Blokující posílání zpráv s bufferem
I
snažíme se odstranit nutnost cˇ ekání na SEND OK
I
pˇri volání funkce send se data kopírují do pomocného bufferu
I
program pak muže ˚ okamžiteˇ pokraˇcovat
I
ˇ pˇrenos dat muže ˚ probehnout bez úˇcasti CPU na straneˇ pˇríjemce se data také kopírují do pomocného bufferu
I
I
ˇ nekdy je buffer jen na jedné straneˇ
Blokující posílání zpráv s bufferem
I
cˇ ekání odesílajícího procesu se podaˇrilo zredukovat
I
pˇribyla ale režie nutná pˇri kopírování dat z/do bufferu˚
I
pokud jsou procesy cˇ asto synchronizovány, muže ˚ být ˇ komunikace bez bufferu˚ efektivnejší
I
pokud se buffery zaplní, dochází k cˇ ekání také pˇríjem je vždy blokující
I
I
nesmí se pokraˇcovat dál, dokud nejsou data zkopírována z bufferu pˇríjemce
Blokující posílání zpráv s bufferem
Možnost deadlocku: P1 receive(&b,1,2); send(&a,1,2); I
P2 receive( &b,1,1 ); send( &a,1,1);
oba procesy cˇ ekají na pˇríjem zprávy
Neblokující posílání zpráv
I
komunikaˇcní funkce vrací ˇrízení programu dˇríve, než je to sémanticky bezpeˇcné
I
programátor musí sám ohlídat, zda již byla data pˇrenesena
I
mezi tím ale muže ˚ zpracovávat jiný kód, který napracuje s posílanými daty
I
ˇ eˇ existují funkce, které ˇreknou, zda již komunikace úspešn ˇ probehla
I
i neblokující komunikace muže ˚ používat buffery
One-to-all broadcast/All-to-one reduction
One-to-all broadcast I jeden proces má identická data o velikosti m a rozešle je všem ostatním I
používá se napˇr. pˇri rozesílání konfiguranˇcích parametru˚
One-to-all broadcast/All-to-one reduction
All-to-one reduction I
každý proces má data o velikosti m a obecneˇ jsou ruzná ˚ (ruzné ˚ hodnoty)
I
data jsou poslána jednomu procesu a souˇcasneˇ slouˇcena ˇ dohromady pomocí nejaké asociativní operace do velikosti m
ˇ Pˇríklad: Máme 100 reálných cˇ ísel umístených na 100 procesech (každý proces má jedno reálné cˇ íslo). Výsledkem redukce je souˇcet všech cˇ ísel a výsledek má proces cˇ íslo 0.
One-to-all broadcast/All-to-one reduction
M
1
2
3
···
Pˇred
p
1
2
3 Po
···
p
One-to-all broadcast/All-to-one reduction
M 1
2
3
···
Pˇred
p
1
One-to-all broadcast
2
3 Po
···
p
One-to-all broadcast/All-to-one reduction
M 1
M M M 2
3
···
Pˇred
p
1
2
3 Po
···
M p
One-to-all broadcast/All-to-one reduction
Mp
M1 M2 M3 1
2
3
··· Po
p
1
2
3
Pˇred
···
p
One-to-all broadcast/All-to-one reduction
Mp
M1 M2 M3 1
2
3
··· Po
p
1
All-to-one reduction
2
3
Pˇred
···
p
One-to-all broadcast/All-to-one reduction
Pp
i=1
1
Mi
2
3
··· Po
p
1
2
3
Pˇred
···
p
One-to-all broadcast/All-to-one reduction - pˇríklad
vstupn´ı vektor
P1 P2 P3 P4
P1
P5 P6 P7 P8
P2
P9 P10 P11 P12
P3
P13 P14 P15 P16
P4
v´ystupn´ı vektor
P1 P2 P3 P4
One-to-all broadcast/All-to-one reduction - pˇríklad
vstupn´ı vektor
P1 P2 P3 P4 One-to-all broadcast
P1
P5 P6 P7 P8
P2
P9 P10 P11 P12
P3
P13 P14 P15 P16
P4
v´ystupn´ı vektor
P1 P2 P3 P4
One-to-all broadcast/All-to-one reduction - pˇríklad
vstupn´ı vektor
P1 P2 P3 P4 V´ypoˇcet
P1
P5 P6 P7 P8
P2
P9 P10 P11 P12
P3
P13 P14 P15 P16
P4
v´ystupn´ı vektor
P1 P2 P3 P4
One-to-all broadcast/All-to-one reduction - pˇríklad
vstupn´ı vektor
P1 P2 P3 P4
P9 P10 P11 P12 P13 P14 P15 P16
P1 P2 P3 P4
v´ystupn´ı vektor
P5 P6 P7 P8
All-to-one reduction
P1 P2 P3 P4
One-to-all broadcast/All-to-one reduction Realizace v pˇrípadeˇ síteˇ typu kruh
8
7
6
5
One-to-all broadcast
1
2
3
4
One-to-all broadcast/All-to-one reduction Realizace v pˇrípadeˇ síteˇ typu kruh
8
7
6
5
One-to-all broadcast
1
2
3
4
One-to-all broadcast/All-to-one reduction Realizace v pˇrípadeˇ síteˇ typu kruh
8
7
6
5
One-to-all broadcast
1
2
3
4
One-to-all broadcast/All-to-one reduction Realizace v pˇrípadeˇ síteˇ typu kruh
8
7
6
5
One-to-all broadcast
1
2
3
4
One-to-all broadcast/All-to-one reduction Realizace v pˇrípadeˇ síteˇ typu kruh
8
7
6
5
One-to-all broadcast
1
2
3
4
One-to-all broadcast/All-to-one reduction Realizace v pˇrípadeˇ síteˇ typu kruh
8
7
6
5
One-to-all broadcast
1
2
3
4
One-to-all broadcast/All-to-one reduction
ˇ Realizace v pˇrípadeˇ síteˇ typu lineární rˇetezec je stejná jako u kruhu. I
poslední spoj nebyl potˇreba
ˇ Realizace v pˇrípadeˇ ortogonální síte: I
nejprve se provede one-to-all broadcast podél jedné souˇradnice, následneˇ podél další
All-to-all broadcast/All-to-all reduction
Všech p procesu˚ provádí souˇcasneˇ one-to-all broadcast nebo all-to-one reduction s ruznými ˚ daty.
All-to-all broadcast/All-to-all reduction
M1
M2
M3
1
2
3
Mp ···
Pˇred
p
1
2
3 Po
···
p
All-to-all broadcast/All-to-all reduction
M1
M2
M3
1
2
3
Mp ···
Pˇred
p
1
All-to-all broadcast
2
3 Po
···
p
All-to-all broadcast/All-to-all reduction
M1
M2
M3
1
2
3
···
Pˇred
Mp
Mp
Mp
Mp
.. .
.. .
.. .
M3
M3
M3
···
M3
M2
M2
M2
···
M2
Mp
M1
M1
M1
···
M1
p
1
2
3
···
p
Po
···
.. .
All-to-all broadcast/All-to-all reduction
Mp,1 Mp,2 Mp,3 · · · Mp,4 .. .
.. .
.. .
.. .
M3,1 M3,2 M3,3 · · · M3,p M2,1 M2,2 M2,3 · · · M2,p M1,1 M1,2 M1,3 · · · M1,p
1
2
3
··· Po
p
1
2
3
Pˇred
···
p
All-to-all broadcast/All-to-all reduction
Mp,1 Mp,2 Mp,3 · · · Mp,4 .. .
.. .
.. .
.. .
M3,1 M3,2 M3,3 · · · M3,p M2,1 M2,2 M2,3 · · · M2,p M1,1 M1,2 M1,3 · · · M1,p
1
2
3
··· Po
p
1
All-to-all reduction
2
3
Pˇred
···
p
All-to-all broadcast/All-to-all reduction
Mp,1 Mp,2 Mp,3 · · · Mp,4 .. .
.. .
.. .
.. .
M3,1 M3,2 M3,3 · · · M3,p
P
··· Po
p
p,
i p i= 1
M
3, i
,i
M
p i= 1
P M 2
3
M
P
2
p i= 1
1
p i= 1
P
1, i
M2,1 M2,2 M2,3 · · · M2,p M1,1 M1,2 M1,3 · · · M1,p
1
2
3
Pˇred
···
p
All-to-all broadcast/All-to-all reduction
Realizace all-to-all broadcast v pˇrípadeˇ síteˇ typu kruh: I
v každém kroku každý uzel pošle svoje data sousedovi vpravo a pˇrijme data od souseda vlevo
I
v následujícím kroku posílá data, která v pˇredchozím kroku pˇrijal
I
vše se opakuje p − 1-krát
ˇ postupuje podél V pˇrípadeˇ ortogonálních sítí se opet jednotlivých souˇradnic.
All-to-all broadcast/All-to-all reduction
Realizace all-to-all reduction v pˇrípadeˇ síteˇ typu kruh: I
v první kroku pošle uzel i data Mj,i pro j = 1, · · · p a j 6= i svému sousedovi vpravo a pˇríjme data Mj,i−1 pro j = 1, · · · p a j 6= i − 1 od svého souseda vlevo
I
v druhém kroku pošle uzel i data Mj,i−1 pro j = 1, · · · p a j 6= i ∧ j 6= i − 1, svému sousedovi vpravo a pˇríjme data Mj,i−2 pro j = 1, · · · p a j 6= i − 1 ∧ j 6= i − 2 od svého souseda vlevo
I
ˇ vše se ješteˇ opakuje p − 2-krát za souˇcasného provádení redukˇcní operace
All-reduce a Prefix-sum
All-reduce I I I
na poˇcátku má každý proces ruzná ˚ data Mi o velikosti m P na konci mají všechny procesy stejný "souˇcet"dat pi=1 Mi All-reduce lze provést jako I I
I
pro m = 1 lze All-reduce použít jako bariéru 1 I
1
All-to-one reduction + One-to-all broadcast Pp All-to-all broadcast, kde se ale provede souˇcet i=1 Mi ˇ každý proces redukci nelze dokonˇcit, dokud k ní nepˇrispeje svým podílem
Bariéra je místo v programu, které nesmí žádný proces pˇrekroˇcit, dokud ho nedosáhnou všechny ostatní procesy. Má význam synchronizace procesu. ˚
All-reduce a Prefix-sum
Prefix-sum I
jde o modifikaci all-reduce
I
pro data M1 , · · · Mp chceme najít Sk = k = 1, · · · p
I
postup je stejný jako u all-reduce, ale každý proces k si "pˇriˇcítá"jen data od procesu˚ s ID < k
I
ˇ nekterá komunikace je tu tady zbyteˇcná, ale celkovou složitost této operace to neovlivní
Pk
i=1 Mi
pro
Scatter/Gather
Scatter I
jeden proces má na poˇcátku p ruzných ˚ zpráv M1 , · · · Mp
I
proces i má na konci zprávu Mi
I
ˇ nekdy se tato zpráva nazývá one-to-all personalized communicatio
Gather I
je to duální operace ke scatter
I
na poˇcátku má každý proces i zprávu Mi
I
na konci má jeden proces všechny zprávy ∩pi=1 Mi
Scatter/Gather
Mp .. . M3 M2 M1
1
2
3
···
Pˇred
p
1
2
3 Po
···
p
Scatter/Gather
Mp .. . M3 M2 M1
1
2
3
···
Pˇred
p
1 Scatter
2
3 Po
···
p
Scatter/Gather
Mp .. . M3 M2 M1
1
2
3
···
Pˇred
p
M1
M2
M3
···
Mp
1
2
3
···
p
Po
Scatter/Gather
1
2
3
··· Po
p
M1
M2
M3
···
Mp
1
2
3
···
p
Pˇred
Scatter/Gather
1
2
3
··· Po
p Gather
M1
M2
M3
···
Mp
1
2
3
···
p
Pˇred
Scatter/Gather
Mp .. . M3 M2 M1
1
2
3
··· Po
p
M1
M2
M3
···
Mp
1
2
3
···
p
Pˇred
Scatter/gather
Realizace scatter v pˇrípadeˇ síteˇ typu kruh: I
je stejná jako u one-to-all broadcast ale s jinými objemy dat
Scatter/gather
8
7
6
5
3
4
Scatter
1
2
Scatter/gather
8
7
6
5
3
4
1
8
1,
M
··
·M
Scatter
2
8
7
6
5
3
4
1
4
1,
M
··
·M
Scatter
2
5,
M
··
8
·M
Scatter/gather
1 ··
2 3 4
·M
2
·M
7
3,
··
8
M
1,
M
6 5
Scatter
4
5,
M
7,
M
··
··
6
·M
8
·M
Scatter/gather
7
5
M
6
M
M
8
M
7
8
Scatter/gather
6
5
2
3
4
M
M
M
M
1
3
2
1
Scatter
4
7
5
M
6
M
M
8
M
7
8
Scatter/gather
6
5
2
3
4
M
M
M
M
1
3
2
1
Scatter
4
All-to-all personalized communication
All-to-all personalized communication I
každý proces i má data Mi,j , která pošle procesu j.
All-to-all personalized communication
Mp,1 Mp,2 Mp,3 · · · Mp,p .. .
.. .
.. .
.. .
M3,1 M3,2 M3,3 · · · M3,p M2,1 M2,2 M2,3 · · · M2,p M1,1 M1,2 M1,3 · · · M1,p
1
2
3
···
Pˇred
p
1
2
3 Po
···
p
All-to-all personalized communication
Mp,1 Mp,2 Mp,3 · · · Mp,p .. .
.. .
.. .
.. .
M3,1 M3,2 M3,3 · · · M3,p M2,1 M2,2 M2,3 · · · M2,p M1,1 M1,2 M1,3 · · · M1,p
1
2
3
···
Pˇred
p
1
All-to-all personalized communication
2
3 Po
···
p
All-to-all personalized communication
Mp,1 Mp,2 Mp,3 · · · Mp,p .. .
.. .
.. .
.. .
M1,p M2,p M3,p · · · Mp,p .. .
.. .
.. .
.. .
M3,1 M3,2 M3,3 · · · M3,p
M1,3 M2,3 M3,3 · · · Mp,3
M2,1 M2,2 M2,3 · · · M2,p
M1,2 M2,2 M3,2 · · · Mp,2
M1,1 M1,2 M1,3 · · · M1,p
M1,1 M2,1 M3,1 · · · Mp,1
1
2
3
···
Pˇred
p
1
2
3 Po
···
p
All-to-all personalized communication
I
jde vlastneˇ o maticovou transpozici
I
stejná analogie jako mezi scatter a one-to-all broadcast platí i mezi all-to-all personalized communication a all-to-all broadcast
I
z toho plyne i realizace all-to-all personalized communication na síti typu kruh nebo na ortogonálních sítích
Circular shift
Circular shift I
ˇ komunikacní ˇ operace patˇrí mezi tzv. permutacní
I
každý proces pošle jednu zprávu o velikosti m slov ˇ nekterému jinému uzlu
Pˇríklad: Circular q-shift I
proces i pošle svá data procesu (i + q) mod p