Abgabe Effiziente Programme WS16/17

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

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.

Bei der vorgegebenen Aufgabe dieses Jahr darf nur vectors.c und vectors.h geändert werden, der Rest (also main.c) ist als Eingabe für den Benchmark zu betrachten.

Vorgegebene Aufgabe: Vektor-Library

Das Interface der Vektor-Library ist in vectors.h umrissen. Ein wichtiger Aspekt dabei ist, dass die Vektoren Werte-Semantik haben und unveränderbar sind. Sie verlässt sich dafür darauf, dass die Anwendung die Vector-Werte nur mit den vorgesehenen Operationen verarbeitet, und sie z.B. nicht mit einfachen Zuweisungen kopiert, oder einen Vektor in einer Variable mit einer einfachen Zuweisung ueberschreibt. Sie können sich bei der Optimierung auch darauf verlassen.

In der Referenzimplementierung vectors.c wird die Wertesemantik so implementiert, dass es immer nur eine Referenz auf einen Vektor gibt, und beim Erstellen einer neuen Referenz mit vcopy() auch gleich der zugehörige Vektor kopiert wird; stattdessen kann man die Referenz auch weitergeben, sodass am ursprünglichen Platz keine Referenz mehr übrigbleibt (vconsume()). Durch diese Eigenschaft der Implementierung kann z.B. vsum(), das zwei Vektoren verbraucht und einen erzeugt, den Speicher eines Operanden für sein Resultat verwenden, und verletzt dabei die Bedingung der Unveränderbarkeit nicht: der Operand wurde ja durch vsum verbraucht und sein Speicher würde sonst einfach freigegeben werden (und Speicher für das Resultat allokiert werden).

Die Anwendung ist eine Variante der Matrixmultiplikation aus der Vorlesung, wobei wir hier für die Messung eine 1999x1999-Matrix mit einer 1999x99-Matrix multiplizieren (Ihr Programm soll aber auch für andere Größen funktionieren). Verändern Sie main.c nicht, sondern optimieren Sie nur vectors.c! Auch wenn auch hier eine Matrixmultiplikation vorkommt, sind die Optimierungsgelegenheiten hier zum Großteil ganz andere als bei dem Beispiel in der Vorlesung.

Mit make check können Sie testen, ob das Programm noch das richtige Resultat für den Testfall liefert. Mit make perf können Sie den Code benchmarken. Das Resultat für die Originalversion ist:

     1801950627  cycles                   #      0.000 M/sec
     4451503743  instructions             #      2.470 IPC  

    0.684736980  seconds time elapsed

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 | WS16/17 ]

Termin/Anmeldung zur Präsentation

11.1., 18.1., 25.1.

	Name	Last modified	Size	Description
	Parent Directory		-
	Makefile	04-Dec-2017 17:42	519
	effizienz-aufgabe17.tar.gz	04-Dec-2017 17:45	1.1M
	main.c	04-Dec-2017 13:38	1.7K
	main.o	04-Dec-2017 16:40	4.4K
	matmul.1999x1999x99	04-Dec-2017 13:37	1.5M
	matmul.out	04-Dec-2017 16:40	1.5M
	mm	04-Dec-2017 16:40	12K
	perf.data	04-Dec-2017 13:37	449K
	vectors.c	01-Dec-2017 19:23	2.0K
	vectors.h	26-Nov-2017 00:08	1.7K
	vectors.o	04-Dec-2017 16:40	4.6K