Multi-Opt - Multi-criterial Code Optimization for Embedded Hard Real-Time Systems
Final Report Abstract
Viele Compiler-basierte Optimierungen wurden vorgeschlagen, um eine einzelnes Entwurfskriterium zu optimieren, während andere Kriterien ignoriert werden. Dies kann zu einer drastischen Verschlechterung der ignorierten Entwurfskriterien führen. In diesem Projekt haben wir Ansätze zur Lösung von mehrkriteriellen Optimierungsproblemen zur Übersetzungszeit vorgestellt. Unser Ziel war, die maximale Ausführungszeit (WCET), die Codegröße und den Energieverbrauch, welche entscheidende Kriterien für harte Echtzeitsysteme sind, zu optimieren. Wir haben eine neuartige Compiler-basierte Kompressionstechnik für harte Echtzeitsysteme vorgestellt. Da das Hauptziel der Kompression darin besteht, die Codegröße so weit wie möglich zu verringern, haben wir das mehrkriterielle Kompressionsproblem als ein Problem mit nur einem Entwurfskriterium umformuliert. Dieses minimiert die Codegröße unter Einhaltung von WCET- und/oder Energieverbrauchsbeschränkungen. Die vorgeschlagene Kompression komprimiert Teile des Eingabecodes zur Übersetzungszeit und dekomprimiert sie zur Ausführungszeit. Der Ansatz erfordert keine teure Hardware zum Dekomprimieren, da ein Compiler den Code der Dekompressionsroutine in den Ausgabe- Assemblercode einfügt, um den Code zur Ausführungszeit zu dekomprimieren. Die Umformulierung eines mehrkriteriellen Problems in ein Problem mit nur einem Zielkriterium ermöglicht das Auffinden einer einzigen optimalen Lösung. Eine solche Umformulierung ist aber nur dann sinnvoll, wenn aus der Problemformulierung eine einzige Zielfunktion erstellt werden kann. Darüber hinaus bedeutet das Setzen von Beschränkungen von Entwurfskriterien, dass diese beschränkten Kriterien möglicherweise nicht vollständig optimiert werden. Ein weiterer Ansatz zur Lösung mehrkriterieller Optimierungsprobleme besteht darin, mögliche Kompromisse zwischen den einzelnen betrachteten Kriterien zu finden. Wir haben evolutionäre Algorithmen im Hinblick auf das Auffinden solcher Kompromisse zwischen WCET, Codegröße und Energieverbrauch zur Übersetzungszeit untersucht. Diese Algorithmen produzieren jedoch nur Lösungen für kleine Benchmarks. Solche Ansätze werden für große Benchmarks undurchführbar aufgrund zeitaufwändiger WCET- und Energieverbrauchsanalysen, die während der evolutionären Algorithmen durchgeführt werden. Wir haben ein auf maschinellem Lernen basierendes Modell entwickelt, das WCET und Energieverbrauch zur Übersetzungszeit vorhersagt. Während der Ausführung evolutionärer Algorithmen haben wir anschließend die zeitaufwändigen Analysen von Entwurfskriterien durch diese schnelleren Vorhersagen ersetzt. Wir haben weiterhin einen neuartigen Ansatz zur Reduktion des Suchraums vorgestellt, der überzählige Dimensionen aus dem Suchraum entfernt. Evolutionäre Algorithmen, die auf dem reduzierten Suchraum ausgeführt werden, erfordern weniger teure Auswertungen der Entwurfskriterien. Die Kombination des Vorhersagemodells und der Reduktionstechnik hat für die meisten Benchmarks die Qualität der Lösungen beibehalten oder sogar verbessert, im Vergleich zu evolutionären Algorithmen, die auf dem reduzierten Suchraum aber jedoch ohne Vorhersagen ausgeführt wurden. Zum Lösen eines mehrkriteriellen Optimierungsproblems zur Übersetzungszeit können wir somit evolutionäre Algorithmen beschleunigen und auch die Qualität der Lösungen verbessern, indem wir Suchräume reduzieren und zeitaufwändige Entwurfskriterien vorhersagen.
Publications
- “Multi-Criteria Compiler-Based Optimization of Hard Real-Time Systems”. In: 21st International Workshop on Software and Compilers for Embedded Systems (SCOPES). ACM, May 2018
Kateryna Muts, Arno Luppold, and Heiko Falk
(See online at https://doi.org/10.1145/3207719.3207730) - “Compiler-Based Code Compression for Hard Real-Time Systems”. In: 22nd International Workshop on Software and Compilers for Embedded Systems (SCOPES). ACM, May 2019
Kateryna Muts, Arno Luppold, and Heiko Falk
(See online at https://doi.org/10.1145/3323439.3323976) - “Compiler-based WCET prediction performing function specialization”. In: 23rd International Workshop on Software and Compilers for Embedded Systems (SCOPES). ACM, May 2020
Kateryna Muts and Heiko Falk
(See online at https://doi.org/10.1145/3378678.3391879) - “Multi-Criteria Function Inlining for Hard Real-Time Systems”. In: 28th International Conference on Real-Time Networks and Systems (RTNS). ACM, June 2020
Kateryna Muts and Heiko Falk
(See online at https://doi.org/10.1145/3394810.3394819) - “Predicting Objectives on a Reduced Search Space of Multiobjective Function Inlining”. In: 24th International Workshop on Software and Compilers for Embedded Systems (SCOPES). ACM, Nov. 2021
Kateryna Muts and Heiko Falk
(See online at https://doi.org/10.1145/3493229.3493303) - “Predicting Worst-Case Execution Times During Multi- Criterial Function Inlining”. In: 7th International Conference on Machine Learning, Optimization, and Data Science (LOD). Springer International Publishing, Oct. 2021
Kateryna Muts and Heiko Falk
(See online at https://doi.org/10.1007/978-3-030-95467-3_21)
