Abgabe Effiziente Programme WS10/11

Wer nichts anderes vorhat, kann die unten vorgegebene Aufgabe für dieses Semester wählen.

Natürlich können Sie, wenn Sie wollen, auch die Implementierung eines anderen Problems optimieren; allerdings hat das einige Nachteile: Sie müssen einen Teil der Zeit Ihrer Präsentation für die Erklärung des Problems und des Algorithmus aufwenden, und die Ergebnisse sind nicht direkt vergleichbar. Der Vorteil (vor allem, wenn Sie einen späteren Termin wählen) ist, dass Sie nicht das wiederholen, was andere gemacht haben, oder ein langsameres Programm präsentieren.

Bereiten Sie eine 15-18-minütige Präsentation vor (am besten machen Sie einen Probelauf, damit sich die Präsentation auch sicher in der Zeit ausgeht). Da Sie dabei nicht soviel Zeit haben wie ich in der Vorlesung, präsentieren Sie die meisten Schritte nur im Überblick (also eventuell nur, wieviel er gebracht hat), und nur ein paar besonders interessante Schritte mit mehr Details. Besonders interessant sind u.a. die Schritte, die unerwartet viel oder wenig bringen.

Vorgegebene Aufgabe: shortest-path

Hintergrund

Das Beispiel dreht sich um die Code-Erzeugung mittels dynamic programming. Das ist eine vereinfachte Form der Befehlsauswahl mit Hilfe von Baum-Grammatiken, die in der LVA Übersetzerbau gelehrt wird. Die Vereinfachung ist die, dass die Bäume zu strings degeneriert sind (also nicht mehr als ein Kind pro Knoten). Das Problem vereinfacht sich dadurch zu einem normalen shortest-path-Problem. Als Eingabe gibt es Sequenzen von Zwischencodebefehlen. Für die Codeerzeugung weiters wichtig sind die Zustände, die verschiedene Registerbelegungen repräsentieren. Für einen Zwischencodebefehl kann es verschiedene Maschinencodesequenzen mit unterschiedlichen Kosten geben, je nachdem in welchem Zustand die Sequenz anfängt und aufhört. Weiters gibt es noch die Möglichkeit, Code für einen Zustandswechsel zu erzeugen, ohne direkt beteiligtem Zwischencodebefehl (epsilon in der Grafik, noop in der Ausgabe). Die Ausgabe unseres Beispielprogramms ist aber nicht der Maschinencode, sondern nur eine Sequenz von Zwischencodebefehlen mit Zuständen (die man allerdings 1:1 zu Maschinencode expandieren kann). Die folgende Grafik illustriert das Problem:

Der obere Teil zeigt einen endlichen Automaten mit drei Zuständen, wobei die Zwischencode-Befehle Übergänge zwischen den Zuständen bewirken können, und jeder Übergang Kosten hat (z.B. hat der Epsilon-übergang von S0 nach S1 die Kosten 2). Der untere Teil zeigt das shortest-Path-Problem für die Code-Erzeugung für die Sequenz "iload iload", ausgehend von S2 und endend in S2. Vor dem ersten iload, zwischen den iloads, und nach dem zweiten iload kann der Zustand mit einem Epsilon-Übergang geändert werden. In unserem Beispiel ist eine optimale Lösung (rot), zunächst in den Zustand S0 überzugehen, und dann keine Zustandsänderung über Epsilon-Kanten mehr vorzunehmen (dünne Linien). Die roten Zahlen im unteren Beispiel sind die kumulierten Kosten eines optimalen Weges bis zum Zielpunkt (wird beim dynamic programming berechnet). Zusammenhang mit Baumgrammatiken: Die Zustände entsprechen Non-Terminale, die Befehle entsprechen Operatoren, die Epsilon-Kanten entsprechen Kettenregeln.

Genaue Aufgabe

Legale Eingaben: Binärdateien mit 32-bit-Werten. Sequenzen (basic blocks) werden mit -1 abgeschlossen und können maximal 128 Befehle lang sein. Befehle werden von Zahlen zwischen 0 und 347 repräsentiert.

Die Ausgabe muss natürlich auch korrekt sein, d.h., das Ergebnis muss bezüglich der Kosten optimal sein. Die genaue Sequenz muss nicht übereinstimmen, die ausgegebenen Sequenzen müssen nur (ebenfalls) optimal sein.

Sie können Ihr Programm (und Doku dazu, z.B. Ihre Präsentation) im Web veröffentlichen (wird nicht beurteilt), und zwar indem Sie auf /nfs/unsafe/httpd/ftp/pub/anton/lvas/effizienz-abgaben/2010w ein Verzeichnis anlegen und Ihre Dateien in diesem Verzeichnis ablegen.

Aufgaben vom [WS02/03 | WS03/04 | WS04/05 | WS05/06 | WS06/07 | WS07/08 | WS08/09 | WS09/10 ]

Termin/Anmeldung zur Präsentation

17.12., 14.1., 21.1., 28.1.

• Eines der Mitglieder der Gruppe klickt auf "Gruppe bilden" und trägt die Matrikelnummer seiner Partner ein (zur Gruppengröße siehe unten).
• Wenn die Gruppe gebildet ist, sollte eines der Gruppenmitglieder auf "Abgabegespräche anzeigen" und "Termine anzeigen" klicken, um sich dort zum Präsentationstermin anzumelden.

	Name	Last modified	Size	Description
	Parent Directory		-
	shortest-path.tar.gz	02-Dec-2010 22:23	203K