Cache-Adressaufteilung und mittlere Speicherzugriffszeit
Geben Sie Cache-Größe, Zeilengröße und Assoziativität ein, um zu sehen, wie sich eine Adresse in Tag, Index und Offset aufteilt, dargestellt als Bitanzahl und als Balken. Zusätzlich berechnet der Rechner die mittlere Speicherzugriffszeit (AMAT) aus Trefferzeit, Fehlzugriffsrate und Miss Penalty, sodass Sie sehen, wie sich die Cache-Organisation auf die Leistung auswirkt.
Ergebnisse
Adressaufteilung (höchstwertige Bits links)
Geben Sie für Cache-Größe, Zeilengröße und Assoziativität Zweierpotenzen ein, wobei die Größe durch Zeilengröße × Wege teilbar sein muss. Die Aufteilung lässt sich außerdem nicht berechnen, wenn Offset- und Index-Bits zusammen die Adressbreite überschreiten.
Zeilen
–
Sets
–
Tag
–
Index
–
Offset
–
Mittlere Speicherzugriffszeit (AMAT)
–
Als Diagramm ansehen
Die übrigen Eingaben bleiben auf ihren aktuellen Werten, während die gewählte Eingabe zwischen dem 1/4- und 4-Fachen ihres aktuellen Werts variiert. Der rote Punkt ist der aktuelle Wert.
Eine Adresse in drei Felder aufteilen
Ein Cache hält Daten des Hauptspeichers in Einheiten, die Zeilen (Blöcke) heißen. Die Anzahl der Zeilen ist Größe ÷ Zeilengröße, die Anzahl der Sets ist Zeilen ÷ Assoziativität. Vom niederwertigen Ende der Adresse aus wählt der Offset ein Byte innerhalb der Zeile und belegt log₂(Zeilengröße) Bits, der Index wählt ein Set und belegt log₂(Sets) Bits, und die übrigen oberen Bits bilden den Tag. Mit den Standardwerten 32 Bit, 32 KB, 64 B und 8 Wegen gibt es 512 Zeilen und 64 Sets; das ergibt einen 6-Bit-Offset, einen 6-Bit-Index und einen Tag mit 32 − 6 − 6 = 20 Bit.
Was die Assoziativität verändert
Verdoppelt man die Assoziativität bei gleicher Größe und Zeilengröße, halbiert sich die Anzahl der Sets: Der Index verliert ein Bit, der Tag gewinnt eines. Ein Weg entspricht einem direkt abgebildeten Cache (Direct-Mapped); setzt man die Wegzahl gleich der Zeilenzahl (512 bei den Standardwerten), erhält man einen voll assoziativen Cache mit einem einzigen Set und einem 0-Bit-Index. Höhere Assoziativität verringert Konfliktfehlzugriffe (Conflict Misses), die entstehen, wenn sich Adressen im selben Set drängen, doch dann müssen mehr Tags parallel verglichen werden, was Komparatorfläche, Leistung und Trefferzeit kostet.
Mittlere Speicherzugriffszeit (AMAT)
Caches sollte man anhand der mittleren Speicherzugriffszeit vergleichen, nicht allein anhand der Fehlzugriffsrate. Es gilt AMAT = Trefferzeit + Fehlzugriffsrate × Miss Penalty, mit den Standardwerten also 4 + 0,05 × 100 = 9 Zyklen. Schon eine Fehlzugriffsrate von 5 % lässt den Mittelwert auf mehr als das Doppelte steigen, weil die Miss Penalty groß ist. Eine niedrigere Fehlzugriffsrate durch einen größeren oder stärker assoziativen Cache nützt nichts, wenn dabei die Trefferzeit steigt, denn sie fällt bei jedem Zugriff an. Bei mehrstufigen Caches ersetzt man die L1-Miss-Penalty durch L2-Trefferzeit + L2-Fehlzugriffsrate × L2-Miss-Penalty.
Einsatz im Design und Fallstricke
Größere Zeilen nutzen die räumliche Lokalität und senken die Fehlzugriffsrate, doch jeder Fehlzugriff bewegt mehr Daten, was die Miss Penalty erhöht, und weniger Zeilen bedeuten mehr Konflikte; die meisten aktuellen CPUs verwenden 64 B. L1-Caches sind oft virtuell indiziert und physisch getaggt (VIPT): Das Set wird gelesen, während der TLB die Adresse übersetzt. Damit Index und Offset innerhalb des Seitenoffsets bleiben, ist die Größe auf Seitengröße × Assoziativität begrenzt, zum Beispiel 4 KB × 8 Wege = 32 KB. Die Tag-Breite bestimmt außerdem die Größe des Tag-Speichers.
Bei 64 Byte Zeilengröße = 2⁶ beträgt der Offset 6 Bit. Die Zeilenzahl ist 32 KB ÷ 64 B = 32768 ÷ 64 = 512 = 2⁹; beim Direct-Mapped-Cache ist die Zeilenzahl zugleich die Satzzahl, der Index hat also 9 Bit. Der Rest ist das Tag: 32 − 9 − 6 = 17 Bit. 19 Bit ist der Wert bei einem 4-fach satzassoziativen Cache, bei dem der Index 2 Bit kürzer ist, und trifft für Direct-Mapped nicht zu.
Die Zeilenzahl beträgt 32 KB ÷ 64 B = 512. Bei 4 Wegen enthält ein Satz 4 Zeilen, die Satzzahl ist also 512 ÷ 4 = 128 = 2⁷, der Index hat 7 Bit und das Tag 32 − 7 − 6 = 19 Bit. 512 ist die Zeilenzahl selbst und die Satzzahl bei Direct-Mapped. Mit höherer Assoziativität sinkt die Satzzahl, und dafür steigen die Tag-Bits und die Zahl der Komparatoren. 32 ist der Wert, der entsteht, wenn man die Zeilengröße 64 irrtümlich durch die Wegezahl teilt.
Mittlere Speicherzugriffszeit = Trefferzeit + Miss-Rate × Miss-Penalty = 2 + 0,04 × 150 = 2 + 6 = 8 Zyklen. Die Trefferzeit fällt bei allen Zugriffen an, und nur bei einem Miss kommt die Miss-Penalty hinzu. 6 Zyklen ist der Wert, bei dem nur der Anteil der Misses berechnet und die Trefferzeit vergessen wurde. 152 Zyklen ist die Zeit für einen einzelnen Zugriff mit Miss und kein Mittelwert. Man sieht, dass sich der Mittelwert schon bei einer Miss-Rate von nur 4 % vervierfacht.
Der Offset sind wegen 64 = 2⁶ die unteren 6 Bit, der Index sind wegen der Satzzahl 64 = 2⁶ die darüberliegenden 6 Bit. 0x1234 = 4660, geteilt durch 64: 4660 ÷ 64 = 72 Rest 52; die Zeilennummer ist also 72. Die Satznummer ist der Rest der Zeilennummer geteilt durch die Satzzahl: 72 mod 64 = 8. 52 ist der Rest bei der Division durch 64 und stellt die Position in der Zeile (Offset) dar. 4 ist lediglich die letzte Stelle der hexadezimalen Adresse und hat mit dem Satz nichts zu tun.
Häufige Fragen
Wie viele Tag-Bits hat ein direkt abgebildeter 32-KB-Cache mit 64-B-Zeilen und 32-Bit-Adressen?
Der Offset hat log₂64 = 6 Bit, und 32 KB ÷ 64 B = 512 Zeilen ergeben einen 9-Bit-Index, also hat der Tag 32 − 9 − 6 = 17 Bit. Bei 8-fach-Assoziativität sinkt die Zahl der Sets auf 64, was einen 6-Bit-Index und einen 20-Bit-Tag ergibt.
Wie viele Index-Bits hat ein voll assoziativer Cache?
Null. Es gibt nur ein Set, daher gehört jedes Bit außer dem Offset zum Tag, und der Tag wird mit jeder Zeile verglichen. Sie können das hier prüfen, indem Sie die Assoziativität gleich der Zeilenzahl setzen.
Was bringt mehr: die Fehlzugriffsrate halbieren oder die Trefferzeit um einen Zyklus verkürzen?
Mit den Standardwerten (4 Zyklen Trefferzeit, 5 % Fehlzugriffsrate, 100 Zyklen Miss Penalty) senkt eine Fehlzugriffsrate von 2,5 % die AMAT von 9 auf 6,5 Zyklen, während eine Trefferzeit von 3 Zyklen 8 Zyklen ergibt; hier zählt also die Fehlzugriffsrate mehr. Bei kleiner Miss Penalty kann sich das umkehren, vergleichen Sie daher mit der AMAT-Formel.