IN assoziatives Gedächtnis Elemente werden nicht nach Adresse, sondern nach Inhalt ausgewählt. Lassen Sie uns das letzte Konzept genauer erläutern. Für Speicher mit Adressorganisation wurde das Konzept eingeführt minimale adressierbare Einheit(MAE) als Datenelement mit individueller Adresse. Lassen Sie uns ein ähnliches Konzept für einführen assoziatives Gedächtnis, und wir werden diese Mindestspeichereinheit haben assoziatives Gedächtnis Anruf assoziative Speicherzeichenfolge(Gurt). Jeder StrAP enthält zwei Felder: ein Tag-Feld (englisch tag – label, label, attribute) und ein Datenfeld. Eine Leseanforderung an den assoziativen Speicher kann wie folgt in Worten ausgedrückt werden: Wählen Sie die Zeile(n) aus, deren Tag(e) dem angegebenen Wert entspricht.
Wir weisen insbesondere darauf hin, dass bei einer solchen Anfrage eines von drei Ergebnissen möglich ist:
- es gibt genau eine Zeile mit dem angegebenen Tag;
- es gibt mehrere Zeilen mit einem bestimmten Tag;
- Es gibt keine Zeilen mit dem angegebenen Tag.
Die Suche nach einem Datensatz anhand von Attributen ist eine typische Aktion für den Zugriff auf Datenbanken, und die Suche in einer Datenbank wird oft als assoziative Suche bezeichnet. Um eine solche Suche durchzuführen, müssen Sie alle Einträge anzeigen und das angegebene Tag mit dem Tag jedes Eintrags vergleichen. Dies ist auch möglich, wenn zum Speichern von Datensätzen ein gewöhnlicher adressierbarer Speicher verwendet wird (und es ist klar, dass dies ziemlich viel Zeit in Anspruch nehmen wird – proportional zur Anzahl der gespeicherten Datensätze!). Um assoziatives Gedächtnis Sie sagen, wenn das assoziative Abrufen von Daten aus dem Speicher von der Hardware unterstützt wird. Beim Schreiben in den assoziativen Speicher wird ein Datenelement zusammen mit dem diesem Element innewohnenden Tag im StrAP platziert. Dazu können Sie jedes kostenlose StrAP verwenden. Schauen wir uns die Sorten an strukturelle Organisation Cache-Speicher oder Methoden zum Zuordnen von RAM zum Cache.
Vollständig assoziativer Cache
Das Diagramm eines vollständig assoziativen Caches ist in der Abbildung dargestellt (siehe Abbildung unten).
Beschreiben wir den Algorithmus zum Betreiben eines Systems mit Cache-Speicher. Zu Beginn des Betriebs ist der Cache-Speicher leer. Wenn beim Abrufen der erste Befehl ausgeführt wird, werden sein Code sowie mehrere weitere benachbarte Bytes des Programmcodes (langsam) in eine der Cache-Zeilen übertragen und gleichzeitig der obere Teil der Adresse geschrieben zum entsprechenden Tag. So wird die Cache-Zeile gefüllt.
Sollten aus diesem Bereich weitere Auswahlen möglich sein, erfolgt diese aus dem Cache (schnell) – „CACHEHIT“. Stellt sich heraus, dass sich das benötigte Element nicht im Cache befindet, handelt es sich um einen „CACHE-Miss“. In diesem Fall erfolgt der Zugriff auf den RAM (langsam) und gleichzeitig wird die nächste Cache-Zeile gefüllt.
Vollständig assoziative Cache-Speicherschaltung
Der Zugriff auf den Cache erfolgt wie folgt. Nachdem die Ausführungsadresse gebildet wurde, werden ihre höchstwertigen Bits, die das Tag bilden, in Hardware (schnell) und gleichzeitig mit den Tags aller Cache-Zeilen verglichen. In diesem Fall sind nur zwei der drei zuvor aufgeführten Situationen möglich: Entweder liefern alle Vergleiche ein negatives Ergebnis (CACH-Miss) oder es wird ein positives Vergleichsergebnis für genau eine Zeile aufgezeichnet (CACH-Treffer).
Wenn bei einem Lesevorgang ein Cache-Treffer erkannt wird, bestimmen die niederwertigen Bits der Adresse die Position in der Cache-Zeile, aus der Bytes abgerufen werden sollen, und die Art der Operation bestimmt die Anzahl der Bytes. Wenn die Länge eines Datenelements ein Byte überschreitet, sind natürlich Situationen möglich, in denen sich dieses Element (in Teilen) in zwei (oder mehr) verschiedenen Cache-Zeilen befindet und sich die Zeit zum Abrufen eines solchen Elements erhöht. Dem kann entgegengewirkt werden, indem Operanden und Anweisungen entlang der Grenzen von Cache-Zeilen ausgerichtet werden, was bei der Entwicklung optimierender Übersetzer oder bei der manuellen Optimierung von Code berücksichtigt wird.
Wenn ein Cache-Fehler auftritt und keine freien Zeilen im Cache vorhanden sind, müssen Sie eine Cache-Zeile durch eine andere ersetzen.
Das Hauptziel der Ersetzungsstrategie besteht darin, Cache-Zeilen beizubehalten, auf die in naher Zukunft am wahrscheinlichsten zugegriffen wird, und Zeilen zu ersetzen, auf die später oder überhaupt nicht zugegriffen wird. Offensichtlich wird der optimale Algorithmus einer sein, der die Zeile ersetzt, auf die später in der Zukunft zugegriffen wird, als jede andere Cache-Zeile.
Leider ist eine solche Vorhersage praktisch unmöglich und es ist notwendig, Algorithmen zu verwenden, die dem optimalen Algorithmus unterlegen sind. Unabhängig vom verwendeten Ersatzalgorithmus muss er in Hardware implementiert werden, um eine hohe Geschwindigkeit zu erreichen.
Unter den vielen möglichen Ersetzungsalgorithmen sind vier die gebräuchlichsten, aufgelistet in der Reihenfolge abnehmender relativer Wirksamkeit. Jedes davon kann in einem vollständig assoziativen Cache verwendet werden.
Der effizienteste Ersetzungsalgorithmus basiert auf der ältesten Verwendung ( LRU – Zuletzt verwendet ), in dem die Cache-Zeile ersetzt wird, auf die am längsten nicht zugegriffen wurde. Studien haben gezeigt, dass der rückwärtsgerichtete LRU-Algorithmus im Vergleich zum optimalen vorwärtsgerichteten Algorithmus recht gut abschneidet.
Am bekanntesten sind zwei Methoden zur Hardware-Implementierung dieses Algorithmus. Im ersten Fall ist jeder Cache-Zeile ein Zähler zugeordnet. In bestimmten Abständen wird dem Inhalt aller Zähler eine Einheit hinzugefügt. Beim Zugriff auf eine Zeile wird deren Zähler auf Null zurückgesetzt. Daher, größte Zahl befindet sich im Zähler der Zeile, auf die am längsten nicht zugegriffen wurde, und diese Zeile ist der erste Kandidat für eine Ersetzung.
Die zweite Methode wird mithilfe einer Warteschlange implementiert, in der Verweise auf diese Zeilen in der Reihenfolge eingegeben werden, in der die Cache-Speicherzeilen gefüllt sind. Bei jedem Zugriff auf eine Zeile wird der Verweis darauf an das Ende der Warteschlange verschoben. Dadurch steht als erstes in der Warteschlange jedes Mal ein Link zu der Zeile, auf die am längsten nicht zugegriffen wurde. Diese Zeile wird zuerst ersetzt.
Ein weiterer möglicher Ersetzungsalgorithmus ist ein First-In-First-Out-Algorithmus ( FIFO – First In First Out ). Hierbei wird die Zeile ersetzt, die am längsten im Cache-Speicher war. Der Algorithmus lässt sich leicht mithilfe der zuvor besprochenen Warteschlange implementieren. Der einzige Unterschied besteht darin, dass sich nach dem Zugriff auf eine Zeichenfolge die Position des entsprechenden Links in der Warteschlange nicht ändert.
Ein anderer Algorithmus ersetzt die am wenigsten häufig verwendete Zeichenfolge (LFU – Least Frequently Used). Die Zeile im Cache-Speicher, auf die am wenigsten zugegriffen wurde, wird ersetzt. Das Prinzip lässt sich in die Praxis umsetzen, indem man jeder Zeile einen Trefferzähler zuordnet, zu dessen Inhalt nach jedem Treffer einer hinzugefügt wird. Der Hauptkandidat für die Ersetzung ist die Zeichenfolge, deren Zähler die kleinste Zahl enthält.
Der einfachste Algorithmus besteht darin, eine zu ersetzende Zeichenfolge zufällig auszuwählen. Die zu ersetzende Zeichenfolge wird zufällig ausgewählt. Dies kann beispielsweise durch einen Zähler realisiert werden, dessen Inhalt sich mit jedem Takt um eins erhöht, unabhängig davon, ob ein Treffer oder ein Fehlschlag vorliegt. Der Wert im Zähler bestimmt die zu ersetzende Zeichenfolge.
Zusätzlich zu den Tag- und Datenbytes kann die Cache-Zeile zusätzliche Servicefelder enthalten, unter denen zunächst das Gültigkeitsbit V (von valid) und das Modifikationsbit M (von modifizieren – ändern, modifizieren) zu beachten sind. Wenn die nächste Cache-Zeile gefüllt ist, wird V auf den Status „gültig“ und M auf den Status „nicht geändert“ gesetzt. Wenn der Inhalt dieser Zeile während der Programmausführung geändert wurde, schaltet das M-Bit um und signalisiert, dass beim Ersetzen dieser Zeile deren Inhalt in den RAM neu geschrieben werden soll. Wenn aus irgendeinem Grund eine Änderung in einer Kopie eines Elements dieser Zeile auftritt, die an einem anderen Ort (z. B. im RAM) gespeichert ist, wird Bit V geschaltet. Beim Zugriff auf eine solche Zeile wird ein Cache-Fehler aufgezeichnet (trotz der Tatsache, dass (das Tag stimmt überein) und der Zugriff erfolgt auf den Haupt-RAM. Darüber hinaus kann das Servicefeld Bits enthalten, die den LRU-Algorithmus unterstützen.
Schätzung des Gerätevolumens
Typische Cache-Speichergröße in modernes System- 8...1024 kByte und die Länge der Cache-Zeile beträgt 4...32 Bytes. Die weitere Bewertung erfolgt für eine Cachegröße von 256 KB und eine Zeilenlänge von 32 Byte, was typisch für Systeme mit Pentium- und PentiumPro-Prozessoren ist. Die Tag-Länge beträgt 27 Bit und die Anzahl der Zeilen im Cache beträgt 256 KB/32 = 8192. Genau so viele digitale Komparatoren mit 27-Bit-Codes werden benötigt, um die oben beschriebene Struktur zu implementieren.
Eine grobe Schätzung der Gerätekosten für den Aufbau eines digitalen Komparators ergibt einen Wert von 10 Trans/Bit, und die Gesamtzahl der Transistoren im Komparatorblock allein beträgt:
10*27*8192 = 2 211 840,
Das ist ungefähr eineinhalb Mal weniger als die Gesamtzahl der Transistoren auf einem Pentium-Chip. Somit ist klar, dass die beschriebene Struktur eines vollständig assoziativen Cache-Speichers () nur mit einer geringen Anzahl von Zeilen im Cache realisierbar ist, d. h. mit kleiner Cachegröße (praktisch nicht mehr als 32...64 Zeilen). Größere Caches werden mit einer anderen Struktur erstellt.
Warum sehen wir eine ständige Steigerung der Leistung von Single-Thread-Programmen? Derzeit befinden wir uns in einem Entwicklungsstadium der Mikroprozessortechnologie, in dem die Steigerung der Geschwindigkeit von Single-Thread-Anwendungen nur vom Speicher abhängt. Die Anzahl der Kerne wächst, die Frequenz ist jedoch auf 4 GHz festgelegt und bringt keinen Leistungsgewinn.
Die Geschwindigkeit und Häufigkeit der Speicheroperationen ist die Hauptsache, durch die wir „unser kostenloses Stück Kuchen“ bekommen (Link). Aus diesem Grund ist es wichtig, den Speicher so effizient wie möglich und insbesondere so schnell wie einen Cache zu nutzen. Um ein Programm für einen bestimmten Computer zu optimieren, ist es hilfreich, die Eigenschaften des Prozessor-Cache zu kennen: Anzahl der Ebenen, Größe, Zeilenlänge. Dies ist besonders wichtig bei Hochleistungscode – Systemkernen, mathematischen Bibliotheken.
Wie ermittelt man die Eigenschaften eines automatischen Caches? (Natürlich gilt cpuinfo nicht als geparst, schon allein deshalb, weil wir letztendlich einen Algorithmus erhalten möchten, der problemlos in andere Betriebssysteme implementiert werden kann. Praktisch, nicht wahr?) Genau das werden wir jetzt tun.
Eine kleine Theorie
Derzeit gibt es drei Arten von Cache-Speichern, die weit verbreitet sind: direkt zugeordneter Cache, assoziativer Cache und multiassoziativer Cache.Direkter Mapping-Cache
- Eine bestimmte RAM-Zeile kann einer einzelnen Cache-Zeile zugeordnet werden, es können jedoch viele mögliche RAM-Zeilen jeder Cache-Zeile zugeordnet werden.Vollständig assoziativer Cache
- Jede RAM-Zeile kann jeder Cache-Zeile zugeordnet werden.Multiassoziativer Cache
- Der Cache-Speicher ist in mehrere „Bänke“ unterteilt, von denen jede als direkt zugeordneter Cache fungiert, sodass eine RAM-Zeile nicht einem einzelnen möglichen Cache-Eintrag zugeordnet werden kann (wie es bei einer direkten Zuordnung der Fall wäre). ), sondern an eine von mehreren Banken ; Die Bankauswahl erfolgt basierend auf LRU oder einem anderen Mechanismus für jede im Cache platzierte Zeile.LRU – Entfernung der „längsten ungenutzten“ Zeile, Speichercache.
Idee
Um die Anzahl der Cache-Ebenen zu bestimmen, müssen Sie die Reihenfolge der Speicherzugriffe berücksichtigen, in der der Übergang deutlich sichtbar ist. Verschiedene Cache-Level unterscheiden sich hauptsächlich in der Speicherreaktionsgeschwindigkeit. Im Falle eines Cache-Fehlers sucht der L1-Cache nach Daten in den folgenden Speicherebenen. Wenn die Datengröße größer als L1 und kleiner als L2 ist, entspricht die Speicherantwortgeschwindigkeit der L2-Antwortgeschwindigkeit. Die vorherige Aussage gilt auch in allgemeinen Fällen.Es ist klar, dass wir einen Test auswählen müssen, bei dem wir Cache-Fehler deutlich erkennen und ihn daraufhin testen müssen verschiedene Größen Daten.
Wenn man die Logik satzassoziativer Caches kennt, die mit dem LRU-Algorithmus arbeiten, ist es nicht schwer, einen Algorithmus zu entwickeln, bei dem der Cache „fällt“, nichts Schwieriges - er geht durch die Zeile. Als Effizienzkriterium betrachten wir die Zeit eines Speicherzugriffs. Natürlich müssen Sie nacheinander auf alle Elemente der Linie zugreifen und dies viele Male wiederholen, um das Ergebnis zu mitteln. Beispielsweise kann es Fälle geben, in denen eine Zeile in den Cache passt, wir aber beim ersten Durchgang die Zeile aus dem RAM laden und daher eine völlig unzureichende Zeit erhalten.
Ich würde gerne etwas Ähnliches sehen wie Schritte, die entlang unterschiedlich langer Linien gehen. Um die Art der Schritte zu bestimmen, betrachten Sie ein Beispiel eines Zeilendurchlaufs für einen direkten und assoziativen Cache. Bei einem satzassoziativen Cache handelt es sich um einen Durchschnitt zwischen einem direkt zugeordneten Cache und einem assoziativen Cache.
Assoziativer Cache
Sobald die Datengröße die Cachegröße überschreitet,
Ein vollständig assoziativer Cache verfehlt jeden Speicherzugriff.
Direkter Cache
Lassen Sie uns überlegen verschiedene Größen Linien. - zeigt Höchstmenge Fehlschläge, wodurch die CPU verschwendet wird, um beim nächsten Überqueren der Zeile auf die Array-Elemente zuzugreifen.
Wie Sie sehen, steigt die Speicherzugriffszeit nicht stark an, sondern mit zunehmender Datenmenge. Sobald die Datengröße die Cachegröße überschreitet, kommt es bei jedem Speicherzugriff zu Fehlern.
Bei einem assoziativen Cache ist der Schritt daher vertikal, während er bei einem direkten Cache schrittweise bis zur doppelten Cache-Größe ansteigt. Ein multiassoziativer Cache wird ein durchschnittlicher Fall sein, ein „Bump“, schon allein deshalb, weil die Zugriffszeit nicht besser sein kann als bei einem direkten.
Wenn wir über Speicher sprechen, ist der Cache am schnellsten, gefolgt vom Betriebsspeicher, und am langsamsten ist der Swap. Darüber werden wir in Zukunft nicht mehr sprechen. Wiederum, verschiedene Ebenen Cache (normalerweise haben Prozessoren heute 2-3 Cache-Ebenen) unterschiedliche Geschwindigkeit Speicherreaktion: Je höher die Stufe, desto langsamer die Reaktionsgeschwindigkeit. Wenn also eine Zeile im Cache der ersten Ebene platziert wird (der übrigens vollständig assoziativ ist), ist die Antwortzeit kürzer als bei einer Zeile, die deutlich größer als der Cache der ersten Ebene ist. Daher gibt es in der Grafik der Speicherantwortzeit im Verhältnis zur Zeilengröße mehrere Plateaus – ein Plateau* der Speicherantwort und Plateaus, die durch unterschiedliche Cache-Level verursacht werden.
*Funktionsplateau - ( i:x, f(xi) - f(xi+1)< eps: eps → 0 }
Beginnen wir mit der Umsetzung
Für die Implementierung verwenden wir C (ANSI C99).Der Code wurde schnell geschrieben, der übliche Durchgang durch Zeilen unterschiedlicher Länge, weniger als 10 MB, viele Male ausgeführt. (Wir werden kleine Teile des Programms vorstellen, die eine semantische Last tragen).
Für (i = 0; i< 16; i++) { for (j = 0; j < L_STR; j++) A[j]++; }
Wir schauen uns die Grafik an und sehen einen großen Schritt. Aber theoretisch klappt alles ganz gut. Daher müssen Sie verstehen: Warum passiert das? Und wie kann man es beheben?
Dies kann offensichtlich aus zwei Gründen passieren: Entweder verfügt der Prozessor nicht über einen Speichercache, oder der Prozessor ist so gut darin, Speicherzugriffe zu erraten. Da die erste Option näher an Science-Fiction ist, ist der Grund für alles eine gute Vorhersage von Anrufen.
Tatsache ist, dass sie heute weit davon entfernt sind, Spitzenprozessoren zu sein, und dass sie neben dem Prinzip der räumlichen Lokalität auch Vorhersagen treffen arithmetische Folge in der Reihenfolge des Speicherzugriffs. Daher ist es notwendig, Speicherzugriffe zu randomisieren.
Die Länge des randomisierten Arrays sollte mit der Länge der Hauptzeichenfolge vergleichbar sein, um die große Granularität der Aufrufe zu beseitigen, und die Länge des Arrays sollte keine Zweierpotenz sein, da es dadurch zu „Überlappungen“ kommt - was zu Ausreißern führen kann. Am besten legen Sie die Granularität konstant fest. Auch wenn es sich bei der Granularität um eine Primzahl handelt, können Sie die Auswirkungen von Überlagerungen vermeiden. Und die Länge eines randomisierten Arrays ist eine Funktion der Länge der Zeichenfolge.
für (i = 0; i< j; i++) {
for (m = 0; m < L; m++) {
for (x = 0; x < M; x++){
v = A[ random[x] + m ];
}
}
}
Danach überraschte uns das lang erwartete „Bild“, über das wir zu Beginn gesprochen hatten.
Das Programm ist in zwei Teile unterteilt: Testen und Datenverarbeitung. Es liegt an Ihnen, zu entscheiden, ob Sie ein Skript in drei Zeilen schreiben, um es auszuführen, oder es zweimal manuell ausführen.
Auflisten der size.file unter Linux
#enthalten
Auflistung der Dateigröße unter Windows
#enthalten
sonst k += 4*1024;
) 0 zurückgeben; )
Im Allgemeinen denke ich, dass alles klar ist, aber ich möchte einige Punkte klarstellen.
Array A wird als flüchtig deklariert – diese Direktive garantiert uns, dass auf Array A immer zugegriffen wird, das heißt, sie werden weder vom Optimierer noch vom Compiler „herausgeschnitten“. Erwähnenswert ist auch, dass die gesamte Rechenlast vor der Zeitmessung ausgeführt wird, wodurch wir den Hintergrundeinfluss reduzieren können.
Die Datei wird unter Ubuntu 12.04 und dem gcc 4.6-Compiler in Assembler übersetzt – die Zyklen werden gespeichert.Datenverarbeitung
Es ist logisch, Derivate zur Datenverarbeitung zu verwenden. Und trotz der Tatsache, dass das Rauschen mit zunehmender Differenzierungsordnung zunimmt, werden die zweite Ableitung und ihre Eigenschaften verwendet. Egal wie verrauscht die zweite Ableitung ist, uns interessiert nur das Vorzeichen der zweiten Ableitung.
Wir finden alle Punkte, an denen die zweite Ableitung größer als Null ist (mit einem gewissen Fehler, da die zweite Ableitung nicht nur numerisch berechnet wird, sondern auch sehr verrauscht ist). Wir legen eine Funktion abhängig vom Vorzeichen der zweiten Ableitung der Funktion auf der Cache-Größe fest. Die Funktion nimmt den Wert 1 an Stellen an, an denen das Vorzeichen der zweiten Ableitung größer als Null ist, und Null, wenn das Vorzeichen der zweiten Ableitung kleiner oder gleich Null ist.
#enthalten
double round (double x) ( int mul = 100; if (x > 0) return floor(x * mul + .5) / mul; else return ceil(x * mul - .5) / mul; ) Float-Größe, Zeit , der_1, der_2; int main())( size = 0; time = 0; der_1 = 0; der_2 = 0; int i, z = 110; for (i = 1; i
2) der_2[i] = 1;
sonst der_2[i] = 0;//Kamm für (i = 0; i
Tests
CPU/Betriebssystem/Kernelversion/Compiler/Kompilierungsschlüssel werden für jeden Test angezeigt.- Intel Pentium CPU P6100 @2,00 GHz / Ubuntu 12.04 / 3.2.0-27-generic / gcc -Wall -O3 size.c -lrt L1 = 0,05 MB L2 = 0,2 MB
L3 = 2,7 MB
Ich werde nicht alles auflistenDas Problem liegt in der geringen Anzahl von Punkten, die in das Intervall bis zum Erreichen des Plateaus fallen; dementsprechend ist der Sprung in der zweiten Ableitung nicht wahrnehmbar und wird als Rauschen gewertet.
Sie können dieses Problem mit der Methode lösen kleinste Quadrate, oder führen Sie Tests durch, während Sie Plateauzonen identifizieren.
Ich würde gerne Ihre Vorschläge zur Lösung dieses Problems hören.
Referenzen
- Makarov A.V. Computerarchitektur und Low-Level-Programmierung.
- Ulrich Drepper Was jeder Programmierer über Speicher wissen sollte
CACHE-Ebenen.
Der Mikroprozessor hat normalerweise mehrere Cache-Ebenen-A(Prozessor-Cache-Speicher, Cache). Erste ( L1 & L1i(Cache für Anweisungen)), zweite ( L2) und drittens ( L3) (es gibt mehr zu Serverlösungen).
Die untere nach Cache-Rang, desto langsamer die Geschwindigkeit seine Arbeit.
Erste Ebene funktioniert normalerweise bei Prozessorfrequenz und hat der breiteste Reifen, aber auch das kleinste Volumen. Dient zur Adressierung von Befehlen Und Anweisungen, nicht jedoch deren vorübergehende Speicherung.
Zweiter und Dritter Ebenen CACHE-und dienen Werte aufzeichnen Berechnungen und für offizielle Informationen, gebraucht öfter im Moment. Hat mehrere Male B O größeres Volumen als der First-Level-Cache, aber auch in n um ein Vielfaches kleinerer Reifen, Was Negativ wirkt Bandbreite.
Cache passiert geteilt(pro Kern) und allgemein(kombiniert).
Zweifellos Gemeinsamer Cache funktioniert Schneller. Da in geteilt Cache, wenn ein Kern Informationen benötigt, die zuvor vorhanden waren von einem anderen Kernel berechnet und ist in seinem CACHE, dann muss es viel langsameren RAM durchlaufen. Manchmal ist es schneller, erneut zu zählen, was der Prozessor tut. Und im Falle des Allgemeinen Cache, könnte einfach Daten nehmen aus Gemeinsamer Cache.
Zum Beispiel ein Prozessor Intel C2D q9550 besteht aus zwei Intel C2D E8400.
Vier Kerne werden nicht nur aufgrund der Nutzung gemeinsam genutzter Busressourcen langsamer sein. L2-Cache ist mittlerweile nicht mehr üblich und er muss nach Workarounds suchen, wenn z.B Kern 1 benötigte verarbeitete Informationen Kern 3. Das erhöht die Zeit Informationsverarbeitung, wodurch die Leistung verringert wird.
Cache-Erinnerung angerufen vollständig assoziativ, wenn jede Zeile RAM kann überall platziert werden Cache-Erinnerung.
In einem voll assoziativen Cache-Speicher nutzt sein gesamtes Volumen maximal aus: Repression Die im CP gespeicherten Informationen werden erst nach vollständiger Ausfüllung ausgeführt. Jedoch suchen V Cache-Speicher auf diese Weise zu organisieren ist eine schwierige Aufgabe.
Ein Kompromiss zwischen diesen beiden Organisationsarten Cache-Dient der Erinnerung mehrfach-assoziativ CP, in dem jede Zeile RAM kann an einer begrenzten Anzahl von Orten in gefunden werden Cache-Erinnerung.
Ersetzen Sie ggf. die Informationen in Cache-Ein neuer Speicher wird mehrmals verwendet Ersatzstrategien. Die bekanntesten unter ihnen sind:
1. LRU- die Zeile, auf die am längsten nicht zugegriffen wurde, wird ersetzt;
2. FIFO – die älteste Zeile im Cache-Speicher wird ersetzt;
3. Zufällig – die Ersetzung erfolgt zufällig.
Die letzte Option, die erheblich spart Hardware Im Vergleich zu anderen Ansätzen bietet es in einigen Fällen mehr effiziente Nutzung Cache-Erinnerung. Nehmen wir zum Beispiel an, dass der CP eine Länge von 4 Zeilen hat und ein zyklischer Abschnitt des Programms eine Länge von 5 Zeilen hat. In diesem Fall mit Strategien LRU und FIFO Cache-Erinnerung wird aufgrund des Mangels praktisch nutzlos sein Cache-Treffer. Gleichzeitig führt die Verwendung der Strategie des zufälligen Informationsaustauschs dazu, dass einige Anrufe an den CP gesendet werden Cache- Treffer.
Korrespondenz zwischen Daten im RAM und in Cache-Speicher wird bereitgestellt, indem Änderungen an diesen Bereichen vorgenommen werden RAM, für die die Daten in Cache-Erinnerungen haben Veränderungen erfahren. Es gibt zwei Hauptmethoden zum Implementieren dieser Aktionen: Durchschreiben und Zurückschreiben.
Beim Lesen funktionieren beide Methoden identisch. Bei der Aufnahme Write-Through-Caching Aktualisierungen Arbeitsspeicher parallel zur Aktualisierung der Informationen im CP. Dies verringert sich etwas Leistung Systeme, da Mikroprozessor Anschließend können Sie sich erneut an dieselbe Adresse wenden, um Informationen aufzunehmen und die vorherige Weiterleitung der Leitung vorzunehmen Cache-Speicher ein RAM wird sich als nutzlos erweisen. Bei diesem Ansatz werden jedoch die Inhalte der entsprechenden Zeilen angezeigt RAM und der CP ist immer identisch. Dies spielt im Multiprozessorbetrieb eine große Rolle Systeme mit gemeinsamen RAM.
Write-Back-Cachingändert eine Zeichenfolge RAM erst wenn Repression Linien Cache-Speicher zum Beispiel, wenn Platz zum Schreiben einer neuen Zeile frei werden muss RAM zum bereits gefüllten CP. Operationen Rückschreibungen werden ebenfalls durch den Konsistenzmechanismus initiiert Cache-Speicher beim Betrieb eines Multiprozessorsystems mit gemeinsam genutztem RAM.
Eine Zwischenstellung zwischen diesen Ansätzen nimmt ein Verfahren ein, bei dem alle zur Übertragung vom CP an vorgesehenen Zeichenfolgen erfasst werden RAM, werden in einem Puffer vorab angesammelt. Die Übertragung erfolgt entweder wann Repression Linien, wie in Write-Back-Caching, ggf. Genehmigung Cache-Speicher mehrerer Mikroprozessoren in einem Multiprozessorsystem oder wenn der Puffer voll ist. Diese Übertragung erfolgt im Batch-Modus, was effizienter ist als die Übertragung einer einzelnen Zeile.
11. Mikroprozessor (MP). Definition. Ausgeführte Funktionen. Grundparameter. MP-Typen abhängig von den Befehlssystemen (CISC, RISC, VLIW).
Ein Mikroprozessor ist ein softwaregesteuertes Universalgerät zur digitalen Verarbeitung diskreter und (oder) analoger Informationen und zur Steuerung des Prozesses dieser Verarbeitung, das auf einem oder mehreren aufgebaut ist. große integrierte Schaltkreise (LSI)
MP-Funktionen.
Nach dem Einschalten geht der Prozessor zur ersten Adresse des Startprogramms und führt dieses Programm aus. Dieses Programm vorab im permanenten (nichtflüchtigen) Speicher aufgezeichnet. Nach Abschluss des anfänglichen Startprogramms beginnt der Prozessor mit der Ausführung des im Permanent- oder RAM-Speicher befindlichen Hauptprogramms, für das er nacheinander alle Befehle auswählt. Der Prozessor kann durch externe Interrupts oder DMA-Anfragen von diesem Programm abgelenkt werden. Der Prozessor wählt Anweisungen aus dem Speicher mithilfe von Lesezyklen über den Bus aus. Bei Bedarf schreibt der Prozessor Daten mithilfe von Schreibzyklen in den Speicher oder an E/A-Geräte oder liest Daten mithilfe von Lesezyklen aus dem Speicher oder an E/A-Geräten.
Somit sind die Hauptfunktionen eines jeden Prozessors wie folgt:
1) Abtasten (Lesen) ausgeführter Befehle;
2) Eingabe (Lesen) von Daten aus dem Speicher oder einem Eingabe-/Ausgabegerät;
3) Daten in Speicher oder Eingabe-/Ausgabegeräte ausgeben (schreiben);
4) Verarbeitung von Daten (Operanden), einschließlich arithmetischer Operationen darauf;
5) Speicheradressierung, d. h. Festlegen der Speicheradresse, mit der der Austausch durchgeführt wird;
6) Interrupt-Verarbeitung und Direktzugriffsmodus.
Optionen
Hauptmerkmale des Mikroprozessors
Mikroprozessoren unterscheiden sich in zwei Hauptmerkmalen voneinander: Typ (Modell) und Taktfrequenz. Identische Mikroprozessormodelle können unterschiedliche Taktfrequenzen haben – je höher die Taktfrequenz, desto höher sind Leistung und Preis des Mikroprozessors. Die Taktfrequenz gibt an, wie viele Elementaroperationen (Zyklen) der Mikroprozessor in einer Sekunde ausführt. Die Taktrate wird in Megahertz (MHz) gemessen. Das ist zu beachten verschiedene Modelle Mikroprozessoren führen die gleichen Operationen aus andere Nummer schlägt Je höher das Mikroprozessormodell, desto weniger Taktzyklen sind erforderlich, um die gleichen Vorgänge auszuführen.
Schauen wir uns die Eigenschaften von Prozessoren genauer an.
1. Typ des Mikroprozessors.
Der Typ des im Computer installierten Mikroprozessors ist der Hauptfaktor, der das Erscheinungsbild des PCs bestimmt. Die Rechenleistung eines Computers hängt davon ab. Abhängig von der Art des verwendeten Mikroprozessors und den dadurch bestimmten Architekturmerkmalen des Computers werden fünf Klassen von PCs unterschieden:
Computer der XT-Klasse;
Computer der AT-Klasse;
Computer Klasse 386;
Computer der Klasse 486;
Computer der Pentium-Klasse.
2. Taktfrequenz des Mikroprozessors – gibt an, wie viele Elementaroperationen (Zyklen) der Mikroprozessor in einer Sekunde ausführt.
Der Taktgenerator erzeugt eine Folge elektrischer Impulse. Die Frequenz der erzeugten Impulse bestimmt die Taktfrequenz der Maschine. Das Zeitintervall zwischen benachbarten Impulsen bestimmt die Zeit eines Betriebszyklus der Maschine oder einfach den Betriebszyklus der Maschine.
Die Frequenz des Taktgenerators ist eines der Hauptmerkmale Personalcomputer und bestimmt maßgeblich die Arbeitsgeschwindigkeit, da jeder Arbeitsgang in der Maschine in einer bestimmten Anzahl von Zyklen ausgeführt wird.
3. Die Geschwindigkeit des Mikroprozessors ist die Anzahl der elementaren Operationen, die der Mikroprozessor pro Zeiteinheit ausführt (Operationen/Sekunde).
4. Prozessorbitkapazität – die maximale Anzahl von Bits des Binärcodes, die gleichzeitig verarbeitet oder übertragen werden können.
Die Bitkapazität des MP wird mit m/n/k/ bezeichnet und umfasst: m – die Bitkapazität interner Register, bestimmt die Zugehörigkeit zu einer bestimmten Prozessorklasse; n – Datenbusbreite, bestimmt die Geschwindigkeit der Informationsübertragung; k – Adressbusbreite, bestimmt die Größe des Adressraums. Beispielsweise wird der i8088 MP durch die Werte m/n/k=16/8/20 charakterisiert.
5. Mikroprozessorarchitektur. (Typen von Mikroprozessoren)
Das Konzept der Mikroprozessorarchitektur umfasst ein System von Befehlen und Adressierungsmethoden, die Fähigkeit, die Ausführung von Befehlen rechtzeitig zu kombinieren, das Vorhandensein zusätzlicher Geräte im Mikroprozessor sowie Prinzipien und Betriebsarten seines Betriebs.
Entsprechend den architektonischen Merkmalen, die die Eigenschaften des Befehlssystems bestimmen, gibt es:
Mikroprozessoren vom Typ CISC mit einem vollständigen Satz an Befehlssystemen (der größte Befehlssatz, universelle MPs, ersetzen ganze Systeme);
Mikroprozessoren vom Typ RISC mit verkürztem Befehlssatz (müssen schnell eine Reihe von Operationen ausführen (insgesamt 120 Befehle), zum Beispiel: Steuerung von Peripheriegeräten);
Mikroprozessoren vom Typ VLIW mit einem sehr langen Befehlswort ((sehr langer Befehl) – Architekturen zur Berechnung statistischer Parameter. Ihre Aufgabe sind riesige Berechnungen);
Mikroprozessoren vom Typ MISC mit minimalem Befehlssatz und sehr hoher Geschwindigkeit usw.
12. Server-Mikroprozessoren. Leistungsanforderungen. Besonderheiten.
Server MP – schnelle Ausführung von Operationen. Aufgaben schnell erledigen. Adressieren Sie eine große Anzahl von OPs und müssen Sie keine Aufgaben ausführen.
Zum Beispiel XEON, AMD Optiron, diese Prozessoren sparen keinen Strom. Sie haben keinen guten Grafikkern.
Spezifikationen:
-Frequenz
-Chipsatz
-Multiprozessorsystem
Cache-Architektur.
Abhängig von der Methode zur Bestimmung der gegenseitigen Korrespondenz zwischen einer Cache-Zeile und einem Bereich des Hauptspeichers werden drei Cache-Speicherarchitekturen unterschieden: Direct-Mapping-Cache, vollständig assoziativer Cache, teilweise oder satzassoziativer Cache.
Direkt zugeordneter Cache.
Beim Direct-Mapping-Cache bestimmt die Speicheradresse, auf die zugegriffen wird, eindeutig die Cache-Zeile, in der sich der erforderliche Block befinden kann. Wir erklären die Funktionsweise eines solchen Caches am Beispiel eines nicht sektorierten Caches von 256 KB mit einer Zeilengröße von 32 Byte und einer zwischengespeicherten Hauptspeicherkapazität von 64 MB – einem typischen Cache eines Pentium-Motherboards. Die Struktur des Cache-Speichers in einem solchen System ist in Abb. dargestellt. 1. Der zwischengespeicherte Hauptspeicher ist bedingt in Seiten unterteilt (in diesem Fall jeweils 256 KB), deren Größe mit der Größe des Cache-Speichers (256 KB) übereinstimmt. Der Cache-Speicher (und bedingt auch die Hauptspeicherseiten) ist in Zeilen unterteilt (256 KB / 32 Bytes – 8 K-Zeilen). Direkte Zuordnungsarchitektur bedeutet, dass jede Cache-Zeile nur die ihr entsprechende Zeile von jeder Seite des zwischengespeicherten Speichers abbilden kann. Da die Größe des Hauptspeichers viel größer ist als die Größe des Caches, kann jede Cache-Zeile von vielen Speicherblöcken mit demselben niederwertigen Teil der Adresse beansprucht werden, der als Offset innerhalb der Seite bezeichnet wird (0 – gesetzt, 1-Satz, 2-Satz ... N-Satz von 32-Byte-Blöcken). Eine Zeile kann zu einem bestimmten Zeitpunkt eine Kopie nur eines dieser Blöcke enthalten. Die Zeilennummer ist die Adresse der Zeile im Cache-Speicher, und das Tag enthält Informationen darüber, welcher Block belegt ist diese Zeile(Ein Tag ist der obere Teil der Adresse, die der Prozessor beim Zugriff auf den Speicher festlegt, oder mit anderen Worten die Seitennummer). Der Tag-Speicher muss eine Anzahl von Zellen haben, die der Anzahl von Cache-Zeilen entspricht, und seine Breite muss ausreichend sein, um die höchstwertigen Bits der Cache-Speicheradresse aufzunehmen, die nicht auf den Cache-Adressbus fallen. Zusätzlich zum Adressteil des Tags sind jeder Cache-Zeile Zeichenbits für die Datengültigkeit und -änderung zugeordnet. Zu Beginn jedes Zugriffs auf den RAM liest der Cache-Speichercontroller zunächst eine Tag-Speicherzelle mit einer durch die Bits A17-A5 bestimmten Zeilenadresse und vergleicht den Inhalt dieser Tag-Speicherzeile mit den Bits A25-A18 des Speichers vom Prozessor festgelegte Adresse und analysiert ein Zeichen der Realität.
Reis. 1. Direkt zugeordneter Cache.
Diese Analyse wird in einer speziellen Tracking-Schleife durchgeführt, die manchmal auch Abfrageschleife genannt wird. Ergibt die Analyse, dass sich der benötigte Block nicht im Cache befindet, wird ein Hauptspeicherzugriffszyklus (Cache-Miss) generiert (oder fortgesetzt). Bei einem Treffer wird die Anfrage vom Cache-Speicher bedient. Im Falle eines Fehlers werden die neuen Daten in der Cache-Zeile abgelegt (sofern sie sauber sind), nachdem der Empfänger die Informationen aus dem Hauptspeicher gelesen hat. , und die höchstwertigen Bits der Adresse werden in ihrem Tag platziert und die Gültigkeit der Daten wird festgelegt. Unabhängig von der vom Hauptspeicher in den Cache angeforderten Datenmenge wird die gesamte Zeile neu geschrieben (da der Gültigkeitsindikator für alle Bytes gilt). Wenn der Cache-Controller das Vorauslesen implementiert, wird in nachfolgenden freien Buszyklen auch die nächste Zeile (sofern sie sauber war) aktualisiert ). Das Lesen „in Reserve“ ermöglicht bei Bedarf die Durchführung eines Batch-Lesezyklus aus dem Cache über eine Zeilengrenze hinweg. Dieser Cache verfügt über die einfachste Hardware-Implementierung und wird im sekundären Cache der meisten Motherboards verwendet. Es hat jedoch einen gravierenden Nachteil. Wenn der Prozessor während der Programmausführung abwechselnd auf dieselbe Zeilenadresse zugreift, jedoch mit unterschiedlichen oder sich zyklisch ändernden Tag-Nummern, werden ständig Cache-Misses aufgezeichnet und der Cache-Speicher verlangsamt den Austausch mit dem Speicher, anstatt ihn zu beschleunigen. Der Seitenwechsel in Multitasking-Betriebssystemen (OS) reduziert auch die Anzahl der Cache-Treffer, was sich auf die Systemleistung auswirkt. Das Erhöhen der Cache-Größe bei gleichzeitiger Beibehaltung der Direct-Mapping-Architektur hat keine großen Auswirkungen, da verschiedene Aufgaben dieselben Cache-Zeilen beanspruchen. Ohne die Cache-Größe zu erhöhen, können Sie die Effizienz des Cachings steigern, indem Sie seine Struktur ändern, was weiter unten erläutert wird.
Manchmal umfasst die Beschreibung eines Direct Map Caches den Begriffssatz, der in einem sektorierten Direct Map Cache anstelle des Begriffs Zeile verwendet wird, und der Sektor wird dann als Zeile bezeichnet. Einem Satz (sowie einer unsektorierten Cache-Zeile) sind Tag-Informationen zugeordnet, die für alle Elemente des Satzes (Zeilen oder Sektoren) gelten. Darüber hinaus verfügt jedes Element der Menge (Zeile oder Sektor) über ein eigenes Gültigkeitsbit (Abb. 2).
Reis. 2. Sektorierter Direct-Mapping-Cache
Mengenassoziativer (teilassoziativer) Cache.
Die satzassoziative Cache-Architektur (Abbildung 3) ermöglicht es jedem zwischengespeicherten Speicherblock, eine von mehreren Cache-Zeilen zu beanspruchen, die zu einem Satz zusammengefasst sind. In dieser Architektur gibt es sozusagen mehrere parallele und koordinierte Direct-Mapping-Kanäle, wobei der Cache-Controller eine Entscheidung darüber treffen muss, in welcher der Zeilen des Satzes der nächste Datenblock platziert werden soll. Im einfachsten Fall kann beispielsweise jeder Speicherblock in eine von vier Satzzeilen passen (ein satzassoziativer Vier-Wege-Cache). Die eingestellte Nummer, in der der angeforderte Datenblock angezeigt werden kann, wird eindeutig durch den mittleren Teil der Adresse bestimmt (wie die Zeilennummer im Direct-Mapping-Cache). Die Satzzeile, die den erforderlichen Block darstellt, wird durch einen Tag-Vergleich (wie in einem assoziativen Cache) bestimmt, der parallel für alle Tag-Speicherzeilen eines bestimmten Satzes (Cache-Kanäle) durchgeführt wird. Darüber hinaus muss jedem Satz ein Zeichen zugeordnet sein, das die Satzzeile definiert, die im Falle eines Cache-Miss durch einen neuen Datenblock ersetzt werden soll (in der Abbildung zeigt ein Pfeil in seine Richtung).
Reis. 3. Vierkanaliger satzassoziativer Cache
Der Ersetzungskandidat ist in der Regel die Zeile, auf die am längsten nicht zugegriffen wurde (LRU – Least Recent Used-Algorithmus). Bei einer relativ großen Anzahl von Kanälen (Leitungen in einem Satz) wird auf eine gewisse Vereinfachung zurückgegriffen – der Pseudo-LRU-Algorithmus für vier Leitungen ermöglicht Entscheidungen mit nur 3 Bits.
Es ist auch möglich, einen FIFO-Ersetzungsalgorithmus (First In, First Out) oder sogar eine zufällige Ersetzung zu verwenden, was einfacher, aber weniger effizient ist. Die satzassoziative Architektur wird häufig für den primären Cache moderner Prozessoren verwendet.
Assoziativer Cache.
Im Gegensatz zu den vorherigen hat ein vollständig assoziativer Cache eine beliebige Zeile kann jeden Speicherblock zuordnen, was die Effizienz bei der Nutzung begrenzten Cache-Speicherplatzes erheblich erhöht. In diesem Fall alle Bits
Reis. 4. Vollständig assoziativer Cache-Speicher.
Die Adressen des zwischengespeicherten Blocks abzüglich der Bits, die die Position (Offset) der Daten in der Zeile bestimmen, werden im Tag-Speicher gespeichert. Um in einer solchen Architektur (Abb. 4) das Vorhandensein der angeforderten Daten im Cache-Speicher festzustellen, ist ein Vergleich mit dem oberen Teil der Tag-Adresse aller Tag-Speicherzeilen erforderlich und nicht mit einer oder mehreren, wie bei der direkten Zuordnung oder Eine satzassoziative Architektur ist erforderlich. Die sequentielle Aufzählung von Tag-Speicherzellen entfällt. (Dies nimmt zu viel Zeit in Anspruch), daher bleibt ein paralleler Vergleich der Tags aller Zellen bestehen, und dies ist eine komplexe Hardwareaufgabe, die nur für kleine Volumina des Primärcaches (M2 Cyrix-Prozessor) akzeptabel gelöst werden kann.
Dieser Speichertyp liegt zwischen den beiden oben diskutierten. Es kombiniert die Einfachheit eines direkt zugeordneten Caches mit der Geschwindigkeit einer assoziativen Suche.
Der Cache-Speicher ist in disjunkte Teilmengen (Blöcke) von Zeilen unterteilt. Jede Hauptspeicherzeile kann nur in eine Cache-Untermenge gehen. Für die Suche nach Blöcken wird die direkte Zuordnung verwendet, und für die Suche innerhalb einer Teilmenge wird die vollständig assoziative Suche verwendet. Die Anzahl der Zeilen in einer Cache-Teilmenge bestimmt die Anzahl der Eingänge (Ports) des Caches selbst.
Wenn 2 n Cache-Zeilen in 2 s disjunkte Teilmengen unterteilt werden, geben die S niederwertigen Bits des RAM an, in welcher Teilmenge (Index) die assoziative Suche durchgeführt werden soll. Senior n-s Die Adressbits des Hauptspeichers sind Tags.
Wenn S=0, dann erhalten wir eine Teilmenge, die einem vollständig assoziativen Cache-Speicher entspricht. Wenn S=n, dann erhalten wir 2 n Teilmengen (also eine Zeile – eine Teilmenge). Dies ist ein direkt zugeordneter Cache-Speicher. Wenn 1 £ S £ n-1, dann haben wir einen satzassoziativen Cache-Speicher.
Abbildung 6.5 zeigt ein Beispiel für einen Cache, bei dem S=1 ist, d. h. es gibt zwei Teilmengen Cache-Speicher. Die vom Prozessor generierte physikalische Adresse 0111 wird in Index 1, der der niedrigstwertigen Ziffer entspricht, und Tag 011 unterteilt. Die zweite Teilmenge von Zeilen im Cache-Speicher wird mithilfe des Index ausgewählt, und dann wird eine assoziative Suche unter den Zeilen durchgeführt Zeilen-Tags der ausgewählten Teilmenge. Die gefundene Zeile 7 mit Tag 011 wird auf den Datenbus (SD) übertragen. Die assoziative Suche wird einzeln durchgeführt
vorübergehend für alle Tags, die die kombinatorischen Vergleichsschemata CC1 und CC2 verwenden.
Reis. 6.5. Multiassoziativer Cache
Moderne Prozessoren verwenden Cache-Speicher mit 4 und 8 Eingängen. Eine Erhöhung der Anzahl seiner Eingaben führt dazu rasanter Anstieg die Komplexität der Hardware-Implementierung des Teils des Caches, der eine assoziative Suche nach Tags ermöglicht.
Funktionen zum Aufzeichnen und Ersetzen von Informationen im Cache-Speicher.
Cache-Kohärenz
Der Lesezugriff auf Cache und RAM kann sofort beginnen. Wenn dann die Informationen im Cache fehlen, ist zum Zeitpunkt der Feststellung dieser Tatsache ein Teil des RAM-Zugriffszyklus bereits abgeschlossen, was die Leistung verbessern kann. Befinden sich die Informationen im Cache, kann der Zugriff auf den RAM gestoppt werden.
Beim schreibenden Zugriff kommen zwei Methoden zum Einsatz: Das Schreiben erfolgt nur im Cache oder gleichzeitig im Cache und im RAM. Diese Methoden werden Algorithmen genannt umkehren WB (Zurückschreiben) und durch Aufzeichnungen WT (Write Through) bzw. Die zweite davon ist einfacher, aber auch langsamer, garantiert jedoch, dass Kopien derselben Informationen im Cache und im RAM immer übereinstimmen. Die meisten frühen Intel-Prozessoren verwenden diesen Algorithmus.
Der WB-Writeback-Algorithmus ist schneller. Informationen werden nur dann in den RAM übertragen, wenn eine Zeile von einer anderen OP-Seite an die Stelle einer bestimmten Cache-Zeile übertragen wird oder wenn ein Befehl zum Aktualisieren des Cache-Inhalts ausgeführt wird. Dieser Algorithmus erfordert eine sorgfältigere Verwaltung, da Kopien derselben Informationen manchmal im Cache und im OP unterschiedlich sind. Darüber hinaus ändert sich nicht jede Zeile, während sie sich im Cache befindet. Wenn keine Änderung stattgefunden hat, ist es nicht erforderlich, die Zeichenfolge erneut in den RAM zu schreiben. Normalerweise verwenden sie das M-Flag (modifiziert) im Tag-Speicher. Es wird auf „0“ zurückgesetzt, wenn die Zeile zum ersten Mal in den Cache geladen wird, und auf „1“ gesetzt, wenn Informationen darauf geschrieben werden. Beim Entladen einer Zeile aus dem Cache wird das Schreiben in das OP nur durchgeführt, wenn das M-Flag auf eins gesetzt ist.
Wenn ein Fehler auftritt, muss der Cache-Controller eine zu ersetzende Zeile auswählen. Für die direkte Anzeige sind Hardwarelösungen am einfachsten. Es wird nur eine Zeile auf einen Treffer getestet und nur diese Zeile kann ersetzt werden. Bei einer vollständig assoziativen oder multiassoziativen Cache-Organisation gibt es mehrere Zeilen, aus denen im Falle eines Fehlschlags ein Kandidat ausgewählt werden muss. Um dieses Problem zu lösen, verwenden Sie die folgenden Sonderregeln, genannt Ersatzalgorithmen .
1) FIFO (First In First Out – wer zuerst kommt – wer zuerst geht);
2) LRU (Least Recent Used – länger unbenutzt als andere);
3) LFU (Least Frequently Used – seltener verwendet);
4) Zufällig.
Die erste und die letzte Methode sind am einfachsten zu implementieren, sie berücksichtigen jedoch nicht, wie oft eine bestimmte Cache-Zeile verwendet wird. In diesem Fall kann eine Zeile gelöscht werden, auf die in naher Zukunft zugegriffen wird. Die Fehlerwahrscheinlichkeit ist bei diesen Methoden deutlich höher als bei der zweiten und dritten.
Beim FIFO-Algorithmus wird die Zeile, die zuerst in den Cache gelangt, zum Ersetzen ausgewählt. Jede neu im Cache platzierte Zeile wird am Ende dieser Warteschlange hinzugefügt. Der Algorithmus berücksichtigt nicht seine tatsächliche Verwendung. Beispielsweise können die ersten geladenen Zeilen Daten enthalten, die während des gesamten Vorgangs erforderlich sind. Dies führt zu einer sofortigen Rückkehr zu der Leitung, die gerade ersetzt wurde.
Der LRU-Algorithmus legt fest, dass die Zeile zum Löschen ausgewählt werden soll, die am längsten nicht verwendet wurde. Bei jedem Zugriff auf eine Zeile wird der Zeitstempel aktualisiert. Dies kann mit erheblichen Kosten verbunden sein. In der Praxis wird jedoch am häufigsten der LRU-Algorithmus verwendet. Der Nachteil besteht darin, dass, wenn das Programm eine große Schleife durchläuft, die sich über viele Zeilen erstreckt, es vorkommen kann, dass die Zeile, auf die am längsten nicht zugegriffen wurde, tatsächlich die nächste ist, die verwendet wird.
Einer der LRU-nahen Algorithmen ist der LFU-Algorithmus, nach dem die am wenigsten häufig verwendete Zeile gelöscht wird. In diesem Fall ist es notwendig, die Anzahl der Zugriffe auf jede Leitung zu zählen und zu kontrollieren. Es kann sich herausstellen, dass die am wenigsten genutzte Zeile diejenige ist, die gerade in den Cache-Speicher geschrieben wurde und auf die nur einmal zugegriffen wurde (während auf andere Zeilen häufiger zugegriffen wurde). Es kann entfernt werden, was ein Nachteil des LFU-Algorithmus ist.
Der Inhalt des Cache-Speichers ändert sich unter der Kontrolle des Prozessors. In diesem Fall kann der Hauptspeicher unverändert bleiben. Andererseits können externe Geräte im Direktzugriffsmodus Daten im OP ändern. In diesem Fall ändert der Cache-Speicher seine Daten nicht. Mehr die Situation ist komplizierter in Multiprozessorsystemen, wenn mehrere Prozessoren auf den gemeinsamen Speicher zugreifen. Es entsteht ein Problem Kohärenz Cache-Speicher.
Das Computersystem hat kohärentes Gedächtnis , wenn jeder Lesevorgang an einer Adresse, der von einem Gerät ausgeführt wird, den Wert der letzten Kopie an dieser Adresse zurückgibt, unabhängig davon, welches Gerät die letzte Kopie geschrieben hat. Das Kohärenzproblem ist für Copy-Back-Systeme am wichtigsten. Sie verwenden spezielle Protokolle und jedem Tag werden Markierungen zur Änderung und Zuverlässigkeit der Informationen hinzugefügt. Diese Flags ermöglichen oder verweigern den Zugriff auf Daten.
Laden...
