65
1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung: Lokalitätsprinzip Zeitliche Lokalität Räumliche Lokalität

1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

Embed Size (px)

Citation preview

Page 1: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

1

8 Speicherverwaltung

Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM-Speicher

Grundprinzip zur Überbrückung: Lokalitätsprinzip• Zeitliche Lokalität• Räumliche Lokalität

Page 2: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

8 Speicherverwaltung8.1 Speicherhierarchie (PC Stand Juni 2002)

Register

Primär-Cache (On-Chip)

Sekundär-Cache (On-Chip oder SRAM)

Hauptspeicher (SDRAM)

Sekundärspeicher (Plattenspeicher)

Kapazität (Bytes): Zugriffszeit:

~ 2 K 0,5 ns

2 * 8 - 64 K 0,5 - 1 ns

256 K - 1 M 2 - 10 ns

128 M - 1 G 20 - 50 ns

100 G - 1000 G 8 - 15 ms

Page 3: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

3

8.2 RegisterorganisationRegister und Registerfenster

Register: schnelle Speicherplätzen, auf die in einem Taktzyklus in der Operandenholphase der Befehlspipeline zugegriffen und in der Resultatspeicherphase zurückgespeichert wird

Man unterscheidet: allgemeine Register, Gleitpunktregister, Multimediaregister und Spezialregister (Befehlszähler, Statusregister)

32 allgemeine Register R0 – R31 von je 32 Bit 32 Gleitpunkt-Register F0 – F31 von je 64 Bit IEEE-Format (bzw.

80 Bit internes Intel-Format) 64, 128 (demnächst 256) Bit breite Multimediaregister Oft ist das Register R0 fest mit dem Wert 0 verdrahtet.

Page 4: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

4

Registerfenster-Prinzip

Gründe für Registerfenster• Forderung nach einer Reduzierung der Speicherzugriffe. • Beobachtung des Speicheraufwandes bei Prozeduraufrufen durch

Sicherung des Registersatzes.• Parameterübergabe möglichst über Register• Viele Register sind technisch möglich

Konzept der überlappenden Registerfenster• Bei RISC I, II, SPARC sowie allgem. Register aller weiteren SPARC-

Prozessoren (Super-, Ultra-, Hyper-)

Page 5: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

5

Überlappende Registerfenster bei der SPARC-Architektur

8 in-Register (ins), 8 lokalen Register (locals) und 8 out-Register (outs)

Page 6: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

6

Umlaufspeicher-Organisation am Beispiel eines SPARC-Prozessors mit acht Registerfenstern

Registerfenster: w0 bis w7 Das augenblicklich aktive

Registerfenster wird über den current window pointer (CWP) referenziert.

Für die Erkennung eines window-overflows / window-underflows wird beim SPARC das window-invalid mask-Register (WIM) verwendet.

SAVE-Befehl (Anfang des Unterprogramms) dekrementiert den CWP.

RESTORE-Befehl inkrementiert den CWP.

Page 7: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

7

Einige Charakteristika von Umlaufspeichern

Ein Umlaufspeicher mit n Registerfenstern kann nur n-1 verschachtelte Prozeduraufrufe behandeln.

Eine relativ kleine Anzahl von Registerfenstern reicht für eine effiziente Prozedurbehandlung aus.

Der Berkeley RISC Prozessor verwendete 8 Fenster mit jeweils 16 Registern.

SPARC-Implementierungen verwenden 7 oder 8 Fenster. Beim SPARC zusätzlich 8 globale Register.

Adressierung:Register 0 bis 7 sind die globalen Register und Register 8 bis 31 beziehen sich auf das aktuelle Fenster.

Problem: Prozess-/Thread-Wechsel!

Page 8: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

8

8.3 Virtuelle Speicherverwaltung

Mehrbenutzer-, Multitasking- und mehrfädige (multithreaded) Betriebssysteme stellen hohe Anforderungen an die Speicherverwaltung.

Programme, die in einer Mehrprozessumgebung lauffähig sein sollen, müssen verschiebbar sein, d.h. nicht an festgelegte, physikalische Speicheradressen gebunden sein.

Speicherreferenzen in den Maschinenbefehlen des Objektcodes erfolgen daher über sogenannte virtuelle oder logische Adressen, die erst bei der Programmausführung in physikalische Speicheradressen transformiert werden.

Ein großer einheitlicher Adressraum für die einzelnen Prozesse. Geeignete Schutzmechanismen zwischen den Prozessen unterstützen.

Page 9: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

9

virtuelle Speicherverwaltung

Die virtuelle Speicherverwaltung unterteilt den physikalisch zu Verfügung stehenden Speicher in Speicherblöcke (als Seiten oder Segmente organisiert) und bindet diese an Prozesse.

Damit ergibt sich ein Schutzmechanismus, der den Zugriffsbereich eines Prozesses auf seine Speicherblöcke beschränkt.

Page 10: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

10

Vorteile der virtuellen Speicherverwaltung

großer Adressraum mit einer Abbildung von z.B. 232 bis 264 virtuellen Adressen auf beispielsweise 228 physikalische Adressen für physikalisch vorhandene Hauptspeicherplätze,

eine einfache Relozierbarkeit (relocation), die es erlaubt, das Programm in beliebige Bereiche des Hauptspeichers zu laden oder zu verschieben,

die Verwendung von Schutzbits, die beim Zugriff geprüft werden und es ermöglichen unerlaubte Zugriffe abzuwehren,

ein schneller Programmstart, da nicht alle Code- und Datenbereiche zu Programmbeginn im Hauptspeicher vorhanden sein müssen,

eine automatische (vom Betriebssystem organisierte) Verwaltung des Haupt- und Sekundärspeichers, die den Programmierer von der früher üblichen Overlay-Technik entlastet.

Page 11: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

11

Virtuelle Speicher und Cache-Speicher

Parameter Primär-Cache virtueller Speicher

Block-/Seitengröße 16-128 Bytes 4 K- 64 K Bytes

Zugriffszeit 1-2 Takte 40-100 Takte

Fehlzugriffsaufwand 8-100 Takte 70000-6000 000 Takte

Fehlzugriffsrate 0.5-10% 0.00001-0.001%

Speichergröße 8 K-64 K 16 MB-8 GB

Page 12: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

12

Entscheidungen bei der Organization einer virtuellen Speicherverwaltung

Wo kann ein Speicherblock im Hauptspeicher platziert werden? • Speicherort einer Seite ist im Hauptspeicher beliebig wählbar

Welcher Speicherblock sollte bei einem Fehlzugriff ersetzt werden? • übliche Ersetzungsstrategie ist die LRU-Strategie (least recently

used) Wann muss ein verdrängter Speicherblock in den Sekundärspeicher

zurückgeschrieben werden? • Falls der zu verdrängende Speicherblock im Hauptspeicher

ungeändert ist, so kann dieser einfach überschrieben werden. • Andernfalls muss der verdrängte Speicherblock in den

Sekundärspeicher zurückgeschrieben werden.

Page 13: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

13

Entscheidungen bei der Organization einer virtuellen Speicherverwaltung

Wie wird ein Speicherblock aufgefunden, das sich in einer höheren Hierarchiestufe befindet?

• Um die Tabellengröße zu reduzieren kann ein Hash-Verfahren auf den virtuellen Seiten-/Segmentadressen durchgeführt werden

Welche Seitengröße sollte gewählt werden? • Große Seiten erfassen mehr Speicherplatz und führen

damit zu weniger TLB-Fehlzugriffen. • Kleine Speicherseiten: geringere Fragmentierung des

Speichers und ein schnellerer Prozessstart. • Lösung ist meist mehrere, unterschiedliche Seitengrößen

zuzulassen oder Segmente und Seiten zu kombinieren.

Page 14: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

14

Virtueller Speicher und virtuelle Speicherverwaltung

Logische Adressen (= effektive Adresse!!) werden während der Programmausführung zuerst in virtuelle Adressen und dann in physikalische Speicheradressen transformiert.

Die effektive Adresse entsteht aus einer Programmadresse durch eine Adressberechnung gemäß der im Befehl gewählten Adressierungsart.

Seitenfehler (Page Fault): ein adressiertes Datum steht nicht im physikalischen Speicher.

Die (Speicher)-Seite (Page) muss dann durch eine Betriebssystem-Routine nachgeladen werden. Dieser Vorgang wird Paging genannt.

Das Benutzerprogramm bemerkt diese Vorgänge nicht.

Page 15: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

15

Abbildung virtueller auf physikalische Adressen

Virtuelle Adresse

Virtuelle Seitenadresse Offset-Adresse

Physikalische Adresse

Physikalische Seitenadresse Offset-Adresse

Übersetzungstabelle(n)

Page 16: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

16

Mehrstufige Übersetzungstabellen

Meist geschieht die Übersetzung einer virtuellen in eine physikalische Adresse nicht über eine, sondern — mehrstufig — über mehrere Übersetzungstabellen.

Oft werden zwei Übersetzungstabellen — eine Segmenttabelle und eine Seitentabelle — benutzt.

Ein Teil der virtuellen Seitenadresse adressiert einen Eintrag in der Segmenttabelle, der wiederum mit dem zweiten Teil der virtuellen Seitenadresse einen Eintrag in der Seitentabelle bezeichnet, der dann die physikalische Adresse der Speicherseite enthält.

Die Seiten sind meist Adressbereiche fester Größe (Größenordnung 1 bis 64 KByte), die Segmente bestehen aus einer variablen Anzahl von Seiten.

Page 17: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

Automatische Adressübersetzung bei 80486-und Pentium-Prozessoren

Page 18: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

18

Adressübersetzungspuffer (Translation Look Aside Buffer TLB)

Das softwaremäßige Durchlaufen der Übersetzungstabellen dauert lange

Hardware-Unterstützung: schnelle Hardware-Tabelle, die als Adressübersetzungspuffer (Translation Look Aside Buffer TLB) bezeichnet wird.

Im TLB stehen aktuelle Abbildungspaare der Form: (virtuelle Seitenadresse, physikalische Seitenadresse)

Hardwaremäßig wird der TLB durch einen Assoziativspeicher realisiert, der die angefragte virtuelle Seitenadresse gegen die gespeicherten virtuellen Seitenadressen vergleicht.

Ein TLB enthält meist nur 32, 64 oder 128 Abbildungspaare und befindet sich bei heutigen Mikroprozessoren auf dem Prozessorchip.

Page 19: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

19

Speicherverwaltungseinheit Memory Management Unit (MMU)

Speicherverwaltungseinheit (Memory Management Unit MMU) enthält den TLB und zusätzliche Logik zur Seitenverwaltung und für den Zugriffsschutz. So werden z.B. folgende Bits mitgeführt:

• resident: Die Seite befindet sich im Hauptspeicher.• supervisor: Der Zugriff ist nur dem Betriebssystem erlaubt. • read-only: Schreibzugriff ist verboten. • dirty: Die Seite wurde verändert.• referenced: Ein Zugriff auf die Seite ist erfolgt.

Page 20: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

20

8.4 Cachespeicher

Unter einem Cachespeicher versteht man einen kleinen, schnellen Pufferspeicher, in dem Kopien derjenigen Teile des Hauptspeichers bereitgehalten werden, auf die aller Wahrscheinlichkeit nach von der CPU als nächstes zugegriffen wird.

Die Cachespeicherverwaltung sorgt dafür, dass, weitgehend unabhängig von der Programmausführung durch die CPU, der Inhalt des Cachespeichers in der Regel das Datum enthält, auf das die CPU als nächstes zugreift.

Durch eine Hardware-Steuerung (Cache-Controller) werden automatisch die Daten in den Cache kopiert, auf die der Prozessor zugreift.

Page 21: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

21

Cache

Auf den Cachespeicher soll der Prozessor fast so schnell wie auf seine Register zugreifen können. Er ist deshalb bei Mikroprozessoren direkt auf dem Prozessorchip angelegt oder in der schnellen und teuren SRAM-Technologie realisiert.

Cache-Treffer (Hit): das angeforderte Datum ist im Cachespeicher vorhanden.

Cache-Fehlzugriff (Miss): das angeforderte Datum steht nur im Hauptspeicher.

Hit-Ratio: Trefferquote

Page 22: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

22

Defs

Die Cache-Zugriffszeit thit bei einem Treffer ist die Anzahl der Takte, die benötigt wird, um ein Speicherwort im Cache zu identifizieren, die Verfügbarkeit und Gültigkeit zu prüfen und das Speicherwort der nachfolgenden Pipeline-Stufe zur Verfügung zu stellen.

Die Trefferrate (hit rate) ist der Prozentsatz der Treffer beim Cache-Zugriff bezogen auf alle Cache-Zugriffe.

Die Fehlzugriffsrate (miss rate) ist der Prozentsatz der Cache-Fehlzugriffe bezogen auf alle Cache-Zugriffe.

Der Fehlzugriffsaufwand (miss penalty) tmiss ist die Zeit, die benötigt wird, um einen Cache-Block von einer tiefer gelegenen Hierarchiestufe in den Cache zu laden und das Speicherwort dem Prozessor zur Verfügung zu stellen.

Die Zugriffszeit (access time) taccess zur unteren Hierarchiestufe ist abhängig von der Latenz des Zugriffs auf der unteren Hierarchiestufe.

Die Übertragungszeit (transfer time) ttransfer ist die Zeit, um den Block zu übertragen, und hängt von der Übertragungsbandbreite und der Blocklänge ab.

Page 23: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

23

Die mittlere Zugriffszeit (average memory-access time) taverage-access ist definiert als (in ns oder Prozessortakten):

taverage-access = (Trefferrate) * thit + (1- Trefferrate) * tmiss = Trefferrate * Cache-Zugriffsrate + Fehlzugriffsrate * Fehlzugriffsaufwand

Einige Begriffe

Page 24: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

24

Blöcke und Sätze

Blockrahmen (Block Frame): eine Reihe von Speicherplätzen im Cachespeicher, dazu ein Adressetikett (Address Tag oder Cache-Tag) und Statusbits.

• Das Adressetikett oder Tag enthält einen Teil der Blockadresse. • Die Statusbits sagen aus, ob die Datenkopie gültig ist.

Blocklänge (Block Size, Line Size): Die Anzahl der Speicherplätze in einem Blockrahmen.

Ein Cache-Block (synonym Cache-Line) ist die Datenportion, die in einen Blockrahmen passt. Typische Blocklängen sind 16 oder 32 Bytes.

Die Menge der Blockrahmen ist in Sätze (Sets) unterteilt.

Page 25: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

25

Weitere Begriffe

Die Anzahl der Blockrahmen in einem Satz wird als Assoziativität bezeichnet.

Gesamtzahl c der Blockrahmen in einem Cachespeicher ist das Produkt aus der Anzahl s der Sätze und der Assoziativität n, also c = s n.

Ein Cachespeicher heißt:• voll-assoziativ, falls er nur aus einem einzigen Satz

besteht (s=1, n=c), • direkt-abgebildet (direct-mapped), falls jeder Satz nur

einen einzigen Blockrahmen enthält (n=1, s=c) und • n-fach satzassoziativ (n-way set-associative) sonst

(s = c/n).

Page 26: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

26

Vollassoziative, satzassoziative und direkt-abgebildete Cache-Speicherverwaltung

Beispiel eines Cache-Speichers mit einer Kapazität von acht Cache-Blöcken (c = 8).

Unter Annahme einer Abbildungsfunktion „Blockadresse modulo Anzahl Sätze“ kann ein Block mit der Adresse 12 in einem der grau markierten Blockrahmen gespeichert werden.

vollassoziativ zweifach satzassoziativ

0

3

1

direkt-abgebildet

0

7

...

2 4

...

Page 27: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

Direkt-abgebildeter Cachespeicher

Tag- teil

Index- teil

Wort- adresse

Satz-/Block- decoder

Satz-/Block- auswahl

Tag Gültigkeits-

bits Block

...

= ok Ja

Ja

Speicherwort

Wort- auswahl

Selektierter Cache-Block

Tag- vergleich

Adresse des gesuchten Speicherworts

Page 28: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

28

Merkmale des direkt-abgebildeten Cachespeichers

Die Hardware-Realisierung ist einfach (nur ein Vergleicher und ein Tag-Speicher).

Der Zugriff erfolgt schnell, weil das Tag-Feld parallel mit dem Block gelesen werden kann.

Es ist kein Verdrängungsalgorithmus erforderlich, weil die direkte Zuordnung keine Alternativen zulässt.

Auch wenn an anderer Stelle im Cache noch Platz ist, erfolgt wegen der direkten Zuordnung eine Ersetzung.

Bei einem abwechselnden Zugriff auf Speicherblöcke, deren Adressen den gleichen Index-Teil haben, erfolgt laufendes Überschreiben des gerade geladenen Blocks. Es kommt zum „Flattern“ (Thrashing).

Page 29: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

n-fach satzassoziative Cachespeicherver-

waltung

...

...

...

...

Assoziativität

Satz[0] Satz[1]

Satz[s-1]

Block- adresse

Block- Offset

Adresse des gesuchten Speicherworts

f

Satz- decoder

Wort- selektor

Speicherwort

Satz- auswahl

Speicherwort- auswahl

Block[0] Block[n-1]

Block- auswahl

gefundener Block

x

Page 30: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

30

Verdrängungsstrategie

Verdrängungsstrategie gibt an, welcher Teil des Cachespeichers nach einem Cache-Miss durch eine neu geladene Speicherportion überschrieben wird.

nur bei voll- oder n-fach satzassoziativer Cachespeicherorganisation angewandt

meist Pseudo-LRU-Strategie, (Least Recently Used).

Page 31: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

31

Pseudo-LRU-Strategie für vierfach satzassoziative Cache-Speicher (drei Bits reichen)

LRU-Bit 0 = 0 ?

Zeile 2 oder 3 wurde am längsten nicht mehr benutzt

Zeile 0 oder 1 wurde am längsten nicht mehr benutzt

nein ja

LRU-Bit 2 = 0 ?

Zeile ersetzen

Zeile 2 ersetzen

nein ja LRU-Bit 0 =

1 ?

Zeile 1 ersetzen

Zeile ersetzen

nein ja

Page 32: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

32

Organisation der Schreibzugriffe

Durchschreibe-Strategie (Write-Through, auch Store-Through-Cache Policy genannt): Ein Datum wird von der CPU immer gleichzeitig in den Cache- und in den Hauptspeicher geschrieben.

Vorteil: eine garantierte Konsistenz der Inhalte von Cache- und Hauptspeicher,Nachteil: die sehr schnelle CPU muß bei Schreibzugriffen mit dem langsamen Hauptspeicher synchronisiert werden.

Gepufferte Durchschreibe-Strategie (Buffered-Write-Through): Store-Through-Cache-Strategie und kleiner Schreibpuffer (der sogenannte Write Buffer), der die zu schreibenden Daten temporär aufnimmt und die Daten in den Hauptspeicher überträgt, während der Prozessor parallel dazu mit weiteren Operationen fortfährt.

Rückschreibe-Strategie (Store-in, auch Write-Back oder Copy-Back Cache Policy genannt): ein Datum wird von der CPU nur in den Cachespeicher geschrieben und das Zustandsbit auf 'ungültig' gesetzt (Dirty Bit). Der Hauptspeicher wird nur dann geändert, wenn das Dirty Bit gesetzt ist und der gesamte Block durch die Verdrängungsstrategie ersetzt wird.

Page 33: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

33

Drei Arten die Verarbeitungsleistung eines Cache-Speichers zu verbessern

durch Verringern der Fehlzugriffsrate, durch Verringern des Fehlzugriffsaufwandes und durch Verringern der Cache-Zugriffszeit bei einem

Treffer

Page 34: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

34

Verringern der Fehlzugriffsrate:Ursachen für die Fehlzugriffe

Erstzugriff (compulsory - obligatorisch): Beim ersten Zugriff auf einen Cache-Block befindet sich dieser noch nicht im Cache-Speicher und muss erstmals geladen werden.

Kaltstartfehlzugriffe (cold start misses) oder Erstbelegungsfehlzugriffe (first reference misses).

Kapazität (capacity): Falls der Cache-Speicher nicht alle benötigten Cache-Blöcke aufnehmen kann, müssen Cache-Blöcke verdrängt und eventuell später wieder geladen werden.

Konflikt (conflict): ein Cache-Block wird verdrängt und später wieder geladen, falls zu viele Cache-Blöcke auf denselben Satz abgebildet werden.

Kollisionsfehlzugriffe (collision misses) oder Interferenzfehlzugriffe (interference misses).

Kollisionsfehlzugriffe treten nur bei direkt abgebildeten oder satzassziativen Cache-Speichern beschränkter Größe auf.

Page 35: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

35

Anzahl der durch Konflikte ausgelösten Fehlzugriffe verringern (1-4)

Größerer Cache-Block: Simulationen zeigten dass die optimale Blockgröße bei 32-128 Bytes liegt

Höhere Assoziativität: 2:1-Cache-Regel: Die Fehlzugriffsrate eines direktabgebildeten Cache-Speichers der Größe n entspricht grob derjenigen eines zweifach satzassoziativen Cache-Speichers der Größe n/2. Üblich sind heute Assoziativitäten von vier- und achtfach.

Victim Cache: ein kleiner Pufferspeicher, auf den genauso schnell wie auf den Cache zugegriffen werden kann und der die zuletzt aus dem Cache geworfenen Cache-Blöcke aufnimmt.

Pseudo-Assoziativität: erlaubt bei einem direktabgebildeten Cache-Speicher die Anzahl der Konflikte zu verringern. Der Cache wird in zwei Bereiche geteilt, auf die mit verschiedenen Geschwindigkeiten zugegriffen wird. Im Fall eines Fehlzugriffs im ersten Cache-Bereich wird in zweiten Cache-Bereich gesucht. Falls das Speicherwort dort gefunden wird, so spricht man von einem Pseudo-Treffer.

Page 36: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

36

Anzahl der durch Konflikte ausgelösten Fehlzugriffe verringern (5-7)

Vorabladen per Hardware (hardware prefetching) • Die einfachste Form des spekulativen Vorabladens ist es, bei einem Cache-

Fehlzugriff nicht einen, sondern gleich noch den darauffolgenden Cache-Block in den Cache-Speicher zu laden.

• Pentium-4-Prozessor erkennt ständig wiederkehrende Zugriffsmuster und führt ein Vorabladen per Hardware durch seine Hardware-Dataprefetch-Einheit durch.

Vorabladen per Software (software data prefetching): Die Software lädt durch spezielle Vorabladebefehle (cache prefetch, cache touch) Daten spekulativ in den Daten-Cache-Speicher.

Compileroptimierungen: Die Befehle und Daten werden vom Compiler so im Speicher angeordnet, dass Konflikte möglichst vermieden werden und die Kapazität besser ausgenutzt wird.

• Mögliche Techniken dafür sind das Zusammenfassen von Array-Datenstrukturen und die Manipulation der Schleifenanordnung

Page 37: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

37

Verringern des Fehlzugriffsaufwandes

Lade- vor Speicherzugriffen beim Cache-Fehlzugriff: Im Falle einer Durchschreibestrategie werden die in den Speicher zu schreibenden Cache-Blöcke in einem Schreibpuffer zwischengespeichert. Dabei kann das Laden neuer Cache-Blöcke vor dem Speichern von Cache-Blöcken ausgeführt werden.

Um sicherzugehen, dass bei einem vorgezogenen Laden keine Datenabhängigkeit zu einem der passierten Speicherwörter verletzt wird, müssen die Ladeadressen mit den Adressen der zu speichernden Daten verglichen werden. Im Falle einer Übereinstimmung muss die Ladeoperation ihren Wert aus dem Schreibpuffer und nicht aus der nächst tieferen Speicherhierarchieebene erhalten.

Auch bei Rückschreib-Cache-Speichern wird bei einem Cache-Fehlzugriff der verdrängte „Dirty“-Block zurückgespeichert. Normalerweise würde das Rückspeichern vor dem Holen des neuen Cache-Blocks erfolgen.

Um den zu ladenden Wert dem Prozessor so schnell als möglich zur Verfügung stellen zu können, wird der verdrängte Cache-Block ebenfalls im Schreibpuffer zwischengespeichert und erst der Ladezugriff vor dem anschließenden Rückschreibzugriff auf dem Speicher durchgeführt

Page 38: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

38

Verringern des Fehlzugriffsaufwandes

Zeitkritisches Speicherwort zuerst (critical word first):

Sobald das angeforderte Speicherwort im Cache ankommt, wird es sofort dem Prozessor zur Verfügung gestellt und dieser kann weiterarbeiten (early restart).

Darüberhinaus kann das angeforderte Speicherwort auch als erstes vom Speicher zum Cache übertragen werden (critical word first, wrapped fetch).

Nichtblockierender Cache-Speicher (non-blocking cache, lockup-free cache): Im Falle eines Cache-Fehlzugriffs können nachfolgende Ladeoperationen, die nicht denselben Cache-Block benötigen, auf dem Cache-Speicher durchgeführt, ohne dass auf die Ausführung der den Fehlzugriff auslösenden Lade- oder Speicheroperation gewartet werden muss. Ein Fehlzugriff blockiert damit keine nachfolgenden Ladebefehle.

Page 39: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

39

Verringern des Fehlzugriffsaufwandes:Verwendung mehrerer Caches

Auf dem Prozessor-Chip: der sogenannte Primär- oder First-Level-Cache (On-Chip-Cache).

Häufig Harvard-Architektur: getrennte On-Chip-Caches: Befehlscache für die Befehle und Datencache für die Daten. Ziel: paralleler Zugriff auf Code und Daten.

Auch auf oder außerhalb des Prozessor-Chips: ein weiterer, größerer Cache, der Sekundär- oder Secondary-Level-Cache (On-Board-Cache).

Der Sekundär-Cache kann parallel zum Hauptspeicher an den Bus angeschlossen werden (Look-Aside-, Backside-Cache).

Die Befehle weisen eine höhere Lokalität als die Daten auf, deshalb wird für die Befehle oft eine größere Blockübertragungsgröße gewählt (typisch 8–32 Befehlsworte bzw. 4–16 Datenworte).

Beim Vorhandensein eines Sekundär-Cache-Speichers wird der Primär-Cache meist als Durchschreibespeicher betrieben, so dass alle Daten im Primär-Cache auch im Sekundär-Cache stehen (Inklusionsprinzip). Der Sekundär-Cache arbeitet dagegen in der Regel mit dem Rückschreibeverfahren.

Page 40: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

40

Verringern der Cache-Zugriffszeit bei einem Treffer

Primär-Cache-Speicher auf dem Prozessor-Chip: • heute bis zu achtfach satzassoziative Daten-Caches als Primär-

Caches auf dem Prozessor-Chip. Die Primär-Cache-Größen variieren von 8 KByte beim Pentium-4- über 16 KByte beim Pentium-III- bis zu 64 KByte beim Athlon-Prozessor.

Virtueller Cache: Vermeiden von Adressübersetzungen. • Der Cache kann mit der virtuellen Adresse (virtueller Cache)

statt mit der physikalischen Adresse (physikalischer Cache) angesprochen werden.

• Je nachdem, ob die Adressumsetzung durch eine Speicherverwaltungseinheit (MMU) vor oder hinter dem Cache vorgenommen wird, spricht man von einem virtuell oder physikalisch adressierten Cache-Speicher.

Page 41: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

41

Zwei Möglichkeiten der Cache Adressierung

(a) virtueller Cache (b) physikalischer Cache

TLB CPU

Cache

Speicher

virtuelleAdresse

physikalischeAdresse

Daten

Daten

TLB CPU

Cache

Speicher

virtuelleAdresse

physikalischeAdresse

Daten

Daten

Page 42: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

42

Verringern der Cache-Zugriffszeit bei einem Treffer

Virtueller Cache: Problem beim „Bus-Schnüffeln“, da die Cache Tags virtuelle (bzw. logische) und nicht physikalische Adressen sind.

effiziente Lösung bietet die als logically indexed und physically tagged bezeichnete Cache-Organisation

• Der Cache-Tag ist eine physikalische Adresse, die durch Übersetzung der höchstwertigen Bits der logischen Adresse mit Hilfe eines TLBs erzielt wird (deshalb: physically tagged).

• Gleichzeitig selektiert der Indexteil der logischen Adresse den Cache-Satz (deshalb: logically indexed) und die niederwertigsten Bits der logischen Adresse selektieren das Speicherwort im Satz.

• Satzauswahl, Speicherwort-Selektion und TLB-Zugriff geschehen gleichzeitig. Die durch den TLB-Zugriff erzielte physikalische Tag-Adresse wird mit dem Cache-Tag des selektierten Cache-Blocks verglichen, um festzustellen, ob der Zugriff ein Treffer oder Fehlschlag ist.

Pipeline-Verarbeitung für Schreibzugriffe auf den Cache: Die Tag-Prüfung eines Cache-Zugriffs und die Cache-Modifikation durch den vorherigen Schreibzugriff können überlappt zueinander ausgeführt werden. Pipeline-Verarbeitung, die Zugriffsgeschwindigkeit wird bei hohen Prozessortaktraten erhöht.

Page 43: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

43

Cache-Optimierungsmöglichkeiten

Technik Fehlzu-griffsrate

Fehlzugriffs-aufwand

Zugriffszeit beim Treffer

Komplexität

Verringern der Fehlzugriffsrate:        

Größerer Cache-Block + –   0

Größere Assoziativität +   – 1

Victim Cache +     2

Pseudo-Assoziativität +     2

Vorabladen per Hardware +     2

Vorabladen per Software +     3

Umordnung durch den Compiler +     0

Verringern des Fehlzugriffsaufwand:        

Laden vor Speichern   +   1

Teilblöcke   + + 1

Zeitkritisches Wort zuerst   +   2

Nichtblockierender Cache   +   3

Sekundär-Cache   +   2

Verringern der Zugriffszeit beim Treffer:        

On-Chip-Cache –   + 0

Virtueller Cache     + 2

Pipelining im Cache     + 1

Page 44: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

44

Ein Parallelrechner besteht aus einer Menge von Verarbeitungselementen, die in einer koordinierten Weise teilweise zeitgleich zusammenarbeiten, um eine Aufgabe zu lösen.

Die Verarbeitungselemente können sein:• spezialisierte Einheiten, wie z.B. die Pipelinestufen einer Vektor-Pipeline oder

die Vektor-Pipelines der Vektoreinheit eines Vektorrechners,• gleichartige Rechenwerke, wie z.B. die Verarbeitungselemente eines

Feldrechners,• Prozessorknoten eines Multiprozessors (die Parallelrechner in einem engeren

Sprachgebrauch),• vollständige Rechner, wie z.B. Workstations oder Personalcomputer eines

Workstation- oder PC-Clusters, die per Software zeitweilig zu einem virtuellen Parallelrechner zusammengeschlossen werden,

• selbst wieder ganze Parallelrechner oder Workstation-Cluster, welche über Fernverbindungen gekoppelt sind und als Metacomputer oder Hypercomputer betrieben werden.

Einschub: ParallelrechnerBegriffsbestimmungen und Einordnung von Parallelrechnern

Page 45: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

45

Flynn charakterisiert Rechner als Operatoren auf zwei verschiedenartigen Informationsströmen: dem Befehlsstrom (bzw. den Befehlsströmen) und dem Datenstrom (bzw. den Datenströmen).

SISD: Single instruction stream over a single data stream SIMD: Single instruction stream over multiple data streams MISD: Multiple instruction streams over a single data stream MIMD: Multiple instruction streams over multiple data streams

Klasse SISD: die von-Neumann-Architekturen (Einprozessorrechner) Klasse MISD: leer Klasse SIMD: die Feldrechner und die Vektorrechner MIMD die Multiprozessorsysteme.

Einordnung von Parallelrechnern - Flynnsche Klassifikation

Page 46: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

46

Feldrechner: Rechner mit einem Feld von regelmäßig verbundenen Verarbeitungselementen, die unter Aufsicht einer zentralen Steuereinheit immer gleichzeitig dieselbe Maschinenoperation auf verschiedenen Daten ausführen.

Vektorrechner: Rechner, dessen Rechenwerk aus mindestens einer pipelineartig aufgebauten Funktionseinheit zur Verarbeitung von Arrays (Vektoren) von Gleitpunktzahlen besteht. Eine solche Funktionseinheit nennt man Vektorpipeline.

Multiprozessorsysteme oder Multiprozessor: Rechner, die in die MIMD-Klasse des Flynnschen Klassifikationsschemas fallen.

• Speichergekoppelte Multiprozessoren• Nachrichtengekoppelte Multiprozessoren

Feldrechner, Vektorrechner und Multiprozessoren

Page 47: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

47

Bei speichergekoppelten Multiprozessoren besitzen alle Prozessoren einen gemeinsamen Adressraum. Kommunikation und Synchronisation geschehen über gemeinsame Variablen.

• Symmetrischer Multiprozessor SMP: ein globalen Speicher• Distributed-shared-memory-System DSM: gemeinsamer Adressraum trotz

physikalisch verteilter Speichermodule

Bei den nachrichtengekoppelten Multiprozessoren besitzen alle Prozessoren nur physikalisch verteilte Speicher und prozessorlokale Adressräume. Die Kommunikation geschieht durch Austauschen von Nachrichten.

Verteiltes Rechnen in einem Workstation-Cluster Metacomputer: Zusammenschluss weit entfernter Rechner Kopplungsgrad nimmt ab, Programme müssen immer grobkörniger sein. Skalierbarkeit der Hardware nimmt zu.

Arten von Multiprozessoren

Page 48: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

48

Konfigurationen

Prozessor Prozessor

Verbindungsnetz

gemeinsamer Speicher

Globaler Speicher Physikalisch verteilter Speicher

Ver

teilt

er A

dre

ßra

umG

emei

nsam

er A

dre

ßra

um

Leer

Prozessor Prozessor

Verbindungsnetz

lokalerSpeicher

lokalerSpeicher

SMP Symmetrischer Multiprozessor DSM Distributed-shared-memory-Multiprozessor

Prozessor Prozessor

Verbindungsnetz

lokalerSpeicher

lokalerSpeicher

send receive

Nachrichtengekoppelter (Shared-nothing-)Multiprozessor

Page 49: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

49

Alle Prozessoren besitzen einen gemeinsamen Adressraum; Kommunikation und Synchronisation geschieht über gemeinsame Variablen.

Uniform-memory-access-Modell (UMA): • Alle Prozessoren greifen gleichermaßen auf einen gemeinsamen Speicher zu.

Insbesondere ist die Zugriffszeit aller Prozessoren auf den gemeinsamen Speicher gleich. Jeder Prozessor kann zusätzlich einen lokalen Cache-Speicher besitzen. Typische Beispiele: die symmetrischen Multiprozessoren

Nonuniform-memory-access-Modell (NUMA): • Die Zugriffszeiten auf Speicherzellen des gemeinsamen Speichers variieren je

nach dem Ort, an dem sich die Speicherzelle befindet. Die Speichermodule des gemeinsamen Speichers sind physikalisch auf die Prozessoren aufgeteilt.

• Typische Beispiele: Distributed-Shared-Memory-Systeme.

Speichergekoppelte Multiprozessoren

Page 50: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

50

Distributed-shared-memory-Systeme sind NUMAs (Non-uniform-memory-access-Modell): Die Zugriffszeiten auf Speicherzellen des gemeinsamen Speichers variieren je nach Ort, an dem sich die Speicherzelle beendet.

• CC-NUMA (Cache-coherent NUMA): Cache-Kohärenz wird über das gesamte System gewährleistet, z.B. Cray/SGI Origin, HP/Convex Exemplar, Sequent NUMA-Q.

• NCC-NUMA (Non-cache-coherent NUMA) : Cache-Kohärenz wird nur innerhalb eines Knotens gewährleistet, z.B. Cray T3D und T3E.

• COMA (Cache-only-memory-architecture-Modell): Der Speicher des gesamten Rechners besteht nur aus Cache-Speichern, z.B. KSR-Rechner.

Nachrichtengekoppelte Multiprozessoren sind NORMAs (No-remote-memory-access-Modell) oder Shared-nothing-Systeme.

Speichergekoppelte Multiprozessoren - Distributed-shared-memory-Systeme

Page 51: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

51

Speichergekoppelte Multiprozessoren- Symmetrische Multiprozessoren (SMP oder UMA)

Page 52: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

52

Cache-Kohärenz und Speicherkonsistenz Cache-Kohärenzproblem

Cache-Kohärenzproblem (Cache Coherency Problem): Gültigkeitsproblem, das beim Zugriff mehrerer Verarbeitungselemente auf Speicherworte des Hauptspeichers entsteht.

Kohärenz bedeutet das korrekte Voranschreiten des Systemzustands durch ein abgestimmtes Zusammenwirken der Einzelzustände.

Im Zusammenhang mit dem Cache muss das System dafür sorgen, dass immer die aktuellen Daten und nicht die veralteten Daten gelesen werden.

Ein System ist konsistent, wenn alle Kopien eines Datums im Hauptspeicher und den verschiedenen Cachespeichern identisch sind. Dadurch ist auch die Kohärenz sichergestellt, jedoch entsteht ein hoher Aufwand.

Page 53: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

53

Cache-Kohärenz

Man kann im begrenzten Umfang die Inkonsistenz der Daten zulassen, wenn man durch ein geeignetes Verfahren dafür sorgt, dass die Kohärenz gewährleistet wird (Cache-Kohärenz-Protokoll).

Das Protokoll muss dafür sorgen, dass immer die aktuellen Daten und nicht die veralteten Daten gelesen werden.

Beim Verändern einer Kopie in einem Cachespeicher müssen alle Kopien in anderen Cachespeichern für ungültig erklärt werden (Write invalidate) oder mit verändert (aktualisiert, Write update) werden, wobei die Aktualisierung auch verzögert (spätestens beim Zugriff) erfolgen kann.

Eine Cachespeicherverwaltung heißt kohärent, falls der bei einem Lesezugriff eines beliebigen Verarbeitungselementes erzielte Datenwert immer derjenige Datenwert ist, der beim zeitlich letzten Schreibzugriff irgendeines der Verarbeitungselemente auf das entsprechende Datum erzielt wurde.

Page 54: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

54

Bus-Schnüffeln (Bus-Snooping)

In Mehrprozessorsystemen, bei denen mehrere Prozessoren mit lokalen Cachespeichern an einen gemeinsamen Bus/Hauptspeicher angeschlossen sind, verwendet man das sogenannte Bus-Schnüffeln.

Die Schnüffel-Logik jedes Prozessors hört am Bus die Adressen mit, die die anderen Prozessoren auf den Bus legen. Die Adressen auf dem Bus werden mit den Adressen, der im Cache gespeicherten Daten, verglichen.

Page 55: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

55

Bus-Schnüffeln

Bei Adressübereinstimmung am Bus geschieht folgendes:• Wenn ein Schreibzugriff auf dieselbe Adresse vorliegt, dann

wird der im Cache gespeicherte Cacheblock für 'ungültig' erklärt (Write-Invalidate-Verfahren), oder mit aktualisiert (Write-Update-Verfahren).

• Wenn ein Lesezugriff auf dieselbe Adresse mit einer modifizierten Datenkopie im Cachespeicher festgestellt wird, dann legt der Cache-Controller ein Snoop Status Signal (SSTAT) auf den Bus. Der Prozessor, der die Adresse auf den Bus gelegt hat, unterbricht seine Bustransaktion. Der „schnüffelnde“ Cache-Controller übernimmt den Bus und schreibt den betreffenden Cacheblock in den Hauptspeicher. Dann wird die ursprüngliche Bustransaktion erneut durchgeführt.

• Siehe MESI-Protokoll (bei Multiprozessoren)

Page 56: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

MESI-ProtokollInvalid

Exclusive modified

Exclusive unmodified

RH

WH

RH

WH

RH

SHR

SH

R

SHW

RMS

SH

W

WM

+

Read hit Read miss, shared Read miss, exclusive Write hit Write miss Snoop hit on a read Snoop hit on a write or read-with-intent-to modify

Dirty line copyback

+

Invalidate transaction

Read-with-intent-to-modify

Cache line fill

RH RMS RME WH WM SHR SHW

Shared unmodified

Page 57: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

57

Speicherkonsistenz

Die Lade-/Speichereinheit eines Prozessors führt alle Datentransfer-Befehle zwischen den Registern und dem Daten-Cache-Speicher durch.

Cache-Kohärenz wird erst dann wirksam, wenn ein Lade- oder Speicherzugriff durch die Lade-/Speichereinheit des Prozessors ausgeführt wird, also ein Zugriff auf den Cache-Speicher geschieht.

Cache-Kohärenz sagt nichts über mögliche Umordnungen der Lade- und Speicherbefehle innerhalb der Lade-/Speichereinheit aus.

Heutige Mikroprozessoren führen jedoch die Lade- und Speicherbefehle nicht mehr unbedingt in der Reihenfolge aus, wie sie vom Programm her vorgeschrieben ist. Prinzipien der vorgezogenen Ladezugriffe und des nichtblockierenden Cache-Speichers

Page 58: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

58

Lade-/Speichereinheit: Prinzip der vorgezogenen Ladezugriffe

Adresse Registerinhalt

Load WriteBuffer

Lade-/Speichereinheit

Page 59: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

59

Speicherkonsistenz bei speichergekoppelten Multiprozessoren

Bei speichergekoppelten Multiprozessoren können im Prinzip zu jedem Zeitpunkt mehrere Zugriffe auf denselben Speicher erfolgen.

Bei symmetrischen Multiprozessoren können trotz Cache-Kohärenz durch Verwendung von vorgezogenen Ladezugriffen oder durch nichtblockierende Cache-Speicher die Speicherzugriffsoperationen in anderer Reihenfolge als durch das Programm definiert am Speicher wirksam werden.

Beispiel Dekkers Algorithmus

Page 60: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

60

Dekkers Algorithmus

Beim Programmablauf sind folgende vier Fälle möglich:• a1 wird ausgeführt, a2 wird nicht ausgeführt;• a2 wird ausgeführt, a1 wird nicht ausgeführt;• a1 und a2 werden beide nicht ausgeführt;• a1 und a2 werden beide ausgeführt

y=0;x=0;...process p1: x=1;

if (y==0) ... führe Aktion a2 aus

 process p2: y=1;

if (x==0) ... führe Aktion a1 aus

Page 61: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

61

Konsistenzmodell

Ein Konsistenzmodell spezifiziert die Reihenfolge, in der Speicherzugriffe eines Prozesses von anderen Prozessen gesehen werden

Im Normalfall setzt der Programmierer die sequenzielle Konsistenz voraus, die jedoch zu starken Einschränkungen bei der Implementierung führt.

Ein Multiprozessorsystem ist sequenziell konsistent, wenn das Ergebnis einer beliebigen Berechnung dasselbe ist, als wenn die Operationen aller Prozessoren auf einem Einprozessorsystem in einer sequenziellen Ordnung ausgeführt würden. Dabei ist die Ordnung der Operationen der Prozessoren die des jeweiligen Programms.

Page 62: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

62

Schwache Konsistenz

Meist wird die Forderung nach einer sequenziellen Konsistenz aufgegeben und sich statt dessen mit einer schwachen Konsistenz (weak consistency) begnügt

die Effizienz der Programmausführung wird gesteigert, in gewissen Phasen der Programmausführung wird eine Verletzung der Zugriffsordnung toleriert, Auswirkungen auf die Programmierung!!!!

Schwache Konsistenz bedeutet, dass die Konsistenz des Speicherzugriffs nicht mehr zu allen Zeiten gewährleistet ist, sondern nur zu bestimmten vom Programmierer in das Programm eingesetzten Synchronisationspunkten.

Einführung von kritischen Bereichen, innerhalb derer Inkonsistenzen zugelassen werden. Die Synchronisationspunkte sind die Ein- oder Austrittspunkte der kritischen Bereiche.

Page 63: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

63

Definition der schwachen Konsistenz

Bevor ein Schreib- oder Lesezugriff bezüglich irgendeines anderen Prozessors ausgeführt werden darf, müssen alle vorhergehenden Synchronisationspunkte erreicht worden sein.

Bevor eine Synchronisation bezüglich irgendeines anderen Prozessors ausgeführt werden darf, müssen alle vorhergehenden Schreib- oder Lesezugriffe ausgeführt worden sein.

Die Synchronisationspunkte müssen sequenziell konsistent sein.

Page 64: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

64

Nachtrag: Speicherverschränkung (Memory Interleaving)

Technik, um die Zugriffsgeschwindigkeit auf den Hauptspeicher stärker an die Verarbeitungsgeschwindigkeit der CPU anzupassen:

Speicher wird in n Speichermodule (oder Speicherbänke) M0,...,Mn-1 unterteilen und jede Speicherbank mit einer eigenen Adressierlogik versehen.

Verteilung auf n Speicherbänke nennt man n-fache Verschränkung.

Page 65: 1 8 Speicherverwaltung Lücke zwischen Verarbeitungsgeschwindigkeit des Prozessors und Zugriffsgeschwindigkeit auf RAM- Speicher Grundprinzip zur Überbrückung:

65

Speicherverschränkung (Memory Interleaving)

Die einzelnen Speicherplätze werden nach Verschränkungsregel (Interleaving Rule) auf die einzelnen Speicherbänke verteilt:

• Ai wird auf die Speicherbank Mj gespeichert genau dann wenn j=i mod n

Die Adressen A0, An, A2n,... werden der Speicherbank M0, die Adressen A1, An+1, A2n+1,... werden der Speicherbank M1 zugeteilt, etc.

Der Zugriff auf die Speicherplätze kann nun zeitlicht verschränkt geschehen

n-fache Verschränkung: nach einer gewissen Anlaufzeit werden in jedem Speicherzyklus n Speicherworte geliefert.