Cache As Cache Can
Tja, an diesem Wort scheiden sich die Geister, insbesondere was die Aussprache angeht. Aber es soll hier nicht um Aussprache, Geschlecht oder Deklination gehen, sondern darum, was eigentlich dahinter steckt.
Der Cache? Die Cache? Das Cache? - Oder wie?
Die wörtliche Übersetzung von Cache ist laut Wörterbuch „unterirdisches Depot“ oder „geheimes Lager“, und das ist gar nicht einmal so falsch, wie es auf den ersten Blick vielleicht aussehen mag. Ein Cache ist ein schneller Speicher, der meist zwischen Prozessor und Speicher liegt (siehe Abb. 1). Auf ihn kann schneller als auf den Hauptspeicher zugegriffen werden, entweder weil er sich direkt auf demselben Chip wie die CPU befindet (wie zum Beispiel beim Motorola 68020 und 68030), oder weil er einfach schneller ist als der übrige Speicher (wie beispielsweise im Mega STE). Schön wäre es, wenn der gesamte Speicher so schnell wäre, leider ist schneller Speicher in großen Mengen jedoch unbezahlbar; ein 68030 mit z.B. 8 MB Cache wäre außerdem in keinem gängigen IC-Gehäuse mehr unterzubringen...
Theorie...
Jetzt stehen wir also vor dem Problem, daß wir nur wenig Cache-Speicher im Vergleich zum Hauptspeicher haben. Wir müssen diesen wertvollen Speicher also möglichst optimal verwalten, um den Geschwindigkeitsgewinn gegenüber einem System ohne Cache zu maximieren. Hier hilft die Theorie weiter. Die Theorie besagt, daß ein Programm sich in einem bestimmten Zeitintervall meist in einem relativ kleinen Speicherbereich aufhält.
Dieses Prinzip wird Referenzlokalität genannt. Das hat jedoch leider nichts mit der Empfehlung einer Stammkneipe durch die CPU zu tun. Ausführliche mathematische Betrachtungen zu diesem Thema sind unter anderem in [1] zu finden.
... und Praxis
Die Praxis hat gezeigt, daß die Theorie ausnahmsweise einmal Recht behält und sogar anwendbar ist. Man kann sogar noch einen Schritt weitergehen. Nicht nur die Daten, die vom Programmzähler adressiert werden (also das Programm selbst), sondern auch die Daten, die vom Programm gelesen werden, besitzen diese Eigenschaft. Das macht die Einführung von getrennten Daten- und Instruktions-Caches sinnvoll. Der 68020 beispielsweise besitzt nur einen Instruktions-Cache von 64 Langwörtern, während der 68030 einen getrennten Daten- und Programm-Cache von jeweils 64 Langwörtern enthält.
Cache-Prinzipien
Es bleibt jedoch problematisch, welche Daten im Cache behalten werden sollen. Beim Lesen und Schreiben besteht grundsätzlich die Möglichkeit, die jeweiligen Daten ohne zusätzlichen Zeitaufwand in den Cache zu übernehmen, sofern sie nicht bereits darin enthalten sind. Normalerweise wird hierzu jedem Wort im Hauptspeicher ein Wort im Cache zugeordnet. Da der Cache ja (viel) kleiner als der Hauptspeicher ist, fallen natürlich mehrere Hauptspeicherwörter auf ein Wort im Cache. Es muß also die Möglichkeit bestehen, zu einem bestehenden Cache-Eintrag die Adresse festzustellen, aus dem das Datum ursprünglich stammte. Diese Adresse wird im sogenannten „Tag“ gespeichert. Das Tag enthält zusätzlich noch Informationen, ob das zum Eintrag gehörende Datum gültig ist, und kann je nach Bedarf noch weitere Bits und Flags enthalten. Nur so kann die Cache-Logik feststellen, ob sich das von der CPU angeforderte Wort im Cache befindet oder nicht. Der erste Fall wird Cache-Hit genannt, der zweite Cache-Miss.
Zwischen den Cache-Einträgen und zwischen den Hauptspeicherwörtern besteht also eine Abbildung, von der die Effizienz des Caches abhängt. Ein gängiges Verfahren der Adreß-Abbildung, die sogenannte direkte Abbildung, zeigt Abbildung 2.
Der Cache des 68020
Einen Sonderfall der direkten Abbildung benutzt der 68020. Hier ist die Blockgröße 4 Bytes (1 Langwort). An diesem einfacheren Beispiel wollen wir auch das Verfahren erklären, bevor wir auf den 68030 eingehen, der auf den ersten Blick komplizierter zu sein scheint.
Der Cache des 68020 (siehe Abb. 3) ist ein 64 Langwörter (256 Byte) großer Instruktions-Cache. Diese 64 Langwörter werden direkt durch die Adreß-Bits A2 bis A7 adressiert. A1 dient der Auswahl des unteren oder oberen Wortes des Cache-Eintrages. Jeder Eintrag enthält ein Tag-Feld, das aus den obersten 24 Adreß-Bits (A8 bis A31), dem FC2-Wert sowie einem Gültigkeits-Bit besteht. Der FC2-Wert ist bei Zugriffen im User-Modus 0, im Supervisor-Modus 1. Das dient dazu, um Supervisor-Code nicht im User-Mode ausführen zu können.
Wenn die CPU den nächsten Befehl holt und der Cache eingeschaltet ist, wird zunächst nachgesehen, ob sich das gewünschte Wort im Cache befindet. Dazu werden die Adreß-Bits A2 bis A7 ausgewertet und im dadurch eindeutig ausgewählten Cache-Eintrag nachgesehen, ob die Adreß-Bits A8 bis A31 und FC2 übereinstimmen und ob der Eintrag überhaupt gültig ist. Wenn ja, wird das Datum aus dem Cache geholt. Ist das Wort nicht im Cache vorhanden, wird der Cache-Eintrag mit dem entsprechenden Langwort aus dem Hauptspeicher geladen, in den Cache eingetragen und als gültig gekennzeichnet. Der 68020 besitzt zur Steuerung der Cache-Operationen das sogenannte Cache-Control-Register (CACR), auf das mit dem MOVEC-Befehl zugegriffen werden kann. Im 68020 sind davon nur die untersten 4 Bits benutzt (siehe Abb. 4). Das Enable-Bit dient dazu, den Cache ein- und auszuschalten. Ist das Bit 0, ist der Prozessor gezwungen, immer direkt auf den Hauptspeicher zuzugreifen. Das kann zum Beispiel dazu benutzt werden, um zu verhindern, daß eine Warteschleife im Cache abgearbeitet wird und somit zu schnell abläuft.
Das Freeze-Bit dient dazu, den Cache einzufrieren. Bei einem Cache-Miss werden dann die im Cache befindlichen Daten nicht durch neue Daten überschrieben. So kann beispielsweise der innerste Teil einer Schleife, der sehr häufig ausgeführt wird, im Cache gehalten werden, während selten ausgeführte Teile (z.B. eine IF-Abfrage) nicht den Cache überschreiben.
Mit dem Clear-Cache-Bit können auf einen Schlag alle Cache-Einträge als ungültig gekennzeichnet werden. Wird dieses Bit im CACR mit 1 beschrieben, werden alle Gültigkeits-Bits gelöscht; beim Lesen wird dieses Bit jedoch immer als 0 gelesen. Damit kann u.a. verhindert werden, daß in einem Multitasking-System nach einem Task-Wechsel der neue Task Programmteile des alten ausführen kann.
Das letzte Cache-Kontroll-Bit im 68020 ist das Clear-Entry-Bit. Wird bei einem Schreibzugriff auf das CACR mit gesetztem CE-Bit der Eintrag als ungültig gekennzeichnet, der mit der Adresse im Cache-Adreß-Register (CAAR) korrespondiert, können gezielt einzelne Cache-Einträge ungültig gemacht werden. Auch dieses Bit liefert beim Lesen immer eine 0. Auf das CAAR-Register wird ebenfalls mit dem MOVEC-Befehl zugegriffen. Detailliertere Informationen können bei Bedarf [2] entnommen werden.
Die Caches des 68030
Nun aber endlich zum 68030. Wenn die Cache-Organisation des 68030 auch komplizierter aussieht (siehe Abb.en 5 und 6), so unterscheidet sich die prinzipielle Arbeitsweise jedoch nicht von der des 68020. Der 68030 besitzt neben einem 64 Langwörter großen Instruktions-Cache auch noch einen 64 Langwörter großen Daten-Cache. Zunächst zum Instruktions-Cache. Die Organisation unterscheidet sich hier etwas von der des 68020. Im Gegensatz zum 68020, bei dem jedes Langwort ein eigenes Tag hatte, besitzen beim 68030 jeweils vier aufeinanderfolgende Langwörter ein gemeinsames Tag. Diese vier zusammengehörigen Langwörter werden auch Cache-Zeile genannt. Auch der Aufbau des Tags unterscheidet sich daher etwas von dem beim 68020, denn jedes Langwort besitzt auch hier ein eigenes Gültigkeits-Bit, so daß sich der Aufbau eines Tags wie In Abbildung 5 ergibt Wann immer der 68030 auf ein Langwort zugreifen möchte, das sich nicht im Cache befindet, wird dieses Langwort aus dem Hauptspeicher in den Cache geladen sowie die drei folgenden Langwörter. Diese Betriebsart wird „Burst Mode“ genannt und ist schneller als vier separate Zugriffe. Die hier zugrunde liegende Theorie ist die, daß ein in Ausführung befindliches Programm im allgemeinen auch die folgenden Befehle ebenfalls abarbeiten wird, so daß auf einen Cache-Miss wahrscheinlich drei Cache-Hits folgen werden.
Der Daten-Cache des 68030 ist dem Instruktions-Cache sehr ähnlich (siehe Abb. 6). Auch er ist 64 Langwörter lang und ebenfalls er in 16 Cache-Zeilen organisiert. Das Tag-Feld enthält hier jedoch zusätzlich noch die Bits FC0 und FC 1. Die Funktionsweise des Daten-Caches ist etwas schwieriger als die des Instruktions-Caches. Ein Datenzugriff kann ein Byte, ein Wort oder ein Langwort umfassen, wobei Wort- und Langwortzugriffe auch auf ungeraden Adressen liegen dürfen. Daraus folgt, daß im schlimmsten Fall zwei ganze Cache-Zeilen ersetzt werden müssen. Schreibzugriffe sind noch schwieriger, da der 68030 nicht nur in den Cache schreibt, sondern immer auch in den Hauptspeicher. Dieses Verhalten nennt man „Write Through“. Ein Prozessor, der nur in den Cache schreibt und nicht in den Hauptspeicher, hätte zwar unter Umständen Geschwindigkeitsvorteile, jedoch müßte er mit einem separaten Befehl dafür sorgen, daß die Cache-Daten in den Hauptspeicher zurückgeschrieben würden („Copy Back“). Das ist jedoch beim 68030 nicht der Fall.
Werden Daten in den Hauptspeicher geschrieben, die sich bereits im Cache befinden, wild der Cache immer automatisch aktualisiert, damit die Cache-Daten mit den Daten im Hauptspeicher konsistent bleiben. Befinden sich die Daten jedoch noch nicht im Cache, kann sich der Prozessor auf zwei verschiedene Arten verhalten, was über das Caehe-Control-Register einstellbar ist Ist die sogenannte „Write-Allocation“ abgeschaltet, werden die alten Daten (von der alten Adresse) im Cache bei einem Schreibzugriff nicht von den neuen Daten (an einer neuen, anderen Adresse) überschrieben. Das bedeutet, daß der entsprechende Cache-Eintrag unverändert die zuletzt gelesenen Daten enthält.
Ist die Write-Allocation eingeschaltet, werden die Daten im Cache bei einem Cache-Miss im Cache eingetragen und die übrigen Daten der Cache-Zeile als ungültig gekennzeichnet. Ein auf Langwortgrenze ausgerichtetes Langwort wird auch als gültig gekennzeichnet. Ist das Langwort jedoch nicht auf eine Langwortgrenze ausgerichtet, oder liegt ein Byte- oder Wort-Zugriff vor, wird der Eintrag als ungültig gekennzeichnet Das liegt daran, daß ein Gültigkeits-Bit nur jeweils für ein zusammenhängendes Langwort gilt nicht jedoch für Teile eines Langwortes.
Das Cache-Control-Register des 68030 spiegelt die kompliziertere Cache-Struktur durch weitere Bits wider (siehe Abb. 7), die jedoch zum 68020 abwärtskompatibel sind. Bits 0 bis 3 sind daher auch schon bekannt und bedürfen keiner weiteren Erläuterung. Neu hinzugekommen ist das Instruction-Burst-Enable-Bit (IBE). Hiermit kann der oben erwähnte Instruktions-Burst-Modus ein- und ausgeschaltet werden. Die Bits 5 bis 7 sind weiterhin unbenutzt und Null.
Die Bits 8 bis 12 entsprechen in der Funktion den Bits 0 bis 4, nur daß sie sich auf den Daten-Cache beziehen. Mit Bit 13 kann die oben beschriebene Write-Allocation ein- und ausgeschaltet werden. Das WA-Bit hat kein entsprechendes Gegenstück im Instruktionsteil des CACR, die Write-Allocation macht jedoch auch für den Instruktions-Cache keinen Sinn, da die CPU nie Befehle schreibt.
Eine ausführliche Betrachtung der Daten- und Instruktions-Caches des 68030 kann in [3] nachgelesen werden.
Der Cache des Mega STE
Soweit zur Beschreibung des Caches im 68020 und im 68030. Wir sind hier auch auf den 68020 eingegangen, weil es entsprechende Erweiterungskarten für den ST gibt. Auch Mega-STE-Besitzer sollen hier nicht ganz leer ausgehen, denn der Mega STE besitzt einen Cache in der Größe von stolzen 16 KB. Da sich in diesem Rechner jedoch ein 68000-Prozessor befindet, liegt der Cache nicht auf dem Prozessor-Chip. Dadurch ist die Cache-Kontrolle auch nicht durch ein Prozessor-Register möglich, sondern geschieht durch ein Hardware-Register, das gleichzeitig auch die Umschaltung von 8 auf 16 MHz übernimmt. Dieses Register befindet sich bei Adresse $FFFF8E21 und hat Byte-Größe. Mit Bit 0 kann der Cache ein- und ausgeschaltet werden (0 = Cache aus, 1 - Cache an). Mit Bit 1 wird der CPU-Takt eingestellt (0=8 MHz, 1 = 16 MHz).
Wir hoffen, daß die Arbeitsweise von Cache-Speichern etwas klarer geworden ist und Sie jetzt unter anderem wissen, warum Ihr Rechner auch mit kleinem Cache so viel schneller ist als ohne,
Uwe Hax & Oliver Scholz
Literatur:
[1] Mario Dal Cin:
Rechnerarchitektur 1,
Skript zur gleichnamigen Vorlesung der Universität Erlangen-Nürnberg 1990
[2] Motorola Inc.:
MC68020 32-Bit-Microprocessor User’s Manual
Prentice-Hall 1985
[3] Steve Williams:
68030 Assembly Language Reference
Addison-Wesley 1989