Problembeschreibung
Genaue Vorhersagen von Prozeßlaufzeiten erfordern
sehr präzise Analysen der Speicherzugriffe in den Programmen. Dazu
sind statische Programmanalysen zu entwickeln bzw. zu verbessern,
die Auskunft über Data-Alignments geben und Zuordnungen von
Speicherzugriffen auf Speicherblöcke und Cachezeilen liefern.
Bekannte Ansätze bei der Wertanalyse von Integervariablen
in Programmen sind in der Lage, sichere Intervalle für die Bereiche der
Werte an einem Programmpunkt zu bestimmen. Neuere Ansätze dagegen können
auch komplexere Beziehungen zwischen den Werten der Variablen ermitteln.
Von besonderem Interesse sind hier lineare Beziehungen, da gerade
bei Iterationen in Schleifen die zugegriffenen Speicherzellen sich
typischerweise in linearer Weise aus den Iterationsvariablen ergeben.
Lineare Beziehungen können zudem verwendet werden, um relative Zugriffe
auf lokale Variablen im Laufzeitkeller zu identifizieren. Dabei sollte
die Analyse nicht vereinfachend annehmen, daß Integervariablen beliebig
große ganze Zahlen enthalten. Vielmehr muß die reale Prozessorarithmetik
in Betracht gezogen werden, die typischerweise modular rechnet. Die deshalb
erforderliche Ermittlung modularer Eigenschaften erlaubt auch,
Alignment-Eigenschaften in Datensegmenten zu überprüfen.
Zielsetzung/Leistungsumfang
Das Ziel ist es, die Möglichkeiten von solchen Analysen
zur Verbesserung der Identifizierung von Speicherzugriffen innerhalb des
Analysewerkzeugs aiT
auszuloten. Dazu soll zuerst einmal das Verhalten des Analysators auf
bestimmten kritischen Beispielprogrammen näher betrachtet werden.
Anschließend soll ein Entwurf entwickelt werden, wie eine Analyse
modularer Arithmetik angemessen mithilfe des
PAG-Systems generiert werden
kann, sodaß eine Abschätzung der Worst-Case-Ausführungszeit davon
profitieren kann.
Die Analysen sollen im PAG-System zur Generierung von
Programmanalysen implementiert und dort mit den existierenden weiteren
Analysen integriert werden. Die erwarteten Vorteile sind nicht nur
genauere Vorhersagen, sondern auch eine deutliche Verbesserung der
Benutzerfreundlichkeit, da Informationen, die bisher von Benutzern
manuell zur Verfügung gestellt werden mußten, nun automatisch
ermittelt werden können.
AP 8.1: Einarbeitung in aiT
In diesem ersten Unterabschnitt soll die betreffende
Wissenschaftlerin sich mit dem aiT-Werkzeug zur Bestimmung von
Worst-Case-Ausführungszeiten vertraut machen. Dazu gehört, die
Infrastruktur kennenzulernen, die im Zusammenhang mit dem
Programmanalyse-Generator PAG bereits von Absint entwickelt wurde.
AP 8.2: Untersuchung der Zielprozessorarchitektur
aiTs genaue Laufzeitanalysen sind jeweils für einen
bestimmten Prozessor maßgeschneidert. In diesem zweiten Unterabschnitt
sollen die Besonderheiten des Instruktionssatzes dieses Prozessors
identifiziert sowie erste Ansätze zu deren Behandlung bei der
verbesserten Wertanalyse entwickelt werden.
AP 8.3: Sichtung der Anwendungsdomäne
Im dritten Unterabschnitt ist es erforderlich,
nicht nur die Charakteristik des Prozessors, sondern auch die
speziellen Eigenschaften typischer zu analysierender Anwendungen
festzustellen. Dazu soll ein geeignetes Bezugsanwendungspaket
zusammengestellt und im Hinblick auf das gegenwärtige Verhalten
des Analysators untersucht werden. Dabei sollen insbesondere
Stellen für Verbesserungsmöglichkeiten bei der Analyse herausgearbeitet
werden.
AP 8.4: Entwicklung der verbesserten Wert-Analyse
Nach den bisherigen Vorarbeiten soll nun ein Konzept
zur Verbesserung der aiT-Wertanalyse erarbeitet und prototypisch
realisiert werden. Dieses Konzept sollte in der Lage sein, modulare
lineare Beziehungen zwischen Variablen und Adressen zu identifizieren.
AP 8.5: Evaluierung der neuen Analyse
Die neuen Konzepte sollen nun anhand der
Bezugsanwendungen sowie möglicherweise weiteren Programmen
unter möglichst realistischen Bedingungen evaluiert werden.
Abhängigkeiten von anderen Arbeitspaketen
Import: AP 1, AP 5, AP 6, AP 7.
Export: AP 9.
Beteiligte Projektpartner
· TU München (verantwortlich)
· AbsInt
|