Superblock-basierte Quellcodeoptimierungen zur WCET-Reduktion

Das Konzept der

Superblöcke

wurde auf dem Gebiet der Compileroptimierungen in der Vergangenheit bereits erfolgreich zur Optimierung der

ACET

(Average Case Execution Time) verwendet. Superblöcke sind dabei spezielle Ketten von Basisblöcken, die es erleichtern, Optimierungen über Basisblockgrenzen anzuwenden und somit ein höheres Optimierungspotential zu schaffen. In der vorliegenden Arbeit wurde dieses Konzept zum ersten Mal zur Reduktion der

WCET

(Worst Case Execution Time) von Programmen für eingebettete Systeme ausgenutzt. Die WCET ist im Kontext der eingebetteten Systeme eine wichtige Metrik, da viele eingebettete Systeme unter Echtzeitbedingungen arbeiten müssen und hierzu eine sichere obere Schranke für die Laufzeit eines Programms unabdingbar ist.

Die vorgestellte Superblockbildung baut auf einem neuartigen Trace-Selektions-Algorithmus auf, der WCET-Daten auswertet. Außerdem wurde das Konzept der Superblöcke zum ersten Mal auf der Quellcodeebene angewandt. Auf diese Weise findet die Optimierung früher statt, so daß eine größere Anzahl nachfolgender Optimierungen von der erzielten Umstrukturierung profitieren kann. Weiterhin wurden die klassischen Optimierungen

Common Subexpression Elimination (CSE)

und

Dead Code Elimination (DCE)

an die Anwendung in Quellcode-Superblöcken angepasst. Mit diesen Techniken wurde auf einer Testmenge von 55 bekannten Standard-Benchmarks eine durschnittliche WCET-Reduktion von bis zu 10.2% erzielt.