David Knötel

Schnelle parallele Multiplikation großer Zahlen mit CUDA

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 01.02.2012

Kurzbeschreibung

Der Schönhage-Strassen-Algorithmus ist ein 1971 vorgestellter schneller Algorithmus zur Multiplikation von großen natürlichen Zahlen. Es wird zunächst die Funktionsweise des Algorithmus und anschließend eine Implementierung des Algorithmus in C vorgestellt. Weiterhin wird die Möglichkeit aufgezeigt, den Algorithmus durch massiv parallele Ausführung einiger Teilabschnitte zu beschleunigen. Die parallelen Berechnungen werden auf die Grafikkarte ausgelagert und erfolgen mit Hilfe der NVIDIA-Architektur CUDA. Durch Einsatz von Laufzeittests und Profiling-Tools werden abschließend die Ergebnisse evaluiert.