Abgabe Effiziente Programme WS11/12

Abgabe Effiziente Programme WS11/12

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

Vorgegebene Aufgabe: Ramanujan-Zahlen

Hintergrund

Ramanujan-Zahlen sind Zahlen, die auf mehrere Arten als Summen zweier Kubikzahlen dargestellt werden können.

Genaue Aufgabe

Das vorgegebene Programm zählt die Ramanujan-Zahlen bis zu einer bestimmten Grenze. Optimieren Sie das Programm so, dass es für fast alle Eingaben weniger Laufzeit und nicht mehr Speicher braucht als das Original. Messen Sie den Effekt ihrer Optimierungsschritte auf die Laufzeit (Anzahl der Zyklen) mit der Benchmark-Eingabe: ramanujan 100000000000. Die interessantesten Schritte und Ergebnisse präsentieren Sie dann (siehe oben).

Die Ausgabe muss natürlich auch korrekt sein, wobei nur die erste Zeile der Ausgabe für die Korrektheit gezählt wird (die anderen Zeilen enthalten nur Informationen über die konkrete Implementation und dürfen beliebig verändert oder weggelassen werden).

Damit Ihre Ergebnisse mit denen anderer Gruppen vergleichbar sind, messen Sie die Zyklen auf der g0 ("make" macht schon den entsprechenden Aufruf). Das vorgegebene Programm verbraucht mit -O 5932M Zyklen (5361M im user mode und 571M im system mode).

Anmerkung bezüglich der Messung des Speicherverbrauchs. Im vorgegebenen Programm berichtet mallinfo() bei größeren n nicht den Speicher, der mit dem calloc() angelegt wurde, wie eine Berechnung des Mindestspeicherverbrauchs zeigte (der über dem Speicherverbrauch lag, der von mallinfo() berichtet wurde); daher zählt das vorgegeben Programm diesen Speicher extra dazu; Sie sollten bei der Verwendung von mallinfo() ebenfalls nachprüfen, ob die Resultate plausibel sind; wahrscheinlich zählt mallinfo() alle größeren Allokationen nicht.

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/2011w 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 ]

Termin/Anmeldung zur Präsentation

Die Termine sind: 
16.12., 13.1., 20.1., 27.1.
Die Terminvergabe erfolgt, über unser Web-Anmeldesystem. Und zwar müssen Sie dabei folgendermaßen vorgehen: Im WS 2011/2012 ist im Normalfall eine Gruppengröße von 3-4 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  -  
[CMP]ramanujan.tar.gz15-Nov-2011 14:17 1.4K 
[DIR]ramanujan/15-Nov-2011 14:17 -  
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