Gefördert vom 
Bundesministerium 
für Bildung 
und Forschung
· Startseite

AP 8: Genauere numerische Analysen

Gefördert vom 
Bundesministerium 
für Bildung 
und Forschung

· Konsortium
· Ausgangspunkt
· Arbeitsplan
  · Arbeiten
  · Arbeitsteilung
  · AP 1
  · AP 2
  · AP 3
  · AP 4
  · AP 5
  · AP 6
  · AP 7
  · AP 8
  · AP 9
  · AP 10
  · Meilensteine
· Presse
· Impressum
· Intern
·

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

AbsInt
Angewandte Informatik GmbHDeutsches Forschungszentrum
für Künstliche Intelligenz GmbHTechnische Universität DresdenInstitut für Datentechnik
und Kommunikationsnetze
an der TU BraunschweigScopeSet Technology Deutschland GmbHaicas GmbHTechnische Universität MünchenSymtavision Stand: 08/2006