Automatische Hardwaresynthese für Löser von konvexen Optimierungsproblemen
Einleitung
Die konvexe Optimierung ist ein Teilgebiet der mathematischen Optimierung. Es gilt dabei eine bestimmte Größe (Zielfunktion) zu minimieren, die von einem Parameter x abhängt. Der mögliche Wertebereich von x ist durch Nebenbedingungen eingeschränkt, die in Form von Gleichungen oder Ungleichungen gegeben sind. Ist sowohl die Menge der zulässigen Werte für x als auch die Zielfunktion konvex, so spricht man von einem konvexen Optimierungsproblem. Beispiele solcher Probleme sind die lineare Programmierung oder die Methode der kleinsten Quadrate. Die Lösung von konvexen Optimierungsproblemen ist in vielen Bereichen der digitalen Signalverarbeitung von Bedeutung, zum Beispiel bei der Model Predictive Control. Allerdings ist der zur Lösung notwendige Rechenaufwand relativ hoch und der daraus resultierende Hardware- und Energiebedarf verhindert oft den Einsatz in der Praxis. Die Lösung dieses Problems in einer spezialisierten Rechnerarchitektur bietet deutliche Vorteile, jedoch ist die manuelle Erstellung einer solchen Schaltung mit großem Entwicklungsaufwand und hohen Kosten verbunden.
Methoden
Im Fachgebiet „Eingebettete Systeme und ihre Anwendungen“ des Fachbereichs Informatik wird an einer Kette von Software-Werkzeugen gearbeitet, die eine abstrakte Definition eines konvexen Problems bzw. einer Gruppe von ähnlichen Problemen automatisch in eine Hardware-Beschreibung für einen spezialisierten Rechenbeschleuniger umsetzt. Dabei wird zunächst mit frei verfügbaren Werkzeugen ein Softwareprogramm für eine Art von konvexen Problemen erzeugt. Anschließend wird dieses Programm mit den eigens entwickelten Werkzeugen weiter verarbeitet, um einen für die Problemklasse optimierten Hardwarebeschleuniger zu erhalten. Dieser wird anschließend auf ein Field Programmable Gate Array (FPGA) abgebildet. Bei einem FPGA handelt es sich um ein elektronisches Bauteil, in das auch ohne die übliche photochemischen ChipFertigung flexibel digitale Schaltungen programmiert werden können. Besonderer Fokus liegt auf der High-Level Synthese, bei der eine Beschreibung der digitalen Schaltung automatisch aus einem Softwareprogramm erzeugt wird. Dazu wird der am Fachgebiet entwickelte C-zuHardware Compiler Nymble eingesetzt. Er erzeugt aus einem Softwareprogramm, welches in der Programmiersprache C vorliegt, eine Hardwarebeschreibung in Verilog HDL. Für die Beschleunigung der konvexen Löser durch spezialisierte Hardware wurde der Compiler Nymble[1] im Rahmen dieses Projektes um Funktionen erweitert, die eine Umsetzung der konvexen Optimierungsprogramme effizienter gestalten. Während andere kommerzielle und akademische C-zuHardware Compiler teilweise schon an der Verwendung von Fließkommaoperationen und Zeigervariablen scheitern oder deutlich zu große Hardware erzeugen, konnte mit Nymble bereits erfolgreich Hardware zur Lösung von kleineren konvexen Problemen erzeugt werden. Zur weiteren Steigerung von Energieeffizienz und Performance wurde außerdem eine vom Standard abweichende Divisionseinheit entwickelt, die auf die Zielhardware angepasst ist. Sie rechnet zwar etwas ungenauer, jedoch deutlich schneller als herkömmliche Divisionseinheiten.
Ergebnisse
So konnte die Rechengeschwindigkeit in einigen Fällen mehr als verdoppelt werden[2]. Der Lichtenberg-Cluster wurde dabei für den letzten Schritt des Übersetzungsflusses, die Abbildung der mittels Nymble erzeugten digitalen Schaltung auf das FPGA genutzt. Dieser extrem rechenaufwendige „Place & Route“ Vorgang benutzt selber heuristische Optimierungsverfahren, die nicht immer die gleiche Lösung liefern. Durch eine Vielzahl von Läufen konnte der mögliche Abbildungsraum exploriert werden und somit eine möglichst gute Realisierung der Rechenbeschleuniger gefunden werden.
Ausblick
Weitere Arbeiten des noch laufenden Projektes sollen die Energieeffizienz und Performance weiter steigern. Neben anderen Werkzeugen zur Erzeugung der Softwareprogramme ist hier auch eine Umstellung auf neuere FPGAs geplant.
