Index of /anton/lvas/effizienz-aufgabe07

Abgabe Effiziente Programme WS07/08

Sie können ein beliebiges Beispiel wählen.

Wer nichts anderes vorhat, soll dieses Jahr ein Programm schreiben, das Conway's Game of Life simuliert. Das (ineffiziente) Ausgangsprogramm und die Ausgangsstellung für den Benchmark ist unten in Einzeldateien und als Paket zu finden.

Das zu optimierende Programm ist dabei life, das aus den Quelldateien life.c life.h readlife.y gebaut wird. life wird wie folgt aufgerufen:

life 100 <f0.l |sort >f100.l

Die Eingabe und die Ausgabe besteht aus je einer Zeile pro lebendiger Zelle, wobei in der Zeile die X- und die Y-Koordinate der Zelle als Dezimalzahl steht. Es kommt auf die Reihenfolge der Werte in der Ausgabe nicht an, Ihr optimiertes Programm darf die gleichen Zeilen auch in einer anderen Reihenfolge ausgeben. Ein passender Test für das optimierte Programm wäre also:

optlife 3000 <f0.l |sort |diff - f3000.l

Das Originalprogramm, wie folgt compiliert und gemessen:

make CFLAGS=-O3
papiex -q -e PAPI_TOT_INS -e PAPI_BR_MSP life 3000 f3000b.l

ergab folgende Messwerte:

13466543701890   Proc cycles
7524249259736    PAPI_TOT_INS
3968070045       PAPI_BR_MSP

Das sind fast 1.5h; verwenden Sie am Anfang daher besser nur 500 Generationen.

Zusätzlich findet sich noch das Skript showlife, das die Stellungen graphisch darstellen kann, und zwar wie folgt:

showlife <f0.l |gv -

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

Aufgaben vom [WS02/03 | WS03/04 | WS04/05 | WS05/06 | WS06/07 ]

Termin/Anmeldung zur Präsentation

Die Termine sind:

11.12.,  8.1.,  15.1., 22.1.   Anmeldung: 13.11.-10.12.

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 ersten Präsentationstermin anzumelden.

Im WS 2007/2008 ist im Normalfall eine Gruppengröße von drei 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		-
Makefile	22-Nov-2007 09:41	688
effizienz-aufgabe07.tar.gz	22-Nov-2007 09:41	48K
f0.l	19-Nov-2007 16:25	2.5K
f0500.l	22-Nov-2007 09:32	6.6K
f1000.l	22-Nov-2007 09:32	13K
f1500.l	22-Nov-2007 09:32	21K
f2000.l	22-Nov-2007 09:32	32K
f2500.l	22-Nov-2007 09:32	38K
f3000.l	22-Nov-2007 09:22	43K
life.c	20-Nov-2007 21:19	2.7K
life.h	19-Nov-2007 15:14	209
readlife.y	19-Nov-2007 15:14	1.0K
semantic.cache	06-Dec-2007 10:01	1.7K
showlife	21-Nov-2007 15:25	85
showlife.ps	21-Nov-2007 15:38	702

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