SIMD és párhuzamosítás

[Daniel Berenyi]

Sziasztok!

Leírok pár gondolatot - mert nagyon bugyognak bennem - és hátha van valami jó ötletetek hozzájuk.

Szóval azon gondolkozok, hogy hogyan kéne a SIMD-s vektor utasításokra és a GPUs nagyon mély hierarchiájú párhuzamos végrehajtókra jól kódot generálni, és nem akar összeállni a dolog (nyilván nem triviális).

Illetve az a rész triviális, ha teljesen független feladatok vannak, amin ugyan azt a műveletsort kell végigcsinálni, és a szálak között nincs adatfüggőség / kommunikáció, akkor az triviálisan párhuzamosítható (vagy szekvencializálható, ha visszafelé kell menni). De a többi eset nagyon nehéz.

Az egyik ötlet: hasonlít-e ez a dolog a regiszter allokációra? Pl. az ember azt mondhatja, hogy tegyük fel, hogy van végtelen sok szálunk, és megpróbáljuk azokra szétosztani a feladatot (először lebontjuk skalárokra), majd ezeket megpróbáljuk egymásmellé gyűjteni, hogy vektorutasítások legyenek belőlük, illetve ha kevesebb szál van, mint ami kell, akkor vissza-szekvencializálunk. Működhet-e ez? (elvileg a Csaba által említett ISPC v mi, Inteles compiler hasonlókat csinál messziről nézve, asszem).

Viszont az adatkommunikációknál és a többszintű esetben nem tudom mi van. A GPU-s tájkép alulról nézve a következő durván nézve:

- alul vannak a 128 bit-es SIMD regiszteres műveletek, ez kb. ua mint a CPU-kon.

- ezeken felül vannak a szálak 32 vagy 64-es csoportokban (warp NVIDIA-n, wavefront AMD-n, etc). Itt vannak olyan műveletek, amelyek a warp szálak között skalár regiszter méretű (32-64 bit) adatokat tudnak átvenni (shuffle szerű), ami nagyon gyors és hatékony. Időnként még a divergens esetek is kezelhetőek + van maszkolás, ha nem kell minden szál az adott művelethez. Ezekből úgy fest egyre több lesz.

- a warpok/szálak felett van a rendes "nagy" szálcsoport, ami kb. 256-1024 szálat tartalmaz, tehát jónéhány warpot ölel fel. Ez a legnagyobb egység, amin belül a szálak még szinkronizálhatóak az élettartamuk alatt, illetve van egy dedikált gyors memóriája (shared/local memory), ami néhány 10k byte méretű és csak ez a csoport látja.

- a szálcsoportok felett van a teljes számítási rács, ami ki lett küldve a kártyára, amelyből azonban nem biztos h egyszerre mindegyik fut, így azok között nincs szinkronizáció, csak a kernelhívás vége, és csak a globális, lassú memórián (VRAM) keresztül kommunikálnak.

- aztán ugye lehet még több kártya is egy gépben, ahol az eszközök között gyorsabb lehet a kommunikáció, mint a RAM felé.

Szóval erre elég macerás átképezni számításokat, kérdés, hogy mit érdemes csinálni. Néhány elképzelés:

- mivel a fordító mindig limitált lesz, a programozónak kell tudnia expliciten leírnia ilyesmiket, viszont ha mindenhova át kell adogatni ilyen szálcsoportokkal kapcsolatos paraméterket, az elcsúfítja a kódokat (pl. ha user defined operátort akar az ember, akkor nem is "fér el" az ilyen info).

- node vannak ezek az implicit argumentumok, és lehetne ezt kicsit abuzálni, és lehetne absztraktul azt mondani, hogy egy adott függvényt a programozó megírhat néhány különböző granularitásban, pl. 4-32-256-os szálmérettel, és ezek közül választhat a fordító, amikor oda jut, hogy na ezt az adott függvényt éppen milyen környezetbe kell beágyazni és ott valójában mennyi szál van. Mert párhuzamos kódból visszatérni szekvencializált kódra valszeg könnyebb, mint fordítva. És ez a paraméter olyasmi lenne, ami fordítási időben eldől, így az ehhez kapcsolódó esetszétválasztás teljesen eltűnhet fordításkor. Cserébe viszont lehet, hogy sok kód duplikációval jár, amit nem akarok de még nem látom át ez hogy nézne ki jobban.

- lehetne a szálcsoportosdinak egy absztrakt modellje, ahol alapvetően az absztrakt szálak között scatter, gather és shuffle műveletek vannak, meg szinkronizáció, meg ilyesmik, mert úgyfest az minden ilyen környezetben van nagyjából.

- nem tudom minek kéne előbb eldöntődnie: a párhuzamosításnak, vagy a memória layoutnak, valószínűleg mindkét irányban kéne tudnia működni a megszorításnak és alkalmazkodásnak, mert mindkettőre vannak use-casek.

Egy másik érdekes aspektus: mennyire lehet tudni, hogy honnan jön a párhuzamosítási lehetőség? Nekem valahogy azaz intuícióm, hogy mindig abból indulunk ki, hogy valamiből sok van, és azok ugyan azt akarjuk csinálni, és ennek magas szintről kéne látszódnia, tehát felülről lefelé.

Ugyanakkor meg az clang/llvm vektorizációjánál olvastam, hogy abban van olyan pass, ami nézegeti előre hátra N utasításig, hogy hol vannak összevonható skalár műveletek, amikből vektor műveletet lehet csinálni. Ez meg alulról felfelé megy. Szerintetek ez is olyan, hogy mindkettőre szükség lehet, vagy a clangos csak kényszermegoldás, mert nincs elég felülről jövő információja?

Egyelőre kb. itt tartok ezügyben...

üdv,

D.

[Csaba Hruska]

Szerintem eloszor ne statikus elemzesben es optimalizatioban gondolkodj, hanem epiteni kene egy rendszert amiben megfigyelheto a runtime viselkedes, hogy mikor var a GPU es mikor van jol kihasznalva. Adat nelkul nem lehet errol gondolkodni. Pl az elmeleti fizikusoknak is kell a sok meresi adat a modellalkotashoz. Szerintem adat nelkul ez gyakorlatilag megoldhatatlan problema.

--
Azért kapta ezt az üzenetet, mert feliratkozott a Google Csoportok „compiler-seminar-budapest” csoportjára.
Az erről a csoportról és az ahhoz kapcsolódó e-mailekről való leiratkozáshoz küldjön egy e-amailt a(z) compiler-seminar-b...@googlegroups.com címre.
Ha szeretné megtekinteni ezt a beszélgetést az interneten, látogasson el ide: https://groups.google.com/d/msgid/compiler-seminar-budapest/CABmfui3dyt1nDBWMpYUWUrZ5%2BBcJe_Z5Bce5%2BQytFkHswnS1YQ%40mail.gmail.com.

[Daniel Berenyi]

Még:

Az világosan látszik, hogy alapvetően sok minden, a loop struktúrák, a memória hozzáférési mintázatok, meg egyebek lineáris összefüggéseket követnek.

És tudom, hogy itt valahol bejönnek a képbe a polihedrális optimizerek, viszont nem látom át, hogy azok pontosan mit csinálnak, mennyire feasible-k, és mi az ami túlmutat rajtuk. Tehát valahogy ez a probléma jelentős részben algebrai.

Így felmerül az, hogy meglehet-e általánosan, parametrikus alakban csinálni egyes rutinokat, hogy a compilernek csak be kelljen helyettesíteni az aktuális kontextusban levő szálak számát (ill. esetleg extra paramétereket) és megkapjon egy használható átrendezést, ami esetleg nemtriviális kombinációiból jön ki mindenféle lineáris formuláknak... Persze ez megint felveti azt a problémát, hogy nem pont az lesz leírva a forráskódban, ami a végén a binárisba kerül, és nehezebb lesz látni h mit is csinál a kód, ezért ezt lehet, hogy valahogy transzparensebben kéne tudni leírni, és így inkább a compiler által ismert algebrai átrendezésekre lyukadok ki megint...

D.

On Sat, Mar 20, 2021 at 4:30 PM Daniel Berenyi <u23...@gmail.com> wrote:

[Daniel Berenyi]

Na, utolsó:

Szóval olyasmire gondolok, ami viszont nem idegen mondjuk a jelenlegi programozástól, hogy a compiler képes legyen esetleg egy indukciót megcsinálni ezen a téren, például:

- Nézd compiler, itt van ez a probléma (pl. egy függvény v expression), amit nem triviális párhuzamosítani.

- de amit felírtam neked, az egy indukció base case-e, a legkisebb eset, ami minden fontos dolgot reprezentál, és helyesen működik, pl. 4 szál esetére.

- adok neked valamilyen formában indukciós szabályokat, amelyek megmondják, hogy hogyan lehet tovább lépni n-ről pl. 2*n szálra

- legyél szíves előállítani a 32, 256, vagy 1024 szálra vonatkozó változatát ennek a kódnak (tehát az összes memória foglalással, adatmozgatással, szinkronizációval, etc, etc együtt).

Ez elég sok esetben úgy érzem, hogy működne, és a base case tök olvashatóvá válna, csak az indukció leírás DSL-jét kéne jól kitalálni....

D.

[Attila Lendvai]

Ugyanakkor meg az clang/llvm vektorizációjánál olvastam, hogy abban van olyan pass, ami nézegeti előre hátra N utasításig, hogy hol vannak összevonható skalár műveletek, amikből vektor műveletet lehet csinálni. Ez meg alulról felfelé megy. Szerintetek ez is olyan, hogy mindkettőre szükség lehet, vagy a clangos csak kényszermegoldás, mert nincs elég felülről jövő információja?

nekem csak DSL temaban van tapasztalatom, a GPU-s dolgokrol eleg keveset tudok. de mindezek fenyeben:

szerintem nem erdemes sokat agyalni az alulrol felfele vektorizacion. egyreszt szerintem idopazarlas, masreszt meg az LLVM-es emberek el fogjak pazarolni az idejuket ra, es te kapsz majd valamit keszen.

az ilyen problemakat szerintem kizarolag fentrol lefele erdemes kezelni, mert ha meg is oldhato ertelmesen a masik iranybol, akkor a megoldas komplex lesz, es torekeny.

szerintem inkabb abba erdemes energiat tenni, h ugy lehessen megforalmazni az algoritmust, egy olyan DSL-el, h abbol viszonylag kis komplexitassal generalhato legyen a hatekony vektorizalt kod.

- attila

[Csaba Hruska]

Ragugliztam es van open source cpu-gpgpu simulator amivel lehet vizsgalni a caches es memoria varakozast is:
https://gem5-gpu.cs.wisc.edu/wiki/

En a helyedben megvizgsalnek es megertenek kulonbozo jo es rossz teljesitmenyu cuda programokat a szimulatorban es a latottak alapjan probalnek kitalalni egy modellt az hatekony program forditasra.

--
Azért kapta ezt az üzenetet, mert feliratkozott a Google Csoportok „compiler-seminar-budapest” csoportjára.
Az erről a csoportról és az ahhoz kapcsolódó e-mailekről való leiratkozáshoz küldjön egy e-amailt a(z) compiler-seminar-b...@googlegroups.com címre.

Ha szeretné megtekinteni ezt a beszélgetést az interneten, látogasson el ide: https://groups.google.com/d/msgid/compiler-seminar-budapest/0nUY7EEOs0VQS5DUNT8McURaIsGloRuphzIILJIlWRWk3f2t9Yts_iHV3YZd9pnLth8mJGMMBoQUkv9HBlXS9BSDPjfKbaJxuuX7SkgmVi0%3D%40lendvai.name.

[Daniel Berenyi]

Attila: Igen, én is így gondolom. A kérdés az, hogy mi az általános jellemzője azoknak a dolgoknak, amikből a végén alul párhuzamos számítások születnek. Az alap tipp az, hogy ez valami reprezentálható funktor struktúra, kérdés h mi meddig illik ebbe bele és mi nem.

Csaba: Nem pont ez a kérdés (amúgy ez a projekt kb. 4-5 éve leálltnak néz ki), mert arról azt hiszem elég jó sejtésem van már, hogy hogy kell egy konkrét rutint optimalizálgatni. A kérdés inkább high-level reprezentációs / beágyazási / DSL kérdés: mi lenne az a jó modell, ami nem veszik el a 100 féle hardver részletben, érthető a programozó számára és a compiler számára és jól definiált átalakításokat tudunk vele elvégezni, amelyek könnyen érthető és implementálható kódból hatékonyabbat csinálnak. Ismételten nem 100%-os hatékonyság a cél, hanem valami olyan ami elért teljesítmény / befektetett munka tekintetében nagyon jó kompromisszum.

D.

[Csaba Hruska]

En nem tudom a valaszt hogy mi a jo modell es hogy kell, szoval nekem ezert tuti kene ilyen mini labor, amiben mindent meg tudok nezni. Az egyaltalan nem szamit hogy aktivan van fejlesztve vagy sem. A semmihez kepest sokkal tobb es a celnak pedig megfelel.

[Gábor Lehel]

Igen én is azt gondolnám hogy az alulról felfele autovec az egy kényszermegoldás (vagy másik szemszögből egy "miért is ne", elvégre arra van az optimalizáló hogy optimalizáljon, ha tud). Az ISPC-s blogposzt sorozat mesélt is erről a konfliktusáról az inteles fordítóírókkal, érdemes lehet elolvasni (ha még nem).

Apropó ISPC: csak olyan szinten hivatkozod, hogy "Csaba által említett", viszont jó lenne tudni (nekem legalábbis nem világos), hogy az miben tér el attól, mint amit te szeretnél, mik a hiányosságai stb. Konkrét viszonyítási pontokból sokkal könnyebb kiindulni, hogy a probléma magját legalább megsejtsem.

De (nulla vektor vagy GPU-s programozási háttérrel! azon kívül hogy olvastam néha dolgokat, meg most ezt az emailt) az első gondolatom nekem is az lenne, hogy lehetne-e vajon úgy csinálni a dolgokat (reális lenne-e), hogy a programozó által írt kód tud az összes rétegről és azokat expliciten kezeli (tud csinálni ilyen szálcsoportok közötti shuffle-eket, meg lokális memóriát elérni), csak azt nem tudja, hogy melyik mekkora, és ezeket absztrakt paraméterként kell kezelnie. (Ill. akár esetleg tudhatna még tenni bele explicit specializációkat is ezen felül, opcionálisan.) (Illetve még, ami mégspekulatívabb, esetleg a kódon belül lehet hogy tudna csinálni magának absztrakciókat az adott alsóbb réteg felett, amikor _nem_ akar expliciten foglalkozni vele.) A fontos use case-ek kifejezhetőek ilyen módon, és mennyit veszítenének teljesítményben ahhoz képest, ha konkrét számokhoz lennének írva? Ill. ez alacsonyabb szintű-e mint amire te gondolnál? (De ha egyáltalán működőképes, akkor köztes rétegnek akár még jó lehet.)

"A kérdés az, hogy mi az általános jellemzője azoknak a dolgoknak, amikből a végén alul párhuzamos számítások születnek." Ehhez megint kellenének konkrét példák ezekre a dolgokra (amikhez közülünk szerintem leginkább csak te értesz?), mert a homályos elképzelésekből nehezen lehet általánosítani.

Ha szeretné megtekinteni ezt a beszélgetést az interneten, látogasson el ide: https://groups.google.com/d/msgid/compiler-seminar-budapest/CANjChEoQVfFqrmxWaNSLQadbF_qBLH0yhymRUWZyuMpn4pYAAA%40mail.gmail.com.