Abgabe Effiziente Programme WS12/12

Abgabe Effiziente Programme WS12/13

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: Hash-Tabelle

Beim vorgegebenen Programm wird eine Liste von Strings in eine Hash-Tabelle eingetragen, und dann wird jeder Name der Liste zehn mal nachgeschaut (in einer anderen Reihenfolge). Zur Überprüfung der Korrektheit wird noch bei jedem String in der Hash-Tabelle ein Wert (die Zeilennummer) gespeichert, und diese Werte werden zum Berechnen eines Ausgabewertes verwendet.

Hinweis: Durch die Anzahl der Strings passt die Hash-Tabelle nicht in den Cache, Optimierungen zur Reduzierung der Anzahl der zugegriffenen Cache Lines sollten also helfen; dabei wird man wahrscheinlich die Hash-Tabelle anders organisieren. Beim Einlesen der Dateien und bei der Hash-Funktion ist die Vorgabe wohl schon einigermassen effizient, auch wenn ich nicht ausschließen kann, dass man auch da noch etwas verbessern kann; allerdings sollten die Verbesserungen auch auf anderen Daten etwas bringen; eine Hash-Funktion, die "zufällig" für die Eingabedatei perfektes Hashing macht, entspricht nicht dieser Vorgabe.

Messen Sie den Effekt ihrer Optimierungsschritte auf die Laufzeit (Anzahl in Zyklen) mit der Benchmark-Eingabe 

perf stat -e cycles hash input input2
Der Basiswert, mit dem zu vergleichen ist, ist 7281M cycles, ermittelt wie folgt: 
gcc -O3 hash.c -o hash
perf stat -e cycles hash input input2
(Die 7281M cycles sind der Median aus 5 Läufen).

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/2012w ein Verzeichnis anlegen und Ihre Dateien in diesem Verzeichnis ablegen. Dort finden Sie auch meine Lösung.

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

Termin/Anmeldung zur Präsentation

Die Termine sind: 
11.1., 18.1., 25.1.
Die Terminvergabe erfolgt, über unser Web-Anmeldesystem. Und zwar müssen Sie dabei folgendermaßen vorgehen: Im WS 2012/2013 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
[ICO]NameLast modifiedSizeDescription
[DIR]Parent Directory  -  
[ ]a.out30-Nov-2012 18:39 9.3K 
[ ]hash01-Dec-2012 19:15 8.7K 
[TXT]hash.c30-Nov-2012 18:39 3.5K 
[ ]hash.zip01-Dec-2012 19:28 12M 
[ ]input22-Nov-2012 17:33 9.8M 
[ ]input222-Nov-2012 17:34 9.8M 
[ ]strings22-Nov-2012 17:30 9.8M 
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