Exercises
Schreiben Sie eine Festkomma-Implementierung des Mandelbrot-Generators.
a.
Sie werden feststellen, dass die Leistung zwischen verschiedenen Pixeln und verschiedenen Frames inkonsistent ist. Woran liegt das?
b.
Wie hoch ist die Rechenintensität des innersten Schleifenkörpers in Operationen pro Byte im Speicher? Was ist die entsprechende Leistungsgrenze für Ihre ARM-CPU? Wie sieht es im Vergleich zu der von Ihnen beobachteten Leistung aus?
c.
Messen Sie die folgenden Leistungskennzahlen für den innersten Schleifenkörper:
▪
Instruktionen pro Iteration
▪
Instruktionen pro Operation
▪
CPI
▪
Cache-Miss-Rate
d.
Verwenden Sie Inline-Assembly, um den innersten Schleifenkörper zu implementieren, und messen Sie die Auswirkungen auf die Leistung im Hinblick auf die Metriken aus Teil c. Wie hoch ist die Beschleunigung im Vergleich zum vom Compiler erzeugten Code?
Parallelisieren Sie den Mandelbrotmengen-Generator mit OpenMP. Wenden Sie die Parallel-for-Anweisung auf die äußerste Schleife (Zeile) an.
a.
Messen Sie die durchschnittliche Anzahl der Zyklen, die für jede Iteration der innersten Schleife (zur Auswertung des Polynoms) für einen Thread und zwei Threads für den Anfangsrahmen erforderlich sind. Berechnen Sie anhand dieser Messungen den Geschwindigkeitszuwachs, ausgedrückt in Pixeln pro Sekunde, von zwei Threads gegenüber einem Thread.
b.
Messen Sie die Zeit für die Berechnung aller Pixel im ersten Bild, wenn Sie den dynamischen Zeitplan im Vergleich zum statischen Zeitplan verwenden.
Was erschwert die Anwendung der SIMD-Operation für den Mandelbrotmengengenerator? Welches ist die effizienteste Methode zur Anwendung von SIMD-Operationen für den Mandelbrotmengengenerator?
Messen Sie den effektiven Schreibdurchsatz für den Linux-Framebuffer. Entspricht er dem Schreibdurchsatz für ein aus dem Heap zugewiesenes Speicherarray?
Berechnen Sie die arithmetische Intensität des Bildumwandlungsprogramms in Operationen pro Pixel. Wie hoch ist die Leistungsgrenze angesichts des effektiven Speicherdurchsatzes Ihrer ARM-CPU? Wie sieht es im Vergleich zu Ihrer beobachteten Leistung aus?
Verwenden Sie OpenMP, um dem Festkomma-Bildumwandlungsprogramm Multicore-Unterstützung hinzuzufügen. Wenden Sie dazu das parallele for-Pragma auf die äußerste (Zeilen-)Schleife an.
Messen Sie die Leistung auf einer ARM-CPU mit vier Kernen. Wie skaliert die Leistung bei der Ausführung mit einem, zwei, drei und vier Threads?
Verwenden Sie Intrinsics, um der Festkommaversion des Bildtransformationsprogramms NEON SIMD-Unterstützung hinzuzufügen. Verwenden Sie Vier-Wege-Operationen, um die folgenden Berechnungen für eine Gruppe von vier Pixeln durchzuführen: Quellpixelposition, Bruchteilsextraktion und Gewichtsberechnung. Inwieweit verbessert dies die Leistung?
Wir können das Mandelbrot-Generatorprogramm nicht einfach mit SIMD-Befehlen optimieren, da benachbarte Pixel eine unterschiedliche Anzahl von Polynomauswertungen erfordern können und jede Iteration des Polynoms von der vorherigen Auswertung abhängig ist. Ein alternativer Ansatz besteht darin, die Schleife in Inline-Assembly zu implementieren, mindestens viermal abzurollen und dann Software-Pipelining zu verwenden, um den CPI der Schleife zu verbessern. In diesem Fall sollten wir bedingte Verzweigungen innerhalb der abgerollten Schleife vermeiden. Da divergierende c-Werte bei nachfolgenden Auswertungen weiter divergieren, können wir mit der Überprüfung der Schleifenausgangsbedingung nach jeder Gruppe von vier Iterationen warten. Wenn jedoch zusätzliche Polynomauswertungen durchgeführt werden, nachdem ein Pc() potenziell außerhalb des Radius-2-Kreises divergiert, müssen wir die zusätzlichen Bereichsanforderungen für unser Festkommaformat berücksichtigen. Berechnen Sie die Anforderungen an den Festkommabereich für diese Optimierung neu und bestimmen Sie, inwieweit dadurch die maximale Zoomstufe verringert wird.
Die Hauptvorteile von Festkomma sind die Verringerung der Operationslatenz und die Möglichkeit, Typkonvertierungen in bestimmten Arten von Grafikcodes zu vermeiden. In Kapitel 2 wird ein Beispielprogramm vorgestellt, dessen Leistung von der Operationslatenz abhängt: die Horner-Methode. Angenommen, wir können die Bereichsgrenzen von Festkomma in unserem Code für die Horner-Methode tolerieren, würde die Umwandlung in Festkomma die Leistung verbessern? Erläutern Sie Ihre Antwort.
In Abschnitt 3.6.5 wurden zwei verschiedene Implementierungen eines verallgemeinerten Festkomma-Additions-Präprozessormakros gezeigt. Die erste wurde von gcc unter maximaler Optimierung erzeugt, die zweite wurde von Hand mit Inline-Assembler programmiert. Beide Implementierungen benötigten ungefähr die gleiche Anzahl von Anweisungen.
a.
Zeigen Sie die Lese-nach-Schreib-Datenabhängigkeiten in beiden Implementierungen. Unter der Annahme, dass der Prozessor eine einzelne Anweisung in der Reihenfolge der Ausgabe verwendet und die Latenz aller ganzzahligen arithmetischen Operationen vier Zyklen beträgt, vergleichen Sie die Anzahl der Datenstillstandszyklen, die für beide Implementierungen benötigt werden.
b.
Schreiben Sie die Inline-Assembler-Version des Festkomma-Additionsmakros neu, um die Anweisungen so zu planen, dass abhängige Anweisungen so weit wie möglich getrennt sind. Inwieweit werden die Stalls reduziert, wenn man von der in Teil a angegebenen Latenz ausgeht?
c.
Schreiben Sie einen Code, der zeigt, wie alle drei Implementierungen (vom Compiler generiert, Inline-Assembly und geplante Inline-Assembly) hinsichtlich ihrer Leistung charakterisiert werden können.
In dieser Frage untersuchen wir die in Abschnitt 3.6.6 beschriebene Inline-Assembly-Implementierung der verallgemeinerten Festkommamultiplikation.
a.
Wie verhält es sich im Hinblick auf die Anzahl der Anweisungen und die Laufzeitleistung im Vergleich zu dem äquivalenten, vom Compiler erzeugten Code für:
res = (((long long)op1 * (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));
Vergewissern Sie sich, dass Sie die Schalter „-O3“ und „-marm“ beim Kompilieren mit gcc verwenden.
b.
Planen Sie die Anweisungen der Inline-Assembly-Version des Multiplikationsmakros so ein, dass die Datenabhängigkeit so gering wie möglich gehalten wird. Messen Sie die Leistung im Vergleich zu der Version in Abschnitt 3.6.6.
c.
Wie viel mehr Leistung wird bei der Inline-Assembler-Implementierung erreicht, wenn die Positionen der Radixpunkte fest statt wie im Code variabel sind? Verwenden Sie für diese Frage sowohl die Anzahl der Anweisungen als auch das tatsächliche Laufzeitverhalten.
Die Berechnung der Pixelwerte für eine Mandelbrot-Menge erfordert eine Funktion zur Umwandlung der Iterationszahl in die Farbkanäle R, G und B. Wenn alle drei Kanäle auf denselben Wert gesetzt werden, wird ein Graubild erzeugt, daher sollte die Steigung jeder Farbkanalfunktion eindeutig sein, und die größte Steigung bestimmt den Farbton des Bildes.
Wie in Abschnitt 3.8.1 beschrieben, kann die Anzahl der Polynomauswertungen den Wert überschreiten, der den Bereich eines Farbkanals überschreitet. Um einen möglichen Überlauf zu vermeiden, müssen Sie bei der Berechnung der einzelnen Pixelwerte eine sättigende Arithmetik verwenden. Wenn der berechnete Wert den zulässigen Höchstwert überschreitet, wird er auf den Höchstwert gesetzt.
Schreiben Sie ein C-Makro, das eine vorzeichenlose 8-Bit-Sättigungsmultiplikation durchführt. Die Funktion nimmt zwei 8-Bit-Operanden und erzeugt ein 8-Bit-Produkt, das auf 255 gesetzt wird, wenn das Produkt 255 überschreitet. Das Makro darf keine Verzweigungsanweisungen enthalten und muss für Datenabhängigkeiten geplant werden.
In dieser Übung soll die Erhöhung der Genauigkeit der Festkommatypen für den Mandelbrot-Generator auf 64-Bit untersucht werden.
a.
Bei einer Zoomrate von 1,5zoom, auf welche Stufe kann das Bild gezoomt werden, bevor diese Genauigkeit überschritten wird?
b.
Definieren Sie ein Makro in C für die Addition zweier (64,56) Festkommawerte. Das Makro kann die 128-Bit-Addition mit vier 32-Bit-Additionen durchführen und das Carry-Flag verwenden, um Überträge von jeder 32-Bit-Gruppe zur nächsthöheren 32-Bit-Gruppe zu implementieren.
c.
Definieren Sie ein Makro in C für die Multiplikation von zwei (64,56) Festkommawerten. Bauen Sie dieses Makro auf das 64-Bit-Additionsmakro aus Teil b auf.
Wie in Abbildung 3.6 gezeigt, besteht eine einfache Möglichkeit, eine 64-Bit-Multiplikation durchzuführen, darin, eine Reihe von vier 32-Bit-Multiplikations-/Shift-/Akkumulationsoperationen durchzuführen, die jeweils ein 64-Bit-Ergebnis erzeugen.
Abbildung 3.6. Ein 8-Bit-Multiplikator, der mit 4-Bit-Multiplikatoren implementiert ist.
In der Abbildung werden zwei 4-Bit-Werte A und B, die die Werte 1110 und 1410 enthalten, jeweils in zwei obere und untere 2-Bit-Teile aufgeteilt, die A1, A0 und B1 und B0 genannt werden. Unter der Annahme, dass die Produkte 4-Bit sind, wird das 8-Bit-Produkt berechnet als (A1*B1) ≪ 4 + (A1*B0) ≪ 2 + (A0*B1) ≪ 2 + (A0*B0).
Um dies auf eine 64-Bit-Multiplikation anzuwenden, muss jeder der beiden 64-Bit-Werte in zwei 32-Bit-Registern gehalten werden. Jede Multiplikation erzeugt ein 64-Bit-Ergebnis, so dass ein 128-Bit-Endprodukt entsteht.
d.
Implementieren Sie unter Verwendung dieser Makros einen 64-Bit-Mandelbrotmengen-Generator und messen Sie den daraus resultierenden Leistungsunterschied.
e.
Implementieren Sie beide Makros in Inline-Assembler und messen Sie die Ergebnisbeschleunigung des Mandelbrot-Generators im Vergleich zu der von Teil d.