zur Startseite

Softwarepraktikum

GPU-basierte Parallelisierung eines arithmetischen Kodierers
Bearbeiter Filip Krumpe
Stephan Passow
Anja Reuter
Ludwig Stage
Betreuer Dipl.-Inf. Tjark Bringewat
Prüfer Prof. Dr.-Ing. Sven Simon
Beschreibung

Bei der arithmetischen Kodierung handelt es sich um ein Entropiekodierungsverfahren, das eine Symbolkette beliebiger Länge auf eine einzige reelle Zahl abbildet, indem es einzelnen Symbolen Intervalle zwischen 0 und 1 zuordnet und diese sukzessive miteinander kombiniert. Dadurch unterliegt es nicht der Beschränkung des Huffman-Verfahrens, jedes Symbol durch eine ganzzahlige Anzahl von Bits repräsentieren zu müssen, was sich in einer zum Teil deutlich effizienteren Kompression äußert.

Gegenstand des Softwarepraktikums ist eine GPU-basierte, parallele Implementierung des arithmetischen Kodierverfahrens. Die Implementierung soll auf CUDA-kompatibler Grafikhardware unter Verwendung der Softwareschnittstelle C for CUDA erfolgen. Idealerweise sollte dabei eine signifikante Beschleunigung im Vergleich zu einer äquivalenten sequentiellen Implementierung des Verfahrens erzielt werden.

Die Parallelisierung des arithmetischen Kodierverfahrens kann auf der Grundlage folgender beiden Ansätze erfolgen:
[1] J. Jiang and S. Jones. Parallel design of arithmetic coding. IEE Proceedings – Computers and Digital Techniques, 141(6):327-333, 1994.
[2] J. Šupol and B. Melichar. Arithmetic Coding in Parallel. International Journal of Foundations of Computer Science, 16(6):1207-1217, 2005.