Algorithm Engineering für parallele Umsetzung komplexer Algorithmen
Final Report Abstract
Beim Algorithm Engineering wird vor allem das Ziel verfolgt, die Kluft zwischen Theorie und Praxis der Algorithmik zu überbrücken. Die aktuellen Entwicklungen im Hardwarebereich haben eine Neuorientierung in diesem Gebiet erforderlich gemacht, die grundsätzlich auf parallele Verarbeitung zielt. Dabei treten aber, insbesondere für komplexe Algorithmen und Programme, Probleme zu Tage, für die bislang keine zufriedenstellenden Lösungen existieren. Aufbauend auf unserer bisherigen, erfolgreichen Arbeit beim Algorithm Engineering haben wir uns im aktuellen Projekt verstärkt mit diesen Aspekten paralleler Algorithmen auseinandergesetzt. Die behandelten Probleme stammen aus den Gebieten Netzwerkoptimierung (mit Fokus auf dem Steiner-Problem) und Kryptanalyse (mit Fokus auf leichtgewichtigen Chiffren). Das Projekt umfasst sowohl theoretische Überlegungen und Algorithmenentwurf als auch praktische Implementierung und experimentelle Bewertung. Im Kontext des Steiner-Problems haben wir alle relevanten Bausteine (Relaxationen für untere Schranken, Heuristiken für obere Schranken, Reduktionen zur Vereinfachung der Probleminstanzen, aber auch exakte Algorithmen) parallelisiert. Dabei waren in vielen Fällen neue algorithmische Konzepte und fast immer großer implementierungstechnischer Aufwand erforderlich. Die Experimente haben die Wichtigkeit bestätigt, sich bei der Parallelisierung nicht auf ein Paradigma festzulegen und nur Kriterien wie Beschleunigung bezüglich eines Ansatzes zu optimieren, sondern möglichst viele, sich in ihrem Verhalten ergänzende Ansätze und Bausteine parallel zu implementieren, um dem Gesamtpaket die nötige Flexibilität zu geben. Empirische Ergebnisse zeigen, dass die geleistete Arbeit sich gerade bei der Behandlung von großen und schwierigen Instanzen auszahlt. Für die parallele Realisierung wurde ein hybrides Modell zugrunde gelegt: Auf der höheren Ebene benutzen wir das Message-Passing-Modell, auf der niedrigeren Ebene das Shared-Memory-Modell. Bei der tatsächlichen Implementierung wurde bei den meisten Bausteinen des Steiner-Pakets dem MPI (Message-Passing Interface) Standard der Vorzug gegeben. Insgesamt gewährleistet unsere Vorgehensweise eine sehr große Flexibilität und Portierbarkeit des Programms. Das resultierende, sehr umfangreiche Softwarepaket dürfte zu den leistungsstärksten im besprochenen Kontext gehören. Es wird für wissenschaftliche Anwendung und Weiterentwicklung frei zur Verfügung gestellt. Bezuglich des Arbeitspakets Parallele Umsetzung ausgewählter Kryptanalysealgorithmen fokussierten sich die geleisteten Arbeiten auf das Thema OBDD-basierte Angriffe auf leichtgewichtige, FSR-basierte Flusschiffren. Hier wurde zunächst ein umfangreiches, auf dem etablierten BDD-Paket CUDD basierendes System zur praktischen Durchführung derartiger Angriffe aufgebaut. Mit diesem System wurden verschiedene Ansätze zur Parallelisierung von OBDD-Angriffen verfolgt, von denen der der Verteilung der Geheiminformation auf zwei parallel zu erzeugende OBDDs vielversprechend erscheint. Die entsprechenden experimentellen Versuchsreihen laufen hier noch, eine Publikation ist in Arbeit.
Publications
- The Steiner tree challenge: An updated study. In 11th DIMACS Implementation Challenge in Collaboration with ICERM: Steiner Tree Problems, 2014
T. Polzin and S. Vahdati Daneshmand
- Lightweight cryptography on ultra-constrained RFID devices. Dissertationsschrift Universität Mannheim, 2018
M. Hamann
