Index of /anton/lvas/effizienz-aufgabe15

Abgabe Effiziente Programme WS14/15

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.

Erlaubte Optimierungen

Auch wenn der Fokus bei der Vorlesung nicht bei effizienten Algorithmen lag, dürfen Sie auch Algorithmen und Datenstrukturen ändern (damit erübrigt sich die Frage, ob eine Änderung den Algorithmus ändert oder nicht). Das ist bei der 2015er-Aufgabe sehr sinnvoll.

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. [Bei der 2015er-Aufgabe sehe ich da allerdings keinen Sinn].

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.

Vorgegebene Aufgabe: Forth-Dictionary

Das vorgegebene Programm (Paket) implementiert eine sehr vereinfachte Form des Forth-Dictionary-Mechanismus in C. Die Beschreibung aus dem Kommentar am Anfang von ep15.c:

   Input: A sequence of the following:
   
   1) '\n' (line feed) followed by a character identifying a wordlist
      followed by a name: define the name in the wordlist
   2) '\t' (tab) followed by a sequence of characters:
      set the search order; the bottom of the search order is first,
      the top last
   3) ' ' (space) followed by a name:
      look up the name in the search order; there may be names that are
       not in the search order.

   Names do not contain characters <= ' ', and these characters are
   also not used for identifying wordlists.

   To verify that these things work, every defined word gets a serial
   number (starting with 1) and a hash is computed across all found
   words

Mit make wird das Programm gebaut, mit dem Referenz-Input laufen gelassen, und gemessen. Dabei kommt auf der g0 folgendes heraus:

>make
perf stat -e cycles:u -e instructions:u -e branch-misses:u -e L1-dcache-load-misses -e L1-dcache-loads ep15 cross.input
1ae56547f8865909

 Performance counter stats for 'ep15 cross.input':

      164587102  cycles                   #      0.000 M/sec
       80381803  instructions             #      0.488 IPC  
         518240  branch-misses            #      0.000 M/sec
       21370347  L1-dcache-load-misses    #      0.000 M/sec
       45603137  L1-dcache-loads          #      0.000 M/sec

    0.059134123  seconds time elapsed

Das sind die Basiswerte, mit denen Sie Ihre Lösung vergleichen sollten (am Besten, indem Sie einen Speedup-Faktor angeben). 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/2015w 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 ]

Termin/Anmeldung zur Präsentation

Die Termine sind:

8.1., 15.1., 22.1.

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 2015/2016 ist im Normalfall eine Gruppengröße von 3 Personen vorgesehen. Wenn Sie eine andere Gruppengröße bilden wollen, kontaktieren Sie mich. Beachten Sie allerdings, dass die Anzahl der Präsentationstermine begrenzt ist, sodass wir nur eine begrenzte Zahl kleinerer Gruppen akzeptieren können.

Anton Ertl

Name	Last modified	Size

Parent Directory		-
cross.input	2015-12-03 11:02	110K
Makefile	2015-12-03 18:17	271
ep15.c	2015-12-03 18:52	4.3K
ep15.tar.gz	2015-12-03 18:53	34K
ep15	2015-12-03 18:53	9.4K
ep15.fs	2016-01-30 18:17	2.2K

Apache/2.4.62 (Debian) OpenSSL/3.0.15 Server at www.complang.tuwien.ac.at Port 80