Index of /anton/lvas/effizienz-aufgabe13

Abgabe Effiziente Programme WS13/14

Sie können ein beliebiges Beispiel wählen.

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 unerwartet wenig bringen.

Vorgegebene Aufgabe: ...

Der Hintergrund dieser Aufgabe ist die Behauptung, dass bei manchen Compilern die meiste Zeit im Scanner verbracht wird, weil man im Scanner Aufwand für jedes einzelne Zeichen betreiben muss, während die Anzahl der Lexeme (für den Parser) oder Baumknoten (für die semantische Analyse und Codeerzeugung) geringer ist. Daher geht es in dieser Aufgabe darum, einen Scanner zu optimieren.

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/
make

Sie 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':

     4202098266  cycles                   #      0.000 M/sec
     6464246074  instructions             #      1.538 IPC  
       14208976  L1-dcache-load-misses    #      0.000 M/sec
         735779  LLC-load-misses          #      0.000 M/sec
       38730919  branch-misses            #      0.000 M/sec

    1.262339639  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/2013w 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 ]

Termin/Anmeldung zur Präsentation

Die Termine stehen noch nicht fest, Sie koennen sich noch nicht anmelden. Die Terminvergabe erfolgt, über unser Web-Anmeldesystem. Und zwar müssen Sie dabei folgendermaßen vorgehen:

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.

Im WS 2013/2014 ist im Normalfall eine Gruppengröße von 3 Personen vorgesehen. Wenn Sie eine andere Gruppengröße bilden wollen, schreiben Sie an studass@complang.tuwien.ac.at. Beachten Sie allerdings, dass die Anzahl der Termine begrenzt ist, sodass wir nur eine begrenzte Zahl kleinerer Gruppen akzeptieren können.

Anton Ertl

Name	Last modified	Size

Parent Directory		-
ep13.tar.gz	18-Nov-2013 17:31	1.2K
llinput	21-Nov-2018 19:05	85M
llinput.bz2	15-Nov-2013 18:48	28M

Apache/2.2.22 (Debian) DAV/2 mod_fcgid/2.3.6 PHP/5.4.36-0+deb7u3 mod_python/3.3.1 Python/2.7.3 mod_ssl/2.2.22 OpenSSL/1.0.1e mod_perl/2.0.7 Perl/v5.14.2 Server at www.complang.tuwien.ac.at Port 80