Opgaver
Skriv en fastpunktsimplementering af Mandelbrot-generatoren.
a.
Du vil bemærke, at ydelsen er inkonsekvent mellem forskellige pixels og forskellige frames. Hvorfor er dette?
b.
Hvad er den aritmetiske intensitet af det inderste loop-legeme i operationer pr. byte, der tilgås fra hukommelsen? Hvad er den tilsvarende ydelsesgrænse for din ARM-CPU? Hvordan er den sammenlignet med din observerede ydelse?
c.
Måler du følgende ydelsesmålinger for det inderste loop-legeme:
▪
instruktioner pr. iteration
▪
instruktioner pr. operation
▪
CPI
▪
cache miss rate
d.
Brug inline assembly til at implementere den inderste løkkekrop, og mål ydelsesvirkningen i forhold til målepunkterne fra del c. Hvad er hastighedsforøgelsen i forhold til den compilergenererede kode?
Paralleliser Mandelbrot-sætgeneratoren ved hjælp af OpenMP. Anvend parallel-for-direktivet på den yderste (række)løkke.
a.
Måler det gennemsnitlige antal cyklusser, der kræves for hver iteration af den inderste løkke (for at evaluere polynomiet) for én tråd og to tråde for den indledende ramme. Brug disse målinger til at beregne hastighedsforøgelsen, udtrykt i pixels pr. sekund, for to tråde i forhold til én tråd.
b.
Måler du tiden til at beregne alle pixels i den første ramme, når du bruger den dynamiske tidsplan sammenlignet med den statiske tidsplan.
Hvad gør det vanskeligt at anvende SIMD-operation til Mandelbrot-sætgeneratoren? Hvad er den mest effektive metode til at anvende SIMD-operation til Mandelbrot-sætgeneratoren?
Måling af den effektive skrivegennemstrømning for Linux Framebuffer. Svarer det til skrivegennemstrømningen for et hukommelsesarray, der er allokeret fra heap?
Beregn den aritmetiske intensitet af billedtransformationsprogrammet i operationer pr. pixel. Hvad er dets ydelsesgrænse i betragtning af den effektive hukommelsesgennemstrømning for din ARM-CPU? Hvordan er den sammenlignet med din observerede ydeevne?
Brug OpenMP til at tilføje multicore-understøttelse til billedtransformationsprogrammet med fastkomma. Anvend derfor parallel for-pragmaet på den yderste (række)løkke.
Måler dens ydeevne på en ARM-CPU med fire kerner. Hvordan varierer dens ydeevne, når den udføres med en, to, tre og fire tråde?
Brug intrinsics til at tilføje NEON SIMD-understøttelse til fastpunktsversionen af billedtransformationsprogrammet. Brug firevejsoperationer til at beregne følgende beregninger for en gruppe på fire pixels: placering af kildepixel, udtrækning af brøkdel og beregning af vægt. I hvilken grad forbedrer dette ydeevnen?
Vi kan ikke uden videre optimere Mandelbrot-generatorprogrammet ved hjælp af SIMD-instruktioner, da nabopixels kan kræve et forskelligt antal polynomieevalueringer, og hver iteration af polynomiet er afhængig af den foregående evaluering. En alternativ fremgangsmåde er at implementere løkken i inline-assembling, afvikle mindst fire gange og derefter bruge software-pipelining til at forbedre løkkenes CPI. I dette tilfælde bør vi undgå betingede forgreninger inden for den udrullede løkke. Da divergerende c-værdier vil fortsætte med at divergere ved efterfølgende evalueringer, kan vi vente med at kontrollere løkkens afslutningsbetingelse efter hver gruppe af fire iterationer. Hvis vi udfører yderligere polynomieevalueringer, efter at en Pc() potentielt divergerer uden for radius-2 cirklen, skal vi imidlertid tage hensyn til de yderligere krav til rækkevidde for vores fastpunktsformat. Genberegn kravene til fixed-point-området for denne optimering og bestem i hvilken grad dette vil reducere det maksimale zoomniveau.
De vigtigste fordele ved fixed-point er reduktionen af operationens latenstid og muligheden for at undgå typekonverteringer i visse typer af grafiske koder. I kapitel 2 fremhæves et eksempelprogram, hvis ydeevne er følsom over for operationens latenstid, nemlig Horners metode. Hvis vi antager, at vi kan tolerere fixed point-grænserne i vores Horner-metodekode, ville det så forbedre ydeevnen at konvertere den til fixed point? Forklar dit svar.
Afsnit 3.6.5 viste to forskellige implementeringer af en generaliseret fastpunktsadditionsmakro i præprocessoren. Den første blev genereret af gcc under maksimal optimering, den anden blev håndkodet ved hjælp af inline assembler-sprog. Begge implementeringer krævede omtrent det samme antal instruktioner.
a.
Vis de read-after-write dataafhængigheder i begge implementeringer. Hvis det antages, at processoren anvender enkeltinstruktioner i rækkefølge, og hvis latenstiden for alle aritmetiske operationer med hele tal er fire cyklusser, hvor mange sammenligner antallet af datastallcyklusser, der er nødvendige for begge implementeringer.
b.
Genskriv inline-assemblerversionen af makroen for fastpunktsaddition for at planlægge instruktionerne således, at afhængige instruktioner er adskilt så meget som muligt. I hvor høj grad reduceres stalls, hvis man antager den latenstid, der er angivet i del a?
c.
Skriv kode, der demonstrerer, hvordan alle tre implementeringer (compilergenereret, inline assembly og planlagt inline assembly) kan karakteriseres med hensyn til ydeevne.
I dette spørgsmål undersøger vi inline assembly-implementeringen af generaliseret fastpunktsmultiplikator, der er beskrevet i afsnit 3.6.6.
a.
Hvordan klarer den sig, med hensyn til antal instruktioner og køretidspræstation, sammenlignet med den tilsvarende compilergenererede kode for:
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)));
Sørg for at bruge indstillingen “-O3” og “-marm”, når du kompilerer med gcc.
b.
Skemalæg instruktionerne i inline-assemblerversionen af multiplikatormakroen for at minimere datafhængighedsforstyrrelser. Mål dens ydeevne i forhold til den version, der er angivet i afsnit 3.6.6.6.
c.
Hvor meget mere gennemgående opnås der for inline-assemblerimplementationen, hvis den ændres således, at radixpunktspositionerne er faste i stedet for variable som i koden? Til dette spørgsmål skal du bruge både antallet af instruktioner og den faktiske køretidsadfærd.
For at beregne pixelværdierne for et Mandelbrot-sæt kræves der en funktion til at konvertere iterationstallet til R-, G- og B-farvekanalerne. Hvis alle tre kanaler indstilles til den samme værdi, vil der blive genereret et gråt billede, så hældningen af hver farvekanalfunktion skal være unik, og hvilken hældning der er størst, vil bestemme billedets nuance.
Som beskrevet i afsnit 3.8.1 kan antallet af polynomievalueringer overstige den værdi, der overskrider intervallet for en farvekanal. For at undgå et potentielt overløb skal du bruge mættende aritmetik, når du beregner hver pixelværdi. Hvis den beregnede værdi på denne måde overstiger den maksimalt tilladte værdi, skal du indstille den til den maksimale værdi.
Skriv en C-makro, der udfører en 8-bit usigneret mættende multiplikation uden fortegn. Funktionen tager to 8-bit operander og producerer et 8-bit produkt, der er sat til 255, hvis produktet overstiger 255. Makroen må ikke indeholde forgreningsinstruktioner og skal planlægges for dataafhængigheder.
Denne øvelse skal undersøge, hvordan man kan øge præcisionen af fastpunktstyperne for Mandelbrot-generatoren til 64-bit.
a.
Ved anvendelse af en zoomhastighed på 1,5zoom, til hvilket niveau kan rammen zoomes, før denne præcision overskrides?
b.
Designe en makro i C til at addere to (64,56) fastpunktsværdier. Makroen kan udføre 128-bits additionen ved hjælp af fire 32-bits additioner og bruge carry-flaget til at implementere carries fra hver 32-bits gruppe til den næststørste 32-bits gruppe.
c.
Designe en makro i C til multiplikation af to (64,56) fixed-point-værdier. Opbyg denne makro oven på 64-bit add-makroen fra del b.
Som vist i figur 3.6 er en enkel måde at udføre en 64-bit multiplikation på at udføre en serie af fire 32-bit multiplikations-/forskydnings-/akkumuleringsoperationer, der hver især giver et 64-bit resultat.
Figur 3.6. En 8-bit multiplikator implementeret med 4-bit multiplikatorer.
I figuren er to 4-bit værdier A og B, der holder værdierne 1110 og 1410, hver adskilt i to 2-bit øvre og nedre dele, der hedder A1, A0 og B1 og B0. Hvis man antager, at produkterne er 4-bits, beregnes 8-bit produktet som (A1*B1) ≪ 4 + (A1*B0) ≪ 2 + (A0*B1) ≪ 2 + (A0*B0).
For at anvende dette på en 64-bit multiplikation, skal hver af de to 64-bit værdier holdes i to 32-bit registre. Hver multiplikation genererer et 64-bit resultat, hvilket giver mulighed for et 128-bit slutprodukt.
d.
Implementer ved hjælp af disse makroer en 64-bit Mandelbrot-sætgenerator og mål den resulterende ydelsesforskel.
e.
Implementer begge makroer i inline assembler-sprog og mål resultatet af Mandelbrot-generatorens hastighedsforøgelse sammenlignet med den i del d.