Grafikkarten können nicht nur bunte Bildchen malen: Beim parallelen Verarbeiten großer Datenmengen laufen die GPUs den CPUs den Rang ab. Dabei dient OpenCL unabhängig von Hardware und Hersteller als Programmierplattform.

In den Top 500 des Supercomputing [1] finden sich immer mehr Hochleistungsrechner, die ihren Spitzenplatz mithilfe von Grafikkarten erkämpften. Das ist eigentlich nicht weiter verwunderlich, übertrifft doch die theoretische Leistungsfähigkeit von Grafikkarten diejenige von CPUs schon seit langem. Wenn GPUs aber schneller als CPUs arbeiten, warum rechnen wir dann nicht alles auf der GPU? Um diese Frage zu beantworten, muss man zunächst einen Blick auf die Architekturen von Grafikkarte und Prozessor werfen.

In aktuellen Rechnern herrschen Quad- und Hexacore-CPUs mit vier respektive sechs Prozessorkernen vor, die parallel unterschiedliche Aufgaben erledigen können. Während etwa Core 1 gerade auf den Hauptspeicher zugreift, addiert Core 2 die Zahlen zweier Register, Core 3 wiederum springt zu einer anderen Instruktion.

GPUs hingegen bestehen aus mehreren dutzend bis mehreren hundert Cores, die sich jedoch nicht so vielfältig einsetzen lassen. So unterliegen die Rechenaufgaben der GPU der sogenannten Datenparallelität (SIMD/SIMT, [2]). Sämtliche gleichzeitig aktiven Cores können nur dieselbe Instruktion ausführen, dies jedoch auf unterschiedlichen Daten. Damit existiert eine grundlegende Einschränkung für GPU-berechenbare Probleme: Sie müssen datenparallelisierbar sein.

Noch vor einigen Jahren waren Grafikkarten konstruktionsbedingt rein der Beschleunigung von Spezialanwendungen vorbehalten. Neben der 2D- und 3D-Beschleunigung waren dies etwa Aufgaben wie Decoding oder Deinterlacing. Um allgemeine, präzise Berechnungen vorzunehmen, musste man tief in die Trickkiste greifen, um auf relativ umständlichem Weg ans Ziel zu kommen.

Wollten Wissenschaftler etwa zwei große Matrizen addieren, so interpretierten sie diese mithilfe von OpenGL als Texturen, ordneten sie hintereinander an und setzten die vordere halb transparent. Das gerenderte Ergebnis, eine Textur, ließ sich als Ergebnismatrix interpretieren. Was bei einer simplen Addition noch recht einfach funktioniert, stößt jedoch schnell an Grenzen, sobald Multiplikationen, Schleifen, Sprünge oder Bedingungen ins Spiel kommen.

Cuda und OpenCL

Anfang 2007 machte Nvidia den ersten Schritt, um ohne die oben genannten Umwege beliebige, datenparallelisierbare Probleme zu lösen. Dazu stellte der Grafikspezialist Programmierern mit Cuda [3] eine entsprechende Schnittstelle zur Verfügung. Mit C for Cuda lassen sich die bereitgestellten Funktionen bequem ansprechen. Allerdings arbeitet Cuda nur auf Grafikkarten von Nvidia und benötigt zudem den speziellen Compiler NVCC, was das Einbetten in bestehende Projekte (etwa mit GCC) erschwert.

Diese Probleme bewogen Apple dazu, die Initiative zu ergreifen und zusammen mit AMD, IBM und Nvidia bei der Khronos Group, die auch die OpenGL-Spezifikation vorantreibt, eine alternative Spezifikation für einen plattformübergreifenden Standard einzureichen. Das Resultat, die Open Computing Language 1.0 (OpenCL), wurde Ende 2008 veröffentlicht [4]. Mit OpenCL lassen sich heterogene, parallele Programme für eine CPU, GPU oder einen DSP erstellen. Damit ermöglicht die Spezifikation, allgemeine Berechnungen auf der GPU auszuführen, unabhängig von Plattform und Hersteller. Da der offene Standard zudem auf ISO C99 aufsetzt, fällt jedem Programmierer zumindest syntaktisch der Einsatz von OpenCL leicht.

Systemvoraussetzungen

Durch den offenen Standard eröffnen sich die Möglichkeiten von OpenCL einem recht weitgefächerten Publikum; praktisch jeder aktuelle Rechner erfüllt die notwendigen Voraussetzungen. Grob gesprochen liegt die Grenze des Erscheinungsjahres zwischen den unterstützten und nicht unterstützten Grafikkarten bei 2007/2008. Implementierungen von OpenCL gibt es unter anderem für Linux, Mac OS X ab 10.6 und Microsoft Windows ab XP SP2 (64 Bit) / SP3 (32Bit). Als Compiler können im Prinzip beliebige C-Compiler dienen, unter anderem GCC ab 4.1, ICC ab 11.x oder MSVS 2008/2010.

Bei AMD/ATI unterstützen alle Radeon-HD-Modelle ab der 5000er-Reihe (auch die Mobility-Varianten) sowie einige FirePro-Modelle den Einsatz von OpenCL. Lediglich Beta-Level-Support genießt die 4000er-Serie, wo ungenauere Fließkommaberechnungen oder Instabilitäten auftreten können. Naturgemäß ideal für OpenCL eignen sich die sogenannten GPU Compute Accelerators der Firestream-Reihe. Eine genaue Liste der unterstützten Boards finden Sie auf der AMD-Website [5].

Nvidia gibt als unterstützte Grafikkarten die GeForce-Reihen 8, 9, 100, 200, 400 und 500 an, die dazu mit mindestens 256 MByte Grafikspeicher aufwarten müssen. Daneben kommen auch einige Quadro- und NVS-Modelle sowie die in Netbooks und Nettops verbaute Systemplattform Ion (Intel Atom plus Nvidia Geforce) mit OpenCL zurecht. Daneben gibt es auch von Nvidia spezielle High-Performance-Computing-Modelle ohne Videoausgang, die auf den Namen Tesla hören. Die komplette Liste hält Nvidia auf seiner Website vor [6]. Auch die neuen Sandy-Bridge-Prozessoren von Intel mit eingebauter GPU lassen sich mit OpenCL nutzen.

AMD unterstützt offiziell das Ausführen von OpenCL auf AMD-x86-Prozessoren ab SSE 2.x; inoffiziell lassen sich jedoch auch CPUs anderer Hersteller verwenden. So kann man für erste Experimente auch ohne unterstützte Grafikkarte OpenCL auf der CPU ausprobieren und gegebenenfalls erst später auf einer geeigneten Grafikkarte ausführen. Auch beim Einsatz auf einer CPU erzielt OpenCL bei geeigneter Programmierung eine Beschleunigung, da es die SSE-Register nutzt.

Die hier vorgestellte Liste OpenCL-fähiger Komponenten ist nicht einmal annähernd vollständig: So bieten beispielsweise auch ARM, S3 und Via OpenCL-Implementierungen für ihre Grafikeinheiten an, IBM unterstützt OpenCL auf den Power- und Cell-Prozessoren. Eine Liste voll standardkonformer Produkte führt die Khronos Group [7].

OpenCL installieren

OpenCL an sich ist nur eine Spezifikation – die jeweiligen Hardware-Hersteller müssen dazu konkrete Implementierungen anbieten, die sich geringfügig von einander unterscheiden können. Im Wesentlichen liefern die Hersteller eine Bibliothek und die dazugehörige Headerdatei. Neben der Ur-Spezifikation für C gibt es auch C++-Bindings, die seit OpenCL 1.1 von Haus aus dabei sind. Sie erleichtern den Umgang mit den OpenCL-Datenstrukturen und ermöglichen kompakteren Code.

Als Besitzer einer unterstützten AMD/ATI-Grafikkarte oder zum Nutzen der CPU muss man AMDs Accelerated Parallel Processing SDK installieren (AMD APP SDK, [8]). Nach dem Herunterladen und Entpacken kann man sich an der beigelegten Anleitung entlanghangeln. Im Wesentlichen gilt es dabei die Pfadvariable $LD_LIBRARY_PATH um den Pfad zur Bibliothek libOpenCL.so zu erweitern. Im AMD-Forum stellt ein Benutzer auch freundlicherweise ein DEB-Paket zur Verfügung, das die Library und die Headerfiles automatisch in die dafür vorgesehenen Systemordner installiert [9] und so das Modifizieren von $LD_LIBRARY_PATH überflüssig macht.

Für Besitzer von Nvidia-Grafikkarten steht der Download des Cuda-Toolkits an [10]. Nach dem Herunterladen und Entpacken der Datei installiert man das Toolkit mit Root-Rechten. Der Standardpfad für die Headerdatei cl.h lautet /usr/local/cuda/include, derjenige für die Library /usr/local/cuda/lib beziehungsweise /usr/local/cuda/lib64 für 64-Bit-Systeme. Um den Library-Pfad dem Linker bekannt zu machen, ergänzen Sie $LD_LIBRARY_PATH entsprechend.

Allerdings enthält das derzeit noch aktuelle Toolkit 3.2 (der Nachfolger 4.0 befindet sich im RC-Status) nur OpenCL-1.0-Libraries ohne die bereits erwähnten C++-Bindings. Es stehen jedoch Entwickler-Treiber zum Download bereit [11], die OpenCL 1.1 zur Verfügung stellen. Als Zwischenlösung laden Sie die C++-Binding-Headerdatei cl.hpp von der Khronos-Group-Website herunter [12] und kopieren diese in den systemweiten Include-Ordner /usr/local/include/CL/.

Los geht’s!

Im Folgenden zeigen wir anhand eines einfachen Beispiels, wie Sie mit wenigen Schritten ein parallelisierbares Problem mittels OpenCL auf der Grafikkarte lösen. Als Ausgangspunkt dient dabei eine Implementierung in C++, die ein Graustufenbild mit einem Kernel faltet [13]. Als entsprechende Anwendungsfelder im Bereich der Bildverarbeitung kommen beispielsweise Gaußscher Weichzeichner, Schärfen, Bewegungsunschärfe oder Gradientenberechnung in Frage. Dabei wird eine kleine Matrix (der Kernel) über jede Position des Bildes geführt. Für jede dieser Positionen dient der Kernel als Gewichtsmatrix. Abbildung 1 diente als Input, einige Beispiele von angewendeten Faltungskerneln sehen Sie in Abbildung 2 bis 9.

Abbildung 1: Das Eingabebild: Larry Ewings Tux.

Abbildung 2: Tux’ Gradienten, gefaltet mit einem Sobel-Kernel.

Abbildung 3: Tux gefaltet mit einem Gauß-Kernel (5×5).

Abbildung 4: Tux gefaltet mit einem Gauß-Kernel (12×12).

Abbildung 5: Tux gefaltet mit einem Mittelwert-Kernel (3×3).

Abbildung 6: Tux gefaltet mit einem Mittelwert-Kernel (5×5).

Abbildung 7: Tux gefaltet mit einem Emboss-Kernel.

Abbildung 8: Tux geschärft.

Abbildung 9: Tux bewegt mit einem Motion-Blur-Kernel.

Die Implementierung

Das Graustufenbild speichern wir in einer simplen Struktur, die Höhe, Breite und Daten in Form eines uchar-Arrays speichert (Listing 1, Zeile 1 ff.): Im data-Feld sind dabei die Datenwerte der Zeilen konkateniert. Das Bild:

A B C
D E F

wäre somit repräsentiert als width = 3, height = 2, data = {A, B, C, D, E, F}. Der Faltungskernel ist analog aufgebaut, nutzt jedoch float anstelle von uchar, wie in Zeile 10 des Listings zu sehen. Die eigentliche Faltung (“convolution”) lässt sich mit recht wenig Code darstellen und erfolgt in Listing 1 ab Zeile 19.

Dabei fällt sofort auf, dass die Faltung vier verschachtelte For-Schleifen aufweist. Die äußeren beiden Schleifen in den Zeilen 25 und 26 iterieren über alle Pixel des Zielbildes. Die inneren beiden Schleifen in Zeile 29 und 30 iterieren über alle Positionen des Kernels und gewichten die Pixel des Eingabebildes mit dessen Werten. Diese gewichteten Werte werden aufaddiert und in das Pixel (x, y) des Ausgabebildes geschrieben (Zeile 36, 39).

In unserem Fall weist das Ausgabebild eine um kernel.width - 1 geringere Breite und eine um kernel.height - 1 geringere Höhe als das Eingabebild auf. Um die Größe des Eingabebildes beizubehalten, müsste man die äußeren Pixel des Eingabebildes nach außen vergrößern, was uns jedoch zusätzliche Randfälle bescheren und die Übersichtlichkeit vermindern würde.

Die Methode clampuchar(int value) (Zeile 14) sorgt dafür, dass Werte, die außerhalb des Definitionsbereichs von uchar liegen ({0, …, 255}) keinen Under- respektive Overflow erzeugen, sondern auf die Extrema (0, 255) abgebildet werden.

typedef struct {
 uint width;
 uint height;
 uchar *data;
} grayImage;
typedef struct {
 uint width;
 uint height;
 float *data;
} convolutionKernel;
// Clamp value to limits of uchar.
uchar clampuchar(int value) {
 return (uchar) std::min((int) std::numeric_limits<uchar>::max(), std::max(value, (int) std::numeric_limits<uchar>::min()));
}
// Convolve a grayscale image with a convolution kernel on the CPU.
grayImage convolve(grayImage in, convolutionKernel kernel) {
 grayImage out;
 out.width = in.width - (kernel.width - 1);
 out.height = in.height - (kernel.height - 1);
 out.data = new uchar[out.height * out.width];
 // Iterate over all pixels of the output image
 for(size_t y = 0; y < out.height; ++y) {
  for(size_t x = 0; x < out.width; ++x) {
   float convolutionSum = 0.0f;
   // Iterate over convolution kernel
   for(size_t ky = 0; ky < kernel.height; ++ky) {
    for(size_t kx = 0; kx < kernel.width; ++kx) {
     // Add weighted value to convolution sum
     convolutionSum += in.data[(y + ky) * in.width + (x + kx)] * kernel.data[ky * kernel.width + kx];
    }
   }
   // Clamp values to {0, ..., 255} and store them
   out.data[y * out.width + x] = clampuchar((int) convolutionSum);
  }
 }
 return out;
}

Eingangs des Artikels war von Datenparallelisierbarkeit die Rede. An der Struktur unserer Faltung erkennen wir, dass wir für jedes Pixel im Ausgabebild genau dieselben Instruktionen ausführen, jedoch auf benachbarten Daten. Lassen wir stattdessen den Faltungskernel für jedes Pixel des Ausgabebildes parallel ausführen, sieht das in Pseudocode so aus wie in Listing 2. Im Prinzip wurden hier also nur die beiden äußeren Schleifen von Listing 1 durch ein fiktives “tue parallel …” ersetzt.

Tue parallel fuer alle y in {0, ..., out.height - 1} und alle x in {0, ..., out.width - 1}
{
 float convolutionSum = 0.0f;
 // Iterate over convolution kernel
 for(size_t ky = 0; ky < kernel.height; ++ky) {
  for(size_t kx = 0; kx < kernel.width; ++kx) {
   // Add weighted value to convolution sum
   convolutionSum += in.data[(y + ky) * in.width + (x + kx)] * kernel.data[ky * kernel.width + kx];
  }
 }
 // Clamp values to {0, ..., 255} and store them
 out.data[y * out.width + x] = clampuchar((int) convolutionSum);
}

Das Rahmenwerk

Erstellt man ein reguläres C++-Programm zum Ausführen auf der CPU, werden alle Daten im Hauptspeicher und den Registern der CPU abgelegt. Um mit der GPU Daten zu verarbeiten, muss man ihr diese zunächst einmal zur Verfügung stellen. Dazu gilt es die zu verarbeitenden Daten vom Hauptspeicher über den Bus in den Grafikspeicher zu kopieren. Das Holen von Ergebnissen geschieht in umgekehrter Richtung.

Die Grafikkarte verarbeitet auf jedem Core einen sogenannten Thread. Diese Threads wiederum führen alle dieselbe Kernelfunktion aus, jedoch mit unterschiedlichem Index pro Thread. Der Kernel in diesem Kontext hat nichts mit dem oben genannten Faltungskernel zu tun: Vielmehr ist hier ein C-Quelltext gemeint, der jedem Thread sagt, was er in Abhängigkeit seines Indexes zu tun hat.

Alle gleichzeitig aktiven Threads führen schließlich zu einem Zeitpunkt genau dieselbe Instruktion aus. Je nach Problemgröße gibt man die benötigte Anzahl an Threads (hier: Pixelanzahl im Ausgabebild) und die Daten (hier: Eingabebild, Ausgabebild, Faltungskernel) an und startet den Kernel.

Ausblick

Dieser Artikel gab einen groben Überblick über den Anwendungsbereich von OpenCL und dessen Installation auf dem Rechner. Die hier vorgestellte CPU-Implementierung eines konkreten Problems bietet die Grundlage für den zweiten Teil dieses Artikels, der in der nächsten Ausgabe erscheint. Dort zeigen wir die konkreten Schritte zur Bildfaltung mittels OpenCL auf der Grafikkarte. Anhand von Laufzeitmessungen für verschiedene Größen von Bild und Faltungskernel werden wir dabei zeigen, unter welchen Umständen sich durch die Arbeit auf der GPU tatsächlich eine merkbare Beschleunigung realisieren lässt.