M5-2. A lineáris algebra párhuzamos algoritmusai. Ismertesse a párhuzamos gépi architektúrák Flynn-féle osztályozását. A párhuzamos lineáris algebrai algoritmusok között mi a BLAS csomag célja, melyek annak a szintjei? Speciálisan, elosztott memóriájú rendszereknél ismertesse a Gaxpy-algoritmust gyűrűn.
Ismertesse a párhuzamos gépi architektúrák Flynn-féle osztályozását. A számítógép architektúrákat és programozási modelleket az adat es az utasítás mennyiségének függvényében a Flynn-féle osztályozás négy csoportra osztja. Flynn féle osztályozás
Single Isntruction
Multiple Instruction
Single Data
SISD
SIMD
Multiple Data
MISD
MIMD
SISD: egy adaton egy utasítás végrehajtása, nincs párhuzamosság Nincs párhuzamosság. SIMD: 1 műveletet hajt végre minden adaton Képfeldolgozáshoz hasznos. példák: GPU (videokártyán grafikai processzor), vektor processzorok, tömbprocesszorok. MISD: különböző műveleteket hajtanak végre ugyanazon az adaton (1 adat sok művelet) példák: többféle szűrő egy jelfeldolgozásánál, többféle kriptográfiai algoritmus futtatása azonos kódolt üzenet feltörésére MIMD: az előző kettő keveréke, különböző adatokon és különböző feladatokat hajtanak végre. Ez a modell az elterjedt, mivel többféle számításra szokták használni a számítógépeket (kivéve amikor nem) példák: mai számítógépek. Az architektúra kétféle módon valósítható meg. közös memóriával és elosztott memóriával.
Az osztályozásnál a párhuzamos architektúrákat osztályozzák. Az egyes feladatoknál nem szükséges a processzorok számát növelni, elég lehet ha több utasítás végrehajtására képesek (több PU processing unit).
1
A párhuzamos lineáris algebrai algoritmusok között mi a BLAS csomag célja, melyek annak a szintjei? A BLAS csomag célja a mátrix és vektor hatékony implementálása és szabványosítása. A rutinok az adott műveletnél legjobb, vagy legjobbnak tartott algoritmus megvalósításait tartalmazzák. A csomag algoritmusai különböző gépcsaládokra optimalizálva is elérhető (például AMD, Intel, Cray, Apple stb.) A csomag ingyenesen felhasználható, a szerzők kérése, hogyha módosítás történik az algoritmusukban, akkor a függvények legyenek átnevezve és jól dokumentálva a módosítások okai. Tehát a csomag célja: hogy elérhető egy ilyen jellegű algoritmusokat kínáló csomag több programozási nyelven és többféle processzorcsaládra. A csomag szintjei: A BLAS (Basic Linear Algebra Subprograms) csomag célja, hogy segítséget nyújtson a lineárisalgebra alapműveleteinek párhuzamos elvégzéséhez. A csomagnak három szintbe sorolható (Level 1 BLAS, Level 2 BLAS, Level 3 BLAS).
az első szint a vektoriális műveletek (vektor-vektor, vektor-skalár szorzás) a második a mátrix vektor műveletek (mátrix-vektor szorzás) a harmadik a mátrix mátrix műveletekre (szorzás, hatványozás)
A csomag legnagyobb előnye, hogy létezik és gyorsan felhasználható. Bárki ki tudja használni, ezzel elősegítve a párhuzamos programozás hatékonyságát, valamint gyorsítja a fejlesztést. 𝑛 2
vektor-vektor szorzás
Ο(log 𝑛)
vektor skaláris szorzás
Ο(1)
n darab processzor
vektorok összeadása (2 darab)
Ο(1)
n darab processzor
darab processzor
vektorok összeadása (n darab, mx1)
Ο(𝑙𝑜𝑔𝑛)
𝑚𝑛 2
mátrix-vektor szorzás (mxn * nx1)
Ο(𝑙𝑜𝑔𝑛)
𝑚𝑛 2
mátrix-vektor szorzás (mxn * nx1)
Ο(𝑛)
Ha soronként 1, m darab processzor van
mátrix-mátrix szorzás (mxn * nxk)
Ο(log 𝑛)
Ο(𝑛3 ) darab processzor
mátrix-mátrix szorzás (mxn * nxk)
Ο(𝑛)
Ο(𝑛2 ) darab processzor
mátrix-mátrix szorzás (mxn * nxk)
Ο(𝑛2 )
Ο(𝑛) darab processzor
darab processzor darab processzor van
Az előbbi becslések szemléltetik az utópia esetét, mert általában nincs n processzorunk.
2
Speciálisan, elosztott memóriájú rendszereknél ismertesse a Gaxpy-algoritmust gyűrűn. Feladat: Gaxpy művelet (general Ax plus y) megoldása. 𝐴 ∈ 𝑅 𝑛 𝑥 𝑛 , 𝑥, 𝑦, 𝑧 ∈ 𝑅 𝑛
𝑧 = 𝑦 + 𝐴𝑥, Tehát a feladat a z vektor kiszámítása.
1. ábra Soros algoritmus
Elosztott memóriás rendszer:
2. ábra Négy processzoros gyűrű
Minden processzornak van saját memóriája és a gyűrűn keresztül tud kommunikálni a többi processzorral. 𝑝 = 𝑝𝑟𝑜𝑐𝑒𝑠𝑠𝑧𝑜𝑟 𝑠𝑧á𝑚, 𝑛 = 𝑎 𝑏𝑒𝑚𝑒𝑛𝑒𝑡 𝑡𝑒𝑙𝑗𝑒𝑠 𝑚é𝑟𝑒𝑡𝑒 𝑟 = 𝑝𝑟𝑜𝑐𝑒𝑠𝑠𝑧𝑜𝑟𝑜𝑛𝑘é𝑛𝑡 𝑘𝑒𝑧𝑒𝑙𝑡 𝑠𝑜𝑟𝑜𝑘 𝑠𝑧á𝑚𝑎 𝑛 = 𝑟𝑝,
𝑧1 𝑦1 𝐴11 ⋮ = ⋮ + ⋮ 𝑧𝑝 𝑦𝑝 𝐴𝑝1
⋯ ⋱ ⋯
𝐴1𝑝 ⋮ 𝐴𝑝𝑝
𝑥1 ⋮ 𝑥𝑝
Számítás közben a feladatot blokkokra bontjuk majd a részeredmények összegződnek (y érték inicializálása az első lépésben) Kommunikáció, az x vektor értékeit körbeadják. Minden egységben ugyanaz az algoritmus fut, add jobbra, várd balról és számold. Lépés
Proc(1)
Proc(2)
Proc(3)
1
𝑥3
𝑥1
𝑥2
2
𝑥2
𝑥3
𝑥1
3
𝑥1
𝑥2
𝑥3
3
Amikor a részvektor (x) megérkezett: Lépés
Proc(1)
Proc(2)
Proc(3)
1
𝑦1 = 𝑦1 + 𝐴13 𝑥3
𝑦2 = 𝑦2 + 𝐴21 𝑥1
𝑦3 = 𝑦2 + 𝐴32 𝑥2
2
𝑦1 = 𝑦1 + 𝐴12 𝑥2
𝑦2 = 𝑦2 + 𝐴23 𝑥3
𝑦3 = 𝑦2 + 𝐴31 𝑥1
3
𝑦1 = 𝑦1 + 𝐴11 𝑥1
𝑦2 = 𝑦2 + 𝐴22 𝑥2
𝑦3 = 𝑦2 + 𝐴33 𝑥3
𝑝
(
𝑃 𝜇 𝑓𝑜𝑙𝑦𝑎𝑚𝑎𝑡𝑜𝑧: 𝑧𝜇 = 𝑦𝜇 +
𝐴𝜇𝑟 𝑥𝑟
)
𝑟=1
A processzoroknál van a mátrix megfelelő darabja, és az x vektor egy része (r darab sora az x vektornak). Az adatok így szétoszthatók a különböző egységek között.
Az algoritmus hatékonysága úgy növelhető, ha minden processzor azonos terhelést kap, tehát ugyanannyi feladatot.
Terheléselosztás Speciális esetben alsó háromszög mátrix, akkor a terhelés nincs jól elosztva:
A terhelés megfelelő elosztásához az egyes processzorhoz tartozó részeket át kell rendezni.
4
A példában a mátrix 9x9 méretű és a p = 3, tehát minden processzorhoz r=3 rész tartozik. Ezeknek a részfeladatoknak az elosztásával lehet a módszert hatékonyabbá tenni. 2𝑟 2 𝑠𝑧á𝑚í𝑡á𝑠𝑖 𝑖𝑑ő 𝑅 ≈ , 𝑘𝑜𝑚𝑚𝑢𝑛𝑖𝑘á𝑐𝑖ó𝑠 𝑖𝑑ő 2 𝛼𝑑 + 𝛽𝑑 𝑟 𝛼𝑑 : 𝑠𝑒𝑛𝑑 𝑣𝑎𝑔𝑦 𝑟𝑒𝑐𝑣 ö𝑠𝑠𝑧𝑒á𝑙𝑙𝑦𝑡á𝑠á𝑛𝑎𝑘 𝑖𝑑𝑒𝑗𝑒, 𝛽𝑑 : ü𝑧𝑒𝑛𝑒𝑡 á𝑡𝑣𝑖𝑡𝑒𝑙 𝑖𝑑𝑒𝑗𝑒, 𝑅: 𝑅 𝑓𝑙𝑜𝑝𝑠 𝑝𝑒𝑟 𝑠𝑒𝑐𝑜𝑛𝑑 (𝑚ű𝑣𝑒𝑙𝑒𝑡𝑣é𝑔𝑧é𝑠) A terhelés elosztás problémája abból fakad, hogy ha 0 érték szerepel a mátrixban, ott nem kell számolni. A szélső esete az alsóháromszög mátrix, ami gyakran előfordulhat (pl. a rendszer örök életére dolgozhat ilyennel ). A probléma megoldása, hogy közel azonos mennyiségű számítási feladatott adjunk ki a processzoroknak. Az alsóháromszög mátrixhoz tartozó ábra, csak szemlélteti a problémát és a megoldását.
5
