Oefeningen
Schrijf een fixed-point implementatie van de Mandelbrot generator.
a.
Je zult merken dat de performance inconsistent is tussen verschillende pixels en verschillende frames. Hoe komt dat?
b.
Wat is de rekenkundige intensiteit van de binnenste lus, in bewerkingen per byte die uit het geheugen wordt gehaald? Wat is de bijbehorende prestatiegrens voor uw ARM CPU? Hoe verhoudt die zich tot uw waargenomen prestaties?
c.
Met de volgende prestatiecijfers voor de binnenste lus:
▪
instructies per iteratie
▪
instructies per operatie
▪
CPI
▪
cache miss rate
d.
Gebruik inline assembly om de binnenste lus te implementeren en meet het prestatie-effect ten opzichte van de metrieken uit deel c. Wat is de snelheid vergeleken met de door de compiler gegenereerde code?
Parallelizeer de Mandelbrot set generator met OpenMP. Pas de parallel-for-richtlijn toe op de buitenste lus (rij).
a.
Met het gemiddelde aantal cycli dat nodig is voor elke iteratie van de binnenste lus (om het polynoom te evalueren) voor één thread en twee threads voor het eerste frame. Gebruik deze metingen om de snelheidswinst, in pixels per seconde, van twee threads ten opzichte van één thread te berekenen.
b.
Meten hoe lang het duurt om alle pixels in het eerste frame te berekenen bij gebruik van het dynamische schema in vergelijking met het statische schema.
Waardoor is het moeilijk om SIMD-werking toe te passen voor de Mandelbrot-set-generator? Wat is de meest efficiënte methode om SIMD toe te passen op de Mandelbrot-setgenerator?
Met de effectieve schrijfdoorvoer voor de Linux-framebuffer. Is dit equivalent met de schrijfdoorvoer voor een geheugenarray die wordt toegewezen vanuit de heap?
Bereken de rekenkundige intensiteit van het beeldtransformatieprogramma in bewerkingen per pixel. Wat is de prestatiegrens ervan, gegeven de effectieve geheugendoorvoer van uw ARM CPU? Hoe verhoudt deze zich tot de waargenomen prestaties?
Gebruik OpenMP om multicore-ondersteuning toe te voegen aan het fixed-point beeldtransformatieprogramma. Pas hiertoe de parallel for pragma toe op de buitenste (rij)lus.
Met de prestaties op een ARM CPU met vier kernen. Hoe zijn de prestaties wanneer het programma wordt uitgevoerd met één, twee, drie en vier threads?
Gebruik intrinsics om NEON SIMD-ondersteuning toe te voegen aan de fixed-point versie van het beeldtransformatieprogramma. Gebruik vierwegbewerkingen om de volgende berekeningen uit te voeren voor een groep van vier pixels: locatie van bronpixels, extractie van fracties en berekening van het gewicht. In welke mate verbetert dit de prestaties?
We kunnen het Mandelbrot-generatorprogramma niet eenvoudig optimaliseren met SIMD-instructies, aangezien aangrenzende pixels een verschillend aantal polynomevaluaties kunnen vereisen en elke iteratie van de polynoom afhankelijk is van de vorige evaluatie. Een alternatieve aanpak is om de lus in inline assemblage te implementeren, ten minste vier keer af te rollen, en dan software pipelining te gebruiken om de lus CPI te verbeteren. In dit geval moeten we conditionele vertakkingen binnen de ontrolde lus vermijden. Omdat divergerende c-waarden zullen blijven divergeren bij volgende evaluaties, kunnen we wachten met het controleren van de loop exit conditie na elke groep van vier iteraties. Echter, het uitvoeren van extra polynomiale evaluaties nadat een Pc() mogelijk buiten de radius-2 cirkel divergeert, vereist dat we rekening houden met de extra bereikvereisten voor ons fixed-point formaat. Bereken opnieuw het vereiste fixed-point bereik voor deze optimalisatie en bepaal in welke mate dit het maximale zoomniveau zal verlagen.
De belangrijkste voordelen van fixed-point zijn de vermindering van de operatie-latentie en de mogelijkheid om typeconversies in bepaalde typen grafische codes te vermijden. In hoofdstuk 2 wordt een voorbeeldprogramma uitgelicht waarvan de prestaties gevoelig zijn voor operatievertraging, de methode van Horner. Ervan uitgaande dat we de beperkingen van fixed-point in onze Horner’s method code kunnen tolereren, zou het omzetten naar fixed-point de prestaties verbeteren? Leg je antwoord uit.
Paragraaf 3.6.5 liet twee verschillende implementaties zien van een gegeneraliseerde fixed-point optel preprocessor macro. De eerste werd gegenereerd door gcc onder maximale optimalisatie, de tweede werd met de hand gecodeerd met inline assembleertaal. Beide implementaties hadden ongeveer evenveel instructies nodig.
a.
Toon de read-after-write data dependencies in beide implementaties. Ervan uitgaande dat de processor gebruik maakt van enkelvoudige instructies, in volgorde uitgifte, en ervan uitgaande dat de latentie van alle integer rekenkundige bewerkingen vier cycli is, hoeveel vergelijk het aantal data stall cycli dat nodig is voor beide implementaties.
b.
Herschrijf de inline assembly versie van de fixed-point optelmacro om de instructies zo te plannen dat afhankelijke instructies zo veel mogelijk gescheiden zijn. In welke mate worden de stalls verminderd, uitgaande van de latency gegeven in deel a?
c.
Schrijf code die laat zien hoe alle drie de implementaties (compiler generated, inline assembly, en scheduled inline assembly) gekarakteriseerd kunnen worden voor prestaties.
In deze vraag onderzoeken we de inline assembly implementatie van gegeneraliseerde fixed-point multiply beschreven in Paragraaf 3.6.6.
a.
Hoe verhoudt deze zich, in termen van aantal instructies en runtime-prestaties, ten opzichte van de equivalente, door de compiler gegenereerde code voor:
res = (((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));
Zorg ervoor dat u de “-O3”- en “-marm”-switches gebruikt wanneer u compileert met gcc.
b.
Scheduleer de instructies van de inline assembly versie van de vermenigvuldig macro om data dependency stalls te minimaliseren. Meet de prestatie ten opzichte van de versie gegeven in Paragraaf 3.6.6.
c.
Voor de inline assembly implementatie, hoeveel meer doorloop wordt bereikt indien veranderd zodanig dat de radix point posities vast zijn in plaats van variabel zoals in de code? Gebruik voor deze vraag zowel het aantal instructies als het feitelijke runtime-gedrag.
Voor het berekenen van de pixelwaarden voor een Mandelbrotverzameling is een functie nodig voor het omzetten van het aantal iteraties naar de R-, G- en B-kleurkanalen. Als alle drie de kanalen op dezelfde waarde worden ingesteld, wordt een grijs beeld gegenereerd, dus de helling van elke kleurkanaalfunctie moet uniek zijn, en welke helling het grootst is, zal de tint van het beeld bepalen.
Zoals beschreven in Paragraaf 3.8.1, kan het aantal polynomiale evaluaties de waarde overschrijden die het bereik van een kleurkanaal te boven gaat. Om een mogelijke overflow te voorkomen, moet u verzadigende rekenkunde gebruiken bij de berekening van elke pixelwaarde. Op deze manier, als de berekende waarde groter is dan de maximaal toegestane waarde, wordt deze op de maximale waarde gezet.
Schrijf een C macro die een 8-bit unsigned saturating multiply uitvoert. De functie neemt twee 8-bit operands en produceert een 8-bit product dat op 255 wordt gezet als het product groter is dan 255. De macro mag geen vertakkingsinstructies bevatten en moet worden gepland voor gegevensafhankelijkheden.
In deze oefening wordt onderzocht hoe de precisie van de fixed-point types voor de Mandelbrot-generator kan worden verhoogd tot 64-bit.
a.
Gebruik makend van een zoom rate van 1,5 zoom, tot welk niveau kan het frame worden ingezoomd voordat deze precisie wordt overschreden?
b.
Definieer een macro in C voor het optellen van twee (64,56) fixed-point waarden. De macro kan de 128-bit add uitvoeren met vier 32-bit adds en de carry flag gebruiken om carries van elke 32-bit groep naar de volgende meest significante 32-bit groep te implementeren.
c.
Define a macro in C for multiplying two (64,56) fixed-point values. Bouw deze macro bovenop de 64-bit add macro uit deel b.
Zoals in figuur 3.6 is te zien, is een eenvoudige manier om een 64-bit vermenigvuldiging uit te voeren een serie van vier 32-bit vermenigvuldigings/shift/accumulatie-bewerkingen die elk een 64-bit resultaat opleveren.
Figuur 3.6. Een 8-bits vermenigvuldiger geïmplementeerd met 4-bits vermenigvuldigers.
In de figuur worden twee 4-bits waarden A en B die de waarden 1110 en 1410 bevatten, elk gescheiden in twee 2-bits boven- en ondergedeelten, genaamd A1, A0 en B1 en B0. Ervan uitgaande dat de producten 4-bits zijn, wordt het 8-bit product berekend als (A1*B1) ≪ 4 + (A1*B0) ≪ 2 + (A0*B1) ≪ 2 + (A0*B0).
Om dit toe te passen op een 64-bit vermenigvuldiging, moet elk van de twee 64-bit waarden in twee 32-bit registers worden gehouden. Elke vermenigvuldiging levert een 64-bits resultaat op, waardoor een 128-bits eindproduct ontstaat.
d.
Op basis van deze macro’s implementeert u een 64-bits Mandelbrot-generator en meet u het verschil in prestaties.
e.
Uitvoeren van beide macro’s in inline assembleertaal en meten van de snelheid van het resultaat van de Mandelbrot-generator in vergelijking met dat van deel d.