Abgabe Effiziente Programme WS07/08

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: 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
[ICO]NameLast modifiedSizeDescription
[PARENTDIR]Parent Directory  -  
[ ]Makefile2007-11-22 09:41 688  
[ ]effizienz-aufgabe07.tar.gz2007-11-22 09:41 48K 
[ ]f0.l2007-11-19 16:25 2.5K 
[ ]f0500.l2007-11-22 09:32 6.6K 
[ ]f1000.l2007-11-22 09:32 13K 
[ ]f1500.l2007-11-22 09:32 21K 
[ ]f2000.l2007-11-22 09:32 32K 
[ ]f2500.l2007-11-22 09:32 38K 
[ ]f3000.l2007-11-22 09:22 43K 
[TXT]life.c2007-11-20 21:19 2.7K 
[TXT]life.h2007-11-19 15:14 209  
[ ]readlife.y2007-11-19 15:14 1.0K 
[ ]semantic.cache2007-12-06 10:01 1.7K 
[ ]showlife2007-11-21 15:25 85  
[ ]showlife.ps2007-11-21 15:38 702  
Apache/2.4.62 (Debian) OpenSSL/3.0.15 Server at www.complang.tuwien.ac.at Port 80