![[ICO]](/icons/blank.gif){kind=icon}
![[PARENTDIR]](/icons/back.gif){kind=icon}
![[ ]](/icons/unknown.gif){kind=icon}
![[ ]](/icons/compressed.gif){kind=icon}
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 18-minütige Präsentation inkl. Aufbau und Fragen 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 unerwartet wenig bringen.
An sich muss das optimierte Programm für die gleiche Eingabe die gleiche Ausgabe produzieren wie das Originalprogramm, insbesondere für die gemessenen Testfälle. Sie können Sich auch überlegen, bestimmte Eingaben nicht korrekt zu verarbeiten, müssen das dann aber dokumentieren und begründen, warum Sie meinen, dass das sinnvoll ist.
Sie dürfen auch die Programmiersprache ändern.
Ausgeschlossen sind allerdings Optimierungen zu Trivialprogrammen
(z.B. if Eingabe=Benchmarkeingabe then print
Benchmarkausgabe), da dabei zuwenig zu lernen ist.
Das vorgegebene Programm ist mittels flex geschrieben, und ist im Prinzip nur der Scanner aus dem Übersetzerbau-Beispiel vom SS 2013; drumherum noch ein Hauptprogramm, das eine Checksumme berechnet (um die Korrektheit zu prüfen). Es kann auf der g0 wie folgt gebaut und die Messwerte auf der Testeingabe ermittelt werden:
tar xfz /nfs/unsafe/httpd/ftp/pub/anton/lvas/effizienz-aufgabe13/ep13.tar.gz cd ep13/ makeSie können versuchen, das vorgegebene Programm direkt zu optimieren (da sehe ich aber wenige Eingriffsmöglichkeiten), das von flex generierte Programm zu optimieren, oder Sie schreiben ein bezüglich I/O-Verhalten äquivalentes Programm (sollte aber auch bei anderen Eingaben äquivalent sein), und optimieren das ggf. noch weiter. Wenn Sie das generierte Programm optimieren, ist es wohl am sinnvollsten, bei den Ineffizienzen anzufangen, die dadurch bedingt sind, dass flex das von lex vorgegebene Interface zum I/O-Teil und zum Hauptprogramm einhalten muss. Die von mir erhaltene Ausgabe und die Messwerte auf dem vorgegebenen Programm sind:
346a1f5bce725194
Performance counter stats for 'scanner /nfs/unsafe/httpd/ftp/pub/anton/lvas/effizienz-aufgabe13/llinput':
4431395680 cycles
6564685892 instructions # 1.48 insn per cycle
1855785 L1-dcache-load-misses
LLC-load-misses
38791797 branch-misses
1.356217363 seconds time elapsed
Das sind die Basiswerte, mit denen Sie Ihre Lösung vergleichen
sollten. Relevant sind vor allem die Zyklen, die anderen Werte können
aber zur Erklärung der gemessenen Zyklen dienen.
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/2016w 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 | WS10/11 | WS11/12 | WS12/13 | WS13/14 | WS14/15 | WS15/16 | WS16/17 | WS17/18 ]
| Name | Last modified | Size | Description |
|---|---|---|---|---|
| Parent Directory | - | ||
| llinput.bz2 | 2013-11-15 18:48 | 28M | |
| ep13.tar.gz | 2018-11-21 18:58 | 1.2K | |