Die Taktraten von Prozessoren werden immer höher und höher. Das Mass Taktrate wird auch in der Computer- und Prozessor-Werbung stark betont. So erstaunt es wenig, dass die Verbesserung der Taktrate eines Prozessors häufig noch als das beste Mittel zur Beschleunigung von Programmen angesehen wird.

Tatsächlich aber gibt es noch andere Wege, Programme schneller ablaufen zu lassen. Gerade auf Computer mit einem hierarchischen Speichersystem ist die gute Ausnutzung der verschiedenen Hierarchiestufen (Register, first level cache, second level cache, main memory) von besonderer Wichtigkeit.

In diesem Wettbewerb soll deshalb eine gegebene Operation auf grossen Matrizen so optimiert werden, dass die vorhandenen Caches des SPARC-Prozessors optimal ausgenützt werden.

Hinweis: Es gibt auch Programme, welche die Leistung Speicherhierarchie eines Systems ausmessen, z.B. die ECT (Als Beispiele sind hier die Messungen von zwei Speichersystemen aufgeführt). Die Maschine, auf der die Messungen der Wettbewerbs-Programm durchgeführt werden, ist mit einer UltraSPARC IIi CPU ausgerüstet, die mit einer Taktrate von 360 MHz läuft. Detailliertere Messungen und weitere Infos zu dieser CPU gibt es hier.

Wettbewerbsaufgabe: Matrix Magic

In der Informatik ist das Verknüpfen zweier Matrizen eine häufig gebrauchte Funktion. Die für den Wettbewerb benutzte Funktion heisst Matrix Magic und soll auf grosse Matrizen (512x512) angewandt werden. Ein sehr langsames, aber einfaches Beispielprogramm wird zur Verfügung gestellt.

Eine genaue Aufgabenstellung mit weiteren Hinweisen ist als PDF hier erhältlich: Wettbewerb-Aufgabenstellung.

Termine:

Abgabetermin: 27.01.2002 24:00 CET
Preisverleihung: 30.01.2002 in der Vorlesung

Hinweise, Material und Test-Code

Im Verzeichnis /afs/ethz.ch/users/s/sysprog/Wettbewerb/ findest Du ein modifiziertes Matrix-Magic-Environment (bestehend aus den Dateien Makefile, input.txt, matrix.h, mmagic.h, mmagic.s, mmagic_env.c, mmagic_env.h und setup.sh) zum Testen Deiner Implementation.

Es folgt nun eine Erklärung der einzelnen Dateien:

Eine von drei möglichen Vorgehensweisen empfiehlt sich zum erstellen einer guten Wettbewerbslösung:

Abgabe

Die Abgabe erfolgt, wie in der Aufgabenstellung beschrieben, durch Kopieren der optimierten Dateien mmagic.s und matrix.h in das vom setup-Skript angegebene AFS-Verzeichnis. In regelmässigen Zeitabständen wird mmagic.s von unserem Testprogramm auf Fehler überprüft und die Geschwindigkeit gemessen. Die Testresultate werden an die Datei grade.log, welche sich im selben Verzeichnis wie mmagic.s befindet, angehängt. Falls unser Testprogramm keine Fehler in mmagic.s erkennt, wird die Lösung in die Rangliste aufgenommen. Die Punktzahl wird anhand der Anzahl Taktzyklen bestimmt, die mmagic.s für verschiedene Testfälle benötigt. Dazu wird das geometrische Mittel über alle Testfälle genommen.

Definitive Rangliste

Die definitive Rangliste ist jetzt online. Sie enthält die beste erzielte Punktzahl aller Gruppen.

Musterlösung

Die Folien mit der Herleitung der Musterlösung sind auf der Vorlesungs-Seite zu finden.

Fragen

Fragen bzgl. Aufgabenstellung, Abgabe und Bewertung können an Cesare Pautasso gesandt werden.


Last update: Feb 06 2002 (fr)

Author/Hrsg: Thomas M. Stricker, <tomstr@inf.ethz.ch>