© Excellent backgrounds/Shutterstock.com
Parallelisierung auf der Grafikkarte mit JNI, Rootbeer und CUDA

High-Performance-Computing mit Java


Während die massive Parallelisierung von Aufgaben auf der Grafikkarte im wissenschaftlichen Bereich bereits seit Jahren Standard ist (Wetterprognosen, pathologische Untersuchungen, Früherkennung von Herzkrankheiten etc.), findet sie in Business­anwendungen noch so gut wie keine Anwendung. Dabei steckt in jedem Desktop-PC häufig mehr Rechenpower als in einem Server. Grafikkarten im mittleren Preissegment sind heute schon mit mehreren Tausend GPU-Kernen ausgestattet und bieten eine immense Rechenleistung. Wegen verschiedener Barrieren bleibt diese GPU-Power aber ungenutzt. Dabei bietet Java über JNI das Potenzial, diese Barrieren zu überwinden. Das Framework Rootbeer [1] hat sich dieses Themas angenommen und soll im Folgenden anhand der Bilderkennungs­software „Visualink“ der Firma gjuce vorgestellt werden.

Die Verteilung von Aufgaben auf mehrere Threads ist nicht erst seit gestern ein Thema. Die Leistung von CPU-Kernen steigt nicht mehr so stark an, dafür werden CPUs jetzt mit mehreren Kernen ausgeliefert und können damit mehrere Threads gleichzeitig verarbeiten. Das Ergebnis ist eine bessere Ausnutzung der Ressourcen und damit eine Steigerung der Performance. Vergleicht man eine aktuelle GPU mit einer CPU (Abb. 1), fällt ein enormer Leistungsunterschied auf. Auch wenn ein direkter Vergleich etwas hinkt (Größenunterschied, Architektur etc.), finden auf einem Intel Core i7 1,4 Milliarden Transistoren Platz, während eine NVIDIA GTX 780M mit 3,8 Milliarden Transistoren ausgestattet ist.

bogaard_1.tif_fmt1.jpgAbb. 1: Entwicklung der theoretischen Leistungsfähigkeit verschiedener GPUs gegenüber CPUs; SP = Single Precision; DP = Double Precision [2]

Der Unterschied ist der, dass die Leistung hier auf mehrere tausend GPU-Kerne verteilt wird und nicht auf einige wenige CPU-Kerne. Das heißt, die einzelnen GPU-Kerne sind zwar tendenziell weniger leistungsfähig, können aber in der Masse parallelisierte Aufgaben besser verarbeiten. Je nach Algorithmus, Datenmenge und GPU sind hier Performanceverbesserungen um mehrere hundert Faktoren möglich.

In diesem Artikel wird der Algorithmus einer Bild­erkennungssoftware zur Verarbeitung auf der GPU portiert. Um hier einen Vergleich mit verschiedenen Parallelisierungsverfahren zu erhalten und den Code Schritt für Schritt anzupassen, wird der Algorithmus zuerst für die Parallelisierung auf der CPU umgestellt (Multi-Threading in Java). Anschließend wird der Rootbeer-GPU-Compiler eingesetzt, um den Code in GPU-Code zu überführen.

Was ist eine Bilderkennung?

Die Bilderkennung ist ein Teilbereich der Mustererkennung, die es erlaubt, zwei Bilder miteinander zu vergleichen und auf Übereinstimmungen zu prüfen (Abb. 2). Dabei können diese Bilder völlig unterschiedlich aufgenommen worden sein.

bogaard_2.tif_fmt1.jpgAbb. 2: Vergleich zweier unterschiedlich aufgenommener Bilder; die gelben Striche markieren die Übereinstimmungen

Wie funktioniert die Bilderkennung?

Dreh- und Angelpunkt der Bilderkennung sind die Interest Points. Sie bestehen aus einer Reihe von Werten, wie beispielsweise den X- und Y-Koordinaten, und der Ausrichtung. Zusätzlich gibt es pro Interest Point noch eine Liste von so genannten „Deskriptoren“, die den Punkt näher beschreiben. Diese Deskriptoren werden zum Vergleich herangezogen. Sowohl zur Ermittlung der Interest Points eines Bilds als auch zum Vergleich gibt es unterschiedliche Verfahren. In der Bilderkennung Visualink wird das SURF-Verfahren [3] (Speeded Up Robust Features) eingesetzt. Zum Vergleich der Interest Points wird das „Nearest-Neighbour-Verfahren“ eingesetzt. Hierbei werden, vereinfacht ausgedrückt, die Entfernungen zwischen den Punkten gemessen. Unterschreiten diese einen bestimmten Schwellenwert, so handelt es sich um einen Treffer, d. h. die Interest Points sind gleich.

Parallelisierung der Bilderkennung

Da jeder Interest Point mit jedem anderen verglichen werden muss (MxN) eignet sich dieses Verfahren hervorragend zur Parallelisierung. Je nach Anzahl der Threads wird die Gesamtaufgabe in kleinere, wenn möglich, gleich große Blöcke unterteilt (Abb. 3). Während auf der CPU mehrere Threads einzelne Aufgabenpakete verarbeiten können, kann das Gleiche auf der GPU tausendfach gemacht werden.

bogaard_3.tif_fmt1.jpgAbb. 3: Aufteilung der Vergleiche auf mehrere Threads

Der Matching-Algorithmus

Der Vergleich der Interest Points findet in der Methode vergleicheInterestPoints() der Klasse Bilderkennung statt (Listing 1), die die Anzahl der „Matches“ zwischen den beiden Listen zurückliefert. Durch die beiden for-Schleifen ist deutlich der MxN-Vergleich zu erkennen. In einer weiteren Schleife findet der eigentliche Vergleich über die Deskriptoren der Interest Points statt. Über diese wird die Entfernung der Interest Points voneinander gemessen. Bei einem Foto mit 4 000 Interest Points, 400 000 Interest Points in der Datenbank und einer Deskriptorengröße von 64 kommen wir insgesamt auf 102 400 000 000 Schleifendurchläufe.

Listing 1

public class Bilderkennung { public int vergleicheInterestPoints(List<IP> ersteListe, List<IP> zweiteListe){ int anzahlMatches = 0; for(IP ip1 : ersteListe){ for(IP ip2: zweiteListe){ for(int index = 0; index < 64; index++){ Desc desc1 = ip1.getDescriptors(index); Desc desc2 = ip2.getDescriptors(index); // Nearest-Neighbour-Verfahren // einsetzen } } } // Anzahl Treffer ermitteln ... return anzahlMatches; } }

Java – CPU Single-Threaded

Als Start für die Performanceanalyse führen wir die Bild­erkennung mit einem Thread auf der CPU aus (Tabelle 1). Dabei vergleichen wir die Interest Points eines Fotos mit verschieden großen Datenmengen. Alle Performancetests werden nach einer Warm-up-Zeit mehrmals ausgeführt. Die Testdaten werden vor jedem Performancetest eingelesen und sind für alle Tests gleich. Das System, auf dem die Tests stattfinden, ist ein Ubuntu 14.04 LTS mit Intel Core i7-4800MQ CPU @ 2.70 GHz × 8 (4 physische Kerne), 16 GB RAM, 64 Bit und Oracle JDK 1.6.0_45 (Server, Mixed-Mode) mit Standard-Memory-Einstellungen. Die Grafikkarte ist eine GeForce GTX 780M.

Anzahl Interest Points Foto

Anzahl Interest Points Datenbank

Benötigte Zeit in Sekunden

Relative Performance

4 000

100 000

17,5

1x

4 000

200 000

35,1

1x

4 000

300 000

52,6

1x

4 000

400 000

69,7

1x

Tabelle 1: Ergebnisse des Performancevergleichs Java – CPU Single-Threaded

Java – CPU Multi-Threaded

Als weiterer Test soll die Parallelisierung noch auf der CPU gemacht werden. Dazu, und für die spätere Portierung auf die GPU, müssen bereits Anpassungen im Quellcode gemacht werden. Dazu wird die Gesamtmenge der Daten vor dem V...

Neugierig geworden? Wir haben diese Angebote für dich:

Angebote für Gewinner-Teams

Wir bieten Lizenz-Lösungen für Teams jeder Größe: Finden Sie heraus, welche Lösung am besten zu Ihnen passt.

Das Library-Modell:
IP-Zugang

Das Company-Modell:
Domain-Zugang