GYakorlatok
Írd meg a Mandelbrot-generátor fixpontos implementációját.
a.
Azt fogod észrevenni, hogy a teljesítmény nem következetes a különböző pixelek és képkockák között. Miért van ez?
b.
Mi a legbelső ciklustest aritmetikai intenzitása, a memóriából elért bájtonkénti műveletekben kifejezve? Mi a megfelelő teljesítményhatár az ARM CPU számára? Hogyan viszonyul a megfigyelt teljesítményhez?
c.
Mérje meg a következő teljesítménymetrikákat a legbelső ciklustestre vonatkozóan:
▪
utasítások per iteráció
▪
utasítások per művelet
▪
CPI
▪
cache miss rate
d.
A legbelső ciklustest megvalósításához használjon inline assembly-t, és mérje meg a teljesítményre gyakorolt hatást a c. rész metrikáihoz képest. Mekkora a sebességnövekedés a fordító által generált kódhoz képest?
Parallelizálja a Mandelbrot-halmaz generátorát OpenMP használatával. Alkalmazza a parallel-for utasítást a legkülső (sor) ciklusra.
a.
Mérje meg a legbelső ciklus minden egyes iterációjához (a polinom kiértékeléséhez) szükséges ciklusok átlagos számát egy szál és két szál esetén a kezdeti kerethez. Használja ezeket a méréseket, hogy kiszámítsa a két szál sebességnövekedését (pixel per másodpercben kifejezve) az egy szálhoz képest.
b.
Mérje meg az első képkocka összes pixelének kiszámításához szükséges időt a dinamikus ütemezés használata esetén a statikus ütemezéshez képest.
Mi nehezíti a SIMD művelet alkalmazását a Mandelbrot-halmaz generátorához? Mi a leghatékonyabb módszer a SIMD művelet alkalmazására a Mandelbrot-halmaz generátorhoz?
Mérje meg a Linux Framebuffer hatékony írási átbocsátóképességét. Megegyezik-e ez a heapről allokált memóriatömb írási teljesítményével?
Kalkulálja ki a képtranszformációs program aritmetikai intenzitását pixelenkénti műveletekben. Mekkora a teljesítményhatára az ARM CPU effektív memóriateljesítménye mellett? Hogyan viszonyul a megfigyelt teljesítményhez?
Az OpenMP segítségével adjunk többmagos támogatást a fixpontos képtranszformációs programhoz. Ehhez alkalmazza a parallel for pragmát a legkülső (soros) ciklusra.
Mérje meg a teljesítményét egy négymagos ARM CPU-n. Hogyan skálázódik a teljesítménye egy, két, három és négy szálon történő végrehajtás esetén?
Az intrinsics segítségével adjunk NEON SIMD támogatást a képátalakító program fixpontos változatához. Négyutas műveletekkel számítsa ki a következő számításokat egy négy pixelből álló csoportra: forráspixel-helymeghatározás, frakciókivonat és súlyszámítás. Milyen mértékben javítja ez a teljesítményt?
A Mandelbrot-generátor programot nem tudjuk egyszerűen optimalizálni a SIMD utasítások használatával, mivel a szomszédos képpontok különböző számú polinomkiértékelést igényelhetnek, és a polinom minden egyes iterációja az előző kiértékeléstől függ. Egy alternatív megközelítés a ciklus inline assemblyben történő implementálása, legalább négyszeres feltekerés, majd a ciklus CPI-jének javításához szoftveres pipelining használata. Ebben az esetben kerülni kell a feltételes elágazásokat a feltekert cikluson belül. Mivel az eltérő c-értékek a további kiértékelésekkel tovább fognak eltérni, várhatunk a ciklus kilépési feltételének ellenőrzésével minden négy iterációból álló csoport után. Azonban további polinomkiértékelések elvégzése, miután egy Pc() potenciálisan a 2 sugarú körön kívülre tér el, megköveteli, hogy figyelembe vegyük a fixpontos formátumunk további tartományi követelményeit. Számítsuk ki újra a fixpontos tartományigényt ehhez az optimalizáláshoz, és határozzuk meg, hogy ez milyen mértékben csökkenti a maximális nagyítási szintet.
A fixpontosság alapvető előnyei a műveleti késleltetés csökkentése és a típuskonverziók elkerülésének lehetősége bizonyos típusú grafikus kódokban. A 2. fejezet egy olyan példaprogramot emel ki, amelynek teljesítménye érzékeny a műveleti késleltetésre, a Horner-módszert. Feltételezve, hogy a Horner-módszer kódunkban el tudjuk viselni a fixpontos tartománybeli korlátokat, javítaná-e a teljesítményt, ha fixpontosra alakítanánk át? Magyarázza meg válaszát.
A 3.6.5. szakasz egy általános fixpontos összeadás preprocesszor makró két különböző implementációját mutatta be. Az elsőt a gcc generálta maximális optimalizálás mellett, a másodikat kézzel kódoltuk inline assembly nyelven. Mindkét implementáció megközelítőleg ugyanannyi utasítást igényelt.
a.
Mutassa be az írást követő olvasás utáni adatfüggőségeket mindkét implementációban. Feltételezve, hogy a processzor egyetlen utasítást használ, sorrendben kiadva, és feltételezve, hogy az összes egészértékű aritmetikai művelet késleltetése négy ciklus, hányszor hasonlítsa össze a két implementációhoz szükséges adatleállító ciklusok számát.
b.
Írja át a fixpontos összeadás makró inline assembly változatát úgy, hogy az utasításokat úgy ütemezze, hogy a függő utasítások minél jobban elkülönüljenek egymástól. Milyen mértékben csökkennek az elakadások, az a. részben megadott késleltetési időt feltételezve?
c.
Írjon olyan kódot, amely bemutatja, hogy mindhárom implementáció (fordító által generált, inline assembly és ütemezett inline assembly) hogyan jellemezhető teljesítmény szempontjából.
Ebben a kérdésben a 3.6.6. szakaszban leírt általános fixpontos szorzás inline assembly implementációját vizsgáljuk.
a.
Hogyan viszonyul az utasítások száma és a futásidejű teljesítmény szempontjából az egyenértékű, fordító által generált kódhoz képest:
res = (((long long long)op1 * (long long long)op2) >> (rp1>rp2?rp1:rp2))) +(rp1>rp2 ? ((((long long)op1 * (long long long)op2) >> (rp1-1))&1) :
((((long long)op1 * (long long long)op2) >> (rp2-1))&1)));
A gcc-vel történő fordításkor mindenképpen használjuk a “-O3” és “-marm” kapcsolókat.
b.
A multiply makró inline assembly változatának utasításainak ütemezése az adatfüggőségi akadások minimalizálása érdekében. Mérje meg a teljesítményét a 3.6.6. szakaszban megadott változathoz képest.
c.
Az inline assembly implementáció esetében mennyivel nagyobb teljesítménnyel érhető el, ha úgy változtatjuk meg, hogy a radixpontok pozíciói fixek legyenek a kódban szereplő változó helyett? Ehhez a kérdéshez használja mind az utasítások számát, mind a tényleges futásidejű viselkedést.
A Mandelbrot-halmaz pixelértékeinek kiszámításához szükség van egy olyan függvényre, amely az iterációszámot az R, G és B színcsatornákra konvertálja. Mindhárom csatorna azonos értékre állítása szürke képet eredményez, ezért az egyes színcsatornák függvényének meredekségének egyedinek kell lennie, és amelyik meredekség a legnagyobb, az határozza meg a kép színárnyalatát.
A 3.8.1. szakaszban leírtak szerint a polinomkiértékelések száma meghaladhatja azt az értéket, amely meghaladja egy színcsatorna tartományát. Az esetleges túlcsordulás elkerülése érdekében telítő aritmetikát kell használnia az egyes pixelértékek kiszámításakor. Így, ha a kiszámított érték meghaladja a maximálisan megengedett értéket, akkor a maximális értékre kell beállítani.
Írjon egy C makrót, amely 8 bites, előjel nélküli telítő szorzást végez. A függvény két 8 bites operandust vesz fel, és egy 255-re beállított 8 bites szorzatot állít elő, ha a szorzat meghaladja a 255-öt. A makró nem tartalmazhat elágazási utasításokat, és ütemezni kell az adatfüggőségeket.
Ez a feladat a Mandelbrot-generátor fixpontos típusainak pontosságát 64 bitesre növeli.
a.
Az 1,5zoomos nagyítási sebességet használva, milyen szintre lehet a képkockát nagyítani, mielőtt meghaladná ezt a pontosságot?
b.
Definiáljon C-ben egy makrót két (64,56) fixpontos érték összeadására. A makró a 128 bites összeadást négy 32 bites összeadással tudja végrehajtani, és a hordozójelzőt használhatja az egyes 32 bites csoportokból a következő legjelentősebb 32 bites csoportba történő hordozás megvalósítására.
c.
Definiáljon egy makrót C-ben két (64,56) fixpontos érték szorzására. Építse ezt a makrót a b. rész 64 bites összeadás makrójára.
Amint a 3.6. ábrán látható, a 64 bites szorzás egyszerű módja az, hogy négy 32 bites szorzási/eltolási/akkumulációs művelet sorozatát hajtjuk végre, amelyek mindegyike 64 bites eredményt ad.
3.6. ábra. Egy 4 bites szorzókkal megvalósított 8 bites szorzó.
Az ábrán az 1110 és 1410 értékeket tartalmazó két 4 bites A és B értéket egyenként két 2 bites felső és alsó részre osztjuk, amelyeket A1, A0 és B1 és B0 névvel jelölünk. Feltételezve, hogy a termékek 4 bitesek, a 8 bites szorzatot a következőképpen kell kiszámítani: (A1*B1) ≪ 4 + (A1*B0) ≪ 2 + (A0*B1) ≪ 2 + (A0*B0).
Hogy ezt 64 bites szorzásra alkalmazzuk, a két 64 bites érték mindegyikét két 32 bites regiszterben kell tartani. Minden egyes szorzás 64 bites eredményt generál, így 128 bites végterméket kapunk.
d.
Ezek a makrók felhasználásával valósítson meg egy 64 bites Mandelbrot-halmaz generátort, és mérje meg az így kapott teljesítménykülönbséget.
e.
Vezesse be mindkét makrót inline assembly nyelven, és mérje meg a Mandelbrot-generátor eredményének gyorsulását a d. részhez képest.