Beschleunigen von Java-Programmen per GPU mit CUDA

Reise in Etappen

Jürgen Schuck

Wenn sequenziell ausgeführte Programme lahmen, kann es helfen, sie zu parallelisieren. Es gibt verschiedene Möglichkeiten, die Auswahl richtet sich nach der Programmstruktur. CUDA ist eine vielversprechende Option zur Parallelisierung auf GPUs.

Moderne GPUs (Graphics Processing Unit) sind massiv-parallele Computer, mit denen sich sequenziell arbeitende Programme auf Trab bringen lassen. Ihre Tausenden von Cores eignen sich hervorragend zum Parallelisieren wiederholt ausgeführter Programmabschnitte. Schleifen sind daher ein guter Ansatzpunkt, wenn es darum geht, ein Programm zu beschleunigen. Potenziell beeinträchtigen sie die Performance, lassen sich aber leicht parallelisieren, wobei die Wirkung mit jedem zusätzlichen Core der ausführenden CPU zunimmt. Verwendet man die einigen Tausend Cores moderner GPUs, lässt sich dieser Effekt theoretisch um etliche Größenordnungen steigern.

Allerdings laufen Anwendungen nicht unmittelbar auf einer GPU. Der Grafikkartenhersteller NVIDIA hat dafür mit seiner Compute Unified Device Architecture (CUDA) eine Schnittstelle definiert, die über eine API in C programmiert wird. Für Java-Anwendungen benötigt man das Java Native Interface (JNI). Es ist also eine Reihe technischer Hürden zu nehmen, um Java mittels CUDA zu parallelisieren. Hinzu kommt, dass langjährige Java-Entwickler sich mit neuen Konzepten sowie mit C/C++ und seinen Werkzeugen beschäftigen müssen, die sie meist nicht vermissen. Mit einem methodischen Vorgehen in überschaubaren Schritten können sie die angeführten Schwierigkeiten jedoch bewältigen.

Die hier vorgestellte Methode entstand zur Parallelisierung eines Java-Programms, dessen Ausführungsgeschwindigkeit durch eine neue Klasse stark gesunken war. Eine Schleife mit mehreren Millionen Durchläufen, die das Programm zudem rund einhundertmal ausführte, war die Ursache dafür. Das Projekt verwendete zur Einbindung von CUDA die Parallel Java 2 Library (PJ2) von Alan Kaminsky vom Rochester Institute of Technology (siehe Kasten „Middleware: Parallel Java 2 Library“). PJ2 ist eine Middleware zum Entwickeln parallel ausführbarer Java-Programme auf großen Rechnersystemen. Die PJ2-API enthält einen Wrapper für CUDA.

Am Anfang jedes Parallelisierungsprojekts sollte unbedingt eine Untersuchung der voraussichtlich zu erwartenden Ergebnisse stehen. Die Fachliteratur im Netz (alle Quellen findet man unter „Alle Links“ am Ende des Artikels) beschreibt die dazu erforderlichen Methoden. Erfolg versprechend sind Schleifen mit vielen identischen und voneinander unabhängigen Durchläufen – häufig der Fall bei Berechnungen mit Vektoren oder mehrdimensionalen Feldern, etwa Bildern. Falls die Logik außerdem nur gelegentliche Speicherzugriffe benötigt, ist die Schleife ein vielversprechender Kandidat für die Ausführung auf einer GPU.

Erst mal Überblick verschaffen

Für die theoretischen Grundlagen zur Parallelisierung sequenziell arbeitender Programme eignet sich Alan Kaminskys Buch BIG CPU, BIG DATA [1]. Vorabausgaben bis August 2015 sind im Rahmen der Lizenzbestimmungen von Creative Commons frei verfügbar. Das erste Kapitel hilft beim Einstieg ins Thema parallele Datenverarbeitung, und das Kapitel über GPUs vermittelt einen umfassenden Überblick zur Programmierung mit CUDA. Vor Projektbeginn sollten die Beteiligten außerdem den CUDA Programming Guide, die CUDA Best Practices und das Handbuch zum CUDA Compiler Driver NVCC aus der Dokumentation von NVIDIA komplett durchlesen [2, 3].

Die Methode gliedert sich in die Phasen Parallelisierung mit PJ2, Einführung von C++-Peer-Objekten, Ableitung von CUDA-Peer-Objekten, Kernel-Entwicklung und -Implementierung sowie Kernel-Optimierung (siehe Abbildung).

Schleifen lassen sich in PJ2 mit der abstrakten Klasse Task parallelisieren. Im Prinzip ersetzt man dazu die betreffende Schleife durch eine Spezialisierung von Task und überträgt den Code aus dem Schleifenkörper in die Methode parallelFor von Task. PJ2 parallelisiert diese sogenannten Worker, indem es den Code in parallelFor als eine Gruppe von Threads auf den Cores der CPU ausführt. Die präsentierte Methode sieht in der ersten Phase, der Parallelisierung mit PJ2, die Implementierung zweier Worker vor. Der erste verwendet die verfügbaren Cores der CPU. Sein Zweck ist es, die eingangs erstellte Prognose zur erwarteten Wirkung einer Parallelisierung zu bestätigen. Es ist nämlich möglich, dass die Schleifenlogik keinen signifikanten Beschleunigungseffekt erlaubt, wenn sich durch eine parallele Ausführung beispielsweise konkurrierende Speicherzugriffe ergeben. Der zweite Worker führt den Code aus der Schleife in einem Kernel als Threads auf den Cores der GPU aus.

Die Entwicklung des Kernels erfordert die Implementierung der Schleifenlogik einschließlich verwendeter Klassen in C/C++ und CUDA. Funktionen aus der Standardbibliothek für C stehen während der Ausführung des Kernels auf der GPU nicht zur Verfügung. Allerdings enthält die Thrust Library aus dem CUDA Toolkit einige Implementierungen auf Basis der Standard Template Library für C++.

Die nächste Phase der Methode erweitert den Programmierkontext von Java um C/C++. Nach der Identifizierung aller Objekte, die der Code der Schleife referenziert, werden die entsprechenden Klassen nach C/C++ mit vorzugsweise gleichen Namen übertragen. Den funktionalen Umfang der Implementierungen dieser C++ Peer Objects (C3P) geben die von den Klassen tatsächlich benötigten Methoden seitens Java vor. Testfälle für JUnit prüfen die Ergebnisse der Methoden von C3P und den entsprechenden Java-Klassen auf Übereinstimmung. Das dafür erforderliche Java-Wrapping der C3P für JNI erledigt CxxWRAP, das die benötigten Java- und C-Sourcen automatisch aus Klassendeklarationen in Header-Dateien erzeugt (siehe Kasten „Gut eingewickelt“). Die JNI-Implementierungen eignen sich außerhalb der Tests auch zum Überprüfen der C3P im Kontext des Java-Programms. Dazu ist ein weiterer Worker erforderlich, der via JNI diese C3P anstelle der Java-Klassen verwendet.

Auf in die dritte Etappe

Das Ziel der dritten Phase ist die Weiterentwicklung der C3P zu Derived CUDA Objects (DCP) für die spätere Verwendung in einem Kernel. DCP entstehen hauptsächlich durch Erweiterungen der Signaturen von Funktionsdeklarationen und -definitionen mit dem Schlüsselwort __device__, das den CUDA-Compiler anweist Kernel-Code zu erzeugen, den die GPU ausführt. Jedes DCP enthält einen Kernel, der spezifische Berechnungen vornimmt, sowie eine main-Funktion, die ihn ausführt und die Ergebnisse in den Standardausgabekanal schreibt. Die C3P erhalten in dieser Phase ebenfalls main-Funktionen mit spezifischen Berechnungen. Testfälle mit Shell-Mitteln prüfen beispielsweise mit cmp die Übereinstimmung der Ausgaben von DCP und entsprechenden C3P.