Prozedurale Abstraktion kanonischer Fragmente

Student:Armin Heckmann
Title:Prozedurale Abstraktion kanonischer Fragmente
Type:study thesis
Advisors:Dreweke, A.; Philippsen, M.
State:submitted on June 1, 2007
Prerequisits:

Auf eingebetteten Systemen ist Arbeitsspeicher (RAM) eine chronisch knappe Ressource. Aus diesem Grund ist es wichtig, möglichst kompakten Programmcode zu erzeugen. Durch Assemblercode ist es theoretisch möglich, hoch optimierten und kompakten Code zu programmieren, jedoch erkauft man sich damit die bekannten Probleme in der Wartung, Pflege und Portierung des Codes. Die am Lehrstuhl entwickelte prozedurale Abstraktion[1] ist eine post link-time Optimierung die gemeinsame Code-Sequenzen in eine eigene Funktion ausgliedert und durch einen Aufruf dieser Funktion ersetzt. Somit ist es möglich, Hochsprachen wie C/C++ einzusetzen und trotzdem sehr kompakten Code zu erzeugen.

Topic:

Das am Lehrstuhl für Informatik 2 entwickelte Programmwerkzeug shrink[2] verringert durch prozedurale Abstraktion den benötigten Speicherverbrauch von Programmen. Zur identifikation von häufigen Assembler Fragmenten wird die auch am Lehrstuhl für Informatik 2 entwickelte "Graph Data Mining" Suite ParSeMis[3] verwendet. In einer ersten Projektstufe wurden nur vollkommen identische Fragmente in neue Prozeduren ausgelagert. In einem zweiten Schritt soll im Rahmen der Studienarbeit dieser Ansatz auf kanonische Instruktionsfolgen erweitert werden. Kanonische Instruktionen sind Instruktionen die anstatt der konkreten Registernamen ein einziges symbolisches Register (R) verwenden:

ARM Assembler Darstellung:
add r1, r2, #4
sub r3, r4, r1
mul r6, r3, #5

Kanonische Darstellung:
add R, R, #4
sub R, R, R
mul R, R, #5

Dazu sind folgende Meilensteine zu erreichen:

  • Es ist zu untersuchen, ob alle vom Miner als gleich identifizierten Einbettungen so modifiziert werden können, dass sie gemeinsam ausgelagert werden können, oder ob Einbettungen eines Fragmentes in mehrere Gruppen zerfallen die dadurch separat ausgelagert werden müssen.
  • Diese gemeinsam auslagerbaren Einbettungen sollen dann mit der geeigneten Abstraktion (CrossJump oder Funktionsaufruf mit und ohne Schattenstapel) ausgelagert werden. Hierbei muss beachtet werden, dass Registerumbenennungen und -permutationen im Vorfeld der Abstraktion durchgeführt werden, um so unterschiedliche häufige Fragmente auf eine gemeinsame Form zurückzuführen. Als Startpunkt hierfür soll [4],[5] dienen.
  • Es soll eine Kostenfunktion implementiert werden, die die Besonderheiten der Extraktion von kanonisch gleichen Einbettungen berücksichtigt (Kosten für Registerumbenennungen und -permutationen, Aufteilung der Einbettungen eines Fragments in mehrere Gruppen, ...).
  • Die entwickelten Verfahren sollen (z.B. anhand ausgewählter Programme der MI-Bench[6]) evaluiert werden.
  • Optional: Es ist zu untersuchen, ob weitere kanonische Formen den Miningprozess oder das Auslagern positiv beeinflussen können.

Literatur
[1] Saumya Debray, William Evans, Robert Muth: Compiler Techniques for Code Compression, 1999
[2] Dreweke, Alexander; Wörlein, Marc; Schell, Dominic; Meinl, Thorsten; Fischer, Ingrid; Philippsen, Michael: Graph-Based Procedural Abstraction. 2006
[3] Wörlein, Marc; Meinl, Thorsten; Fischer, Ingrid; Philippsen, Michael: A quantitative comparison of the subgraph miners MoFa, gSpan, FFSM, and Gaston. In: Jorge, Alipio; Torgo, Luis; Brazdil, Pavel (Hrsg.): Knowledge Discovery in Database: PKDD 2005 (9th European Conference on Principles and Practices of Knowledge Discovery in Databases Porto, Portugal 2005-10-03 - 2005-10-07). Berlin: Springer, 2005, S. 392-403
[4] Saumya Debray, William Evans, Robert Muth, and Bjorn De Sutter. Compiler techniques for code compaction. ACM Trans. Program. Lang. Syst., 22(2):378-415, 2000.
[5] Keith Cooper, Nathaniel McIntosh. Enhanced Code Compression for Embedded RISC Processors. In Proc. ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), S. 139-149, Atlanta, GA, USA, Mai 1999
[6] www.eecs.umich.edu/mibench/

watermark seal