Index of /anton/lvas/effizienz-aufgabe16

Abgabe Effiziente Programme WS16/17

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 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).

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.

Vorgegebene Aufgabe: Primzahlenzwillinge zählen

Das vorgegebene Programm erzeugt mit dem Algorithmus "Sieb des Erathostenes" die Primzahlen und zählt dann die Primzahlenzwillinge (zwei Primzahlen mit der Differenz 2). 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 cycles:k -e instructions:u -e branch-misses -e L1-dcache-load-misses:u -e L1-dcache-store-misses:u -e LLC-loads:u -e LLC-stores:u -e LLC-load-misses:u -e LLC-store-misses:u pi2 1000000000
3424506 Primzahl-Zwillinge <= 1000000000

 Performance counter stats for 'pi2 1000000000':

    36853691835  cycles                   #      0.000 M/sec
      460823637  cycles                   #      0.000 M/sec
    16409716977  instructions             #      0.880 IPC  
      105631399  branch-misses            #      0.000 M/sec
      336240788  L1-dcache-load-misses    #      0.000 M/sec
     6433672819  L1-dcache-store-misses   #      0.000 M/sec
      234126762  LLC-loads                #      0.000 M/sec
      780718162  LLC-stores               #      0.000 M/sec
      123683248  LLC-load-misses          #      0.000 M/sec
      752737955  LLC-store-misses         #      0.000 M/sec

   11.097182413  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 (und zwar die Summe der User-Zyklen (cycles:u) und Kernel-Zyklen (cycles:k), die anderen Werte können aber zur Erklärung der gemessenen Zyklen dienen. Interessant ist auch der Speicherverbrauch.

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 ]

Termin/Anmeldung zur Präsentation

Die Termine sind:

13.1., 20.1., 27.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 2016/2017 ist im Normalfall eine Gruppengröße von 2 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		-
Makefile	24-Nov-2016 18:52	277
pi2	24-Nov-2016 18:15	8.1K
pi2.c	24-Nov-2016 14:46	1.5K

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