Bevezető
Sokszor és sokan vagyunk elégedetlenek a felhasználói programok vagy játékok sebességével, gépigényével, amit általában a rendelkezésre álló számítási kapacitás hiányának, tehát a hardver szűkös erőforrásainak tudunk be. De minden éremnek két oldala van, így most bekukkantunk a másik, azaz a szoftveres oldalra is. Alapvetően persze ezt is a hardver felől tesszük, így – és a közérthetőség végett – néhány programozástechnikai részletet leegyszerűsítettünk vagy kihagytunk, ez a leírás ugyanis nem arról szól, hogy bárkit megtanítsunk professzionális szinten az optimalizálás mesterfogásaira. A témát a tudományos számítási feladatok irányából közelítjük, de egészében véve a rendelkezésre álló processzor jobb kihasználásáról lesz szó most – néhány részlet valószínűleg sokkal inkább lesz érthető a GPU-n programozóknak, mert az új processzorok bizonyos szempontokból közelítenek a mai grafikus egységekhez.
Idén szeptemberben az IDF-en Victor Lee tartott egy nagyon érdekes előadást az optimalizálásról, melybe természetesen a marketingesek is beleszóltak, hiszen egy kicsit reklámozni kellett az új Xeon Phít – Lee úr tehát kellő mennyiségben, de érdekfeszítően beszélt erről is. De kezdjük az elején! Victor Lee vezető beosztású mérnök az Intel Santa Clara-i kutatólaboratóriumában, ahol az architektúra, illetve a szoftverek optimalizálásával foglalkozik. Részt vett a Pentium 4, az Itanium és a QPI busz kifejlesztésében is. Érdekes az is, hogy 1997 óta dolgozik az Intelnél, holott a Szilícium-völgyben általában 3-4 évente munkahelyet vált a legtöbb ember. A processzorok tervezése esetén azonban más a helyzet, hiszen több generáció is kellhet egy architektúrának, mire az kiforrja magát, így tehát logikus, hogy azok vigyék végig, akik már jól ismerik.
Az optimalizálással alapvetően az a baj, hogy sosincs rá (elég) idő. Sajnos elterjedt az a nézet, miszerint a hardver annyira olcsó, hogy egyszerűen jobban megéri erős vasat, mintsem okosan megírt szoftvert használni. A baj csupán, hogy olyan ez, mint a terhes nő esete: ha egy nő kilenc hónap alatt kihord egy gyereket, attól még három nővel ugyanez nem sikerül három hónap alatt! Bevezetésként tehát nézzük meg a számítási teljesítmény változását az elmúlt négy évtizedben, mely érdekes módon nem csupán megsokszorozódott, hanem nagyjából tízévente egy nagyságrendet ugrott.
Victor Lee több olyan témát is felvetett, amihez kis túlzással sosem elég a számítási teljesítmény. Ilyen példának okáért az anyagok viselkedésének szimulálása, a tőzsdei információk elemzése (előrejelzése), a csillagkutatás, az embertömeg szimulációja (pánikhelyzetben a tömeg viselkedése), az energiakutatás, az orvostudomány stb.
Intel processzorok ma
A processzorok fejlődésének útja nagyon sokáig az egy szálon elérhető teljesítmény növeléséről szólt. Ennek legkézenfekvőbb megoldása az órajel növelése volt, azonban egy bizonyos határnál már nem éri meg vagy egyszerűen nem megoldható a további emelés (bár az Intel kutatólaboratóriumában volt 10 GHz-en üzemelő processzor is, mint az kiderült egy másik előadáson). Ekkor fordultak a többprocesszoros és többmagos, később többszálú (HT, azaz HyperThreading) megoldások felé. Ezek viszont új programozói hozzáállást is igényelnek, mivel az ilyen típusú processzorokat többszálú programokkal lehet jól kihasználni. Tehát, ha a gondolkodásunkat és a kódunkat hozzáigazítjuk az adott platformhoz és a processzor(ok)hoz, akkor megtarthatjuk az alkalmazások teljesítménynövekedésének ütemét.
Nézzük, miből gazdálkodnak most a szerencsés programozók! Az új Xeonok a nehéztüzérségnek számítanak (Xeon v2): maximum 12 mag, 2,0-3,4 GHz-es órajel, HyperThreading, óriási L3 cache (10-30 MB) és 128-256 bites SIMD. A Xeon Phi ezzel szemben 50-61 mag, 1-1,25 GHz, négyszálú HyperThreading és 512 bites SIMD. Utóbbinál még jobban látszik a tendencia a párhuzamosítás irányába. Ami szintén érdekes – de érthető –, hogy az egyes magokon elérhető memória-sávszélesség csökken.
Az Intel Xeon Phi
Victor Lee két fő csapásirányt nevezett meg: a lehető legjobb párhuzamosítást és az adatok leghatékonyabb kezelését. Az első a párhuzamosan végrehajtható utasításokkal, a „többszálúsítással” és a több mag kihasználásával operál, míg a második az, ami kicsit nagyobb elmélyedést igényel a processzor lelkivilágában. Itt jön be a memóriavezérlők csatornánkénti és/vagy magonkénti sávszélessége és az L1, L2 és L3 gyorsítótárak (cache) megfelelő kihasználása. Igaz, hogy egyelőre a cache működésébe nem nagyon lehet beleszólni, de rebesgetnek valamit egyfajta cacheQoS-ről is. Per Hammarlund (többek között a Haswell főtervezője) erről azt mondta, hogy a cache működését a mostani tipikus számítási feladatokhoz optimalizálták, és az esetek 99 százalékában meg is felel a programozóknak.
Létezik azért többszintű prefetch utasítás is, és az Intel C fordítója (ICC) is támogat már elég sok cache-sel kapcsolatos beállítást. Ebből a szempontból a GNU C fordítója (GCC) érthetően le van maradva, de állítólag nagyon jó munkát végeznek úgymond reverse engineeringben, tehát várható, hogy előbb-utóbb felbukkannak hasonló beállítási lehetőségek ott is.
Programfejlesztés, vektoriális modell
A klasszikus szoftverfejlesztési modell három lépcsőből áll:
- Tervezés: a legjobb algoritmusok és adatstruktúrák kiválasztása;
- Implementálás: megvalósítás a futtató architektúra és a rendelkezésre álló eszközök figyelembevételével;
- Analízis: teljesítmény ellenőrzése és javítása.
Az eddigi megközelítésben két „vázból” állt a modell: először megírták a kódot az adott programnyelv sajátosságainak figyelembevételével, majd jöhetett az optimalizálás (scalar framework). Amikor már elégedettek voltak a program teljesítményével, akkor jöhetett az adott processzor utasításkészletének legjobb kihasználása, ezzel további sebességnövekedéshez jutva (vector framework).
Lee úr ezt a két vázat kiegészítette egy harmadikkal, a párhuzamosítással, tehát az egy szálon kielégítően futó programunkat megpróbáljuk több szálon is hatékonyan futtatni. Nyilván létezhetnek olyan esetek, amikor már sokkal korábban kell gondolnunk a többszálú futtatásra, de általános iránymutatásnak nagyon jó és egyszerű ez a megközelítés. További érdekesség még, hogy a programunk által használt erőforrások függvényében az analízis és az optimalizálás az egyes szinteken más-más nagyságú gyorsulást hoz.
A skaláris modell
Az algoritmusok megválasztásánál két tényezőt írt le: a komplexitást és az intenzitást. A komplexitás gyakorlatilag az adott adaton elvégzendő számítás mennyiségét és bonyolultságát, míg az intenzitás a memóriából beolvasandó és kiírandó adatmennyiséget jellemzi. Nyilván processzorunk akkor optimálisan kihasznált, ha nem kell a memóriára túl sokat várni, de nem is töltünk el olyan dolgok kiszámításával értékes ciklusokat, amelyek közben olcsón elérhetőek lennének a memóriából is. Az adatstruktúrák esetében azok szerkezetét és méretét célszerű okosan eldönteni, például érdemes a cache-line méretét figyelembe venni, és a leggyakrabban használt adatokat tenni előre. Általában drága a 16 bájt határon átnyúló adatok használata, illetve a bitmezőkkel is érdemes spórolni, ha csak egy-két bitet akarunk használni, hiszen bejön/bejöhet velük plusz léptetés. Lehetőség szerint inkább használjunk egy folyamban, de legalábbis nagyobb egységekben olvasható adatokat, és kerüljük a véletlenszerűséget.
“A fordító a barátod”, szól a mondás, és ebben van igazság! Az Intelnél (is) rengeteg időt szentelnek a fordítók okosítására. Egyrészt jobban kihasználják a hardver képességeit automatikusan, másrészt egyre több lehetőséget nyújtanak a testreszabásban. Ugyanakkor a fordító nem a Szent Grál, nem old meg minden problémát, és nem javítja ki a hanyagul megírt kódot. Szükség van jól optimalizálható kódra (pragmák, vektorizálható kód stb). Használjuk ki az architektúra képességeit! Egyik kedvenc a streaming store, amikor úgy tudunk inicializálni egy teljes cache-line-nyi adatot, hogy azt nem kell előtte beolvasni, hiszen tudjuk, hogy a teljes 64 bájtot felülírjuk. Érdemes továbbá használni a hardveres támogatást élvező utasításokat, hiszen sokkal nagyobb teljesítményt lehet velük elérni (pl. egyszeres pontosságú RECIP és RSQRT a Xeon Phín 1 órajelciklust vesz igénybe).
Az analízis történhet analitikus vagy dinamikus módon. Az analitikus mód nagyon fontos lenne már a kódolás korai szakaszában, hiszen ha tudjuk, hogy az adott C kód milyen gépi kóddá fordul, akkor lehet sejtésünk maximális teljesítményéről. Ha tehát már az analitikus elemzés idején kiderül, hogy a megcélzott teljesítmény közelében sem vagyunk, akkor még időben lehet más megoldást keresni. A dinamikus analízisre szerencsére több eszköz is létezik, fizetősök és ingyenesek egyaránt. Az Intel processzoraiban (is) van meglehetősen sok belső számláló, amit teljesítményelemzéshez lehet felhasználni. Ilyen program például a gprof, az oprofile, a Valgrind az ingyenesek közül, vagy az Intel VTune a fizetős csapatból, természetesen a teljesség igénye nélkül. Ezeknek az eszközöknek a használatához már érdemes kicsit elmélyedni a processzorok működésében. Az Intel VTune jól használható grafikus kezelőfelülettel rendelkezik, de természetesen futtatható parancssorból is, ami sokszor megkönnyíti az életet. Van pár előre beállított elemzésmódja, azok nagy segítséget jelentenek a kezdeti analíziseknél.
Vektoriális modell, párhuzamosítás
A vektoriális modell
Amikor már az elérhető legjobb algoritmusunk van a skaláris elemzésnek köszönhetően, akkor dönthetjük el, hogy vertikális vagy horizontális vektorizálást alkalmazunk-e. Alapvetően a SIMD utasításkészlet nagy előnye, hogy több, egymástól független adaton lehet egyszerre dolgozni. Victor Lee a képfeldolgozást említette, amikor például több pixelen lehet ugyanazt a műveletet végrehajtani. Ennek a megoldásnak az előnye, hogy viszonylag egyszerű, és ha a program jól van megírva, akkor a fordító ezt automatikusan meg tudja csinálni. Hátránya viszont, hogy egyszerre nagyobb mennyiségű adaton dolgozva sokkal könnyebb összeszemetelni a cache-t, amitől elég sokat lehet lassulni.
A horizontális vektorizálás az az eset, amikor megpróbálunk ugyanazon az adaton több műveletet elvégezni, ami általában kisebb adatmennyiséget igényel egyszerre, viszont több munkát a programozótól. Adatstruktúrák esetén itt merül fel a kérdés, hogy struktúrákat szervezzünk tömbbe vagy tömböket struktúrába. Hagyományosan legtöbbünk struktúrákat szervez tömbbe (array-of-structure), ami jól olvasható kódot eredményez. Ezzel az a probléma, hogy tipikusan minden egyes struktúrának ugyanazon az elemén akarunk végigmenni, ami azt eredményezi, hogy jó eséllyel csak sok olvasásnyi költséggel tudjuk ezt megvalósítani. Tipikusan, ha például x, y és z koordinátákat tárolunk, és az összes x koordinátán akarunk először végigmenni, akkor float típusú adatok esetén minden 12. bájtra van szükségünk. Erre nincs túlságosan jó hardveres támogatás még akkor sem, ha a prefetch hajlamos felismerni mintákat is. Ezzel szemben, ha az x koordinátákat szervezzük egy tömbbe, az y koordinátákat egy másikba és a z-k kerülnek egy harmadikba, akkor az egymást követő koordinátákon sokkal hatékonyabban tudunk végigmenni. Természetesen ennek is megvan a maga hátránya: ha nem eleve ilyen szervezésű az adatunk, akkor konvertálni kell, ami nagyon költséges is lehet.
Az implementálási szakaszban pl. segíthet az Intel Cilk Plus, használhatunk pragmákat (simd, ivdep, aligned), amelyek a fordítónak segítenek, vagy írhatunk rögtön vektorizált kódot is. Figyeljünk oda, hogy egyszeres vagy kétszeres pontosságú adatokkal dolgozunk-e (az ajánlás szerint törekedjünk a használható legkisebbre), de semmiképp se keverjük, mert akkor a fordító nem tudja automatikusan vektorizálni. Ismét csak használjuk bátran a hardver speciális képességeit, ebben az esetben pl. alignment (palign, valign), pack/unpack stb.
A vektoriális modell analízisénél számolhatunk például vektorsűrűséget (az összes vektorutasítás és az összes utasítás hányadosa) vagy effektív SIMD hányadost (utóbbi megmutatja, hogy a SIMD x utasításszélességét mennyire használjuk ki). A SIMD hányadost a VTune is kiszámolja, aminek egy mostani Xeon processzor esetén illik azért 2 felett lennie, és akkor még nem beszélhetünk hatékony kódról.
Párhuzamosodjunk!
Eddig tartott a klasszikus modell esetén az optimalizálás. Látható, hogy ha komolyan gondolják, akkor igencsak gondolkodás- és erőforrás-igényes folyamat. Vágjunk hát bele az utolsó, de egy ideje talán a legfontosabb szempont szerinti optimalizálásba, a párhuzamosításba!
Ha már egyetlen magon (vagy inkább egyetlen szálon) elégedettek vagyunk a hatékonysággal, ideje kihasználni az összes párhuzamos erőforrásunkat. Rögtön beleütközhetünk Amdahl törvényébe, ami pongyolán fogalmazva azt mondja ki, hogy a párhuzamosítás által elérhető sebességnövekedést korlátozza a szekvenciális kód mennyisége. Tehát el kell dönteni, hogy a kód mekkora/melyik részét akarjuk párhuzamosítani, és melyiket meghagyni szekvenciálisnak. Sajnos a legjobb szekvenciális kód nagyon sokszor nem a legjobban párhuzamosítható. Például ha írtunk egy kis aritmetikai sűrűségű kódot, ami kiválóan fut egyetlen szálon, viszont az adatok függnek egymástól, akkor ez nem párhuzamosítható egyszerűen.
Nagyon fontos a rendelkezésre álló cache és sávszélesség megfelelő kezelése. A processzorok többsége ugyanis úgy van tervezve, hogy az egyes magok valójában nagyobb sávszélességet tudnak felhasználni, mint amennyi a teljes sávszélességből egyenlően rájuk esne. Lee úr ezt úgy magyarázta, hogy a cache nagyon hasonlít az emberi agy működéséhez ilyen szempontból: közepes terhelésen minden rendben, minden szép és sehol egy hiba. Azonban ha az emberi agyat elkezdjük teljesítőképességének határaihoz közel terhelni, akkor előbb-utóbb kiesik a ritmusból, és bizony megakad, belassul néha. A gyorsítótárak hatékonyabb kihasználásában segít a blokkosítás/tömbösítés. Ez azt jelenti, hogy megpróbáljuk a felhasználandó adatokat akkora szeletekre bontani, hogy egyrészt a helyi cache-ekbe beférjenek, másrészt a prefetch algoritmus meg tudja tanulni az adatelérési mintát. Az implementálás területén elég sok segítséget kapunk megfelelő API-któl és könyvtáraktól, úgymint OpenMP, Intel Cilk, Intel Threading Building Blocks, pThreads stb.
Természetesen nincs mindez ingyen, a párhuzamosítással bejönnek annak "költségei" is: programszálak indítása/leállítása, szinkronizálás a szálak között és egyéb korlátozások. Mindezek figyelembevételével dönthetünk úgy, hogy nem akarjuk kihasználni az összes párhuzamos erőforrásunkat, mert egyszerűen nem éri meg. Például egy Xeon Phi 60 magján futó programunk szinkronizálása lehet annyira bonyolult, hogy érdemesebb 4 vagy 8 szálban gondolkodni csak.
Az adatok megosztása a magok között szintén okozhat fejtörést. Előfordulhat például, hogy két mag ugyanazon a cache-line-on elhelyezkedő különböző változót használja, legrosszabb esetben egymást fogják lassítani az állandó frissítéssel. Könnyű tehát elérni, hogy a magok versengjenek egymással az erőforrásokért, így minden további nélkül ki is lehet éheztetni ezeket. És itt jön be megint az analízis! A korábban említett számlálók és egy megfelelő program használatával jól lehet saccolni, hogy mi történik kódunk futása közben. A VTune beépített profiljainak valamelyikével megnézve, hogy hol tölti el a legtöbb időt a programunk, van lehetőségünk célzott módosításokat végrehajtani. Egyszerre látjuk a programforrást és a gépi kódot is az adott utasításban eltöltött idővel együtt. Itt jön jól, ha sejtjük a processzor működését, és láttunk már assembly-t is.
Végszó
Zárásként nézzük meg még egyszer összefoglalva, hogy az egyes szinteken milyen eszközeink lehetnek programunk jobbá tételére!
Az IDF-en mutattak pár példát is, hogy a megfelelő eljárásokkal mekkora sebességnövekedést tudtak elérni (természetesen ahol a Xeon Phi nagyon jól teljesít, ott ezt külön kiemelték).
- Mátrix szorzás: Egy „közönséges” Core i7-975-ön 64-szeres sebességnövekedés érhető el az említett technikák alkalmazásával. A konkrét megvalósítás Dhiraj Kalamkar és Sangeeta Bhattacharya (Intel Labs, India) kutatásának eredménye.
- STAC-A2 sebességteszt: A STAC-A2 egy architektúra-független sebességteszt-csomag, ami a Monte Carlo módszerrel piaci kockázatok számítását végzi. A legnagyobb bankoknak több ezer gépből álló fürtjei vannak, melyek hasonló számításokat végeznek folyamatosan. Nem kérdéses, hogy mennyit lehet nyerni az ilyen jellegű programok adott architektúra történő optimalizálásával.
- Hydro: Jason Sewall 2011-es disszertációjának anyaga, melynek címe "Hatékony és skálázható forgalom és összenyomható folyadékszimulálás hiperbolikus modellek alkalmazásával". Az eredeti algoritmusok finomhangolásával jelentős teljesítménynövekedésre tehetünk szert.
Összegzésül, első körben azt lehet elmondani, hogy szomorú, de jól jellemzi az optimalizálás elhanyagoltságát az a tény, hogy a 250 fős előadóban legfeljebb harmincan voltak kíváncsiak erre a témakörre. Másodszor, a kód hatékonyságának javítása rendkívül időigényes és összetett feladat. Érthető, hogy sok fejlesztő és cég nem szán rá (elegendő) időt, de ez nem elfogadható. Természetesen van egy határ, aminél tovább javítani a kód hatékonyságán már aránytalanul sok időbe kerül, de sajnos eddig a pontig is igen kevesen jutnak el. Harmadszor pedig jó látni, hogy vannak még emberek, akik lelkiismeretesen és hatalmas tudással a hátuk mögött dolgoznak az optimalizáláson.
Végezetül az aktuális Biblia a témával kapcsolatban. Forgassátok egészséggel! Továbbá az előadások anyaga is letölthető innen.
&rew
