Bachelorarbeit : Implementierung eines Algorithmus zur Bestimmung der Tiefe sich überdeckender Rechtecke in OpenCL

Michael Krause

Betreuer: Prof. Dr. Helmut Alt, Dr. Ludmila Scharf

Zur Berechnung der Tiefe von sich überdeckenden Rechtecken wurde von Alt et al. ein neuer Algorithmus vorgeschlagen, dessen besondere Eigenschaft darin besteht, parallelisierbar zu sein. Diese Arbeit soll zeigen, wie man diesen Algorithmus auf einer entsprechenden Plattform implementieren kann. Als Werkzeug wurde die Open Computing Language (OpenCL) verwendet, um die Lauffähigkeit auf einer Grafikkarte zu realisieren. Sowohl auf das Werkzeug als auch auf den Algorithmus wird detaliert eingegangen. Ausgehend von einer in C implementierten sequentiellen Referenz wird gezeigt, wie man eine parallele Version ableiten kann. Bei einem ersten Versuch der Implementierung sind Limitierungen aufgetreten, die unter anderem durch das OpenCL-Modell bedingt sind. Diese Einschränkungen werden diskutiert und mit Hilfe einer alternativen, von den Algorithmus-Autoren vorgeschlagenen Datenstruktur umgangen, um die Zielkomplexität von O(log2n) im PRAM Modell zu erreichen.