Kurzfassung. Die vorliegende Arbeit bescha¨ftigt sich mit der Implementierung von Teilen eines Registrierungsalgorithmus in der Compute Unified Device Architecture (CUDA) von NVIDIA und der daraus resultierenden Zeitersparnis. Es wurden die einzelnen Schritte des Registrierungsalgorithmus analysiert und auf ihre Parallelisierbarkeit untersucht. Die Implementierungen wurden anhand von 20 thorakalen CT-Datensa¨tzen evaluiert und der SpeedUp berechnet. Es wurde eine Beschleunigung vom Faktor 143 bei der TPS Interpolation und ein Faktor 12 beim Image Warping erreicht. Obwohl nur 2 Teilschritte auf der GPU umgesetzt wurden, konnte ein Speedup des Gesamtverfahren von 2.175 erreicht werden. Dies zeigt das eine GPU-Implementierung effizienter als eine CPU-basierte Parallelisierung sein kann.
Ausgangsdaten fu¨r die Registrierung sind ein Referenzbild IF und ein zu
registrierendes Bild IM , sowie zugeho¨rige Segmentierungsmasken des relevanten
Organs (z.B. der Lunge) MF und MM . Der Registrierungsalgorithmus besteht
aus zwei wesentlichen Komponenten: einer oberfla¨chenbasierten Vorregistrierung
und einem diffeomorphen, intensita¨tsbasierten Registrierungsschritt [
Fu¨r die Umsetzung der GPU-basierten Parallelisierung wurden zuna¨chst die anteiligen Rechenzeiten der einzelnen Teilschritte bestimmt (Abb. 1). Anschließend wurde die Eignung der einzelnen Teilschritte fu¨r eine GPU-basierte Parallelisierung untersucht (Abschn. 2.1) und eine Gewichtung hinsichtlich Eignung und Relevanz fu¨r eine Beschleunigung festgelegt. Die GPU-basierte Parallelisierung wurde dann schrittweise entsprechend der gefundenen Gewichtung durchgefu¨hrt (Abschn. 2.2). Die GPU-Implementierung wurde fu¨r eine NVIDIA Quadro FX 3800 optimiert. Diese Grafikkarte hat 1024 MB globalen Speicher, 24 Multiprozessoren mit je 8 Prozessor-Kernen. 2.1
Laufzeitkomplexitat und Parallelisierbarkeit Die Schritte des Registrierungsalgorithmus wurden in der Reihenfolge der gro¨ßtmo¨glichen Laufzeitersparnis analysiert. Die TPS Interpolation und die diffeomorphe Registrierung sind mit 47.8% und 45.0% die zwei aufwa¨ndigsten Schritte des Registrierungsalgorithmus und bieten sich damit fu¨r eine Parallelisierung an. Die TPS Interpolation kann aufgrund der einfachen Verarbeitungsschritte einfach in CUDA implementiert werden. Die diffeomorphe Registrierung besteht aus mehreren Teilen (Abb. 1): Die Exponentiation erfordert es, dass zwei Deformationsfelder im Grafikkartenspeicher gehalten werden. Das ist momentan aufgrund von Speichereinschra¨nkungen nicht mo¨glich, es wa¨re notwendig einen Streaming-Ansatz zu implementieren, um diese Einschra¨nkung zu umgehen. Die Regularisierung wurde bereits stark auf der CPU optimiert und es ist fraglich in wieweit mit CUDA eine weitere Verbesserung erreicht werden kann. Das Warping ist aufgrund seiner simplen Funktion einfach in CUDA zu implementieren. Ein weiterer positiver Aspekt der CUDA Implementierung des Warping ist die Verwendung des Textur-Speicher, der es erlaubt die in der Grafikkarten-Hardware implementierte trilineare Interpolation zu nutzen. Die Berechnung des UpdateFeld ist ein Schritt der sich aufgrund der einfachen Funktion gut mit CUDA implementieren la¨ßt.
Die Umsetzung der Nicht linearen Oberfla¨chen Registrierung und des
ICPAlgorithmus beno¨tigen eine Implementierung des
k-Nearest-Neighbour-Algorithmus (kNN) auf der GPU. Zwar gibt es bereits Ansa¨tze diesen Algorithmus in
CUDA zu implementieren, diese sind aber in der Anzahl der verwendbaren Punkte
begrenzt [
Aufgrund obiger Analyse werden zuna¨chst die Schritte TPS, Warping, Compute Update Field und Regularisierung in CUDA umgesetzt. Die Oberfla¨chen Generierung ist aufgrund des geringen Anteils an der Laufzeit und dem hohem Aufwand einen Marching-Cubes-Algorithmus in CUDA zu implementieren nicht fu¨r eine CUDA-Implementierung vorgesehen. Da ICP und die nicht-lineare Oberfla¨chen Registrierung den kNN-Algorithmus beno¨tigen, muss zuna¨chst eine kNN-Implementierung verfu¨gbar sein die nicht in der Anzahl der Punkte limitiert ist. Die Schritte Exponantiation und Konkatenation ko¨nnen, aufgrund ihres hohen Speicherbedarfs, erst implementiert werden wenn ein Streaming-Ansatz fu¨r CUDA implementiert wurde.
Input data
Marching
Cubes 0,1% Warping 0,1%
ICP 1,5% Diffeom.
Reg. 45,0%
Surface
Reg. 5,4% 0,1%
TPS Interpol. 47,8% Diffeom. Reg.
Warping 14,1%
Comp.
Update 7,1%
Regularization 31,7%
Exponentiation 45,8% Abb. 1. Aufbau des Registrierungsalgorithmus. An jedem Schritt sind die Anteile an der Gesamtlaufzeit angegeben.
GPU-basierte Beschleunigung/Parallelisierung Bei der TPS Interpolation wird an zwei korrespondierenden Landmarken Sets mit N Punkten ein Deformationsfeld bestimmt. Im ersten Schritt wird dabei eine Matrix der Gro¨ße 3 × (3 + N + 1) auf der CPU invertiert. Die Matrix wird zusammen mit den Landmarken auf die GPU u¨bertragen. Außerdem muss ein Bereich des Grafikkarten-Speichers fu¨r das zu generierende Deformationsfeld reserviert werden. Anschließend wird fu¨r jedes Voxel im Displacement Field ein Thread auf der Grafikkarte erzeugt, die dann parallel die Transformation berechnen.
Das Image Warping erfordert es das verwendete Bild und das Deformationsfeld in den Grafikspeicher zu u¨bertragen. Um weitere Zeitersparnis zu erreichen, wird das Bild in den Textur-Speicher der Grafikkarte geladen und die Hardware implementierte Interpolation verwendet. 3
Die Laufzeiten der GPU-Programme wurden mit CudaEvents der NVIDIA CUDA API gemessen und umfassen auch die Operationen zur Speicherallokation und Speichertransfer. Die Laufzeiten der Programmteile die die CPU verwenden wurden mit der C time Bibliothek erfasst. Zur Messung wurden 20 thorakale CT-Datensa¨tzen verwendet. Alle Zeiten wurden fu¨nfmal gemessen und jeweils der Mittelwert verwendet.
Da die urspru¨ngliche Implementierung der TPS-Interpolation auf VTK basiert, wurde zusa¨tzlich noch eine CPU basierte Ausfu¨hrung des Kernel Code angegeben um Overhead von VTK bei der Zeitmessung auszuschließen (Abb. 2a).
Da beim Schritt Image Warping aufgrund der Normalisierungsschritte fu¨r den Textur-Speicher zusa¨tzlicher Aufwand entsteht, umfasst die Zeitmessung auch diese Schritte (Abb. 2b). Die Normalisierungsschritte sind erforderlich, da der Textur-Speicher nur im Bereich [0;1] funktioniert.
Zur Berechnung der erreichten Beschleunigung des gesamten
Registrierungsalgorithmus nach Amdahl [
(b) Warping Abb. 2. Vergleich der Implementierungen verwendet. Die Beschleunigung der TPS-Interpolation um den gemittelten Faktor 143 und des Image Warping um den gemittelten Faktor 12 ergibt eine Beschleunigung des gesamten Algorithmus um 2,175. 4
Am Graphen in Abb. 2a kann man erkennen das die Implementierung des TPSResampling in CUDA eine erhebliche Zeitersparnis mit sich bringt. Der Beschleunigungsfaktor liegt bei ca. 143 im Vergleich zu einer Implementierung mit VTK. Die Implementierung des Warping hat eine geringere Ersparnis gebracht (Abb. 2b), der Beschleunigungsfaktor liegt bei ca. 12. Allerdings wird durch die ha¨ufige Verwendung des Warping, im Gesamtkontext des Registrierungsalgorithmus, die Laufzeit erneut bedeutend verringert.
Die weiteren Schritte beinhalten die Umsetzung der in Abschnitt 2.1 genannten Schritte, wie beispielsweise die Berechnung des Update Feldes. Außerdem werden die Schritte die nicht einfach parallelisierbar sind weiterhin auf mo¨gliche Optimierungen untersucht. Eine weitere Mo¨glichkeit fu¨r Optimierungen wa¨ren die Normalisierungsschritte des Warping. Die Normalisierung ko¨nnte ebenfalls auf der GPU ausgefu¨hrt werden.
Durch eine Grafikkarte die mehr globalen Speicher bietet wa¨re es mo¨glich weitere Teilschritte auch ohne einen Streaming-Ansatz zu implementieren. Die Arbeit zeigt aber, dass sich auch durch die GPU-Implementierung weniger Teilschritte nicht-lineare Registrierungs-Algorithmen erheblich beschleunigen lassen.