GPGPU Computing - ein Überblick für Anfänger und Fortgeschrittene

Gipsel

Admiral Special
Mitglied seit
10.10.2002
Beiträge
1.951
Renomée
150
Standort
Hamburg
  • Spinhenge ESL
  • Docking@Home

Einleitung​


<center><img src="http://www.planet3dnow.de/photoplog/file.php?n=6095&w=o" border="1" alt="GPGPU Computing"></center>

Der Begriff GPGPU (General Purpose GPU) taucht seit einiger Zeit immer häufiger auf, sobald es um Grafikkarten geht. Nun ist Planet 3DNow! zugegebenermaßen nicht unbedingt berühmt für seine ausführlichen Tests von Grafikkarten und dieser Artikel wird auch nicht versuchen das zu ändern. Allerdings verdient es schon Beachtung, wenn die Grafikschmieden den Anspruch erheben, dass ihre GPUs nicht mehr nur immer schneller immer aufwändigere Grafik rendern können. Vielmehr sollen sie auch für allgemeine Aufgaben (engl.: general purpose) eingesetzt werden und die herkömmlichen CPUs dort um Faktor 10 oder mehr überflügeln.

Der Grundstein für diese Entwicklung wurde mit der Erweiterung des klassischen Ablaufs des Grafik-Renderings gelegt. Statt einer Abfolge von Transformation der 3D-Koordinaten der Objekte in Bildschirmkoordinaten und Beleuchtungsberechnung, Rasterisation und Texturierung mittels fester, in Hardware gegossener Routinen können jetzt für jeden Vertex (Eckpunkt eines Dreiecks) und für jeden Pixel vom Spieleprogrammierer definierte kleine Programme ausgeführt werden, die diese Aufgabe übernehmen und die Erzeugung aufwändiger Effekte ermöglichen. Dies sind die sogenannten Vertex- bzw. Pixelshader oder einfach Shader.

Mit jeder neuen GPU-Generation wurden diese Möglichkeiten erweitert und Beschränkungen aufgehoben. Schon früh wurde deshalb von einigen Enthusiasten versucht, die Grafik-Hardware auch für andere Zwecke einzusetzen. Nun allerdings stellen beide großen Hersteller Schnittstellen bereit, die speziell für GPGPU gedacht sind. Außerdem haben sie in den letzten beiden Jahren Features nur für die Verbesserung des GPGPU-Computing in der Hardware integriert, die für das Grafikrendering nicht eingesetzt werden. Dies zeigt, dass die Hersteller das Thema durchaus für wichtig erachten.

Dieser Artikel will einen Einblick in dieses Thema bieten. Er soll dem bisher vielleicht CPU-zentrierten Planet 3DNow!-Leser die Hardwareunterschiede zwischen CPUs und GPUs etwas näher bringen und auch ein paar grundlegende Prinzipien erläutern, die sich daraus für die Programmierung der GPUs ergeben. Schließlich wird an ein paar einfachen Beispielen gezeigt, dass die Programmierung von GPUs gar nicht so schwierig sein muss.

[BREAK=GPU vs. CPU, ein Vergleich]

GPUs sind natürlich ursprünglich für die spezielle Aufgabe des Grafikrenderings entwickelt worden. Daher sind sie nach vollkommen anderen Prinzipien als eine CPU konstruiert. Eine "klassische" CPU versucht möglichst schnell ein einzelnes Programm auszuführen. Dafür wird oft sehr viel Aufwand betrieben. Zum Beispiel versuchen moderne superskalare Out-of-Order CPUs möglichst viele voneinander unabhängige Instruktionen im Programm zu finden und dann parallel auszuführen (Ausnutzung des sogenannten ILP, Instruction Level Parallelism). Die für weitere Performancesteigerungen auf diesem Wege zusätzlich erforderliche Kontrolllogik ist inzwischen allerdings sehr aufwändig verglichen mit dem möglichen Gewinn.

Deshalb wurden auch andere Wege beschritten, um die Performance für den Anwender zu steigern. Inzwischen sind diverse SIMD-Erweiterungen (Single Instruction Multiple Data) zur Ausnutzung von DLP (Data Level Parallelism, die gleichen Operationen werden gleichzeitig mit einer ganzen Anzahl an Daten ausgeführt) sowie Multithread fähige bzw. Multicore-CPUs zur Ausnutzung des TLP (Thread Level Parallelism, mehrere Programme/Prozesse/Threads laufen gleichzeitig) im Mainstream angekommen. Wenn man von Nischenprodukten wie Suns Niagara absieht, ist trotzdem immer noch die Performance eines einzelnen Threads ausschlaggebend für das Design. Dies drückt sich unter anderem auch in den verbauten Caches aus. Damit versucht man einfach zu verhindern, dass die Ausführung des Programms durch einen langsamen Speicherzugriff ausgebremst wird.

GPUs (und Suns Niagara) dagegen starten von der entgegen gesetzten Zielstellung. Wie lange z.B. die Berechnung eines einzelnen Pixels*) dauert, ist ziemlich egal. Wichtig ist nur, wie lange man für sehr viele benötigt (z.B. für ein ganzes Frame), die allerdings zumeist gleichzeitig berechnet werden können. Es geht also um den Gesamtdurchsatz. Hier ist die Ausnutzung von DLP bzw. auch TLP ausschlaggebend. Auf die aufwändige Logik zur Extraktion des ILP wird komplett verzichtet. GPUs sind also im Prinzip recht einfache In-Order Prozessoren ohne jegliche spekulative Ausführung, Sprungvorhersage (Branch Prediction) oder ähnliches. Das ermöglicht es im Vergleich zu CPUs viel mehr "produktive" Ausführungseinheiten unterzubringen. Es wird einfach davon ausgegangen, dass schon immer irgendwo ausführbare Arbeit vorhanden sein wird, für die alle Daten vorliegen und die nicht mehr auf Ergebnisse von vorhergehenden Instruktionen wartet. Durch diese Philosophie kann man auch auf die großen Caches der CPUs verzichten. Wird ein Wert aus dem Speicher benötigt, so werden nicht die Ausführungseinheiten blockiert, bis der Wert gelesen wurde, sondern einfach mit einem anderen Pixel weiter gemacht. Auf einer GPU werden also immer möglichst viele Pixel gleichzeitig berechnet. Das sind schon bei niedrigen Auflösungen immer deutlich mehr, als es Ausführungseinheiten gibt.

Diese Unterschiede zwischen CPU und GPU spiegeln sich natürlich deutlich in den Hardware-Eckdaten wider. Die Angaben dazu sind meist sehr stark vom Marketing geprägt. So ist die Bezeichnung "shader core" oder "streaming core" nicht mit einem Kern einer CPU zu vergleichen (mehr dazu auch im folgenden Abschnitt). Nachfolgend werde ich also diese Marketing-Angaben größtenteils ignorieren. Hoffentlich wird jetzt keiner von den Zahlen erschlagen, aber für die Interessierten gibt es hier erstmal eine Gegenüberstellung der so verschiedenen Konzepte.
<table width=90% border=1 cellpadding=1>
<tr><th width=10%></th><th width=26%>RV770 / RV790</th><th width=26%>45nm K10</th><th width=26%>GT200b</th></tr><tr><td>Die Größe</td><td>256 / 282 mm²</td><td>258 mm²</td><td> ~490 mm²</td></tr><tr><td>Transistoren</td><td>956 / 959 Millionen</td><td>758 Millionen</td><td>1,4 Milliarden</td></tr><tr><td>Taktfrequenz</td><td>bis 850 MHz</td><td>bis 3,2 GHz</td><td>bis 648 / 1476 MHz</td></tr><tr><td>Kernanzahl</td><td>10 (sogenannte SIMDs)</td><td>4</td><td>30 (10 Cluster zu je 3)</td></tr><tr><td>Speichercontroller</td><td>4 x 64 Bit GDDR3/4/5
(~125 GB/s mit GDDR5 @ 975 MHz)
</td><td>2 x 64Bit DDR2/3
(~21 GB/s mit DDR3-1333)
</td><td>8 x 64 Bit GDDR3
(~159 GB/s mit GDDR3 @ 1242 MHz)</td></tr><tr><td>L1-Cache</td><td>10 x 16kB = 160kB Daten</td><td>4 x 128kB (pro Kern 64kB Daten und 64KB Instruktionen)</td><td>10 x 16kB (24kB?) = 160kB (240kB?) Daten</td></tr><tr><td>L2-Cache</td><td>4 x 64kB shared
(pro Mem-Controller 64kB)</td><td>4 x 512kB dedicated</td><td>8 x 32kB shared
(pro Mem-Controller 32kB)</td></tr><tr><td>L3-Cache</td><td>-</td><td>6MB shared</td><td>-</td></tr><tr><td>Integereinheiten (Kerne addiert)</td><td>10 x 5 x 16 = 800 ALUs (32 Bit)
10 x 1 x 16 = 160 Multiplier (32/32 Bit)
</td><td>superskalar (die normalen Kerne):
4 x 3 = 12 ALUs/AGUs (64 Bit)
4 x 1 = 4 Multiplier (64/128 Bit)
SIMD (SSEx-Einheiten):
4 x 2 x 4 = 32 ALUs (32Bit)
4 x 1 x 2 = 8 Multiplier (32/64 Bit)
</td><td>30 x 1 x 8 = 240 ALUs (32Bit)
30 x 2 x 1 = 60 Multiplier (32/32Bit)</td></tr><tr><td>Fließkommapipelines</td><td>gemeinsam mit Integereinheiten</td><td>getrennt bei skalarem Code, gemeinsame Resourcen bei SIMD</td><td>gemeinsam mit Integereinheiten</td></tr><tr><td>Extended precision (80bit)</td><td>nicht möglich</td><td>4 x 1 = 4 ADD und
4 x 1 = 4 MUL
Peak: 25,6 GFlops bei 3,2 GHz</td><td>nicht möglich</td></tr><tr><td>Double precision (64bit)</td><td>10 x 1 x 16 = 160 MULADD oder
10 x 2 x 16 = 320 ADD oder
10 x 1 x 16 = 160 MUL
Peak: 272 GFlops bei 850MHz
</td><td>4 x 1 x 2 = 8 ADD und
4 x 1 x 2 = 8 MUL
(entspricht 8 MULADDs)
Peak: 51,2 GFlops bei 3,2 GHz
</td><td>30 x 1 = 30 FMA oder
30 x 1 = 30 ADD oder
30 x 1 = 30 MUL
Peak: 89 GFlops bei 1476 MHz</td></tr><tr><td>Single precision (32bit)</td><td>10 x 5 x 16 = 800 MULADD oder
800 ADD oder 800 MUL
Peak: 1360 GFlops bei 850MHz
</td><td>4 x 1 x 4 = 16 ADD und
4 x 1 x 4 = 16 MUL
(entspricht 16 MULADD)
Peak: 102,4 GFlops bei 3,2 GHz
</td><td>30 x 1 x 8 = 240 MULADD oder
240 ADD oder 240 MUL
und jeweils zusätzlich
30 x 2 x 4 = 240 MUL
Peak: 708/1063 GFlops bei 1476 MHz</td></tr></table>
Tabelle 1: Gegenüberstellung der technischen Daten von GPUs und einer CPU. Die Notation bei der Anzahl der Ausführungseinheiten ist immer Kerne x Anzahl der Einheiten pro Kern x SIMD-Breite einer Einheit. Die Werte in Klammern hinter der Anzahl der Integermultiplier gibt die Bitbreite der Eingangswerte und des Ergebnisses an. Ein 32/64 Multiplier gibt das 64 Bit breite Resultat der Multiplikation zweier 32 Bit-Werte zurück. Bei einem 32/32 Multiplier sind dafür zwei Schritte nötig (entweder die unteren oder die oberen 32 Bit werden zurückgegeben).

Dazu ist anzumerken, dass die L1/L2 Caches der GPUs reine Lese-Caches sind. Schreiboperationen laufen nicht über die Caches, sondern werden über einen Write-Combining Puffer als Streaming Stores ausgeführt. Die Kohärenz der Caches wird anders als bei CPUs nicht durch die Hardware garantiert.

*: Im Folgenden wird zur Vereinfachung häufig davon ausgegangen, dass ein Pixelshader ausgeführt wird.

[BREAK=GPU vs. CPU II, Die-Shots und Hardwareunterschiede]

Viele P3D-Leser haben sicherlich eine Idee von der Funktionsweise und dem Aufbau einer CPU. Deshalb soll der Unterschied zu einer GPU auch kurz mit entsprechenden Die-Shots und einem vereinfachten Blockdiagramm des RV770 / RV790 verdeutlicht werden.

<a href="http://www.planet3dnow.de/photoplog/index.php?n=6089"><img src="http://www.planet3dnow.de/photoplog/file.php?n=6089" border="1" alt="GPGPU Computing"></a>
Abb. 1: Maßstabsgetreue Darstellung der Phenom II (oben) und RV770 (unten) Dies, rechts oben ist ein K10-Kern vergrößert abgebildet. Man beachte die Größe der Caches beim Phenom II (insgesamt 8,5 MB) und die im Verhältnis kleinen Ausführungseinheiten. Im mit "ALUs" bezeichneten Kasten befinden sich die 3 Integer-ALUs und 3 AGUs. Im RV770-Bild nehmen die Ausführungseinheiten (weiß umrandet) und auch die Register (türkis umrandet) einen deutlich größeren Platz ein.

<a href="http://www.planet3dnow.de/photoplog/index.php?n=6092"><img src="http://www.planet3dnow.de/photoplog/file.php?n=6092" border="1" alt="GPGPU Computing"></a>
Abb. 2: Vereinfachtes Blockdiagramm eines RV770 / RV790. Die SIMD-Arrays werden vom "Ultra-Threaded Dispatch Processor" mit Instruktionen versorgt. Dabei besitzt jede Ausführungseinheit des SIMD-Arrays ein eigenes Registerfile. Zwischen den einzelnen Einheiten eines Arrays können Daten mit Hilfe des "Local Data Share" ausgetauscht werden. Über die Textureinheiten werden Daten gelesen, das Schreiben erfolgt über die ROPs (Render Backends) an den Caches vorbei.

Man erkennt, wie der Verzicht auf große Caches, aufwändiger Out-of-Order Logik sowie Einschränkungen bei der Funktionalität (nur 32 Bit Integer statt 64 Bit, einfachere Multiplier, reduziertem Funktionsumfang der Einheiten usw.) es ermöglicht, die GPU mit Ausführungseinheiten regelrecht vollzustopfen. Sie nehmen im Verhältnis eine viel größere Fläche ein. Dazu kommt, dass es beim Entwurf in gewissem Umfang möglich ist, die Packungsdichte der Schaltungen gegen die Taktfähigkeit abzuwägen. Bei CPUs favorisiert man eher die Taktfähigkeit, da anders als bei GPUs die Performance nicht einfach über eine größere Anzahl von Einheiten wieder hereingeholt werden kann.

Was vielleicht auffällt sind die regelmäßigen Strukturen bei den Shadercores (türkis umrandet). Dies ist kein Cache, wie man vielleicht mit Blick auf eine CPU vermuten könnte, sondern das sind die Register! Wie schon erwähnt wird auf einer GPU versucht, möglichst viele Pixel parallel zu berechnen. Die Daten und Zwischenergebnisse müssen natürlich alle irgendwo stehen. Es macht keinen Sinn, sie irgendwie in den Speicher auszulagern (wie das bei CPUs bei einem Threadwechsel passiert). Deswegen bieten GPUs extrem viel Platz in den Registern und können so sehr viele Pixel bereithalten, die bei Auftreten einer Verzögerung bei der Berechnung eines anderen Pixels (weil z.B. auf einen Speicherzugriff gewartet wird) direkt einspringen können. Im Falle des RV770/RV790 stehen insgesamt etwa 2,5 MB Register zur Verfügung (10 x 16 x 4 x 256 x 4 x 32 Bit), beim GT200 sind es immerhin auch 1,875 MB (30 x 8 x 4 x 512 x 1 x 32 Bit)*). Die Registerfiles einer CPU sind dagegen beinahe lächerlich klein, allerdings stehen die Register auch komplett einem Thread zur Verfügung und müssen nicht mit sehr vielen anderen geteilt werden (bei Intels Hyperthreading höchstens mit einem anderen).

Ein weiterer Unterschied zur CPU ist die Unterstützung lediglich elementarer Operationen für Rechnungen in doppelter Genauigkeit. Es steht nur der Grundumfang an Funktionen zur Verfügung, der unbedingt erforderlich ist. Kompliziertere Operationen wie Division, Wurzel oder gar transzendente Funktionen müssen sowohl bei ATI als auch NVIDIA "in Software" erledigt werden. Hierbei kommt dem GT200 zu Gute, dass er anders als ATI-Hardware (oder auch der GT200 selber bei single precision) Fused-Multiply-Add (FMA) beherrscht. Bei der Ausführung einer Multiplikation und der anschließenden Addition (x = a * b + c) wird bei x86-CPUs (egal ob FPU oder SSEx), auf ATI-Hardware und bei NVIDIA in einfacher Genauigkeit insgesamt zweimal gerundet (nach der Multiplikation und nach der Addition, auch wenn bei GPUs beide Operationen kombiniert mit einem einzigen Befehl abgesetzt werden). Bei Ausführung eines FMA-Befehls wird nur ein einziges Mal gerundet (ganz am Ende), das Ergebnis ist potentiell etwas genauer. Der mögliche Unterschied im Ergebnis betrifft nur das allerletzte (niedrigstwertige) Bit. Bei der Implementation einer sehr genauen mathematischen Bibliothek für GPUs ist der FMA-Befehl aber sehr nützlich. Weiterhin unterstützt NVIDIA auch mehr Rundungsmodi (für double precision alle in der IEEE 754 Norm aufgeführten) und beherrscht noch ein paar andere Feinheiten. Insgesamt hat sich NVIDIA bemüht, eine komplette normgerechte Unterstützung von doppelter Genauigkeit einzubauen und hat dafür wahrscheinlich sogar Performance geopfert. ATI war dagegen mit dem RV670 (HD3800er Serie) Vorreiter in Sachen doppelter Genauigkeit und hat beim RV770 nur an der Geschwindigkeit gearbeitet. Trotzdem ist der von NVIDIA eingeschlagene Weg die Richtung, in die wahrscheinlich auch ATI mit der späteren GPU-Generationen gehen wird.

*: Kerne x Einheiten pro Kern x Threads pro Einheit x verfügbare Register x Anzahl Register pro Eintrag x Breite

[BREAK=GPU-Hardware aus Sicht des Programmieres: Quads, Wavefronts und Warps]

Im vorherigen Abschnitt ist hoffentlich deutlich geworden, dass GPUs einen vollkommen anderen internen Aufbau besitzen als CPUs. Demzufolge unterscheidet sich natürlich auch die dem Programmierer präsentierte Schnittstelle und damit auch die Herangehensweise bei der Programmierung. Bei herkömmlichen CPUs (z.B. x86) ist man auf den Algorithmus fixiert und rechnet normalerweise jeweils nur mit einem einzigen Datenelement. Gute Compiler können dabei eventuell erkennen, ob bestimmte Teile des Algorithmus mittels SSEx vektorisiert werden können. Dies ist häufig bei Schleifen der Fall, in dem z.B. bei jedem Durchlauf praktisch die gleiche Berechnung nur mit verschiedenen Daten durchgeführt wird. Ist der Compiler nicht in der Lage, solche Situationen korrekt zu erkennen, hilft nur die explizite Nutzung der SSEx-Instruktionen, in dem man die sozusagen per Hand einbaut.

Die GPU-Programmierung verfolgt dagegen passend zur Hardware ein anderes Konzept. Im einfachsten Fall implementiert man den Algorithmus genau wie auf der CPU für ein einzelnes Datenelement. Beim Aufruf werden allerdings nicht einzelne Werte übergeben, mit denen dann gerechnet wird, sondern gleich ganze Arrays. Die Berechnung wird nun mit einem Aufruf implizit für alle Elemente des/der Arrays ausgeführt. Dabei hat man wenig bis gar keine Kontrolle über die Reihenfolge der Rechnungen, die natürlich auch keine (oder kaum) Abhängigkeiten voneinander aufweisen dürfen, damit das Ganze funktioniert. Allgemein ist dieser Ansatz als "Stream Computing" bekannt.

Im Vergleich mit bekannten Techniken wie SIMD oder Multithreading sprechen AMD/ATI und NVIDIA bei der Rechnung für ein einzelnes Datenelement gerne von einem Thread und nennen das Konzept gelegentlich auch SIMT (single instruction multiple threads). Der Begriff "Thread" stimmt hierbei aber nicht mit dem allgemeinen Bild eines Threads überein, da sie auf GPUs nicht unabhängig voneinander ausgeführt werden können. Der "single instruction"-Teil bei SIMT kommt indessen daher, dass immer eine ganze Gruppe von Threads quasi im Gleichschritt ausgeführt werden (muss). So eine Gruppe teilt sich eine Menge Hardware-Resourcen im Scheduler (um Hardware zu sparen natürlich). Sie besitzt zum Beispiel nur einen einzigen Instruction Pointer (Zeiger auf den jeweils nächsten Befehl eines Programms). Ein einziger Befehl wird immer für die komplette Gruppe ausgeführt. Deswegen können z.B. Verzweigungen im Programm auch nicht auf der Ebene der einzelnen Threads erfolgen. Sobald nur ein einziger Thread einen anderen Weg nimmt als die anderen, werden nacheinander beide (alle) möglichen Wege durchlaufen, was die Laufzeit natürlich stark ansteigen lässt.

<a href="http://www.planet3dnow.de/photoplog/index.php?n=6094"><img src="http://www.planet3dnow.de/photoplog/file.php?n=6094" border="1" alt="GPGPU Computing"></a>
Abb. 3: Erzeugung der "Threads" bei einem Pixelshader. Die Wavefronts werden aus einzelnen Quads zusammengesetzt und dann an die SIMD-Arrays verteilt. Bei Compute-Shadern kann festgelegt werden, welche Wavefronts zusammen auf einem SIMD laufen. Darauf wird später noch kurz eingegangen.

Die Größe so einer Gruppe ist durch die Hardware festgelegt und beträgt üblicherweise 32 (NVIDIA, einige AMD-GPUs, z.B. RV730) oder 64 Threads (z.B. RV670, RV740, RV770/790). Wie kommen jetzt diese Gruppen zu Stande? Wie bei den technischen Daten ausgeführt, besitzt jeder Kern der GPUs (jedes SIMD-Array) eine Anzahl von Shader-Einheiten (8 bei NVIDIA, oft 16 bei AMD). Bei beiden Herstellern verarbeiten diese Einheiten jeweils 4 Threads über 4 Takte verteilt. Dies ist sozusagen ein Überbleibsel des Grafikrenderings. Vielleicht sagt der Begriff Quad dem einen oder anderen etwas. Genau die 4 Pixel eines Quads werden heute immer noch bei einem Pixelshaderprogramm von so einer Einheit berechnet. Allgemein erhöht diese Vorgehensweise die Effizienz der Einheiten, da Latenzen besser versteckt (die effektiven Latenzen werden geviertelt) und die Caches besser genutzt werden können (benachbarte Pixel benötigen wahrscheinlich auch die gleichen/benachbarte Daten). Dadurch ergeben sich dann auch zwangsläufig die Größen der Gruppen als das Vierfache der Anzahl der Shadereinheiten pro Kern. AMD und NVIDIA haben sich natürlich auch tolle Namen dafür ausgedacht. So nennt NVIDIA so eine Gruppe "Warp", bei AMD heißt sie "Wavefront". Im Prinzip ist das nur die Abarbeitung von SIMD-Befehlen einer ISA mit breit angelegtem SIMD auf schmalerer Hardware. Es entspricht in etwa der SSE-Implementation vor Core 2 und Phenom. Dort wurden SSEx-Befehle, die auf 128 Bit Registern definiert sind, auch in zwei 64 Bit-Häppchen abgearbeitet. Hier sind es jetzt 4 Häppchen von 256 (NVIDIA) oder 512 Bit (ATI).

Zur weiteren Steigerung der Effektivität unterstützen die SIMD-Einheiten Multithreading. Das heißt, mehrere Wavefronts/Warps können gleichzeitig auf einer Einheit ausgeführt werden. Muss eine Wavefront/Warp auf einen Wert aus dem Speicher warten, wird zu einer anderen umgeschaltet, bei dem alle Daten vorhanden sind. Wie schon erwähnt, werden dabei die Inhalte der Register nicht im Speicher gesichert. Alle Wavefronts/Warps müssen sich daher die vorhandenen Register teilen. Damit ist die Anzahl der maximal gleichzeitig ausgeführten Wavefronts oft durch die Menge der Register limitiert, die ein Programm belegt. Ein Beispiel, bei einem Shaderprogramm, welches 16 Register benötigt, können auf einem RV770 maximal 256 / 16 = 16 Wavefronts (1024 "Threads") gleichzeitig auf einem SIMD-Array (Kern) laufen. Dies ergibt für den ganzen Chip dann 10 x 16 x 64 = 10240 gleichzeitig in Berechnung befindliche "Threads" (Pixel). Je komplexer ein Shader ist (mehr Register benötigt), desto schwieriger wird es die Speicherlatenzen zu verstecken. Dies macht klar, dass bei der Programmierung der GPUs darauf geachtet werden muss, möglichst wenige Register zu belegen.

[BREAK=GPU-Hardware aus Sicht des Programmieres: Kerne, SIMD und VLIW]

Die Begrifflichkeiten und die Herangehensweise unterscheiden sich stark zu einer CPU, aber man kann auch versuchen, das auf einen gemeinsamen Nenner herunterzukochen.
Mit den von CPUs bekannten Begrifflichkeiten entspricht ein Kern am ehesten einem SIMD-Core des RV770. Er hat einen eigenen L1-Cache, kann unabhängig von anderen SIMDs Befehle ausführen und besitzt eigene Load-Store-Einheiten (TMUs). Bei NVIDIA ist das nicht ganz so einfach. So sind nur die sogenannten "Thread Processing Cluster", die aus je zwei oder drei (G80/G92/G94 bzw. GT200) "Streaming Multiprocessors" (mit je 8 ALUs und 2 Special Function Units) bestehen, wirklich unabhängig. So teilen sich die Streaming Multiprocessors eines TPC den L1-Cache und die TMUs und können auch nicht wirklich unabhängig voneinander Befehle ausführen. Dies ist ein Bereich, an dem NVIDIA wahrscheinlich mit dem GT300 arbeiten wird, so dass die "Streaming Multiprocessors" dann eher einem CPU-Kern entsprechen werden, als sie das jetzt noch tun.

Wesentlicher Bestandteil eines Kerns einer GPU ist eine (oder mehrere) SIMD-Einheit(en). Die Breite der SIMD-Einheiten ist dabei deutlich größer als bei CPUs. Während SSE maximal vier 32 Bit-Werte auf einmal verarbeitet, so sind es entsprechend der Größe der Warps bzw. Wavefronts bei GPUs 32 oder gar 64 Werte (in Hardware jeweils ein Viertel davon)! Vor diesem Hintergrund erübrigt sich eigentlich auch die im Zusammenhang mit Intels Larrabee manchmal aufkommende Diskussion, ob die dort verwendeten SIMD-Register mit einer Breite von 16 float-Werten überhaupt effektiv genutzt werden können. Es ist sogar eher so, dass Larrabee die Einheiten in einigen Fällen wahrscheinlich erheblich effizienter als heutige GPUs nutzen kann. Dadurch, dass auch "horizontale" Operationen in den Registern und sogenannte "Swizzles" (Vertauschen von Werten in einem SIMD-Register) durchgeführt werden können, ist eine extrem schnelle Kommunikation zwischen den einzelnen "Threads" (in der GPU-Terminologie entspricht das ja einfach einer Spalte der SIMD-Register) möglich. Dies ist auf heutigen GPUs zwar auch machbar (ATI: Local Data Share, NVIDIA: Shared Memory), aber kostet erheblich mehr Performance, da die einzelnen Spalten bei GPUs in physisch getrennten Registern stehen. Bei einigen GPGPU-Anwendungen dürfte dies Larrabee deutlich helfen, für den Einsatz als normale 3D-Karte allerdings eher nicht. Außerdem erhöht dies natürlich die Komplexität (große, zusammenhängende Registerfiles statt vieler kleinerer nötig), was sich negativ auf die Transistoranzahl auswirkt.

Ein Punkt ist bisher noch fast unbeachtet geblieben. Was hat es eigentlich mit den fünffachen ALUs der ATI-GPUs auf sich? Ursprünglich hat man häufig einen Gegensatz zwischen den skalaren ALUs bei NVIDIA und "Vektor-ALUs" der ATIs konstruiert. Dies trifft es aber nicht. Vielmehr nutzt ATI hier eine Möglichkeit, die Anzahl der ALUs und damit die potentielle Rechenleistung der GPU zu steigern, ohne den Verwaltungsaufwand zu vergrößern, wie es etwa mit einer Erhöhung der Kernanzahl verbunden wäre. Wie geht das?

Beim Vergleich der GPU- und CPU-Konzepte wurde erwähnt, dass GPUs auf alle aufwändigen Maßnahmen zur Nutzung des ILP in einem Programm verzichten, da sowieso genügend Datenparallelität (sprich: viele Pixel, die gleichzeitig berechnet werden können) vorhanden ist, um die Einheiten auszulasten. Nun, es hätte vielleicht besser heißen sollen, dass auf alle aufwändige Hardware kostenden Maßnahmen hierfür verzichtet wird. Da aber zumeist doch sehr viele parallel auszuführende Anweisungen in einem Shaderprogramm vorhanden sind, kann man über andere Methoden nachdenken, als sie bei x86er CPUs angewandt werden.

Sicher kennen viele den Itanium von Intel. Seine Architektur beruht auf einem EPIC (Explicitly Parallel Instruction Computing) genannten Konzept. Die Idee hierbei ist, den Aufwand zur Ausnutzung des ILPs von der Hardware in die Software, d.h. in einen Compiler zu verlagern. Der Prozessor bekommt dabei sogenannte VLIWs (Very Long Instruction Words) zur Ausführung zugeteilt, d.h. immer ganze Bündel an Befehlen (für jede Ausführungseinheit genau einen Befehl) für die der Compiler sichergestellt hat, dass sie parallel ausgeführt werden können. Im Gegensatz zu einem superskalaren Prozessor (das sind fast alle modernen x86-CPUs) muss dafür keine Hardware eingesetzt werden. Ebenso bei den GPUs. Insgesamt kann ATI so weitere Funktionseinheiten integrieren und spart die Kontroll-Logik, die für weitere Kerne notwendig wäre. Man erhöht also die theoretische Performance pro Transistor, macht sich aber dafür abhängiger vom Compiler, der auch genügend parallele Instruktionen finden muss, damit das Konzept aufgeht.

<a href="http://www.planet3dnow.de/photoplog/index.php?n=6096"><img src="http://www.planet3dnow.de/photoplog/file.php?n=6096" border="1" alt="GPGPU Computing"></a>
Abb. 4: Schematische Darstellung einer "VLIW-Einheit". Sie besteht im Wesentlichen aus den x, y, z, w-Einheiten und der t-Einheit sowie dem zugehörigen Registerfile. x,y,z,w sind identische ALUs und führen die meisten gebräuchlichen Operationen aus (allerdings keine Integer-Multiplikationen, erst ab RV7x0 können sie Bit-Shifts). Die t-Einheit beherrscht praktisch alles was x, y, z, w können, ermöglicht aber zusätzlich auch die Berechnung komplizierterer Operationen (z.B. der transzendenten Funktionen, daher der Name, aber eben auch die Integer-Multiplikationen).

Dabei ist das keine ganz einfache Aufgabe, da sich ATI für immerhin 5 parallele Einheiten entschieden hat (seit dem R600, d.h. ab der HD2000er-Serie sind die Shader so aufgebaut). Im Grunde besitzt eine VLIW-Anweisung immer 7 Slots (je 64 Bit groß). Die ersten 5 Slots beinhalten Anweisungen für die x,y,z,w und t-Einheiten, die weiteren beiden Slots sind für bis zu vier 32bit Konstanten reserviert. Mit einer einzigen solchen Anweisung vom Thread-Sequenzer wird dann über 4 Takte verteilt dieses Befehlsbündel mit bis zu 5 einzelnen Operationen für alle 64 Datenelemente in der Wavefront ausgeführt. Bei Spielen geht die Rechnung meist ganz gut auf, da dort häufig mit Vertices (meist 4 Werte, x,y,z,w) oder mit Farbwerten (ebenfalls häufig 4 Werte, rot, grün, blau, alpha) gerechnet wird. Daher existieren meist genügend unabhängige Instruktionen, die dann zu entsprechenden Instruktionsgruppen zusammengefasst werden können.

Diverse Tests mit komplexen Shadern aus Spielen zeigen die Konkurrenzfähigkeit bzw. sogar Überlegenheit dieses Konzepts in dadurch limitierten Szenarien. Üblicherweise sind dabei durchschnittlich 3,5 der insgesamt 5 Slots einer Instruktionsgruppe belegt. Im Falle von GPGPU-Anwendungen kann es sinnvoll sein, manuell einfach mehrere Rechnungen zusammenzufassen. Bei für GPUs geeigneten Anwendungsfällen mit hohem Datenparallelismus ist dies normalerweise sehr einfach und z.B. bei Portierung von Code, der bereits SSE nutzt, sogar schon erledigt. Für NVIDIA-GPUs bringt dieses Vorgehen allerdings nicht so viel.

Die meisten dieser Details der GPUs bleiben für den Programmierer unsichtbar. Trotzdem können sie sehr hilfreich sein, um die Umsetzung auf GPUs zu planen und zu verstehen, wo es klemmen könnte. Als Programmierer bekommt man erstmal nur eine sehr vereinfachte, abstrahierte Darstellung zu sehen, die mit der zugrunde liegenden Hardware nicht unbedingt viel zu tun haben muss. Dies hat neben ein paar Nachteilen den Vorteil, dass man zu einem großen Teil hardwareunabhängig arbeiten kann. Das gleiche Programm kann meist völlig unverändert auch auf neuen Grafikkarten eingesetzt werden. Irgendein Spiel wird auch auf der nächsten Grafikkartengeneration noch laufen, da der Treiber die Umsetzung der programmierten Shader auf die eventuell vollkommen neue Hardware vornimmt. Dies soll aber im nächsten Abschnitt näher erläutert werden.

[BREAK="Softwarestack" zur Programmierung einer GPU]

Ursprünglich wurden für die GPGPU-Nutzung meist Pixelshader-Programme geschrieben, die dann über DirectX oder OpenGL im Prinzip einfach ein Bild gerendert haben. Der Farbwert jedes Pixels stand dabei für das jeweilige Ergebnis. Nun unterliegen Pixelshader genau wie Vertexshader gewissen Beschränkungen, weil sie ja eigentlich von der Spezifikation her für das Grafikrendering entwickelt wurden. Außerdem erhöht dies die Komplexität, da dabei einige Sachen unnötig ausgeführt werden. Deshalb haben beide Hersteller Schnittstellen eingeführt, um die Nutzung der GPUs von DirectX bzw. OpenGL zu trennen.

Einen Vorreiter in dieser Sache, die Stanford University mit ihrem Distributed Computing Projekt [URL="http://dc.planet3dnow.de/wiki/index.php?title=Folding%40Home"]Folding@Home[/URL], sollte man hierbei nicht unerwähnt lassen. Die ersten GPU-Clients benutzten eine BrookGPU genannte, ebenfalls in Stanford entwickelte Variante der C-kompatiblem Stream Computing Language Brook. Hier übersetzt ein Source to Source Compiler den Quelltext (normales C mit ein paar Erweiterungen) in den entsprechenden Shadercode für DirectX bzw. OpenGL und kapselt so den eigentlichen Code für die Grafikkarte vom Entwickler.

Das gleiche Prinzip liegt eigentlich allen Ansätzen zur Nutzung einer Hochsprache für GPGPU zu Grunde. Der Unterschied heute ist nur, dass OpenGL bzw. DirectX als Zwischenstufe zur Nutzung der GPU durch eine andere, für GPGPU-Computing entwickelte Schnittstelle ersetzt wurde. Im Fall von NVIDIAs CUDA (Compute Unified Device Architecture, eigentlich „C for CUDA“) übersetzt ein Compiler den Code in eine PTX (Parallel Thread eXecution assembly language) genannte, assemblerartige Zwischensprache. In dieser Form wird die Routine in das eigentliche Programm eingebettet. Zur Laufzeit (also nach Start des Programms) wird der PTX-Code dann an den Treiber übergeben, der das mit einem Just-in-time-Compiler für die jeweils installierte Grafikkarte übersetzt und schlussendlich ausführt. Bei AMD läuft es im Prinzip genauso, nur die Namen sind anders. Statt CUDA heißt es dort Brook+ (eine erweiterte Variante von Brook) und die assemblerartige Zwischensprache heißt ganz einfach IL (Intermediate Language). Wenn man will (oder muss), ist es auch möglich, den so erzeugten IL- bzw. PTX-Code noch zu ändern oder auch gleich die Routine auf dieser Ebene zu entwerfen. Dies ist allerdings meist recht aufwändig. Während NVIDIA eigentlich voll auf CUDA setzt, hat bei AMD die "Zwischenebene" einen eigenen Namen bekommen: CAL (Compute Abstraction Layer). Die aufgrund der VLIW-Architektur sehr wichtige Optimierung findet übrigens erst im CAL-Compiler bei der Umwandlung von IL in den hardwarespezifischen Code statt.

<a href="http://www.planet3dnow.de/photoplog/index.php?n=6093"><img src="http://www.planet3dnow.de/photoplog/file.php?n=6093" border="1" alt="GPGPU Computing"></a>
Abb. 5: Prinzipieller Ablauf zur Nutzung der GPU. Der Code für die GPU wird mit einem Compiler in eine Zwischensprache übersetzt und in die ausführbare Datei eingebettet. Zur Laufzeit übersetzt und optimiert ein weiterer Compiler (Teil des Grafikkartentreibers) das für die konkret vorhandene GPU. Der Ablauf ist bei ATI und NV GPUs im Prinzip gleich.

An dem grundlegenden Prinzip wird sich auch mit dem demnächst bald erscheinenden OpenCL nichts ändern. Sogar IL bzw. PTX werden erhalten bleiben. Beide Hersteller schalten lediglich einen zusätzlichen OpenCL-Compiler davor, der (ebenfalls als JIT-Compiler) OpenCL C in PTX bzw. IL umwandelt. Schon jetzt sind die Compiler der Grafikkartenhersteller recht flexibel. So werden auch die DirectX-Shader in der HLSL-Hochsprache mit einem JIT-Compiler verarbeitet (zu PTX bzw. IL) und es ist zumindest bei ATI möglich, Brook+ in HLSL zu übersetzen. Weil ganz selten direkt für die Hardware programmiert wird, sind diese Compiler sehr wichtig. Darum kann eine neue Treiberversion durch Optimierungen an den Shader-Compilern manchmal auch einiges an Performance herausholen.

[BREAK=Ein einfaches Brook+-Programm für die GPU]
(nicht am Programmieren interessierte Leute können ruhig weiter blättern)

Jetzt aber mal zur Sache. Nach diesem ewigen Vorgeplänkel, was muss ein Programmierer denn eigentlich praktisch tun, um eine GPU zu nutzen? Wählen wir mal irgendein aus der Luft gegriffenes Beispiel aus (obwohl das gar nicht so weit von dem entfernt ist, was z.B. Milkyway@home tut). Angenommen ich will folgendes Problem lösen:
Für irgendeine Funktion zweier Variablen f(x,y) soll die Summe über alle Funktionwerte für alle ganzzahligen x und y von 0 bis N-1 gebildet werden.
Für eine CPU würde man das so programmieren (Pseudocode):
Code:
Ergebnis = 0
von x = 0 bis N-1
{
	von y = 0 bis N-1
	{
		Ergebnis = Ergebnis + f(x,y)
	}
}

Unglücklicherweise hängt jeder Durchlauf durch die Schleifen vom vorhergehenden ab, es lässt sich also in der Form nicht parallelisieren. Aber man kann einfach die Addition zu den bisherigen Werten weglassen, den Wert von f(x,y) in den Speicher schreiben und erst in einem zweiten Schritt die Addition ausführen. Klingt vielleicht zuerst etwas widersinnig, ist aber für die Parallelisierung hier nötig. Ein Brook+-Kernel, der den ersten Schritt macht, sieht so aus:

Code:
kernel void funktionswerte(out float wert<>)	// Ausgabe von Fließkommawerten einfacher Genauigkeit (float)
{
	float x = indexof(wert).x;	// Erstmal die Koordinaten rauskriegen,
	float y = indexof(wert).y;	// für die der Wert gerade berechnet wird
	wert = f(x,y);		// muss natürlich durch irgendeine Rechnung ersetzt werden
}

Ziemlich einfach, oder? Fehlt bloß noch die Addition der einzelnen Werte, die werden ja bisher einfach nur in den Grafikkartenspeicher geschrieben. Dazu benutzt man einen sogenannten Reduzierkernel, der aber auch ganz einfach aussieht.

Code:
reduce void summe(float wert<>, reduce float Ergebnis)
{
	Ergebnis += wert;
}

Damit das Ganze funktioniert, muss das Programm, welches die Kernel aufruft, natürlich noch ein wenig Vorbereitungsarbeit erledigen. Denn woher "wissen" die Kernel eigentlich, für welche Werte das alles ausgeführt werden soll?

Wahrscheinlich sind die <> Zeichen schon aufgefallen. Die kennzeichnen immer einen sogenannten Stream, effektiv ist das jeweils ein Array im Grafikkartenspeicher. Wenn nicht anderweitig festgelegt, wird ein Kernel immer für alle Elemente eines Streams ausgeführt. Mit dieser Funktion ersetzt man praktisch die beiden geschachtelten Schleifen vom CPU-Code. Bei der Definition eines Streams muß man natürlich angeben, wie viele Dimensionen (hier zwei) er hat und wie groß er ist (hier N x N Elemente) und welchen Typ die Elemente haben (hier float, also Fließkommazahlen einfacher Genauigkeit). Komplett mit den Aufrufen der Kernels sieht dies im Programmcode dann so aus:

Code:
float Ergebnis;
Stream<float> wert(2, {N, N});	// float-Array auf Grafikkarte reservieren, 2 Dimensionen, N x N Elemente
funktionswerte(wert);		// Funktionswerte berechnen und im Array ablegen
summe(wert, &Ergebnis);	// Summe über die Werte bilden, Rückgabe in Ergebnis

So, war doch gar nicht so schwer das erste Brook+-Programm!

Auf der nächsten Seite überprüfen wir mal, ob das überhaupt schneller als auf der CPU läuft.

[BREAK=Ein einfaches Brook+-Programm für die GPU, Performance im Vergleich zur CPU]

Vielleicht sollte man mal überprüfen, ob sich das Ganze überhaupt von der Performance her lohnt, d.h. ob die GPU hier überhaupt schneller als die CPU ist. In diesem einfachen Beispiel müssen praktisch kaum Daten zur Grafikkarte hin oder wieder zurück übertragen werden. Das entfällt also schon mal als möglicherweise bremsender Faktor. Speicherzugriffe haben wir auch nur wenige (nichts Lesen, nur einen Wert Schreiben bei der Funktionsberechnung, ein paar Werte Lesen und Schreiben beim Reduzierkernel), sieht also fast so aus, als könnte das was bringen. Kommt jetzt nur noch auf die Funktion an, die man da einsetzt. Die Faustregel ist einfach, je komplizierter die wird, also je mehr gerechnet werden muss, desto eher lohnt sich die GPU.

Ein einfacherVersuch: f(x,y) = x² + y, N = 1000 also 1000 x 1000 = 1.000.000 Elemente

Der Funktionswerte-Kernel wird in 6 VLIW-Instruktionen für die GPU übersetzt. Davon entfallen schon 4 auf die Bestimmung der x- und y-Werte. Damit sieht das Ganze nicht sehr effizient aus. Trotzdem begrenzen in diesem Fall auf einer RV770 (RV730 auch) schon die ROPs, da nur 16 bzw. 8 Werte pro Takt in den Speicher geschrieben werden können. Die dafür notwendige Speicherbandbreite von 48 GB/s bei 750 MHz (16 x 4 = 64 Byte pro Takt) limitiert dagegen noch nicht. Anders beim RV670 (HD3800er Reihe). Hier entscheiden wirklich die 6 Takte pro Datenpunkt über die Geschwindigkeit der Rechnung. Aber betrachten wir den Fall der schnelleren RV770. Hier benötigt die GPU für die Berechnung der Werte etwa 65.000 Takte (1.000.000 / 16), mithin knappe 0,1 Millisekunden bei 750 MHz, wobei die Summierung noch hinzukommt (dauert praktisch genau so lange).

Eine CPU schafft bei perfekter Ausnutzung von SSE (ist hier ganz gut möglich) maximal 2 Werte pro Takt (allerdings schon inklusive der Summation). Die gleiche Aufgabe ist also von einem Kern in 500.000 Takten erledigt, bei 3 GHz also in etwa genauso schnell wie die GPU (unter 0,2 Millisekunden). Dabei kommt der CPU zu gute, dass die komplette Rechnung in den Registern ablaufen kann, man also gar keine Speicherbandbreite benötigt. Hier lohnt sich der Aufwand einer GPU-Version also selbst für eine High-End Grafikkarte nicht.

Eine einfache Möglichkeit ist jetzt, immer gleich 4 Datenwerte auf einmal zu berechnen, z.B. vier verschiedene x-Werte. Der Stream muss dann natürlich nur noch 250 x 1000 Werte für N=1000 groß sein und der Reduzierkernel eben entsprechend auch jeweils 4 Werte zusammenzählen. Netterweise gibt es zu diesem Zweck schon passende Vektortypen, mit denen man den Kernel anpassen kann:

Code:
kernel void funktionswerte4(out float4 wert<>)
{
	float4 x;		// Erstmal die Koordinaten rauskriegen,
	float4 y;		// für die der Wert gerade berechnet wird, x-Werte werden mit 4 skaliert
	x.x = indexof(wert).x * 4.0f;	
	x.y = indexof(wert).x * 4.0f + 1.0f;
	x.z = indexof(wert).x * 4.0f + 2.0f;
	x.w = indexof(wert).x * 4.0f + 3.0f;
	y = indexof(wert).y;	// der Wert wird in alle Komponenten von y geschrieben
	wert = x * x + y;	// führt die Rechnung jeweils für alle 4 Komponenten aus 
}

Für viele vielleicht überraschend und erstaunlich, aber dieser Kernel, der vier mal so viel Arbeit erledigt, wird ebenfalls in nur 6 VLIW-Instruktionen übersetzt. Hier kommt einem zu Gute, dass jede VLIW-Instruktion 5 Slots besitzt und sowohl die Indexberechnung*) als auch die eigentliche Werteberechnung für alle 4 Komponenten parallel erfolgen kann. Dies ist natürlich erheblich besser. Allerdings stellt selbst schneller GDDR5 nicht genügend Speicherbandbreite bereit, um die Werte alle in den Speicher schreiben zu können. Man könnte theoretisch immer noch 16 Werte pro Takt speichern, allerdings ist jetzt jeder Wert 16 Byte, statt nur 4 Byte groß. Das würde also 192 GB/s Speicherbandbreite erfordern und die sind einfach nicht da. Effektiv wird man sich also mit maximal 10 Schreibvorgängen (zu je 16 Bytes) pro Takt zufrieden geben müssen. Die Ausführungseinheiten könnten etwa das Zweieinhalbfache liefern! Hinzu kommt, dass immer noch nur ein Drittel der Instruktionen (2 von 6) die eigentliche Berechnung erledigen, der Verwaltungsaufwand bei so einer einfachen Rechnung ist also beträchtlich. Trotzdem ist dies immer noch deutlich besser als der erste Versuch (etwa doppelt so schnell). Die zweite Version würde zumindest schon einen einzelnen Kern einer CPU von der Performance her schlagen können.

Man sieht also, dass es gar nicht so einfach ist, die Rechenleistung der GPUs wirklich zu nutzen. Was dazu benötigt wird, ist ein Algorithmus, der nicht übermäßig einfache Rechnungen beinhaltet (ROPs bzw. Speicherbandbreite begrenzen durch die vielen Schreibvorgänge) und trotzdem genügend Parallelität anbietet, um an vielen Elementen gleichzeitig zu rechnen. Weiterhin ist es gut, wenn die Daten immer möglichst vollständig auf der Grafikkarte verbleiben können. Kopiervorgänge selbst über PCI-Express 2.0 sind deutlich langsamer als der auf den Karten verbaute Speicher und können so beträchtlich zur Gesamtlaufzeit beitragen.

*: Das ist auch eine Demonstration dafür, dass die VLIW-Slots durchaus unterschiedliche Instruktionen beinhalten können (Indexberechnung), sie also nicht nur wie Vector-ALUs einsetzbar sind.

[BREAK=Beispiele aus dem Distributed Computing]

Ein ganz einfaches und gut (wenn auch nicht perfekt) für GPUs geeignetes Problem ist z.B. die Überprüfung der sogenannten Collatz-Vermutung, DC-Jüngern vielleicht unter dem Begriff 3x+1 bekannt. Um was handelt es sich da? Man nehme eine positive ganze (natürliche) Zahl x. Ist sie gerade, teilt man sie durch zwei, wenn sie ungerade ist, multipliziert man sie mit 3 und addiert 1 dazu (daher 3x+1). Im Prinzip besagt diese Vermutung (die bisher noch kein Mathematiker beweisen oder widerlegen konnte), dass man mit dem beschriebenen Vorgehen am Ende letztendlich immer bei 1 landet (bzw. in einer Schleife immer 4, 2, 1, 4, … durchläuft). Um die Vermutung zu widerlegen, reicht es ja, ein einziges Gegenbeispiel zu finden, was das Ziel des 3x+1@home-Projektes war (wurde nicht geschafft, es ist also immer noch ungelöst). Inzwischen wurden alle Zahlen bis etwa 10^23 schon überprüft, man muss also mit sehr großen Zahlen arbeiten, was wir jetzt hier mal vernachlässigen (wir beschränken uns auf 32 Bit, größere Zahlen gehen aber im Prinzip genauso).

Das eigentliche Problem ist die Verzweigung in Abhängigkeit davon, ob die Zahl gerade oder ungerade ist. Ein Kernel, der die Anzahl der Schritte bestimmt (üblicherweise sind das ein paar hundert bei großen Zahlen), bis man bei 1 ankommt, könnte im einfachsten Fall z.B. so aussehen (ist noch nicht die schnellste Variante ;)) und unterscheidet sich praktisch in nichts von normalem C-Code:

Code:
kernel void collatz(uint x<>, out uint steps<>)
{  
    uint i = 0;		// Anzahl Schritte
    uint z = x;		// zu überprüfender Wert

    while(z!=1) 		// solange 1 nicht erreicht
    {
        if(z & 1)		// z ist ungerade
        {
             z = (z + z) + (z + 1);	// Addition ist schneller als Multiplikation (begrenzte Anzahl der Multiplier)
			// Klammern um Abhängigkeitskette zu kürzen
        }else			// z ist gerade
        { 
             z = z>>1;	// schieben um ein Bit nach rechts, deutlich schneller als eine echte Division durch zwei
        }
        i++;			// Erhöhen der Schrittzahl
    }

    steps = i;		// Ausgabe der Schrittanzahl bis zum Erreichen der 1
}

Die Speicherbandbreite spielt hier bei der großen Anzahl von Schritten überhaupt keine Rolle. Allerdings sind wie schon gesagt Verzweigungen ein Problem. Sie können nur für komplette Wavefronts, also Gruppen von bis zu 64 Datenelementen wirklich als Verzweigungen ausgeführt werden. Nehmen verschiedene Threads innerhalb einer Wavefront unterschiedliche Wege, so werden alle möglichen Wege für alle Datenelemente nacheinander ausgeführt. Dabei werden alle Ergebnisse aller Zweige berechnet und hinterher nur das Ergebnis des jeweils richtigen Weges übernommen, der Rest wird praktisch umsonst gemacht und am Ende verworfen (die Technik heißt Prädikation, nicht zu verwechseln mit Branch prediction, also der Sprungvorhersage). Bei so kleinen Verzweigungen wie hier, werden allerdings beide Zweige parallel ausgeführt, nicht nacheinander (bei ATI ist das wegen der 5 Slots pro VLIW-Einheit auch wirklich parallel möglich und rettet damit die Auslastung der Slots, ansonsten wären hier skalare Einheiten klar im Vorteil) und das Ergebnis mit einem "conditional move" (bedingtes Kopierens eines Wertes in ein anderes Register) gesetzt. Bei den nicht vorhersagbaren Sprüngen für dieses Problem stellt das die optimale Lösung dar (und würde auch bei einer optimierten CPU-Variante so gemacht werden).

Dadurch kann man die Geschwindigkeit im Prinzip sehr gut vorhersagen. Das ganze Brook-Programm wird in lediglich 7 VLIW-Instruktionen übersetzt, wovon 5 innerhalb der Schleife sitzen (und davon 2 die Schleife steuern, wenn der Compiler cleverer wäre, würde eine reichen). Man kann auf einem RV770/RV790 mit diesem simplen Code also genau 160 VLIW-Einheiten / 5 = 32 Schritte pro Takt ausführen, bei 750 MHz also 24 Milliarden Schritte pro Sekunde. Mit manuellem Eingriff in den IL-Code würden 4 Instruktionen ausreichen, also 30 Milliarden Schritte pro Sekunde erreicht. Wegen der voneinander abhängigen Instruktionen kann eine CPU die identische Aufgabe nicht unter 3 Takten pro Schritt ausführen. Ein 3 GHz Quadcore würde also maximal 3 GHz * 4 Kerne / 3 Takte = 4 Milliarden Schritte pro Sekunde schaffen. Wenn man mit größeren Zahlen arbeitet (selbst 64 Bit reichen für eine reale Umsetzung nicht aus, 128 Bit sind Pflicht) besitzt die CPU einen prinzipiellen Vorteil, wenn ein 64 Bit-Programm eingesetzt wird. Es müssen einfach weniger abhängige Instruktionen ausgeführt werden, da 64 Bit auf einmal abgearbeitet werden können und nicht nur 32 Bit. Dies wird zu einer gewissen Verkleinerung (aber nicht Halbierung) des Vorsprungs der GPU führen (natürlich nur unter 64 Bit). Weiterhin besitzt die CPU den Vorteil für jede Zahl wirklich nur die benötigte Anzahl an Schritten ausführen zu müssen. Bei GPUs muß die Schleife so lange durchlaufen werden, bis wirklich alle Werte in einer Wavefront/Warp bei 1 ankommen. Trotzdem bleibt die GPU für diese Aufgabe besser als eine CPU geeignet.

Bisher waren ja alle Kernels ganz klein und friedlich. Als Vergleich, wie umfangreich ein Kernel sein kann, schaue man auf das Distributed Computing Projekt Milkyway@home. Inklusive der vorbereitenden Arbeiten führt der Kernel, der dort den Hauptteil der Rechnung erledigt (ist im Prinzip eine Gauß-Legendre-Integration mit ziemlich vielen Stützpunkten, falls das irgendwer genau wissen will), in seiner einfachsten Version (die anderen machen noch mehr) jedes Mal folgende Operationen aus:
  • Kopieren von 4800 double-Werten als Lookup-Table zur Grafikkarte (38,4 kB)
  • Kopieren von 24 double-Werten in den Constant Cache der GPU (Parameterübergabe)
  • Berechnung von 1,12 Millionen double2-Werten (17,92 MB), pro double2 (zwei double Werte) werden dabei
    • 13684 double precision Operationen ausgeführt (10691 VLIW-Instruktionen)
    • 18 Register (zu je 128 Bit) belegt (d.h. maximal 14 Wavefronts können gleichzeitig laufen), das sind noch verhältnismäßig wenige Register
    • 225 double-Werte (1800 Bytes) aus Lookup-Tables gelesen
    • 2 double-Werte (16 Bytes) in den Speicher geschrieben
Das Ganze wird (zusammen mit einem Reduktionskernel) für eine übliche Workunit 160 mal gemacht. Als Vorbereitung müssen einmalig vor Beginn der Rechnung noch 85.400 double-Werte (~ 683 kB) ebenfalls als Lookup-Tables auf der Grafikkarte hinterlegt werden. Wie man sieht, ist das Verhältnis von Rechenoperationen zu Speicherzugriffen sehr viel günstiger als bei dem einfachen Beispielkernel. Wurden dort lediglich 2 Rechenoperationen pro Datenelement ausgeführt, so kommen hier mehr als 50 Rechenoperationen auf einen Speicherzugriff. Der ganze Kernel verarbeitet zwar insgesamt über 2,2 GB an Speicherzugriffen, davon wird allerdings erstens einiges durch die Caches abgefangen und zum zweiten bleibt man auch weit entfernt von der maximalen Speicher-Transferrate moderner Grafikkarten. Der Datentransfer über PCI-Express bleibt auch sehr im Rahmen, selbst AGP-Karten können ohne Leistungsverlust mithalten (auch weil der Rückkanal praktisch nicht genutzt wird). Deshalb benötigt dieser Kernel auf einer HD 4870 auch nur ziemlich genau 100 Millisekunden für die dabei gerechneten 15,33 GFLOPS. Da dabei nur maximal 22 GB/s Speicherbandbreite benötigt wird, könnte sogar der Speicher der Karte massiv untertaktet werden (kostet nur beim Reduktionskernel etwas Geschwindigkeit). Summa Summarum wird also eine Rechenleistung von über 150 GFLOPS erreicht. Bei dem Instruktionsmix in dem Kernel ist das mehr als 95% der hier theoretisch möglichen Performance (die 240 GFLOPS double precision Peak schafft man nur mit MULADD-Instruktionen). Dies ist weit mehr, als z.B. ein 3 GHz Quadcore erreichen kann (48 GFlops theoretische Peakleistung). Effektiv ist eine HD 4870 hier etwa 5 bis 6 mal schneller, als alle 4 Kerne so eines Quadcores zusammen. Dabei muss natürlich klar sein, dass diese Bedingungen nicht immer erfüllt werden können. Milkyway@home stellt mit seinem Algorithmus gewissermaßen (trotz doppelter Genauigkeit) fast einen Idealfall dar.

[BREAK=Performance-Fallen / Speicherhierarchie]

In den vorhergehenden Abschnitten wurden schon Sachen genannt, die die GPU ordentlich ausbremsen können. Das sind zum einen sehr kurze Shader, die die ROPs oder die Speicherbandbreite überfordern und zudem ein ungünstiges Verhältnis von Verwaltungsaufwand zu Rechenaufwand aufweisen. Ständig große Datenmengen aus dem Hauptspeicher des Rechners zur GPU und wieder zurück zu schieben ist natürlich ebenfalls keineswegs förderlich, genau wie sehr viele Verzweigungen. Um ein paar der zusätzlichen Fallen zu verstehen, muss man sich vielleicht noch einmal den Abschnitt über die Hardware der GPUs in Erinnerung rufen.


<a href="http://www.planet3dnow.de/photoplog/index.php?n=6090"><img src="http://www.planet3dnow.de/photoplog/file.php?n=6090" border="1" alt="GPGPU Computing"></a>
Abb. 6: Speicherhierachie von ATIs HD4000er Serie

Ein wesentlicher Punkt waren die Unterschiede zur CPU bei der Organisation der Caches. Bei CPUs funktionieren sie sowohl als Lese- als auch Schreibpuffer. Zudem wird die sogenannte "Kohärenz" der verschiedenen Caches (L1/L2/L3 sowie zwischen mehreren Kernen oder auch Sockeln) garantiert. Das heißt selbst wenn Kern1 einer CPU irgendeinen Wert in seinem L1-Cache verändert (der aber natürlich eine Speicherstelle im Hauptspeicher puffert), und Kern3 dann auf die gleiche Speicherstelle zugreift (die sich auch schon im Cache dieses Kerns befinden kann), wird garantiert, dass Kern3 immer mit den aktuellen Daten (in diesem Fall aus dem L1-Cache von Kern1) arbeitet. Dazu werden jeweils Abfragen an alle Kerne/CPUs im System gesendet, falls der Status nicht bekannt ist und falls nötig die aktuellen Daten übertragen. Dies stellt natürlich einen erheblichen Aufwand dar, den man bei aktuellen GPUs einfach mal gespart hat (Intels Larrabee wird die Caches allerdings kohärent halten). Die Caches einer GPU werden wie schon vorher erwähnt praktisch als reine Lesecaches eingesetzt*). Sie dienen nur dazu, die Bandbreitenanforderungen an den Speicher zu vermindern, da häufig die gleichen oder direkt benachbarte Werte ausgelesen werden (z.B. bei Textursamples). Schreibvorgänge werden nicht gecached. Will man also einen soeben geschriebenen Wert in einem anderen Thread benutzen, so ist nicht garantiert (ziemlich unwahrscheinlich), dass der neue Wert auch wirklich aus dem Speicher gelesen wird. Damit das klappt, muss man sicherstellen, dass die Caches für das Lesen der Daten nicht benutzt werden. Dies kann über das Flushen der Caches erreicht werden, was aber natürlich nicht zu knapp Performance kostet.

Neuere GPUs bieten allerdings noch eine andere Möglichkeit Daten zwischen Threads auszutauschen. Ab den RV7x0 bei ATI und schon ab dem G80 bei NVIDIA existiert ein kleiner 16 kB messender Speicherbereich pro Kern, auf den die Threads (können mehrere Wavefronts/Warps sein, die übergeordnete Gruppen bilden), lesend und schreibend zugreifen können (write private / read public Modell, ein Thread kann also alles lesen, was die anderen Threads schreiben, aber nur in seinen eigenen Bereich schreiben). NVIDIA nennt das shared memory, ATI Local Data Share (LDS). Weiterhin kann man ausnutzen, dass auf GPUs bei einem Threadwechsel (d.h. wenn zwischen Warps/Wavefronts umgeschaltet wird) alle Daten in den Registern bleiben. Normalerweise kann man nur auf die Register zugreifen, die zu dem eigenen Thread der aktuellen Wavefront gehören. Diese Beschränkung lässt sich allerdings bei ATI auch für eine beliebige Anzahl an Registern aufheben. Damit können die jeweils n-ten Threads aller auf dem SIMD laufenden Wavefronts einen Teil der Register gemeinsam verwenden. Dies kann zum Beispiel für effizientere Reduktionen benutzt werden.

Beide Methoden zum Datenaustausch zwischen Threads sind zwar schon ein erheblicher Fortschritt gegenüber dem recht unflexiblen Streaming-Modell (was gar keine Kommunikation vorsieht) und kann für einige Algorithmen durchaus einen Geschwindigkeitsvorteil von Faktor 10 bringen, trotzdem wird in solchen Fällen Larrabee mit seiner CPU-ähnlichen Flexibilität wahrscheinlich im Vorteil sein. Dazu kommen die Schwierigkeiten bei der Programmierung wenn man die im Vergleich kompliziertere Speicher-Hierarchie der GPUs optimal nutzen will. CUDA offerierte hier von Anfang an die volle Kontrolle durch den Programmierer (oder bürdete sie ihm auf ;)). Mit Brook+ hat man dagegen erst seit kurzem mit den Neuerungen der Stream-SDK 1.4 entsprechende Eingriffsmöglichkeiten. Die Features der neueren GPUs (wie LDS) wurden erst verspätet mittels Brook+ ansprechbar. Wollte man ATI-GPUs für entsprechende Algorithmen richtig nutzen, kam man bisher praktisch nicht um die Programmierung in IL herum.

Auch für die zukünftige Unterstützung von OpenCL hat das eben Beschriebene wahrscheinlich Auswirkungen. So besitzen wohl erst die RV7x0-GPUs alle von OpenCL vorgesehenen Features in Hardware. Es kann also durchaus sein, dass OpenCL auf ATI-Seite erst ab der HD 4000er Serie unterstützt werden wird. Allerdings ist es (mit entsprechendem Performanceverlust) im Prinzip auch möglich, die fehlenden Funktionen in Software für die älteren Grafikkarten nachzubilden. Da müssen wir uns überraschen lassen!


*: Genaue Informationen zum Thema Caches bei GPUs sind sehr rar, beide Hersteller halten sich da ziemlich bedeckt. Eventuell updaten Threads schon den L1-Cache in "ihrem" SIMD bei Schreibvorgängen auf Adressen, die auch im L1-Cache liegen (ansonstens werden Schreibzugriffe wie gesagt überhaupt nicht gecached, es ist kein write-through cache), aber diese Änderung wird nicht zu den anderen Caches propagiert. Falls also ein Thread Daten liest und sie geändert wieder in den Speicher schreibt, so bekommt er selber bei einem nochmaligen Lesen den bereits geänderten Wert aus dem Cache zurück. Bei anderen Threads ist das Verhalten aber mehr oder weniger undefiniert (weil auf anderen SIMDs andere Werte in den Caches stehen können bzw. ohne Synchronisation und Flushen der Caches unklar ist, wann genau die Threads ausgeführt werden und ihre Daten lesen).

[BREAK=Compute Shader]

Die wesentliche Neuerung der HD 4000er Karten von der Seite der Programmierbarkeit ist die Unterstützung einer neuen Shader-Art, der sogenannten Compute-Shader (zwar verwandt, aber nicht zu verwechseln mit den DirectX11 Compute Shadern). Nur damit können alle Features der GPU wie z.B. LDS genutzt werden. Außerdem ermöglichen die Compute Shader den gleichen Grad der Kontrolle über die Speicherhierarchie sowie die Zuordnung von Threads in Wavefronts/Warps und der Bildung weiterer Gruppen von Wavefronts/Warps wie mit NVIDIAs CUDA. Dies erfordert zum Teil durchaus mehr Aufwand bei der Programmierung, um nicht unnötig Performance zu verschenken. HD 3000er Karten (oder auch die neueren, wenn nicht im Compute-Shader-Modus, d.h. üblicherweise also Pixel- bzw. Fragmentshader) teilen die Threads nach einem vordefinierten Muster (das ATI ironischerweise "Hierarchical Z pattern" nennt) in die einzelnen Wavefronts ein. Der Programmierer hat darauf keinen wirklichen Einfluß. Im Prinzip übernimmt der Rasterizer diese Aufgabe. Dieser wurde natürlich für Grafikanwendungen optimiert, so dass da in etwa folgendes Muster benutzt wird (das genaue rückt ATI nicht raus und kann sich auch von GPU zu GPU unterscheiden):

<a href="http://www.planet3dnow.de/photoplog/index.php?n=6091"><img src="http://www.planet3dnow.de/photoplog/file.php?n=6091" border="1" alt="GPGPU Computing"></a>
Abb. 7: Wahrscheinliches Muster der Zuweisung von Threads aus der Execution domain bei Pixelshadern und das damit verbundene mögliche Layout der Memory Tiles. Der RV730 mit einer Wavefront-Größe von nur 32 Threads/Pixeln benutzt 8x4 Tiles. Höherdimensionale Anordnungen von Threads werden in Software durch Address-Translation erzeugt.

Die Zuordnung von Threads/Pixeln erfolgt im Pixelshadermodus immer in Einheiten von 2x2 (ein Quad) als kleinster Einheit. Dies hat zur Folge, dass z.B. bei eindimensionalen Streams immer nur die Hälfte der Ausführungseinheiten benutzt wird (eine Hälfte eines Quads, also wird genauer nur die Hälfte der Taktzyklen gerechnet, da ein Quad ja von einer Einheit gerechnet wird). Die Wavefronts selber bilden Blöcke aus jeweils 8x8 Threads. Der Scheduler kann aber mehrere nur teilweise gefüllte Blöcke zu einem zusammenfassen, nur die Quads sind "unteilbar". Der Vorteil dieser automatischen Zuordnung ist, dass auch die Streams in einem angepassten Layout im Speicher abgelegt werden. Durch das "Memory Tiling" (im Prinzip eine Anpassung der Datenlayouts an das Interleaving der einzelnen Speichercontroller) werden die Caches bei vielen Aufgaben optimal genutzt und auch die Last über alle Speichercontroller verteilt. Also für viele Aufgaben ist es wirklich das einfachste und auch schnellste dieses vordefinierte Layout zu benutzen.

Im Falle der Compute-Shader bei ATI (bei CUDA schon seit G80) sind die Restriktionen der Zuordnung aufgehoben. Die einzelnen Threads bilden kein 2D-Array mehr, sondern sind einfach eine Liste. 2D, 3D usw. Anordnungen werden wiederum über Address-Translation erzeugt. Dies ermöglicht die nötige Kontrolle über die Zuweisung der Thread-IDs (sind jetzt keine 2D-Koordinaten mit unklarer Zuordnung mehr) für die Nutzung des Local Data Share oder auch den gemeinsamen Registern zwischen verschiedenen Wavefronts. Allerdings geht damit auch mehr Verantwortung auf den Programmierer über, der sich jetzt um das Layout seiner Daten im Speicher selber kümmern muss/kann. Und das ist aufgrund der Knauserigkeit der Hersteller mit genauen Informationen über die Caches oder die Funktionsweise des Memory Tilings manchmal schwierig. ATI gibt selbst ein Beispiel, wie sich durch eine zu naive Umstellung eines einfachen Kernels von Pixel- auf Compute-Shader die Performance mal fast halbieren kann (keine Angst, durch eine angepasste Umsetzung und Ausnutzung der neuen Möglichkeiten kann/wird die Performance steigen). Dies zeigt aber, das man sich durchaus Gedanken über die optimal angepasste Umsetzung machen muss und diese bei verschiedenen Grafikkarten durchaus auch unterschiedlich aussehen kann, selbst wenn z.B. OpenCL eingesetzt wird.

[BREAK=Zusammenfassung und Fazit]

<center><img src="http://www.planet3dnow.de/photoplog/file.php?n=6095&w=o" border="1" alt="GPGPU Computing"></center>

Ich hoffe, die Seiten haben nicht die Geduld so manchen Lesers überstrapaziert. Das Thema des Artikels war vielleicht etwas zu breit angelegt, um es überall knapp und prägnant auf einfache Formeln zu bringen. Aber vielleicht kann ja dieses Fazit noch was rausreißen ;)

Mit den GPUs hat sich in den letzten Jahren eine Klasse von Hardware entwickelt, die eine extrem hohe Rohperformance zur Verfügung stellen kann. Anders als CPUs versuchen sie nicht, die Ausführung von wenigen Threads zu beschleunigen, sondern den Durchsatz möglichst hoch zu halten. Deswegen werden grundsätzlich andere Konzepte verfolgt, um die Performance zu steigern. GPUs setzen auf eine parallele Verarbeitung möglichst vieler Daten. Dazu kommen eine Vielzahl an Techniken zum Einsatz (SIMD, VLIW, Multithreading), die darauf ausgerichtet sind, mit möglichst wenig Verwaltungsaufwand möglichst viel zu rechnen und somit auch mehr Transistoren in Ausführungseinheiten statt in das Drumherum investieren zu können. Das Resultat ist eine allgemein gut 10 mal höhere Rohleistung als CPUs, die allerdings eingeschränkter nutzbar ist. Längst nicht immer begrenzt die verfügbare Rechenleistung die Geschwindigkeit.

Dieser Ansatz ist für Grafikrendering und auch einfache GPGPU-Aufgaben gut geeignet. Dazu kommt ein etwas anderes aber ebenfalls recht einfaches Programmiermodell als von der CPU bekannt zum Einsatz. Kompliziertere Probleme oder auch neue ausgefeilte Renderingmethoden erfordern allerdings eine immer flexiblere Programmierung der GPUs. Die Grafikhersteller versuchen dieser Entwicklung mit neuen GPUs und komplexeren Softwareschnittstellen gerecht zu werden.

Anfang nächsten Jahres wird mit Intels Larrabee ein neuer Konkurrent in den Markt einsteigen, der gerade dazu bestimmt ist, die Flexibilität bei der Programmierung neu zu definieren. Anders als die GPUs trägt Larrabee eindeutig die Gene einer normalen CPU in sich (z.B. kohärente Schreib-Lese-Caches). Zu den auf Durchsatz optimierten (Multithreading) und entsprechend vereinfachten in-order Kernen gesellt sich entsprechend den Anforderungen jeweils eine breite SIMD-Einheit, die allerdings wie auf CPUs organisiert ist (einfaches und sehr schnelles horizontales Data Sharing). Außerdem gestaltet Intel die Programmierung deutlich CPU-ähnlicher. Der Preis dafür ist ein höherer Aufwand für diese Features und Möglichkeiten. So wird Larrabee sicher kein Leichtgewicht was Transistorzahl und Die-Fläche angeht. Die angestrebte Kernanzahl wird wohl erst in 32 nm möglich werden. Hier kann Intel allerdings gegebenenfalls ihren Vorsprung bei der Fertigungstechnik in die Wagschale werfen. Bei der theoretischen Performance/Transistor und auch bei herkömmlicher Spielegrafik wird sich Larrabee voraussichtlich den vorher vorgestellten RV870 von ATI und dem GT300 von NVIDIA geschlagen geben müssen. Trotzdem ist es sehr wahrscheinlich, dass einige/viele kompliziertere Algorithmen sehr gut auf Larrabee laufen werden und er so auf dem Feld des GPGPU-Computing neue Maßstäbe setzen kann. Hier wird man sehen müssen, welche Konzepte die beiden großen etablierten Anbieter diskreter GPUs dagegensetzen werden.

 
Zurück
Oben Unten