Thema:

Algorithmen für Hardware Caches und TLB

Ausarbeitung
im Rahmen des Seminars „Algorithmen für Speicherhierarchien“
im Fachgebiet Informatik

vorgelegt von: 

Andreas Toeche-Mittler

Abgabetermin: 2004-08-06

Inhaltsverzeichnis ...  II

Abbildungsverzeichnis ...  III
Abkürzungsverzeichnis  ...  IV
Symbolverzeichnis  ...  V

1 Entwicklung der CPU- und Hauptspeichergeschwindigkeit  ...  1

2 Virtueller Speicher und Hardware Caches ...  2
2.1 Virtueller Speicher  ...  2
2.1.1 Paging und Segmentierung  ...  2
2.1.2 Die Seitentabelle  ...  3
2.1.3 Der Translation Lookaside Buffer (TLB)  ...  5
2.2 Hardware Caches  ...  6
2.2.1 Blockplatzierung  ...  7
2.2.2 Blockidentifikation ...  8
2.2.3 Blockersetzung ...  9
2.2.4 Write-Strategie  ...  10
2.2.5 Klassifizierung von Cache misses  ...  11

3 Optimierter Radix-Sort für Hardware Caches und TLB ...  13
3.1 Der Radix-Sort Algorithmus  ...  13
3.1.1 Counting-Sort  ...  14
3.1.2 Laufzeitabschätzung  ...  15
3.2 Parameterwahl für Radix-Sort  ...  16
3.2.1 Parameterwahl im RAM-Modell  ...  16
3.2.2 Parameterwahl im Cache Memory Model (CMM)  ...  16
3.2.3 Parameterwahl im Internal Memory Model (IMM)  ...  18
3.3 PSLSB Radix-Sort  ...  25

4 Fazit  ...  27

Literaturverzeichnis  ...  28

Abbildungsverzeichnis
Abb. 2.1: Vereinfachter Seitentabelleneintrag  ...  3
Abb. 2.2: Umrechnung von einer virtuellen in eine physische Adresse ...  4
Abb. 2.3: Vollassoziativer, direkt abbildender und 2-Wege teilassoziativer Cache ...  8
Abb. 2.4: Aufbau einer Cacheadresse ...  8
Abb. 2.5: Cache miss rate in Abhängigkeit von Ursache, Cachegröße und -typ  ...  12
Abb. 3.1: Aufteilung einer Integerzahl in Ziffern ...  13
Abb. 3.2: Radix-Sort bei sieben Zahlen mit je drei Ziffern  ...  13
Abb. 3.3: Der Counting-Sort Algorithmus in Java  ...  14
Abb. 3.4: Anzahl an Cache misses pro Ziffer in Abhängigkeit von r  ...  18
Abb. 3.5: Working Set von Radix-Sort in den verschiedenen Phasen ...  20
Abb. 3.6: TLB misses bei W > T ...  22
Abb. 3.7: TLB misses bei W = T ...  23
Abb. 3.8: Zugriffe auf die Arrays der permute phase  ...  24
Abb. 3.9: Arrays einer lokalen Sortierung in PLSB Radix-Sort ...  26
Abb. 4.1: Gesamtlaufzeiten der unterschiedlich optimierten Radix-Sort Varianten  ...  27

Abkürzungsverzeichnis
CMM Cache Memory Model
CPU Central Processing Unit
div division
IMM Internal Memory Model
KB Kilo Byte
LRU Least Recently Used
LSB Least Significant Bit
MB Mega Byte
mod modulo
RAM Random Access Machine
TLB Translation Lookaside Buffer

Symbolverzeichnis

[...]

1 Entwicklung der CPU- und Hauptspeichergeschwindigkeit

Die meisten Algorithmen werden auf dem RAM¹-Modell analysiert, das unter anderem davon ausgeht, dass der Zugriff auf den Hauptspeicher genauso schnell wie die arithmetische Operation von zwei Wörtern ist, die sich in den CPU²-Registern befinden. In den letzten 20 Jahren ist die Geschwindigkeit von CPUs jedoch rapide angestiegen, wobei die Hauptspeichergeschwindigkeit nur langsam zugenommen hat. Der Grund dafür besteht darin, dass die treibende Kraft bei der Entwicklung von neuen Prozessoren die Geschwindigkeit und bei der Entwicklung von Speicherchips die Speicherkapazität ist. Somit wird die vereinfachende Annahme des RAM-Modells heutzutage stark verletzt.³

Um die Diskrepanz zwischen CPU- und Hauptspeichergeschwindigkeit zu reduzieren, werden Hardware Caches eingesetzt, die jeweils einen Teil der Hauptspeicherdaten vorhalten und diese schnell zur Verfügung stellen. Bei der Entwicklung von effizienten Algorithmen müssen diese Caches berücksichtigt und optimal genutzt werden. Eine weitere hardwaretechnische Gegebenheit, die für effiziente Algorithmen berücksichtigt werden muss, stellt der Translation Lookaside Buffer (TLB) dar, der in fast allen modernen Computersystemen zu finden ist. Dieser TLB erhöht die Geschwindigkeit von Systemen mit virtuellem Speicher, der dazu benutzt wird um Programme ausführen zu können, deren Speicherbedarf den vorhandenen physischen Hauptspeicherplatz übersteigt.

Zunächst wird in Kapitel 2 auf den Virtuellen Speicher mit TLB und auf die Hardware Caches eingegangen. Aufbauend auf diesen hardwaretechnischen Gegebenheiten wird in Kapitel 3.1 der Radix-Sort Algorithmus vorgestellt, der dann in Kapitel 3.2 für verschiedenen Modelle optimiert wird: das RAM-Modell, das Cache Memory Model (CMM), das Caches berücksichtigt, und das Internal Memory Model (IMM), das zusätzlich den TLB berücksichtigt. In Kapitel 3.3 wird dann eine modifizierte Variante des Algorithmus – PLSB Radix-Sort – vorgestellt. Abschließend werden in Kapitel 4 die verschiedenen Optimierungen und Varianten von Radix-Sort miteinander verglichen.

2 Virtueller Speicher und Hardware Caches

2.1 Virtueller Speicher

Schon früher stießen Programmierer auf das Problem, dass ihre Programme zu groß für den verfügbaren Hauptspeicher waren. Die Lösung dieses Problems wurde durch das Aufteilen der Programme in so genannte Overlays gelöst, die jeweils in den Hauptspeicher passten. War ein Overlay fertig, wurde es auf der Festplatte ausgelagert und das nächste Overlay eingelagert. Da es sehr aufwendig war, die Programme aufzuteilen, kam man auf die Idee, diese Arbeit dem Computer zu überlassen. 1961 entwickelte FOTHERINGHAM daraufhin den virtuellen Speicher.⁴

2.1.1 Paging und Segmentierung

Beim virtuellen Speicher erhält jedes Programm seinen eigenen virtuellen Speicherbereich, der wesentlich größer ist, als der physisch vorhandene Adressbereich. Nur die Teile des Programms, die gerade benötigt werden, liegen im Hauptspeicher. Die restlichen Teile werden auf der Festplatte gespeichert. Für die Aufteilung in kleinere Einheiten existieren die folgenden beiden Techniken:

• Beim Paging wird der virtuelle Adressraum in Einheiten gleicher Größe unterteilt, die Seiten genannten werden. Der physikalische Hauptspeicher wird ebenfalls in gleichgroße Einheiten unterteilt, den so genannten Seitenrahmen⁵, die dieselbe Größe wie die Seiten besitzen.
• Bei der Segmentierung werden dagegen der virtuelle und der physische Speicher in unterschiedlich große Einheiten, die Segmente genannt werden, unterteilt. 

Der Vorteil der Segmentierung besteht darin, dass sich eine Einheit flexibel an den benötigten Speicherplatz anpasst. Allerdings wird durch die unterschiedliche Größe der Segmente die Platzierung einer neuen Einheit in dem Hauptspeicher schwieriger. So kann es vorkommen, dass bei einer schlechten Platzierungsstrategie⁶ der Hauptspeicher so ungünstig belegt ist, dass die freien Abschnitte über den ganzen Speicher verteilt sind und nicht zusammenhängen. Wären die Abschnitte zusammenhängend, könnten möglicherweise weitere Segmente eingelagert werden. Dieses Problem wird auch als externe Fragmentierung bezeichnet.

Beim Paging kann dieses Problem aufgrund der identischen Größe der Seiten nicht auftreten. Allerdings existiert hier das Problem der internen Fragmentierung: Manche Seiten werden aufgrund der festen Größe nicht komplett durch die Programme ausgefüllt (z. B. die letzte Seite der Programme), so dass wiederum Speicherplatz verschwendet wird.⁷

Da in den meisten Computersystemen das Paging verwendet wird und auch die Untersuchungen in Kapitel 3.2 auf einem System mit Paging basieren, wird auf die Segmentierung im Folgenden nicht weiter eingegangen.

[....]

1 Random Access Machine

2 Central Processing Unit

3 Vgl. Rahman (2003), S. 171.

4 Vgl. Tanenbaum (2002), S. 222.

5 Oft auch als Seitenkacheln bezeichnet.

6 Mögliche Platzierungsstrategien sind z. B. Next Fit, Best Fit, Worst Fit und Quick Fit. Vgl. Tanenbaum (2002), S. 220ff.

7 Vgl. Hennessy, Patterson (1996), S. 434f.