J
/dev/null schrieb:
Wieviele Zeichen auf einer Seite angezeigt werden: ~600
Dann würde ich 2KB als Cache-Line nehmen. Dann hast Du gut Platz außenrum.
Bei den verschiedenen Cache-Arten geht es im wesentlichen darum, wie man die Daten in den Cache reinschreibt und sie dort eben findet. Denn das muß ja möglichst schnell gehen.
Zunächst mal holt man sich die Adresse des Bytes, also den Offset vom Beginn der Datei. Das sind in Deinem Fall wohl 32 Bit.
Irgendwie müssen wir an soner Zahl jetzt sehen wo wir in den Cache gucken müssen. Zunächst lagern wir mal nur Zeichen in den Cache, die an einer durch 2048=2^11 teilbaren Adresse anliegen, das heißt die unteren 11 Bit dieser Adresse geben sozusagen nur den Offset an, wie weit wir in die Cache-Zeile schauen müssen. Dann haben wir noch 21 Bit übrig. Jetzt gibt's mehrere Möglichkeiten:
Wir können einfach in jede Cache-Zeile für alle Adressen benutzen. Dann müssen wir für jede Cache-Zeile einen Vergleich opfern. Bei sagen wir mal 100 Cache-Zeilen, also 100 Vergleiche. Das ist wohl zu viel.
Das heißt man speichert für jede Zeile noch den sogenannten Tag, diese 21 Bit eben mit und vergleicht die dann. Das kostet natürlich Zeit. Das wäre dann vollassoziativ.
Eine andere Möglichkeit wäre DirectMapped: Man sag, okay ich habe 128 Cache-Lines, also geben die nächsten 7 Bit der Adresse (immer von hinten gerechnet) die Cache-Zeile an. Und nur die restlichen 21-7=14 Bit sind der Tag. Damit liegt kommt eine bestimmte Speicherstelle der Datei auch immer in eine feste Cache-Zeile und ist somit sehr leicht aufzuspüren. Allerdings kann es da halt passieren, das zwei ständig benötigte Dateistücke sich ständig gegenseitig verdrängen, weil sie in die gleiche Zeile müssen. Bei vollassoziativ (AV) wäre das kein Problem, jeder würde seine eigene Zeile kriegen.
Des wegen gibt es noch eine Mischform: n-fach satzassoziativ.
Wir Teilen unsere 128 Cache-Lines in 16 Blöcke ein, jede davon mit 8 Lines. Dann verwenden wir von den 21 Bit Adresse 4 für die Adressierung des Blocks und dort innerhalb arbeiten wir mit den restlichen 17 Bit vollassoziativ weiter. Dadurch brauchen wir aber nur 8 Vergleiche und das Problem, mit der Verdrängung wie bei DM-Caches haben wir auch nicht ganz so arg.
Ich denke der satzassoziative ist für Dein Problem am besten geeignet. AV wird meist in Hardware gegossen (prozessor-cache und so), weil da die Vergleiche parallel ablaufen können.
Wieso schreibst Du eigentlich die list selber? Was hältst Du von std::list?
MfG Jester
