Cannons algoritm

Inom datavetenskap är Cannons algoritm en distribuerad algoritm för matrismultiplikation för tvådimensionella maskor som först beskrevs 1969 av Lynn Elliot Cannon .

Den är särskilt lämplig för datorer som är placerade i ett N × N- nät. Medan Cannons algoritm fungerar bra i homogena 2D-rutnät, har det visat sig vara svårt att utöka den till heterogena 2D-rutnät.

Den största fördelen med algoritmen är att dess lagringskrav förblir konstanta och är oberoende av antalet processorer.

Scalable Universal Matrix Multiplication Algorithm (SUMMA) är en mer praktisk algoritm som kräver mindre arbetsyta och övervinner behovet av ett kvadratiskt 2D-rutnät. Det används av biblioteken ScaLAPACK , PLAPACK och Elemental .

Algoritmöversikt

När vi multiplicerar två n × n matriser A och B behöver vi n × n bearbetningsnoder p arrangerade i ett 2D-rutnät. Inledningsvis är p _i,j ansvarig för a _i,j och b _i,j .

// PE(i, j) k := (i + j) mod N; a := a[i][k]; b := b[k][j]; c[i][j] := 0; för (l:= 0; 1 < N; l++) {c[i][j]:= c[i][j] + a * b; samtidigt { skicka a till PE(i, (j + N − 1) mod N); skicka b till PE((i + N − 1) mod N, j); } med { ta emot a' från PE(i, (j + 1) mod N); ta emot b' från PE((i + 1) mod N, j ); } a := a'; b := b'; }

Vi måste välja k i varje iteration för varje processorelement (PE) så att processorer inte kommer åt samma data för att beräkna $a_{ik}*b_{kj}$ .

Därför måste processorer i samma rad/kolumn börja summera med olika index. Om till exempel PE(0,0) beräknar $a_{00}*b_{00}$ i det första steget, väljer PE(0,1) $a_{ 01}*b_{11}$ först. Valet av k := (i + j) mod n för PE(i,j) uppfyller denna begränsning för det första steget.

I det första steget fördelar vi inmatningsmatriserna mellan processorerna baserat på den tidigare regeln.

I nästa iteration väljer vi en ny k' := (k + 1) mod n för varje processor. På så sätt kommer varje processor att fortsätta få åtkomst till olika värden på matriserna. Den data som behövs finns då alltid hos grannprocessorerna. En PE(i,j) behöver sedan a $\displaystyle a}$ från PE(i,(j + 1) mod n) och $b$ från PE((i + 1) mod n,j) för nästa steg. Detta innebär att $a$ måste skickas cykliskt till vänster och även $b$ cykliskt uppåt. Resultaten av multiplikationerna summeras som vanligt. Efter n steg har varje processor beräknat alla $a_{ik}*b_{kj}$ en gång och dess summa är alltså den sökta $c_{ij}$ .

Efter den initiala distributionen av varje processor behöver endast data för nästa steg lagras. Dessa är mellanresultatet av föregående summa, a $a_{ik}$ och a $b_{kj}$ . Detta innebär att alla tre matriserna bara behöver lagras i minnet en gång jämnt fördelade över processorerna.

Generalisering

I praktiken har vi mycket färre processorer än matriselementen. Vi kan ersätta matriselementen med submatriser, så att varje processor bearbetar fler värden. Den skalära multiplikationen och additionen blir sekventiell matrismultiplikation och addition. Bredden och höjden på submatriserna kommer att vara $N=n/{\sqrt {p}}$ .

Algoritmens körtid är ${\displaystyle T{\mathcal {(n,p)}}=T_{coll}(n/N,p)+N*T_{seq}(n /N)+2(N-1)(T_{start}+T_{byte}(n/N)^{2})} ,$ där $T_{coll}$ är tiden för den initiala fördelningen av matriserna i det första steget, $T_{seq}$ är beräkningen av de mellanliggande resultaten och $T_{start}$ och $T_{byte}$ står för den tid det tar att upprätta en anslutning respektive överföring av byte.

En nackdel med algoritmen är att det finns många anslutningsinställningar, med små meddelandestorlekar. Det vore bättre att kunna överföra mer data i varje meddelande.

Se även

• Systolisk array

externa länkar

• Föreläsning på Berkeley
• mu.oz.au