Övningar
Skriv en fastpunktsimplementering av Mandelbrotgeneratorn.
a.
Du kommer att märka att prestandan är inkonsekvent mellan olika pixlar och olika bilder. Varför är det så?
b.
Vad är den aritmetiska intensiteten för den innersta slingkroppen, i operationer per byte som nås från minnet? Vad är motsvarande prestandabegränsning för din ARM-processor? Hur förhåller det sig till din observerade prestanda?
c.
Mät följande prestandamått för den innersta loopkroppen:
▪
instruktioner per iteration
▪
instruktioner per operation
▪
CPI
▪
cache miss rate
d.
Använd inline assembly för att implementera den innersta slingkroppen och mät prestandapåverkan med avseende på mätvärdena från del c. Vad är hastighetsökningen jämfört med den kompilatorgenererade koden?
Parallellisera Mandelbrot-uppsättningsgeneratorn med hjälp av OpenMP. Tillämpa parallell-for-direktivet på den yttersta (rad)slingan.
a.
Mät det genomsnittliga antalet cykler som krävs för varje iteration av den innersta slingan (för att utvärdera polynomet) för en tråd och två trådar för den första ramen. Använd dessa mätningar för att beräkna hastighetsökningen, i termer av pixlar per sekund, för två trådar jämfört med en tråd.
b.
Mät tiden för att beräkna alla pixlar i den första bilden när man använder det dynamiska schemat jämfört med det statiska schemat.
Vad gör det svårt att tillämpa SIMD-operationer för generatorn för Mandelbrot-mängden? Vad är den mest effektiva metoden för att tillämpa SIMD-operation för Mandelbrotgeneratorn?
Mät den effektiva skrivgenomströmningen för Linux Framebuffer. Är det likvärdigt med skrivgenomströmningen för en minnesarray som allokeras från heap?
Beräkna den aritmetiska intensiteten för bildomvandlingsprogrammet i operationer per pixel. Vad är dess prestandabegränsning med tanke på den effektiva minnesgenomströmningen för din ARM-processor? Hur förhåller det sig till din observerade prestanda?
Använd OpenMP för att lägga till flerkärnigt stöd till bildomvandlingsprogrammet med fast punkt. Tillämpa parallell for-pragmaet på den yttersta (rad)slingan.
Mät dess prestanda på en ARM-CPU med fyra kärnor. Hur varierar dess prestanda när den utförs med en, två, tre och fyra trådar?
Använd intrinsics för att lägga till NEON SIMD-stöd till fastpunktsversionen av bildomvandlingsprogrammet. Använd fyrvägsoperationer för att beräkna följande beräkningar för en grupp av fyra pixlar: placering av källpixlar, extraktion av fraktioner och beräkning av vikt. I vilken grad förbättrar detta prestandan?
Vi kan inte enkelt optimera Mandelbrotgeneratorprogrammet med hjälp av SIMD-instruktioner, eftersom angränsande pixlar kan kräva olika antal polynomutvärderingar och varje iteration av polynomet är beroende av den föregående utvärderingen. Ett alternativt tillvägagångssätt är att implementera slingan i inline-assemblering, avveckla minst fyra gånger och sedan använda pipelining i programvara för att förbättra slingans CPI. I det här fallet bör vi undvika villkorliga förgreningar i den avrullade slingan. Eftersom divergerande c-värden kommer att fortsätta att divergera vid efterföljande utvärderingar kan vi vänta med att kontrollera villkoret för att avsluta slingan efter varje grupp av fyra iterationer. Att utföra ytterligare polynomutvärderingar efter att en Pc() potentiellt avviker utanför cirkeln med radie 2 innebär dock att vi måste ta hänsyn till de ytterligare intervallkraven för vårt fastpunktsformat. Beräkna om kraven på intervallet för fastpunktsformatet för denna optimering och bestäm i vilken grad detta kommer att minska den maximala zoomnivån.
De principiella fördelarna med fastpunktsformatet är minskningen av operationens latenstid och möjligheten att undvika typkonverteringar i vissa typer av grafiska koder. Kapitel 2 belyser ett exempelprogram vars prestanda är känslig för operationens latenstid, Horners metod. Om vi antar att vi kan tolerera begränsningarna i intervallet för fast punkt i vår kod för Horners metod, skulle en konvertering till fast punkt förbättra prestandan? Förklara ditt svar.
Avsnitt 3.6.5 visade två olika implementeringar av ett generaliserat preprocessormakro för fastpunktsaddition. Den första genererades av gcc under maximal optimering, den andra var handkodad med hjälp av inline-assembleringsspråk. Båda implementeringarna krävde ungefär samma antal instruktioner.
a.
Visa databeroendena för läsning efter skrivning i båda implementeringarna. Om man antar att processorn använder sig av en enda instruktion, i ordning utfärdande, och om man antar att latensen för alla heltalsaritmetiska operationer är fyra cykler, hur många jämför antalet cykler för datastoppning som behövs för båda implementeringarna.
b.
Skriv om inline-assembleringsversionen av fastpunktsadditionsmakron för att schemalägga instruktionerna så att beroende instruktioner är separerade så mycket som möjligt. I vilken grad minskas stalls, om man utgår från den latenstid som anges i del a?
c.
Skriv en kod som visar hur alla tre implementeringarna (kompilatorgenererad, inline-assemblering och schemalagd inline-assemblering) kan karakteriseras med avseende på prestanda.
I denna fråga undersöker vi inline assembly-implementationen av generaliserad fastpunktsmultiplikation som beskrivs i avsnitt 3.6.6.
a.
Hur förhåller det sig, när det gäller antal instruktioner och prestanda vid körning, jämfört med motsvarande kompilatorgenererad kod för:
res = ((((long long long)op1 * (long long)op2) >> (rp1>rp2?rp1:rp2))) +(rp1>rp2 ? ((((long long)op1 * (long long)op2) >> (rp1-1))&1) :
((((long long)op1 * (long long)op2) >> (rp2-1))&1)));
Se till att du använder alternativen ”-O3” och ”-marm” vid kompilering med gcc.
b.
Skynda instruktionerna i inline-assembleringsversionen av multiplikationsmakron för att minimera dataväxlingar. Mät dess prestanda i förhållande till den version som ges i avsnitt 3.6.6.
c.
För inline-assemblerimplementationen, hur mycket mer genomgående uppnås om den ändras så att radixpunktspositionerna är fasta i stället för variabla som i koden? Använd för denna fråga både antalet instruktioner och det faktiska beteendet vid körning.
För att beräkna pixelvärdena för en Mandelbrot-mängd krävs en funktion för att konvertera iterationsantalet till färgkanalerna R, G och B. Att ställa in alla tre kanalerna på samma värde kommer att generera en grå bild, så lutningen för varje färgkanalsfunktion bör vara unik, och vilken lutning som är störst kommer att bestämma bildens nyans.
Som beskrivits i avsnitt 3.8.1 kan antalet polynomutvärderingar överstiga det värde som överskrider intervallet för en färgkanal. För att undvika ett potentiellt överflöde måste du använda mättande aritmetik när du beräknar varje pixelvärde. Om det beräknade värdet överskrider det högsta tillåtna värdet sätts det på så sätt till det högsta värdet.
Skriv ett C-makro som utför en 8-bitars osignerad mättande multiplikation utan förtecken. Funktionen tar två 8-bitars operander och producerar en 8-bitars produkt som sätts till 255 om produkten överstiger 255. Makrot får inte innehålla förgreningsinstruktioner och ska schemaläggas för databeroenden.
Denna övning kommer att undersöka hur man kan öka precisionen för fastpunktstyperna för Mandelbrotgeneratorn till 64-bitar.
a.
Med en zoomfrekvens på 1,5zoom, till vilken nivå kan man zooma in ramen innan precisionen överskrids?
b.
Skriv ett makro i C för att addera två (64,56) fastpunktsvärden. Makroet kan utföra 128-bitars adderingen med hjälp av fyra 32-bitars adderingar och använda carry-flaggan för att implementera överföringar från varje 32-bitarsgrupp till den näst mest signifikanta 32-bitarsgruppen.
c.
Definiera ett makro i C för att multiplicera två (64,56) fixpunktsvärden. Bygg detta makro ovanpå 64-bitars add-makrot från del b.
Som visas i figur 3.6 är ett enkelt sätt att utföra en 64-bitars multiplikation att utföra en serie av fyra 32-bitars multiplikations-/förskjutnings-/ackumuleringsoperationer som var och en ger ett 64-bitars resultat.
Figur 3.6. En 8-bitars multiplikator implementerad med 4-bitars multiplikatorer.
I figuren är två 4-bitarsvärden A och B som innehar värdena 1110 och 1410 vardera uppdelade i två 2-bitars övre och nedre delar, som benämns A1, A0 och B1 och B0. Om man antar att produkterna är 4-bitar beräknas 8-bitarsprodukten som (A1*B1) ≪ 4 + (A1*B0) ≪ 2 + (A0*B1) ≪ 2 + (A0*B0).
För att tillämpa detta på en 64-bitarsmultiplikation måste vart och ett av de två 64-bitsvärdena hållas i två 32-bitsregister. Varje multiplikation genererar ett 64-bitars resultat, vilket möjliggör en 128-bitars slutprodukt.
d.
Med hjälp av dessa makron implementerar du en 64-bitars Mandelbrotgenerator och mäter den resulterande prestandaskillnaden.
e.
Implementera båda makron i inline-assembleringsspråk och mät Mandelbrotgeneratorns resultatförbättring jämfört med den i del d.