Kurzfassung. Zur Bewa¨ltigung komplexer Berechnungen wird in der medizinischen Bildverarbeitung immer ha¨ufiger Spezialhardware eingesetzt. Die Open Computing Language offeriert die Mo¨glichkeit eines gleichzeitig hardware-unabha¨ngigen und performanten Programms. Dies wurde von uns am Beispiel der Bildrekonstruktion untersucht und gezeigt, dass sich mit Hilfe von OpenCL auf CPU-Systemen Leistungssteigerungen einfach erzielen lassen. Des weiteren wird ein hohe Unabha¨ngigkeit der Implementierung von der Hardware erreicht und somit die Nutzung moderner Technologien, wie z.B. Grafikprozessoren, erleichtert. Die Laufzeit unseres Problems konnten wir auf einer Vierkern-CPU von 40 min auf 6; 5 min reduzieren. Durch die Verwendung einer Grafikkarte und einfache Optimierungen wurde schließlich eine Laufzeit von 17 s erreicht.
In den letzten Jahren hat nicht nur die durchschnittliche Datenmenge
medizinischer Datensa¨tze zugenommen, sondern die zum Einsatz kommenden
medizinischen Bildverarbeitungalgorithmen wurden auch komplexer. Um den
dadurch gestiegenen Rechenaufwand effizient zu bewa¨ltigen wird oft
Spezialhardware (Multi-core [
Die Ende 2008 vero¨ffentlichte Open Computing Language (OpenCL) verspricht eine einheitliche, effiziente und portable Programmierung verschiedener leistungsstarker Hardwarearchitekturen.
In dieser Arbeit wird zuerst OpenCL kurz vorgestellt, um dann am Beispiel der 3D Rekonstruktion von C-arm CT deren Eignung fu¨r die medizinische Bildverarbeitung zu untersuchen. Unser Augenmerk liegt dabei auf dem unkomplizierten Umstieg zu OpenCL, der Portierbarkeit des Quelltextes bezu¨glich der Architektur und der dabei erreichten Leistung.
Als Beispiel fu¨r einen medizinischen Bildverarbeitungsalgorithmus verwenden
wir die 3D Ru¨ckprojektion von C-arm CT Daten. Die Methode nach Feldkamp
et al. [
Bei RabbitCT handelt es sich um ein Framework zum Vergleich verschiedener, optimierter Implementierungen der 3D Ru¨ckprojektion. Dazu wird ein Mess- und Auswertungsprogramm, eine Beispiel-Implementierung, und ein standardisierter Datensatz mit Geometrieinformationen o¨ffentlich zur Verfu¨gung gestellt. Dies erlaubt einen fundierten Vergleich der Laufzeit verschiedener Implementierungen, sowie der von ihnen erreichten Bildqualita¨t.
Die 496 Projektionsbilder der Gro¨ße 1240 960 des RabbitCT Datensatzes sind bereits vorverarbeitet und gefiltert. Die Aufnahmegeometrie wird in Form von Projektionsmatrizen bereitgestellt. Fu¨r unseren Vergleich verwendeten wir eine Volumenauflo¨sung (x,y,z) von 5123 Volumenelementen. 2.2
OpenCL ist ein offener Standard zur Programmierung heterogener Systeme. Ziel ist die Bereitstellung einer einheitlichen Programmierschnittstelle fu¨r effiziente und portable Programme. Die drei Kernkonzepte von OpenCL werden im folgenden vorgestellt. Fu¨r eine ausfu¨hrliche Einfu¨hrung in OpenCL verweisen wir auf die Webseite der Khronos-Group1, welche den Standard verwaltet, sowie auf Tutorials und Anleitungen von NVIDIA und AMD.
Plattformmodell. Das Plattformmodell besteht aus einem Host, der Verbindung zu einem oder mehreren OpenCL Devices aufnimmt. Ein OpenCL Device ist unterteilt in eine oder mehrere Compute Units. Diese sind weiter unterteilt in ein oder mehrere Processing Elements auf denen die tatsa¨chliche Programmausfu¨hrung stattfindet. Dabei sind Host und Device logisch voneinander getrennt, was die Portabilita¨t sicherstellt.
Ausfuhrungsmodell. Das OpenCL-Ausfu¨hrungsmodell legt die Ausfu¨hrung der Kernel fest. Kernel sind Programme, die in einem C-Dialekt programmiert und auf dem OpenCL Device parallel ausgefu¨hrt werden. Wenn ein Kernel vom Host-programm zur Ausfu¨hrung an das OpenCL Device u¨bergeben wird, wird ein Indexraum erzeugt. Fu¨r jede Stelle in diesem Indexraum wird eine Instanz dieses Kernels ausgefu¨hrt. Diese Kernel-Instanz wird Workitem genannt und ist identifizierbar u¨ber die Position im Indexraum. Workitems werden in Gruppen zu Workgroups zusammengefasst. Speichermodell. Das OpenCL-Speichermodell basiert wie die beiden anderen Modelle auf der Trennung von Host und Device. Dabei gibt es verschiedene Arten von Speicher, die unterschiedliche Zugriffseigenschaften und Latenzen aufweisen. 3
Neben Hauptprozessoren wurden aufgrund ihrer hohen Rechenleistung auch Grafikkarten untersucht. 3.1
Fu¨r die Laufzeitmessung der CPU-basierten Implementierungen wurde ein Rechner mit einem Intel Core2 Extreme X9650 Vierkern-Prozessor mit 3:0 GHz Taktrate verwendet. Als Ausgangspunkt diente die zu RabbitCT geho¨rende Referenzimplementierung. Hierbei handelt es sich um eine einfache Umsetzung der mathematischen Rechenvorschrift. Die Implementierung wird lediglich mit dem Compiler u¨bersetzt und von diesem optimiert. Dadurch wird bei der Ausfu¨hrung nur ein Prozess verwendet, die Laufzeit liegt bei ca. 42 min (Abb. 1).
Da drei der vier Prozessorkerne durch den einzelnen Prozess nicht verwendet werden, wurde der Algorithmus als Erstes parallelisiert und auf mehere Prozesse aufgeteilt. Ein einfach zu verwendendes, weit verbreitetes Werkzeug hierfu¨r ist die Open Multi-Processing (OpenMP) Erweiterung, z.B. fu¨r C/C++. Diese verwenden wir, um auf einfache Weise alle 4 Kerne auszunutzen. Mit Hilfe von OpenMP wurde die a¨ußere Schleife (z-Richtung des Volumens) des Algorithmus in mehrere Blo¨cke aufgeteilt, die nun jeweils von einem anderen Prozessor bearbeitet werden. Dies erbringt einen Geschwindigkeitsgewinn um Faktor 4; 3 auf eine Laufzeit knapp unter 10 min.
Ebenfalls auf Basis der Referenzimplementierung betrachten wir nun eine OpenCL Implementierung auf der CPU. Als Framework wird hierbei das ATI Stream SDK 2.1, welches OpenCL 1.0 unterstu¨tzt, verwendet. Jeder OpenCL Kernel bearbeitet eine (oder mehrere) x-y-Schicht(en) des Volumens. Allein der Einsatz von OpenCL bringt gegenu¨ber OpenMP eine zusa¨tzliche Geschwindigkeitssteigerung um Faktor 1; 5 und eine Laufzeit von ca. 6; 5 min. Der zusa¨tzliche Geschwindigkeitsgewinn la¨sst sich dadurch erkla¨ren, dass der OpenCL Compiler die Vektoreinheiten besser ausnutzt als sein OpenMP Pendant. 3.2
Zur weiteren Beschleunigung greifen wir auf die Leistung einer Grafikkarte zuru¨ck. Fu¨r die Messungen wurde eine NVIDIA QuadroFX 5600 benutzt. Dabei wurde der CUDA 3.1 Treiber verwendet, der OpenCL 1.1 unterstu¨tzt.
Die auf der CPU entwickelte OpenCL Implementierung kann durch a¨nderung des OpenCL Device im Host-Programm ohne weitere Anpassungen auf der Grafikkarte ausgefu¨hrt werden, scho¨pft aber nicht deren volle Leistung aus. Grafikkarten bieten ein Vielfaches an Recheneinheiten und erfordern deshalb einen ho¨heren Grad an Parallelisierung. Daher wird der Algorithmus nicht nur in zRichtung aufgeteilt, sondern u¨ber alle Volumenelemente. Diese GPU Implementierung mit OpenCL kann im Vergleich zur CPU einen Geschwindigkeitsgewinn um Faktor 1; 3 auf ca. 5 min verbuchen. Die Performanz wurde zwar verbessert, allerdings fa¨llt der Gewinn geringer als erwartet aus.
Ursache hierfu¨r ist die spezifische Architektur von Grafikkarten. Zwar bieten GPUs eine enorme theoretische Rechenleistung, intensiver Zugriff auf den Grafikspeicher der Karte stellt allerdings einen Engpass dar. Um diesen Einfluss zu verringern wenden wir die folgenden Optimierungen fu¨r Grafikkarten an.
Zuerst haben wir den sogenannten coalesced Speicherzugriff verwendet. Greifen alle Kernel einer Workgroup gleichzeitig in einem bestimmten seriellen Muster auf den Speicher zu, dann kann die effektive Speicherbandbreite deutlich erho¨ht werden. Bei einer Transaktion kann dann ein gro¨ßerer Datenblock, anstatt mehrerer Kleiner, zum bzw. vom Speicher u¨bertragen werden.
Um diese Technik in unserem Fall anzuwenden, gehen wir von der beschriebenen 3D-Aufteilung des Problems zuru¨ck zu einer 2D-Aufteilung, parallelisiert u¨ber die x-z-Ebene. Wichtig ist hierbei, dass jeder Kernel nun eine Zeile des Volumens in y-Richtung und jede Workgroup einen Teil einer Zeile in x-Richtung bearbeitet. Durch diese Art der Paralleliserung wird sichergestellt, dass die Kernel innerhalb einer Workgroup sequentiell auf den Volumenspeicher zugreifen und der Zugriff somit coalesced ist. Die Geschwindigkeit wird hierdurch weiter um einen Faktor 2; 9 auf eine Laufzeit von unter 2 min verbessert.
Durch den Einsatz von Textureinheiten wird schließlich eine weitere Technik zur Laufzeitverbesserung von Bildverarbeitungsalgorithmen angewendet. Moderne Grafikkarten bieten neben speziellen Textur-Caches auch Recheneinheiten zur Interpolation zwischen Texturelementen (Pixeln). In unserem Fall kann dieser besondere Speichertyp fu¨r die Projektionsbilder verwendet werden. Sind angeforderte Werte bereits im Cache vorhanden, so werden die Zugriffe auf den Hauptspeicher der Grafikkarte reduziert. Durch die Verwendung von Texturen ko¨nnen 4 Speicherzugriffe und deren bilineare Interpolation in Software durch einen einzigen Zugriff auf die Textur ersetzt werden. Letztendlich konnte durch die Verwendung von Texturen ein weiter Geschwindigkeitszuwachs um Faktor 6; 3 auf eine Laufzeit von unter 17 s erreicht werden. 4
Im Rahmen dieser Arbeit spielte die Erzielung der maximalen Leistung eine sekunda¨re Rolle. Prima¨r sollte die einfache Verwendung von OpenCL gezeigt werden, mittels der sich sowohl eine betra¨chtliche Leistung als auch ein einfacher Wechsel zwischen unterschiedlicher Hardware erreichen la¨sst. Die Ergebnisse in Abbildung 1 zeigen eindrucksvoll den durch die Benutzung von OpenCL mo¨glichen Geschwindigkeitsgewinn. Da die OpenCL Kernel alle im gleichen C-Dialekt geschrieben sind, ist der Unterschied zwischen ihnen marginal und ermo¨glicht sowohl eine schnelle Realisierung als auch einen einfachen Umstieg zwischen Hardwarearchitekturen. Hierbei anzumerken ist der Umstand, dass die gezeigAbb. 1. Laufzeit verschiedener Programme in [s]. Ku¨rzere Balken sind besser. (c) bedeutet coalesced Speicherzugriff, (t) bedeutet Benutzung von Textureinheiten. Die oberen drei Balken (blau) nutzen die CPU, die unteren drei (gru¨n) die GPU. ten Optimierungen Wissen u¨ber die Architekturen voraussetzen und nutzen, was die Portabilita¨t einschra¨nkt. Erwa¨hnenswert ist auch die Tatsache, dass die verwendete Grafikkarte kein Modell der neuesten Generation ist, und hier weitere Geschwindigkeitszuwa¨chse mo¨glich sind. 5
Zusammenfassend kann festgestellt werden, dass OpenCL ein sehr vielversprechendes Framework darstellt. Wenngleich noch Optimierungen fu¨r verschiedene Plattformen notwendig sind, ist der Code im allgemeinen sehr portabel. Dabei bietet OpenCL bereits auf der CPU Geschwindigkeitsvorteile gegenu¨ber dem etablierten Framework OpenMP. Der Umstieg auf die Grafikkarte ist einfach realisierbar und birgt weitere enorme Geschwindigkeitszuwa¨chse.
Wir gehen davon aus, dass OpenCL zuku¨nftig ein weites Anwendungsspektrum und großes Interesse findet. Eine weitere Verbesserung der Compiler ist zu erwarten, wodurch eventuell auch die beschriebenen Optimierungen automatisiert werden.
Literaturverzeichnis