Assoziativität und Konfliktfehler

In einem Cache mit einem Platz pro Zeile werfen zwei stark genutzte Zeilen, die sich einen Platz teilen, sich immer wieder gegenseitig hinaus. Geben Sie jedem Platz mehrere Wege, und das Problem verschwindet größtenteils, außer die Zeilen Ihrer Tabelle liegen genau 4096 Byte auseinander. Diese Lektion baut einen satzassoziativen Cache und zeigt, wie eine Zeilengröße als Zweierpotenz dazu führen kann, dass 100 % der Lesezugriffe verfehlen.

Im direkt abgebildeten Cache des letzten Themas hat jede Speicherzeile genau einen Platz. Nutzt Ihr Programm immer wieder zwei Zeilen, die auf denselben Platz fallen, etwa Zeile 0 und Zeile 8 in einem Cache mit 8 Plätzen, verdrängt jeder Zugriff auf die eine die andere, obwohl die anderen sieben Plätze leer sein können. An der Cache-Größe liegt es nicht: Die Zeilen streiten um einen zu kleinen Platz. Ein solcher Fehlzugriff heißt Konfliktfehler.

Die Lösung ist, Plätze zu gruppieren. Plätze werden zu Sätzen zusammengefasst, und jeder Platz in einem Satz ist ein Weg. Eine Speicherzeile gehört zu einem Satz, gefunden über denselben Rest wie zuvor, darf aber in jedem Weg dieses Satzes liegen. Zwei kollidierende Zeilen teilen sich jetzt einen Satz mit Platz für beide. Die Zahl der Sätze folgt aus den Größen:

Eine Adresse zerfällt jetzt in drei Teile. Der Offset ist das Byte in der Zeile. Der Satzindex sagt, zu welchem Satz die Zeile gehört. Das Tag ist der Rest der Zeilennummer, und der Cache vergleicht es, um zu sehen, ob ein Weg diese Zeile hält. Die Funktion unten teilt eine Adresse für einen Cache mit 64-Byte-Zeilen und 64 Sätzen.

def split_address(address, line_bytes, n_sets):    line = address // line_bytes    return line // n_sets, line % n_sets, address % line_bytes1print(split_address(74565, 64, 64))

(18, 13, 5)

1. 1Tag, Satzindex und Offset: Jedes ist eine ganzzahlige Division oder ein Rest der Adresse.

Adresse 74565 ist Byte 5 von Zeile 1165. Zeile 1165 kommt in Satz 13 (1165 modulo 64), und 18 ist, was von der Zeilennummer übrig bleibt, das Tag. Jede Zeile mit Satz 13 konkurriert um die acht Wege dieses Satzes, gleich welches Tag sie hat.

Ist ein Satz voll und kommt eine neue Zeile, muss eine Zeile gehen. Die übliche Regel ist LRU: Die am längsten nicht benutzte Zeile wird verdrängt. Wir können jeden Satz als Python-Liste halten, geordnet von der am längsten bis zur zuletzt benutzten.

1. 1
   Satz bestimmenDie Zeilennummer modulo die Anzahl der Sätze.
2. 2
   In jedem Weg nachsehenBei einem Treffer die Zeile ans Ende der zuletzt benutzten verschieben.
3. 3
   Bei Fehlzugriff hinzufügenDie neue Zeile ans Ende der zuletzt benutzten setzen.
4. 4
   Die älteste verwerfenHält der Satz mehr Zeilen als Wege, die erste entfernen.

Hier ist der ganze Cache. Der Lauf unten liest zwei Zeilen, die Adressen 0 und 256, die in einem 256-Byte-Cache mit 64-Byte-Zeilen kollidieren, erst mit einem Weg und dann mit zwei.

class SetAssocCache:    def __init__(self, size_bytes, line_bytes, ways):        self.line_bytes = line_bytes        self.ways = ways        self.n_sets = size_bytes // (line_bytes * ways)        self.sets = [[] for _ in range(self.n_sets)]        self.hits = 0        self.misses = 0    def access(self, address):        line = address // self.line_bytes        lines = self.sets[line % self.n_sets]        if line in lines:            lines.remove(line)            lines.append(line)1            self.hits += 1            return True        self.misses += 1        lines.append(line)        if len(lines) > self.ways:            lines.pop(0)2        return Falsefor ways in (1, 2):    cache = SetAssocCache(size_bytes=4 * 64, line_bytes=64, ways=ways)    flags = [cache.access(a) for a in [0, 256, 0, 256, 0, 256]]    print(ways, "way:", flags)

1 way: [False, False, False, False, False, False]
2 way: [False, False, True, True, True, True]

1. 1Eine treffende Zeile ans Ende zu schieben hält die Liste geordnet: Der erste Eintrag ist immer der am längsten nicht benutzte.
2. 2Der volle Satz verliert seinen ersten Eintrag, die am längsten nicht benutzte Zeile.

Mit einem Weg verdrängen sich die beiden Zeilen und alle sechs Zugriffe verfehlen. Mit zwei Wegen passen beide Zeilen in ihren Satz: Nach den ersten beiden Kaltstart-Fehlzugriffen trifft jeder Zugriff. Ein zusätzlicher Weg hat alle Konfliktfehler dieses Musters beseitigt.

Jetzt die Falle. Eine Tabelle mit 512 float64-Spalten hat Zeilen von genau 4096 Byte. Eine Spalte zu lesen heißt, die Adressen 0, 4096, 8192 und so weiter zu lesen. In unserem Cache ist der Satzindex die Zeilennummer modulo 64, und 4096 Byte sind genau 64 Zeilen, also hat jede dieser Adressen denselben Satzindex. Der Code gibt den Satz der ersten sechs Zeilen für eine Zeilengröße von 4096 Byte und von 4160 Byte aus, also 4096 plus eine zusätzliche Cache-Zeile.

n_sets = 64for row_bytes in (4096, 4160):    sets = [(i * row_bytes // 64) % n_sets for i in range(6)]    print(row_bytes, "->", sets)

4096 -> [0, 0, 0, 0, 0, 0]
4160 -> [0, 1, 2, 3, 4, 5]

Bei 4096-Byte-Zeilen streiten alle Schlusskurse einer Spalte um Satz 0. Bei 4160-Byte-Zeilen laufen sie durch die Sätze 0, 1, 2, 3 und so weiter und nutzen den ganzen Cache. Der nächste Code liest 96 Schlusskurse zweimal und misst die Fehlzugriffsrate für 1, 2, 4 und 8 Wege.

def column_trace(n_rows, row_bytes, passes):    return [i * row_bytes for i in range(n_rows)] * passesdef miss_rates_by_ways(trace, size_bytes, line_bytes, ways_list):    rates = {}    for ways in ways_list:        cache = SetAssocCache(size_bytes, line_bytes, ways)        for address in trace:            cache.access(address)        rates[ways] = cache.misses / len(trace)    return ratesfor row_bytes in (4096, 4160):    print(row_bytes, miss_rates_by_ways(column_trace(96, row_bytes, 2), 32768, 64, [1, 2, 4, 8]))

4096 {1: 1.0, 2: 1.0, 4: 1.0, 8: 1.0}
4160 {1: 0.5, 2: 0.5, 4: 0.5, 8: 0.5}

Die aufgefüllte Tabelle verfehlt nur im ersten Durchlauf: 0,5 aller Lesezugriffe, gleich wie viele Wege. Die ausgerichtete Tabelle verfehlt bei jedem Zugriff, selbst mit 8 Wegen, denn 96 Zeilen brauchen 96 Plätze und der Satz hat 8. Schlimmer noch: LRU verdrängt in einem zyklischen Muster immer die Zeile, die Sie als Nächstes lesen, der zweite Durchlauf findet also nichts. Mehr Wege würden erst helfen, wenn sie die Zahl der Zeilen erreichen.

Das Labor folgt der Lektion: die Adressaufteilung, der LRU-Cache, die zwei Arten von Spuren, der Vergleich nach Zahl der Wege und die Studie an der echten SPY-Tabelle.

• Funktion · FrageBaut auf
• split_address(address, line_bytes, n_sets)Welches Tag, welchen Satz und welchen Offset hat eine Adresse?Die ganzzahlige Division
• SetAssocCache(size_bytes, line_bytes, ways).access(address)Ist dieser Lesezugriff ein Treffer in einem LRU-Cache mit mehreren Wegen?Sätze von Zeilen in LRU-Reihenfolge
• conflict_trace(n_lines, line_bytes, n_sets, rounds)Welche Adressen kollidieren alle in einem Satz?Einfache Arithmetik
• column_trace(n_rows, row_bytes, passes)Welche Adressen berührt das Lesen einer Spalte?Einfache Arithmetik
• miss_rates_by_ways(trace, size_bytes, line_bytes, ways_list)Wie ändern mehr Wege die Fehlzugriffsrate?SetAssocCache
• study(bars)Was kosten Zeilen im Abstand von 4096 Byte?column_tracemiss_rates_by_ways

Nächstes Thema: Der Cache hält jetzt die richtigen Zeilen, wenn sie nicht kollidieren, aber wie lange bleiben Zeilen nützlich? In Zeitliche Lokalität und Arbeitsmengen messen Sie, wie bald ein Wert wieder gelesen wird, und finden die Cache-Größe, ab der ein Programm hineinpasst.