Lösung von Ein- und Mehrpersonenspielen auf der Grafikkarte mit perfekten Hashfunktionen

Inhaltsverzeichnis

1 Einleitung
1.1 Motivation und Hintergrund
1.2 Aufbau der Arbeit

2 Grundlagen
2.1 Spiele und Spieltheorie
2.2 Theoretische Grundlagen zum Hashing
2.2.1 Vorüberlegungen
2.2.2 Minimale perfekte Hashfunktionen
2.3 GPU-Grundlagen
2.3.1 Entwicklung der Gra kkarten
2.3.2 Architektur moderner Gra kprozessoren TM
2.3.3 NVIDIA CUDA
2.3.4 ATI StreamTM und OpenCL
2.4 Breitensuche mit GPU-Unterstützung

3 Das Einpersonenspiel Englisches Solitär
3.1 Hashfunktion für Spielzustände
3.2 Lösen des Spiels
3.3 Implementierung und Resultate

4 Das Einpersonenspiel Frösche und Kröten
4.1 Hashfunktion für Spielzustände
4.2 Lösen des Spiels
4.3 Implementierung und Resultate

5 Das Zweipersonenspiel Mühle
5.1 Hashfunktion für Spielzustände
5.2 Lösen des Spiels
5.2.1 Bewertung von Spielzuständen
5.2.2 Retrogerade Analyse für Zug- und Sprungphase
5.2.3 Implementierung und Resultate für Zug- und Sprungphase
5.2.4 Klassi zierung von Zuständen der Setzphase
5.2.5 Implementierung und Resultate für die Setzphase
5.3 Ein optimaler Spieler

6 Fazit

Abbildungsverzeichnis

Algorithmenverzeichnis

Literaturverzeichnis

Kapitel 1
Einleitung

In dieser Arbeit wird die Lösung von konkreten kombinatorischen Ein- und Mehrpersonenspielen behandelt. Dabei kommt der Gra kprozessor als Co-Prozessor zum Einsatz, um die Berechnungen zu beschleunigen. Im Rahmen dessen werden Hashfunktionen verwendet, um Spielinformationen e zient zu verwalten.

1.1 Motivation und Hintergrund

Seit wenigen Jahren existiert der Trend, die GPU¹ (Gra kprozessor) nicht mehr ausschlieÿ- lich für die Bilderzeugung und -verarbeitung zu verwenden, sondern auch als Co-Prozessor zur Unterstützung der CPU² (Hauptprozessor). Im Falle eines diesbezüglich geeigneten Gra kprozessors sprechen wir auch von einer GPGPU ( General Purpose Graphics Pro- cessing Unit ).

Dieser Trend lässt sich durch die besondere Entwicklung der GPU in der jüngsten Vergangenheit erklären. Der auf dem Markt für Gra kkarten anhaltend starke Wettbe- werbsdruck der letzten 10 bis 15 Jahre hat dazu geführt, dass sich Gra kprozessoren zu stark parallelisierten Systemen mit mehreren Hundert Prozessorkernen entwickelt haben. Der Grund für diese Entwicklung ist, dass im Rahmen der Bildverarbeitung für viele ver- schiedene Bildpunkte bzw. Texturen oftmals dieselben Arbeiten durchzuführen sind, so dass ein entsprechend parallelisierter Gra kprozessor diese Aufgaben wesentlich schneller durchführen kann, als ein Prozessor, der diese Informationen sequentiell verarbeitet.

Während für CPUs mit zwei, vier oder acht Prozessorkernen der Begri Mehrkern- Prozessoren (Multicore ) verwendet wird, spricht man bei GPUs aufgrund der groÿen Zahl der Recheneinheiten von Vielkern-Prozessoren (Manycore ). Moderne GPUs eignen sich hervorragend für die Anwendung des Paradigmas der parallelen Programmierung.

Um die Parallelität der GPUs anderweitig nutzen zu können als nur zur Bildverarbeitung und -erzeugung, sind neue APIs 3 (Programmierschnittstellen) entstanden, wie z. B. CUDA ( Compute Uni ed Device Architecture ) von dem Gra kkartenhersteller NVIDIA, Stream von der Firma ATI oder OpenCL.

In Forschung und Industrie werden ständig weitere bezüglich Parallelisierbarkeit viel- versprechende Algorithmen auf die GPU portiert. Dies führt im Allgemeinen zu einer Be- schleunigung der entsprechenden Algorithmen, was zahlreiche Verö entlichungen zu Pro- blemstellungen aus informationstechnischen Anwendungsgebieten diverser Fachrichtungen belegen, wie z. B. Mathematik (Göddeke et al. [GSMY+08]) oder Medizin (Owens et al. [OLG+07]), in denen entsprechend komplexe Berechnungen mit Hilfe der GPU um ein Vielfaches im Vergleich zur CPU beschleunigt werden konnten. Dabei enthält die Arbeit von Owens et al. [OLG+07] eine Übersicht über eine Auswahl weiterer solcher Arbeiten auch aus dem Kernbereich der Informatik.

Für den Bereich Informatik dient als weiteres Beispiel die Verö entlichung von Bo²na£ki, Edelkamp und Sulewski [BES09], in der es um die Verwendung der GPU zur Beschleunigung der probabilistischen Modellprüfung geht.

Im Bereich der Astronomie wurde mit CUDA eine neue Version der Client-Anwendung seti@home entwickelt, die die Beteiligung an der Suche nach Regelmäÿigkeiten in kosmi- schen Signalen auf einem Client-Rechner, in Abhängigkeit von der vorliegenden GPU, um einen Faktor von bis zu 10 beschleunigen kann. Für weitere Details sei auf folgende Inter- netadressen verwiesen:

http://setiathome.berkeley.edu/

http://boinc.berkeley.edu/cuda.php

Wie bereits erwähnt, werden in dieser Arbeit kombinatorische Ein- und Mehrperso- nenspiele unter Verwendung der GPU gelöst. Das Lösen von Spielen ist für die Informatik interessant, weil sich häu g Problemstellungen z. B. aus dem Bereich der verteilten Syste- me oder aber aus der Wirtschaft als Spiele modellieren lassen. Hierbei wird versucht, aus Zusammenhängen im Spielmodell Erkenntnisse für die ursprüngliche Problemstellung zu gewinnen.

Zunächst einmal ist zu klären, was unter Lösen zu verstehen ist. Bei einem Brettspiel mit Figuren, die auf verschiedenen Positionen stehen können, stellt u. a. die Anzahl der Figuren und deren Positionen zu einem Zeitpunkt einen Spielzustand4 dar. Die Lösung des Spiels besteht im Rahmen dieser Arbeit darin, den zugehörigen Zustandsgraphen mit einer Breitensuche (BFS 5) von ausgewählten Initialzuständen aus zu analysieren. Dabei wir bei den Einpersonenspielen ermittelt, wie viele verschiedene Zustände überhaupt er- reichbar sind und wie viele von diesen auf einem Pfad zum Spielgewinn liegen, so dass ein entsprechender Pfad (z. B. eine Folge von Spielzügen) konstruiert werden kann. Beim Zweipersonenspiel werden sämtliche Spielsituationen klassi ziert, so dass ein entsprechen- der Algorithmus in der Lage ist, das Spiel mit diesen Informationen optimal zu spielen. In diesem Zusammenhang kommen Hashfunktionen zum Einsatz, um Bitvektoren für die Zustandsraumsuche verwenden und Spielzustandsinformationen speichere zient mit der GPU austauschen zu können.

Moderne GPUs sind also stark parallelisierte Systeme. Das Lösen von Spielen ist für die Informatik interessant, wobei Breitensuchen im Spielzustandsraum eine Rolle spielen, und da im Rahmen einer Breitensuche für mehrere voneinander unabhängige Knoten Nachfolger gesucht werden, ist diese für eine Parallelisierung unter Verwendung der GPU geeignet.

1.2 Aufbau der Arbeit

Kapitel 2 gewährt dem Leser zu Anfang einen Einblick in Spiele und Spieltheorie. Im Anschluss werden die theoretischen Grundlagen für diese Arbeit bezüglich Hashing behandelt, denn entsprechend geeignete Hashfunktionen ermöglichen eine e ziente Verwaltung benötigter Spielinformationen und deren e ziente Übertragung zwischen Arbeitsspeicher (RAM⁶ ) und Gra kspeicher (VRAM⁷ ).

Danach folgt ein Überblick über die Entwicklung der Gra kkarten, woraufhin die Architektur moderner GPUs und die technischen Grundlagen vermittelt werden, um die einleitend angedeuteten Vorzüge und die Eignung der GPU als Co-Prozessor besser nachvollziehen zu können. Zusätzlich wird CUDA von der Firma NVIDIA mit seinen elementaren Konzepten vorgestellt und es wird kurz begründet, warum CUDA als API für die GPU im Rahmen dieser Arbeit den Vorzug vor Stream oder OpenCL erhalten hat. Im Anschluss wird die Breitensuche unter Verwendung der GPU erläutert.

Kapitel 3, 4 und 5 befassen sich mit der Lösung von konkreten kombinatorischen Ein- und Mehrpersonenspielen auf der GPU mit perfekten Hashfunktionen. Bei den ersten bei- den Spielen handelt es sich um Halma-Varianten für das Einpersonenspiel. Zum Lösen dieser Spiele werden Hashfunktionen verwendet, die sich der Binomialkoe zienten bedie- nen, eine im Rahmen dieser Arbeit entstandene und umgesetzte Idee. Beim dritten Spiel handelt es sich um ein bekanntes Zweipersonenspiel. Hier reichen die vorher verwendeten Hashfunktionen mit Binomialkoe zienten nicht aus, so dass wir für unsere Zwecke auf deren Verallgemeinerung, die Multinomialkoe zienten, zurückgreifen.

Anschlieÿend folgt in Kapitel 6 ein Fazit zu den Ergebnissen dieser Arbeit und eine Übersicht weiterer für dieses Thema interessanter Arbeiten.

Kapitel 2
Grundlagen

Dieses Kapitel vermittelt die Grundlagen, die für das Verständnis des im Rahmen die- ser Arbeit umgesetzten, e zienten Lösens von konkreten Spielen auf der GPU notwendig sind. Zur Motivation werden zunächst Spiele und die damit verbundene Spieltheorie kurz beleuchtet. Danach werden minimale perfekte Hashfunktionen vorgestellt, die im Rahmen dieser Arbeit zum Einsatz kommen. Anschlieÿend erfolgt ein kurzer Exkurs in die Entwick- lung der Gra kkarten und eine Einführung in die Architektur moderner Gra kprozessoren. Auÿerdem werden die in dieser Arbeit verwendeten Konzepte von CUDA vermittelt, wor- aufhin zum Abschluss des Kapitels das Schema der Breitensuche unter Verwendung der GPU vorgestellt wird.

2.1 Spiele und Spieltheorie

Die Beschäftigung mit Spielen liegt darin begründet, dass viele reale Problemstellungen als Spiel modelliert werden können. Die Lösung des entsprechenden Spiels oder aus dem Spiel erkannte Zusammenhänge liefern dann für gewöhnlich auch Erkenntnisse für das ursprüngliche Problem, aus dem diese kaum oder nur schwer zu ermitteln sind.

Die Modellierung von Spielen zu gegebenen Problemstellungen mit anschlieÿender Ana- lyse des entstandenen Spiels hat Mitte des 20. Jahrhunderts zu einer neuen wissenschaft- lichen Disziplin geführt, der Spieltheorie. Dazu haben besonders von Neumann [Neu28], Morgenstern und von Neumann [MN44] und Nash [Nas50] beigetragen. Eine allgemeine Einführung in die Spieltheorie gibt z. B. Osborne [Osb03], allerdings mit einer wirtschafts- wissenschaftlichen Sichtweise. Die Anfänge dieser Art der Modellierung reichen noch weiter zurück, nämlich bis ins mittlere 19. Jahrhundert, als Antoine Augustin Cournot 1838 im Rahmen seiner Arbeit [Cou38, Cou24] aus der Beschäftigung mit Bedingungen für Mono- und Duopole sowie perfekten Wettbewerb eine entsprechende Spielmodellierung ableitete.

Wie das Beispiel vermuten lässt, sind die Anfänge der Spieltheorie tatsächlich sehr stark mit den Wirtschaftswissenschaften verknüpft. So stellten die ersten Spielmodellierungen sehr spezi sche Marktteilnehmerinteraktionen dar, die noch keinen besonderen theoretischen Wert hatten. Doch im Laufe der Zeit wurden die Fragestellungen immer allgemeiner, wodurch die neu entstehende Wissenschaft zunehmend auch für Mathematiker und Informatiker interessant wurde.

Unter Verwendung von in der Spieltheorie existierenden Konzepten können aber auch in der Informatik u.a. verteilte Systeme formal analysiert werden. Ein Beispiel einer solchen Arbeit gibt Sandholm [San99], der sich mit Multiagentensystemen auseinandergesetzt hat.

Die vorliegende Arbeit befasst sich allerdings nicht mit der Spieletheorie an sich, sondern mit der Beschleunigung des Lösens von Spielen durch Verwendung des Gra kprozessors, ohne dabei eine konkrete Problemstellung aus einem anderen Anwendungsbereich, als Spiel modelliert, zu betrachten. Die hier vorgestellte Methodik kann dann auf ähnliche Spiele übertragen werden und ist dadurch allgemein motiviert.

2.2 Theoretische Grundlagen zum Hashing

Hashfunktionen sind ein wichtiges Werkzeug für die Lösung der in dieser Arbeit behandelten Spiele. Dabei müssen diese bestimmte Eigenschaften besitzen, die in diesem Abschnitt vorgestellt und erläutert werden.

2.2.1 Vorüberlegungen

Wie in der Einleitung angedeutet, handelt es sich bei den kombinatorischen Spielen in dieser Diplomarbeit um Brettspiele. Dabei ergeben Anzahl und Stellung der Spielsteine (bzw. Spiel guren) zu einem Zeitpunkt einen Spielzustand. Diesen Zustand kann man für die Verarbeitung mit Rechnern trivialerweise in Datenfeldern darstellen, so dass jedes Element des Datenfelds genau einer diskreten Position auf dem Spielfeld entspricht und Auskunft darüber gibt, was für eine Art Spielstein sich auf der betre enden Position be ndet oder ob die Position gegebenenfalls leer steht.

Beispielsweise gibt es in den im Rahmen dieser Arbeit behandelten Einpersonenspielen mehrere Milliarden denkbare Spielzustände, in Frösche und Kröten sind es über 4,8 Milliarden. Bedenkt man die Gröÿe des zugehörigen Spielzustandsraums, ist die Verwaltung der einzelnen Zustände in solch expliziter Form mit enormen Ressourcen verknüpft. Als Alternative zur expliziten Darstellung werden Hashfunktionen verwendet, die einem konkreten Spielzustand einen eindeutigen Zahlenwert zuweisen. Knuth [Knu98, S. 513 .] gibt eine generelle Einführung zu Hashfunktionen und Hashing.

Der Bedarf an Speicher für die Kodierung eines Spielzustands wird durch den Hash- wert verringert. Schlieÿlich belegt ein einziger groÿer Ganzzahlwert in den meisten Fällen1 ^[1]

2.2. THEORETISCHE GRUNDLAGEN ZUM HASHING 7

weitaus weniger Speicher als ein Datenfeld mit vielen, wenn auch kleinen, Ganzzahlwerten. Für die Bearbeitung eines Zustands eignet sich allerdings die explizite Form besser. Zur Konvertierbarkeit zwischen den Darstellungen je nach Bedarf ist zu gewährleisten, dass aus einem Hashwert wieder die Kodierung des entsprechenden Spielzustands als Da-tenfeld rekonstruiert werden kann.

Eigentliches Ziel der Verwendung von entsprechenden Hashwerten ist jedoch die Nut- zung eines Bitvektors, um Informationen zum gesamten Spielzustandsraum speicheref - zient zu verwalten. Wenn ein gegebenes Spiel höchstens m Spielzustände annehmen kann und eine entsprechende Hashfunktion existiert, die Spielzustände eindeutig auf Zahlen des Intervalls [0, . . . , m − 1] abbildet, nutzen wir einen Bitvektor mit einer Länge in O(m). Die- ser beinhaltet die Informationen zum gesamten Spielzustandsraum, wobei die zugehörigen Bits eines Spielzustands direkt durch seinen Hashwert adressiert werden.

Die angestellten natürlichsprachlichen Überlegungen bezüglich der gewünschten Eigenschaften für Hashfunktionen sollen nun schrittweise formalisiert werden.

2.2.2 Minimale perfekte Hashfunktionen

Wir beginnen mit einer grundlegenden De nition.

2.2.1 De nition (Hashfunktion). Eine Hashfunktion ist eine Abbildung h eines Uni- versums U auf eine Schlüsselmenge {0, . . . , m − 1}, in der typischerweise |U | ≥ m gilt.

Aus der Menge der denkbaren Spielzustände sind oft viele vom Anfangsspielzustand aus nicht erreichbar. Für unsere Zwecke ist daher eine möglichst kleine Menge S ⊆ U interessant, die dennoch alle erreichbaren Spielzustände enthält.

Bereits gefordert wurde, dass die gewünschten Hashfunktionen eindeutig sein müssen.

2.2.2 De nition (Perfekte Hashfunktion). Eine Hashfunktion h : S −→ K heiÿt per- fekt, wenn sie injektiv ist, wobei die Wertemenge K zumeist eine Menge von Ganzzahlen ist.

Auÿerdem benötigen wir für die De nition minimaler perfekter Hashfunktionen noch folgende De nition zur Platze zienz von Hashfunktionen.

2.2.3 De nition (Platze zienz von Hashfunktionen). Die Platze zienz einer Hashfunktion h : S −→ {0, . . . , m − 1} entspricht dem Verhältnis zwischen Menge der Schlüssel und Menge der Daten, also dem Grad m/|S|.

Injektivität hatten wir bereits für unsere Zwecke als erforderlich herausgestellt. Damit die Hashfunktion nun auch platzoptimal ist, sollte diese auch surjektiv sein, also insgesamt bijektiv.

Tabelle 2.1: Übersicht der Gra kstandards von 1981 bis 1987 (Quelle: Eickmann [Eic07]).

Abbildung in dieser Leseprobe nicht enthalten

2.2.4 De nition (Minimale perfekte Hashfunktion). Eine perfekte Hashfunktion h heiÿt minimal, wenn der Grad ihrer Platze zienz 1 beträgt. In dem Fall gilt also |S| = m.

Die Umkehrung einer perfekten Hashfunktion ergibt eine eindeutige Abbildung. Damit eine entsprechende Hashfunktion im Rahmen dieser Arbeit verwendet werden kann, muss deren Umkehrung bestimmbar sein und eine e ziente Rekonstruktion eines Spielzustands über seinen zugehörigen Hashwert ermöglichen.

2.3 GPU-Grundlagen

Dieser Abschnitt gibt einen Einblick in das Thema Gra kkarten, wobei der Gra kprozessor im Fokus steht. Auch die bereits erwähnten APIs für GPU-Programme werden in Grundzügen vorgestellt, wobei nur auf CUDA näher eingegangen wird.

2.3.1 Entwicklung der Gra kkarten

Vor Ende der 1970er Jahre hatten Rechnersysteme lediglich Text darzustellen, wofür einige wenige auf dem Mainboard integrierte Komponenten zuständig waren. Es war also noch keine Gra kkarte im Sinne eines gröÿeren eigenständigen Subsystems mit eigenem Speicher vorhanden. Erst in den frühen 1980er Jahren ng der Hersteller IBM an, entsprechende Systeme zu entwickeln und auf dem Markt anzubieten.

Die in den Folgejahren verbreiteten Standards sind in Tabelle 2.1 aufgelistet. Bei der Au ösung des MGA-Standards handelt es sich dabei nicht um Bildpunkte, sondern um feste Blöcke in denen jeweils ein Zeichen aus dem ASCII-Zeichensatz dargestellt werden konnte. Der einzige Standard, der in der Tabelle nicht von IBM stammt, ist der HGC-Standard ( Hercules Graphics Card ). Für dessen 3 Farben waren allerdings spezielle Monitore not- wendig.

1987 brachten verschiedene Hersteller unterschiedliche Gra klösungen heraus, die zu- meist unter dem Kürzel SVGA ( Super Video Graphics Array ) vermarktet wurden. Die Hersteller konnten sich lange Zeit nicht auf einen gemeinsamen Standard einigen, so dass sich 1989 ein Kommitee gründen musste, das diese Aufgabe übernahm. Mit SVGA und mehr Gra kspeicher waren nun, angefangen mit 800×600 Bildpunkten, höhere Au ösun- gen und mehr Farben möglich.

Im weiteren Verlauf erlaubte einfach ein ständiges Mehr an Gra kspeicher höhere Auflösungen mit mehr Farben. Die entsprechenden Standards heiÿen chronologisch sortiert XVGA, UVGA, SXGA und UXGA (siehe Eickmann [Eic07]).

Ab 1994 wurden Chips auf Gra kkarten verbaut, die als Gra kbeschleuniger dienen sollten. Bis dahin wurde das Bild immer vollständig von der CPU berechnet und über die Gra kkarte ausgegeben. In den folgenden Jahren sollte die CPU immer mehr Aufgaben der Bildverarbeitung an den Gra kbeschleuniger abtreten. Die Anforderungen an die Gra kkarten stiegen stark an, vor allem mit Beginn des 3D-Zeitalters in der Computergra k, so dass die Gra kbeschleuniger bezüglich ihrer Architektur immer mehr auf die Bildverarbeitung und -erzeugung angepasst wurden.

1999 brachte NVIDIA eine GPU auf den Markt, die in der Lage war, Gra kdaten einer virtuellen Welt eigenständig in 2D-Darstellung umzurechnen. Desweiteren konnte diese auch Veränderungen der Position oder der Ausrichtung des Betrachters innerhalb der virtuellen Welt, sowie Beleuchtung der einzelnen Bildpunkte gemäÿ eines vorzugebenden Beleuchtungsmodells selbständig berechnen. Weitere Informationenen nden sich auf den Herstellerseiten:

http://www.nvidia.com/object/gpu.html

Im Prinzip entwickelte sich die GPU im weiteren Verlauf von Jahr zu Jahr derart, dass immer mehr Funktionen und Transformationen aus der Bildverarbeitung und -erzeugung direkt unterstützt und dadurch e zienter berechenbar wurden. Da wir uns in dieser Ar- beit nicht mit Bildverarbeitung und -erzeugung beschäftigen, wird hier auf eine detaillierte Entwicklung der unterstützten Gra kfunktionen verzichtet. In diesem Zusammenhang sind aber entsprechende APIs für Gra kfunktionen zu erwähnen, z. B. OpenGL, die Gra kbe- fehle bei geeigneter GPU direkt von dieser ausführen lassen. Weitere Informationen zu OpenGL nden sich unter:

http://www.opengl.org/

Die beschriebene Entwicklung führte dazu, dass der Gra kprozessor zu einem stark parallelisierten System wurde, der bei entsprechenden Problemstellungen eine höhere Be- rechnungskraft hat, als eine CPU mit zwei oder mehr Prozessorkernen. Aus diesem Grund folgten 2002 und 2003 erste Überlegungen, ob sich der Gra kprozessor auch über Gra-

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Schematischer Aufbau eines TPC ( Thread Processing Cluster )

k hinaus verwenden lieÿe, wie z. B. damals von David Kirk2 gegenüber ExtremeTech im Rahmen eines Interviews3 geäuÿert.

Wir halten fest, dass eine Gra kkarte heutzutage im Wesentlichen einen Gra kbeschleuniger (GPU) und Gra kspeicher beinhaltet, der ausschlieÿlich der GPU zur Verfügung steht. Diese Beschreibung schlieÿt auch Onboard-Gra kkarten mit ein.

2.3.2 Architektur moderner Gra kprozessoren

Die GPU, die auf der im Rahmen dieser Arbeit genutzten Gra kkarte GTX 285 der Firma NVIDIA verbaut ist, beinhaltet 240 Prozessorkerne und wird mit GT200 bezeichnet. Wir wollen uns nun näher mit dem Aufbau dieses Gra kprozessors befassen.

Auf der GPU liegt eine SIMD -ähnliche Architektur ( Single Instruction, Multiple Data ) vor. Das heiÿt, die Prozessorkerne führen dieselben Instruktionen aus, arbeiten aber auf unterschiedlichen Daten.

Die 240 Prozessorkerne werden als Streamingprozessoren (SP ) bezeichnet. Sie hängen in speziellen Strukturen mit zusätzlichen Einheiten zusammen. Doch bevor wir auf die zusätzlichen Einheiten zu sprechen kommen, soll zunächst die bloÿe Zusammensetzung dieser Strukturen aus Streamingprozessoren beschrieben werden.

- Ein Streaming-Multiprozessor (SM ) setzt sich aus 8 SPs zusammen.
- Jeweils 3 SMs ergeben eine TPC -Einheit ( Texture/Thread Processing Cluster ).

2.3. GPU-GRUNDLAGEN

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Schema der Transistorenverteilung auf CPU und GPU

Ein TPC beinhaltet also insgesamt 24 SPs. Die genutzte GPU setzt sich demnach bei 240 Streamingprozessoren aus 30 SMs bzw. 10 TPC-Einheiten zusammen. Abbildung 2.1 demonstriert den Aufbau eines solchen TPC.

Nachdem wir nun die Zusammensetzung der erwähnten Strukturen aus Streamingpro- zessoren kennen, sollen nun die zusätzlich vorhandenen Elemente vorgestellt werden.

- Jeder Streamingprozessor besitzt jeweils eine FPU ( Floating Point Unit und zwei ALUs ( Arithmetic Logic Units ).
- Ein Streaming-Multiprozessor beinhaltet neben den Streamingprozessoren noch zwei SFUs ( Special Function Units ) und lokalen gemeinsamen Speicher ( Shared Memo- ry bzw. SRAM ), auf den ausschlieÿlich seine Streamingprozessoren Zugri haben.

ALUs sind Schaltkreise für Arithmetik- und Logikoperationen. FPUs und SFUs sind in erster Linie für das ursprüngliche Aufgabenfeld der Gra kkarte gedacht, also die Bilder- zeugung und -verarbeitung. Durch sie werden Berechnungen auf Gleitkommazahlen stark beschleunigt.

Neben dem gemeinsam genutzten Speicher haben die einzelnen Streamingprozessoren natürlich auch ihre eigenen Register. Dies ermöglicht verschiedenen Prozessen4, die innerhalb eines Streaming-Multiprozessors ausgeführt werden, einerseits, unabhängig voneinander eigene Daten in den entsprechenden Registern zu verwalten, andererseits aber auch, Daten von anderen Threads aus dem SRAM aufzugreifen.

Auÿerdem sind im Vergleich zu einer CPU wesentlich mehr Transistoren der GPU der Datenverarbeitung zugeteilt und nur wenige für Kontroll uss und Zwischenspeicher, siehe auch Abbildung 2.2.

Die Architektur der GPU ist dadurch für sehr berechnungsintensive und stark paralle- lisierbare Aufgabenstellungen besonders gut geeignet, eben die Art von Berechnungen, die

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3: Berechnungskraft bei Gleitkommaoperationen (Quelle: NVIDIA [NVI08a])

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.4: Maximaler Datendurchsatz (Quelle: NVIDIA [NVI08a])

bei der Bilderzeugung und -verarbeitung häu g anfallen. In den Abbildungen 2.3 und 2.4 erhalten wir einen Eindruck von der erreichbaren Berechnungskraft und Speicherbandbreite der GPU im Vergleich zur CPU.

Wie bereits angedeutet, liegt der Speicher auf der Gra kkarte in unterschiedlicher Form und hierarchisch vor.

- Der globale Speicher, auf den alle Streamingprozessoren zugreifen können, ist der Gra k-Hauptspeicher (VRAM). Der Zugri auf diesen durch die GPU ist vergleichs- weise langsam, kann aber durch Coalescing beschleunigt werden. Beim Coalescing werden kleine5 Speicherzugri e auf nebeneinander liegende Speicherzellen zu einem groÿen Zugri kombiniert.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.5: Beispiele möglicher Speicherzugri smuster für Coalescing

- Der lokale gemeinsame Speicher (SRAM) innerhalb eines Streaming-Multiprozessors hat eine Gröÿe von 16 Kilobytes. Der Zugri auf diesen Speicher durch die entspre- chenden Streamingprozessoren gleicht von der Geschwindigkeit her einem Register- zugri , erfolgt also wesentlich schneller als ein Zugri auf den globalen Speicher.
- Jeder Streamingprozessor besitzt auÿerdem noch eigene Speicherregister, auf die aus- schlieÿlich dieser zugreifen kann.

Coalescing kann bei aktuellen NVIDIA-Gra kkarten sogar erfolgen, wenn Threads in einem beliebigen Muster auf verschiedene Adressen innerhalb eines begrenzten Adressbereichs des Speichers zugreifen, wie in Abbildung 2.5 illustriert. Wenn mehrere Threads zu einem Zeitpunkt versuchen, in dieselben Speicherzellen zu schreiben, sprechen wir von nebenläu gem Schreiben ( concurrent writing ). Hierbei kann nicht vorhergesagt werden, in welcher Reihenfolge der Zugri vergeben wird. Laut NVIDIA ist dabei aber zumindest die Gefahr von Deadlocks6 ausgeschlossen.

Da in der vorliegenden Arbeit eine aktuelle Gra kkarte der Firma NVIDIA genutzt wird, betrachten wir nun das Coalescing ebenso aktueller Gra kkarten etwas näher. Der Hersteller spricht hier von Gra kkarten, mit Berechnungskraft (Compute Capability 7) 1.2 oder höher. Dabei werden die verschiedenen, simultanen Speicherzugri e der Threads innerhalb einer Gruppe wie folgt zu einem einzigen Zugri zusammengefasst.

- Zugri e auf 8-Bit groÿe Wörter innerhalb eines 32 Byte groÿen Speicherbereichs.
- Zugri e auf 16-Bit groÿe Wörter innerhalb eines 64 Byte groÿen Speicherbereichs.
- Zugri e auf 32-Bit oder 64-Bit groÿe Wörter innerhalb eines 128 Byte groÿen Speicherbereichs.

Die GPU arbeitet ausschlieÿlich auf Daten, die ihr im VRAM bereitgestellt werden. Diesbezüglich lässt sich bei Gra kkarten der Firma NVIDIA gezielt steuern, ob und welche Daten für den jeweils anstehenden Arbeitsprozess in den lokalen gemeinsamen Speicher kopiert werden sollen. Ein Zugri auf den Hauptspeicher des Computers ist für die GPU nicht möglich.

Diese und weitere Informationen zur Architektur der GPU lassen sich gröÿtenteils im CUDA Programmierhandbuch [NVI08a] nden. Die übrigen Details, die sich speziell auf die im Rahmen dieser Arbeit verwendete Gra kkarte beziehen, stellt der Hersteller auf seinen Internetseiten bereit.

http://www.nvidia.de/object/product_geforce_gtx_285_de.html

2.3.3 NVIDIA CUDATM

Bei CUDA handelt es sich um den Ansatz von NVIDIA, die im vorangegangenen Ab- schnitt erwähnten Möglichkeiten bezüglich paralleler Datenverarbeitung auf der GPU im Rahmen der Anwendungsentwicklung nutzbar zu machen. CUDA wurde von NVIDIA En- de²⁰⁰⁶ angekündigt und erschien kurze Zeit darauf in der Version¹.⁰. Seit Mitte²⁰⁰⁷ sind zahlreiche wissenschaftliche Arbeiten verö entlicht worden, in denen für verschiedene Anwendungsbereiche die Nutzbarkeit der Rechenkraft der GPU mittels CUDA untersucht wurde. Einen kleinen Überblick gibt dazu die Verö entlichung von Owens et al. [OLG+07]. Momentan ist CUDA in der Version 2.3 verfügbar. Weitergehende Details zu CUDA, die über die in diesem Kapitel vorgestellten, grundlegenden Inhalte hinausgehen, können den Herstellerseiten entnommen werden.

http://www.nvidia.de/CUDA/

CUDA setzt auf der Programmiersprache C auf und zielt darauf ab, dem Entwickler bei minimaler Erweiterung des C-Sprachumfangs alle nötigen Mittel zur Verfügung zu stellen, um die GPU entsprechend nutzen zu können. Dadurch wird vor allem C-Entwicklern der Einstieg in CUDA erleichtert.

Im Gegensatz zur Generierung von nebenläu gen Prozessen in gängigen Programmier- sprachen, abstrahiert CUDA die Thread-Generierung insofern, dass sich der Nutzer nicht mehr um die genauen Details der Thread-Initialisierung und deren Verwaltung kümmern muss. Unter anderem ist es dabei nicht notwendig, die genaue Zahl der Prozessorkerne zu kennen. Die gestarteten Threads werden automatisch auf die Streaming-Multiprozessoren verteilt.

Diesbezüglich sei erwähnt, dass NVIDIA auch im Bereich der Bilderzeugung und -ver- arbeitung immer schon über die dafür bereitgestellten APIs von der zugrundeliegenden Architektur abstrahierte, um über diese möglichst wenig Informationen o enlegen zu müs- sen. Entwickler im Gra kbereich verwenden demnach ebenfalls vorde nierte Funktionen, wenn es um NVIDIA Gra kkarten geht.

Das Ganze bringt die Vorteile, dass sich Programmierer im Rahmen der Anwendungsentwicklung nicht unnötig stark mit der konkret vorliegenden Architektur auseinandersetzen müssen, und natürlich, dass die Programme innerhalb der entsprechenden NVIDIAProduktfamilie portierbar bleiben, obwohl sich die Hardware im Gra kkartenbereich immer noch sehr rasant weiterentwickelt. Die Entwicklung von Code zur parallelen Ausführung wird durch diese Umstände insgesamt erleichtert.

CUDA verwendet eine Thread-Hierarchie, wobei Threads in Blöcke (Thread-Block ) und diese wiederum in Grids zusammengefasst werden. Dies hat ausführungstechnische Konsequenzen, die man als Entwickler kennen muss. Die maximale Anzahl von möglichen Threads, sowohl innerhalb eines Thread-Blocks als auch insgesamt, wird nämlich durch die vorliegende Hardware vorgegeben.

Wenn die in einem Programm genutzten Thread-Blöcke maximal 96 Threads beinhal- ten, ist das Programm durchweg portierbar. Aktuelle Gra kkarten von NVIDIA erlauben aber auch eine Thread-Block-Gröÿe von bis zu 512 Threads. Verwendet man bei gegebener aktueller Hardware die maximale Blockgröÿe, schränkt dies zwar einerseits die Portier- barkeit auf ähnlich aktuelle Hardware ein, andererseits wird das Programm dadurch aber auch im Allgemeinen schneller, da Threads nur innerhalb eines Thread-Blocks nebenläu- g zur Ausführung kommen. Die Blöcke an sich werden auf die verfügbaren StreamingMultiprozessoren verteilt und müssen bei entsprechend groÿer Anzahl in Gruppen sequentiell abgearbeitet werden.

Bevor wir uns beispielhaft noch mit einigen bezüglich Parallelität wichtigen Sprachele- menten von CUDA auseinandersetzen, können wir an dieser Stelle schon einmal folgendes zusammenfassend festhalten. Der Programmierer wird durch CUDA in die Lage versetzt, ohne groÿen Aufwand sehr groÿe Mengen von Threads erzeugen zu lassen, die idealerweise in kleinen Gruppen (Thread-Blöcke) auf je einer Teilmenge der gesamten Datenmenge agie- ren. Sinnvollerweise sollte die Aufteilung in Teilmengen so gestaltet sein, dass diese, über die Thread-Blöcke betrachtet, voneinander unabhängig bezüglich der durchzuführenden Berechnungen sind.

Im Kapitel zu Speicherbandbreiten des aktuellen Programmierhandbuchs zu CUDA [NVI08a, S. 52 .] wird die Verwendung des lokalen gemeinsamen Speichers durch die Threads generell empfohlen, selbst dann, wenn die Instruktionenfolge für die Threads kurz ist. Demnach muss die Zugri sgeschwindigkeit auf den lokalen gemeinsamen Speicher so vorteilhaft sein, dass die Zeit für ein vorheriges Kopieren von Daten aus dem globalen Gra kspeicher in jedem Fall in Kauf genommen werden kann.

Im Rahmen der Anwendungsentwicklung mit CUDA ist es also Aufgabe des Program- mierers, eine sinnvolle Partitionierung der zu verarbeitenden Daten zu ermitteln. Diese Aufteilung sollte sich an der Thread-Hierarchie orientieren und Datenpartitionen ergeben, die bezüglich der auszuführenden Berechnungen unabhängig voneinander betrachtet wer- den können. Auf diese Weise kann die Berechnungskraft der GPU besser entfaltet werden. CUDA bietet die Möglichkeit, Threads innerhalb eines Blocks miteinander zu synchro-nisieren. So kann sichergestellt werden, dass alle Threads in einem Block einen bestimmten Punkt in ihrer Instruktionenfolge erreicht haben, bevor einer der Threads weiterarbeiten darf. Beispielsweise wird eine Synchronisierung notwendig, wenn ein Teil der gestarteten Threads Daten in den gemeinsamen Speicher kopieren soll, die von allen Threads für die eigentliche Berechnung benötigt werden.

In diesem Zusammenhang ist darauf hinzuweisen, dass dies eine lokale Synchronisierung darstellt, die innerhalb eines Thread-Blocks erfolgt, nicht darüber hinaus. Ebenso können Threads nicht über Thread-Block-Grenzen hinaus Daten im SRAM für andere Blöcke zur Verfügung stellen.

Die erwähnte Instruktionenfolge für die Threads wird in einem so genannten Kernel niedergeschrieben, einer Prozedur, der ein CUDA Schlüsselwort vorangestellt wird. Der Aufruf eines Kernels unterscheidet sich von einem in C sonst üblichen Prozeduraufruf darin, dass beim Aufruf eines Kernels spezi ziert werden muss, wie viele Threads mit welcher Hierarchie den Kernel ausführen sollen. Die einzelnen Threads können während der Ausführung ihre global eindeutige Thread-ID ermitteln und dann in Abhängigkeit von dieser auf verschiedene Daten zugreifen.

Alle Threads eines Blocks werden gleichzeitig gestartet und in Teilgruppen gleichzeitig bearbeitet, wobei die Gröÿe dieser Teilgruppen von der Anzahl der Prozessorkerne abhängt, die dem Block zur Verfügung stehen.

Über den Sprachumfang von C hinaus bietet CUDA auch zusätzliche, unter anderem mehrdimensionale Datentypen, mit denen entsprechend mehrdimensionale ThreadHierarchien spezi ert werden können.

Für weitergehende Details zu CUDA sei hiermit auf die Arbeiten von Nickolls et al. [NBGS08] und Halfhill [Hal08] verwiesen. Eine umfassende Beschreibung der CUDA API enthalten das CUDA Programmierhandbuch [NVI08a] und die CUDA Referenz [NVI08b] der Firma NVIDIA.

Ein CUDA Beispielprogramm

Abbildung in dieser Leseprobe nicht enthalten

Zusätzlich zu erwähnen ist die Verfügbarkeit von Funktionen cudaMemcpyHostToDevice bzw. cudaMemcpyDeviceToHost, die uns den Transfer groÿer Mengen von Daten vom RAM in den VRAM oder umgekehrt ermöglichen.

Der Kernel des Beispielprogramms führt eine Matrixaddition mit anschlieÿender Multiplikation eines Skalars durch, wobei die einzelnen Matrixelemente parralel verarbeitet werden. CUDA bietet eine Vielzahl von Funktionen, die auf die Eigenschaften von NVIDIA Gra kkarten zugeschnitten sind. Um die Fähigkeiten einer solchen Gra kkarte optimal ausnutzen zu können, ist eine intensive Beschäftigung mit den wichtigsten Funktionen von CUDA und der GPU-Architektur notwendig.

2.3.4 ATI StreamTM und OpenCL

Im folgenden Abschnitt sollen noch zwei weitere APIs für die Umsetzung parallelisierbarer Aufgaben auf der GPU vorgestellt werden. Zumindest OpenCL könnte in Zukunft für Arbeiten in diesem Bereich eine interessante Alternative darstellen.

Stream ist dabei eine entsprechende Plattform, die seitens AMD/ATI entwickelt wurde. ATI war zwar bereits Ende 2006 mit dem Stream Konzept in Erscheinung getreten, aber ein eher mäÿiger Erfolg in der Anfangsphase führte dazu, dass dieses innerhalb des Un- ternehmens nur einen niedrigen Stellenwert erhielt und von daher kaum weiter entwickelt wurde. Erst seit Ende 2008 bemüht sich das Unternehmen stärker um eine Verbesserung des Konzepts, gewissermaÿen als eine Art Reaktion auf die allgemein gute Resonanz auf CUDA, hat es aber in Forschung und Industrie bislang nicht zu einer vergleichbaren Ver- breitung gescha t. Weitere Informationen be nden sich auf den Herstellerseiten. http://www.amd.com/stream/

Im Gegensatz zu CUDA und Stream ist OpenCL ( Open Computing Language ) eine herstellerunabhängige API, die neben GPUs auch noch als parallele Programmierplattform für Multicore-CPUs und DSPs ( Digitial Signal Processors ) dient.

Der OpenCL 1.0 Standard wurde Ende 2008 verö entlicht und setzt wie CUDA auf der Programmiersprache C auf. Ziel von OpenCL ist die Vereinfachung der Anwendung des parallelen Programmierparadigmas auf hierfür geeigneten Prozessoren durch Vereinheitlichung. Die Initiative für die Entwicklung dieser Plattform ging Mitte 2008 von Apple aus und die ersten Arbeiten diesbezüglich sind u. a. direkt in Kooperation mit AMD, Intel und NVIDIA erfolgt, also den für einen Erfolg des Konzepts wichtigen Herstellern von Prozessoren im Computer- und Gra kbereich.

OpenCL wird von einer Vielzahl von Herstellern aus verschiedenen Bereichen unter- stützt, so dass es als Plattform in Zukunft sicherlich weite Verbreitung erlangen dürfte. Weiterführende Informationen sind auf den Seiten der Khronos Group8 verfügbar. http://www.khronos.org/opencl/

Für diese Arbeit hat CUDA den Vorzug gegenüber Stream und OpenCL in erster Linie deswegen erhalten, weil die Hardware, die für diese Arbeit zur Verfügung steht, eine NVIDIA Gra kkarte ist. Ansonsten gibt es keine objektiven Gründe, die die Bevorzugung einer dieser APIs rechtfertigen könnte.

Allerdings scheint der Entwicklerkreis, der CUDA nutzt, gröÿer zu sein, vor allem im wissenschaftlichen Bereich. Es konnten zumindest nur wenige Verö entlichungen ermittelt werden, in denen ATI Stream oder OpenCL Verwendung nden.

2.4 Breitensuche mit GPU-Unterstützung

Dieser Abschnitt beinhaltet, wie die Breitensuche für den endlichen Spielzustandsraum S eines Spiels unter Verwendung der GPU konkret durchgeführt wird. Seien für das Spiel eine (minimale) perfekte Hashfunktion h : S −→ {0, . . . , |S| − 1}, ihre Umkehrfunktion h−¹ und eine Startmenge von Spielzuständen Vstart ∈ S gegeben. Wir lassen dabei vorerst die genaue Art der Verarbeitung von Hashwerten auf der CPU-Seite auÿer Acht.

Spielzustände stehen bezüglich der Spielregeln teilweise in Bezug zueinander. Dabei existiert eine Kante (u, v) im zugehörigen Spielzustandsgraphen GS = (V, E), wenn ein

Algorithmus 2.1 Breitensuche

Abbildung in dieser Leseprobe nicht enthalten

gültiger Spielzug existiert, der das Spiel von Spielzustand u in Spielzustand v überführt. Je nach Spiel ist im Rahmen einer konkreten Implementierung zu berücksichtigen, ob die Kanten gerichtet oder ungerichtet sind.

[...]

---

¹ Akronym zu Graphics Processing Unit .

² Akronym zu Central Processing Unit .

³ Akronym zu Application Programming Interfaces .

In einigen Spielen kann der Zustand noch weitere Faktoren beinhalten, wie z. B. die Historie bei Schach, die dort den Zustandsraum endlich hält.

⁵ Akronym zu Breadth First Search .

⁶ Akronym zu Random-Access Memory .

⁷ Akronym zu Video Random-Access Memory .

¹ In allen Fällen, auÿer bei extrem kleinen Spielfeldern, was bei den Brettspielen in dieser Diplomarbeit nicht der Fall ist.

² Chef-Wissenschaftler bei NVIDIA: http://www.nvidia.com/object/bio_kirk.html ³ http://www.extremetech.com/article2/0,2845,1091392,00.asp

⁴ Prozesse werden auch als Threads bezeichnet.

⁵ Speicherzugri e, die jeweils kleiner als 64 Bit sind.

⁶ Eine Situation, bei der sich alle beteiligten Prozesse wechselseitig blockieren und die Arbeit infolgedessen zum Erliegen kommt.

⁷ Bei NVIDIA entspricht eine Compute Capability 1.x bestimmten Fähigkeiten bzw. Eigenschaften für Gra kkarten.

⁸ Die Khronos Group rati zierte die abschlieÿende Vorlage für OpenCL seitens Apple und der übrigen genannten Hersteller und verabschiedete den OpenCL 1.0 Standard.