Graphbasierte Prozedurale Abstraktion

Aufgrund gesunkener Preise für Hauptspeicher sind heutzutage bereits die

PC-Einsteigermodelle mit mehr als 1 GB RAM ausgestattet. Neben den PC und

NetBook-Systemen gibt es aber eine große Anzahl von Computersystemen,

bei denen Speicher nur in sehr begrenztem Umfang zur Verfügung

steht. Zu diesen Systemen gehören eingebettete Systeme, wie wir sie in

Haushaltsgegenständen wie Waschmaschinen, Fernsehern oder Kühlschränken

finden. Um die Energiekosten, den Platzbedarf und die Herstellungskosten

so gering wie möglich zu halten, wird bei diesen Systemen nur

sehr wenig Speicher verbaut. Wird Software für diese Systeme entwickelt,

so ist eine der Hauptaufgaben, den Speicherbedarf klein zu halten.

Der Beitrag dieser Arbeit besteht darin, Code-Redundanzen aus dem Programm

zu entfernen und somit den benötigten Speicherbedarf für das Programm

zu minimieren. Dazu nutzen wir Graphminer, um nach häufigen Teilen

zu suchen, und optimieren diese für unser Aufgabengebiet. Graphminer

werden unter anderem bereits für die computergestützte Medikamentenforschung

genutzt. Unser Algorithmus ist dabei in der Lage, Instruktionen, die

vom Übersetzer zur besseren Ausnutzung der Systemressourcen in eine andere

Reihenfolge gebracht wurden, als semantisch äquivalent zu erkennen

und zusammen zufassen. Auch die Verwendung unterschiedlicher Register

stellt für unseren Ansatz kein Hindernis dar.

Wir haben durch Untersuchungen problemspezifischer Rahmenbedingungen

allgemein nicht effizient lösbare Probleme wie die maximale Cliquenberechnung

und die Suche nach häufigen Fragmenten in gerichteten Graphen

derart optimiert, dass diese Probleme auf heutzutage üblichen PCs mit nur

geringem Speicherverbrauch in wenigen Minuten gelöst werden können.

Mit dem von uns entwickelten Ansatz zur graphbasierten prozeduralen Abstraktion

sind wir den bisherigen Standardverfahren überlegen. So ist es

uns möglich, im Schnitt 20% des Programm-Codes zu entfernen, ohne die

Semantik des Programms zu verändern. In Ausnahmefällen ist es uns sogar

möglich, das Programm um fast 50% zu verkleinern. Damit erzeugen wir mit

unserem Algorithmus zwischen 4- bis 13-mal kleinere Programme, als sonst

zur Zeit möglich ist. Die stärkere Reduzierung der Code-Größe führt dabei

zu einer 50% höheren Laufzeit als bei den bisherigen Verfahren.