UnivIS
Informationssystem der Friedrich-Alexander-Universität Erlangen-Nürnberg © Config eG 
FAU Logo
  Sammlung/Stundenplan    Modulbelegung Home  |  Rechtliches  |  Kontakt  |  Hilfe    
Suche:      Semester:   
 Lehr-
veranstaltungen
   Personen/
Einrichtungen
   Räume   Forschungs-
bericht
   Publi-
kationen
   Internat.
Kontakte
   Examens-
arbeiten
   Telefon &
E-Mail
 
 
 Darstellung
 
Druckansicht

 
 
Einrichtungen >> Technische Fakultät (TF) >> Department Informatik (INF) >> Lehrstuhl für Informatik 2 (Programmiersysteme) >>
Graphbasierte Prozedurale Abstraktion

Als besonders dringend erscheint uns gegenwärtig die Verbesserung der Programmierwerkzeuge für eingebettete Systeme. Solche Systeme werden heutzutage zu oft noch sehr maschinennah programmiert. Das inzwischen bei der Programmierung von Arbeitsplatzrechnern übliche Abstraktions- und Komfortniveau (Objektorientierung, automatische Speicherbereinigung, Ausnahmebehandlung, Parallelität, Aspektorientierung, Komponenten, ...) scheint im Bereich der eingebetteten Systeme noch in weiter Ferne, wodurch Portabilität, Robustheit und Wartbarkeit der erstellten Software erheblich beeinträchtigt wird. Dies ist ein erhebliches volkswirtschaftliches Problem, das gerade auch deshalb bedeutsam ist, weil Europa auf diesem Feld nicht von Amerika dominiert wird. Fernziel muss es daher sein, das Abstraktionsniveau bei der Programmierung eingebetteter Systeme schrittweise zu erhöhen, indem Optimierungstechniken entwickelt werden, die trotz des erhöhten Abstraktionsniveaus "kleinen" Code garantieren.

Neben der offensichtlichen Frage, wie die bekannten Optimierungstechniken auf die Code-Größe wirken, drängen sich neue Einzelfragen auf. Während der RAM-Bedarf einer Applikation auf Desktop-Rechnern kaum eine Rolle spielt, ist dieser für eingebettete Systeme oft essentiell. Objektorientierter - vor allem bibliotheksbasierter - Code bietet ein erhebliches, bislang ungenutztes Potential für prozedurale Abstraktion zur Code-Verkleinerung. Neben der Code-Größe kommt auch dem Aspekt der Energie-Effizienz eine wachsende Bedeutung als Zielgröße der Code-Optimierung zu. Hier muss der Übersetzer, ggf. im Zusammenspiel mit dem Betriebssystem, optimieren bzw. auf die Hardware-Parameter einwirken. Die Behandlung der nicht-uniformen Speicherzugriffshierarchie, die in verteilten Systemen neben Registern, Cache und Hauptspeicher um eine weitere Leistungsebene vertieft ist, stellt auch bei eingebetteten Systemen eine Herausforderung dar, da z.B. Flash-Speicher zu berücksichtigen sind. Können eingebettete Systeme (ebenso verteilte Systeme) - der Tradition von Desktop-Prozessoren folgend - auch weiterhin mit der Illusion eines transparenten Zugriffs programmiert werden? Kann man durch statische Analyse Informationen über bestehende Lokalitätsbeziehungen zwischen Daten extrahieren? Welche Optimierungen sind dann möglich? Profitieren statische Analyse und Laufzeitmechanismen von einander? Wie können durch Programmanalyse Pre-Fetch- und Post-Store-Kommandos im generierten Code erzeugt werden, durch die Cache-Effekte überdeckt, Wartezeiten vermieden oder Energie gespart werden?

Eine gängige Methode zur Code-Größenverkleinerung ist die Prozedurale Abstraktion (PA): gleiche Code-Abschnitte im Programm werden gesucht und daraus eine einzige neue Prozedur erzeugt. Die Code-Abschnitte werden durch Aufrufe der neu erzeugten Prozedur ersetzt, wodurch die Redundanz innerhalb eines Programms und somit seine Größe reduziert wird. Redundanz entsteht durch die Art und Weise, wie Übersetzer Code generieren (z.B. durch Schablonen). Die bisherigen PA-Ansätze betrachten das Programm als Folge von Instruktionen und suchen nach exakt gleichen Teilfolgen. Sind allerdings Instruktionen innerhalb einer Teilfolge vertauscht, wird sie nicht als weitere Instanz der gesuchten Folge erkannt. Somit fallen potentielle Code-Fragmente für die PA aus der Analyse heraus und das Ergebnis wird suboptimal. Der am Lehrstuhl untersuchte Ansatz löst dieses Problem indem die Instruktionen eines Grundblocks statt in einer Folge in einen Datenflussgraphen (DFG) umgesetzt werden. Ein Graph-Mining-Werkzeug sucht in den DFGs nach gemeinsamen Fragmenten in ARM Assembler-Code, der auf eingebetteten Systemen weit verbreitet ist. In Kooperation mit dem Projekt ParSeMiS, das sich mit der Optimierung von Graph-Minern befasst, werden auch die für PA spezifischen Probleme beim Graph-Minen angegangen. Im Berichtszeitraum wurden die Analysen zur korrekten Rekonstruktion des Datenflussgraphen verfeinert. Eine möglichst genaue Rekonstruktion erhöht das Einsparungspotential im Vergleich zu den herkömmlichen sequentiellen Verfahren. Des Weiteren wurden verschiedene Auslagerungsmethoden optimiert. Diese dienen dazu, die von ParSeMiS als häufig eingestuften Code-Fragmente herauszuziehen und damit das Programm zu verkleinern. Die optimierten Auslagerungsmethoden zeichnen sich vor allem dadurch aus, dass sie möglichst kosteneffizient semantisch gleiche Fragmente vereinheitlichen.

Projektleitung:
Prof. Dr. Michael Philippsen

Beteiligte:
Dr.-Ing. Alexander Dreweke, Dipl.-Inf. Marc Wörlein, Dipl.-Inf. Tobias Werth

Laufzeit: 1.4.2006 - 31.12.2010

Kontakt:
Philippsen, Michael
Telefon +49-9131-85-27625, Fax +49-9131-85-28809, E-Mail: michael.philippsen@fau.de
UnivIS ist ein Produkt der Config eG, Buckenhof