Ausgabe 2003-03-12
Lutz Prechelt
1. Wie groß muss die
Netzbandbreite des Web-Servers von amazon.de in der Vorweihnachtszeit sein?
2. Betrachten Sie alle
Sortieralgorithmen, die sie kennen. Welche davon haben ein besonders günstiges
Cache-Verhalten beim Sortieren von float-Werten in Bezug auf
a.)
Ausnutzung von Cache-Zeilen
b.)
Ausnutzung von Cache-Lokalität im Ganzen
Was ändert sich, wenn
statt dessen Straßennamen zu sortieren sind?
3. Angenommen, Sie
müssen an einer extrem leistungskritischen Stelle Felder von genau 4
Integer-Werten sortieren. Die ursprüngliche Anordnung muss zusätzlich erhalten
bleiben, d.h. Sie kopieren beim Sortieren in ein neues Feld um. Welches Verfahren setzen Sie ein?
4. Bestimmen Sie das
Cache-Verhalten auf einem Rechner Ihrer Wahl. Messen Sie dazu die Laufzeit
eines Sortierverfahrens für unterschiedliche Feldgrößen.
·
Verwenden Sie den (unvollständigen) vorgegebenen
Testrahmen. (siehe Vorlesungs-Webseite) Das verwendete Sortierverfahren ist
java.util.Arrays.sort.
·
Messen Sie beginnend mit 10-elementigen Feldern
Feldgrößen mit jeweils um 10% wachsenden Elementanzahlen.
·
Fahren Sie soweit fort, wie es die Messzeit und der Hauptspeicher
des Rechners noch bequem zulassen, z.B. bis zu einer Endgröße von 10 Mio. Elementen.
·
Messen Sie die Laufzeit pro Feldelement
·
Stellen sie die Messwerte als x/y-Plot dar, z.B. mit Hilfe
von Gnuplot oder einem ähnlichen Programm. (Hinweis: Excel macht von Natur aus
KEINE x/y-Plots!)
·
Was können Sie aus den Messdaten über das Cacheverhalten ablesen?
·
Korrigieren Sie nötigenfalls den Testrahmen so, dass Sie brauchbare
Daten erhalten.
·
Was haben Sie aus dem ganzen Experiment gelernt? Listen
Sie mindestens drei Erkenntnisse auf.