Generation and Optimization of Real-Time Code for Embedded Multiprocess and Multiprocessor Systems
Final Report Abstract
Harte Echtzeitsysteme müssen beweisbar vorgegebene Zeitschranken einhalten. Das Einhalten aller dieser sogenannten Deadlines ist somit eine funktionale Eigenschaft des Systems. In modernen harten Echtzeitsystemen konkurrieren mehrere parallel laufende Tasks auf mehreren Prozessoren um Ressourcen wie Speicherzugriffe und Rechenzeit. Diese Tasks kommen nach beliebigen Anregungsmustern zur Ausführung und unterliegen oftmals allesamt den zuvor genannten Zeitschranken. Ein System wird als „planbar“ bezeichnet, wenn beweisbar alle Tasks sämtliche Zeitschranken unter allen Umständen einhalten. Üblicherweise wird ein System zunächst entworfen und implementiert. Jeder einzelne Task des fertigen Systems wird dann mit speziellen Werkzeugen hinsichtlich seines schlimmstmöglichen Laufzeitverhaltens analysiert. Die Ergebnisse dieser Analyse werden dann schließlich verwendet, um die Planbarkeit des Gesamtsystems zu zeigen oder zu widerlegen. Dabei sind Tasks hier nur noch unveränderliche Black Boxes. Stellt sich ein System als nicht planbar heraus, kann ein Task auf dieser Ebene nicht optimiert werden. Statt dessen müssen Ausführungshäufigkeiten der Tasks oder die zugrundeliegende Hardware-Architektur angepasst werden. Beides ist in der Praxis jedoch häufig unpraktikabel oder sehr teuer. Compiler können die Laufzeit einzelner Tasks erheblich optimieren. Vor diesem Projekt verfügten diese allerdings nicht über die nötigen Modelle, um den Einfluss ihrer Optimierungen auf die Planbarkeit des Gesamtsystems einschätzen zu können. Ressourcen wie kleine aber schnelle Scratchpad Speicher konnten daher nicht effizient genutzt werden. Optimierungen, um die Planbarkeit zu verbessern, erfolgen statt dessen weitestgehend manuell per Trial und Error-Verfahren durch den Programmierer. Im Rahmen dieses Projekts wurden die Planbarkeitsanalyse auf System-Ebene und die Optimierung von Programm-Code auf Compiler-Ebene miteinander vereint. Es wurde ein Optimierungsmodell basierend auf ganzzahlig-linearer Optimierung (Integer-Linear Programming, ILP) entworfen. Dieses ermöglicht dem Compiler, gezielt die Planbarkeit des Systems zu optimieren. Dies funktioniert sowohl für Multiprozess- als auch für Multiprozessor-Systeme. Das ILP-Modell garantiert dabei eine Optimalität im Rahmen der mathematischen Darstellung. Als alternatives Verfahren wurde weiterhin ein Optimierungsmodell auf Basis eines genetischen Algorithmus entworfen. Die Methoden wurden innnerhalb des WCET-Aware C Compiler (WCC) des Antragstellers implementiert und für die Plattformen Infineon TriCore sowie ARM7TDMI evaluiert. Die Evaluierung ergab, dass die genetischen Algorithmen zu rechenaufwendig sind, um damit komplexe Mehrprozess- und Mehrprozessor-Systeme zu optimieren. Die ILP-basierten Ansätze hingegen weisen einen akzeptablen Rechenaufwand auf. Da innerhalb des ILP-basierten Ansatzes nur wenige rechenintensive Analysen notwendig sind, eignet sich dieser Ansatz sehr gut zur planbarkeitsorientierten Optimierung auch relativ komplexer Systeme. Insbesondere bei Multiprozess-Systemen, die gleichzeitig auf mehreren Prozessorkernen arbeiten, zeigte sich bei speicherbasierten Optimierungsmethoden mit dem entworfenen ILP-Modell ein massives Verbesserungspotential im Hinblick auf die Planbarkeit.
Publications
- “Schedulability-Oriented WCET-Optimization of Hard Real- Time Multitasking Systems”. In: 8th Junior Researcher Workshop on Real-Time Computing (JRWRTC). 2014, pp. 9–12
Arno Luppold and Heiko Falk
- “Code Optimization of Periodic Preemptive Hard Real-Time Multitasking Systems”. In: 18th International Symposium on Real-Time Distributed Computing (ISORC). 2015, pp. 35–42
Arno Luppold and Heiko Falk
(See online at https://doi.org/10.1109/ISORC.2015.8) - “Schedulability aware WCET-Optimization of Periodic Preemptive Hard Real-Time Multitasking Systems”. In: 18th International Workshop on Software & Compilers for Embedded Systems (SCOPES). 2015, pp. 101–104
Arno Luppold and Heiko Falk
(See online at https://doi.org/10.1145/2764967.2771930) - “Cache-Aware Instruction SPM Allocation for Hard Real-Time Systems”. In: 19th International Workshop on Software & Compilers for Embedded Systems (SCOPES). 2016, pp. 77–85
Arno Luppold, Christina Kittsteiner, and Heiko Falk
(See online at https://doi.org/10.1145/2906363.2906369) - “Practical Challenges of ILP-based SPM Allocation Optimizations”. In: 19th International Workshop on Software & Compilers for Embedded Systems (SCOPES). 2016, pp. 86–89
Dominic Oehlert, Arno Luppold, and Heiko Falk
(See online at https://doi.org/10.1145/2906363.2906371) - “Bus-aware Static Instruction SPM Allocation for Multicore Hard Real-Time Systems”. In: 29th Euromicro Conference on Real-Time Systems (ECRTS). 2017
Dominic Oehlert, Arno Luppold, and Heiko Falk
(See online at https://dx.doi.org/10.4230/LIPIcs.ECRTS.2017.1) - “Schedulability-Aware SPM Allocation for Preemptive Hard Real-Time Systems with Arbitrary Activation Patterns”. In: Design, Automation and Test in Europe (DATE). 2017, pp. 1074–1079
Arno Luppold and Heiko Falk
