Algorithmen für Hardware Caches und TLB

  II  

Inhaltsverzeichnis

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 RA-MModell 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

  III  

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  

– IV –

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

– V –

Symbolverzeichnis

a Assoziativität des Caches

B Blockgröße

b Destination-Array

c Count-Array

k Größte zu sortierende Ziffer

M Cachegröße

N Anzahl der zu sortierenden Zahlen

r Anzahl der Bits pro Ziffer

S Seitengröße

T Größe des TLB

w Anzahl der Bits pro Zahl

W Working Set

– 1 –

1 Entwicklung der CPU- und Hauptspeichergeschwindigkeit

Die meisten Algorithmen werden auf dem RAM 1 -Modell analysiert, das unter anderem davon ausgeht, dass der Zugriff auf den Hauptspeicher genauso schnell wie die arithme- tische Operation von zwei Wörtern ist, die sich in den CPU 2 -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 be- steht 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. 3

Um die Diskrepanz zwischen CPU- und Hauptspeichergeschwindigkeit zu reduzieren, werden Hardware Caches eingesetzt, die jeweils einen Teil der Hauptspeicherdaten vor- halten 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 mo- dernen 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 über- steigt.

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 ver- schiedenen Modelle optimiert wird: das RAM-Modell, das Cache Memory Model (CMM), das Caches berücksichtigt, und das Internal Memory Model (IMM), das zusätz- lich 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.

1 Random Access Machine

2 Central Processing Unit

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

– 2 –

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 Hauptspei- cher 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. 4

2.1.1 Paging und Segmentierung

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

• Beim Paging wird der virtuelle Adressraum in Einheiten gleicher Größe unter- teilt, die Seiten genannten werden. Der physikalische Hauptspeicher wird eben- falls in gleichgroße Einheiten unterteilt, den so genannten Seitenrahmen 5 , 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 be- nö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 6 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ögli-

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. Tanen- baum (2002), S. 220ff.

– 3 –

cherweise 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 auf- treten. Allerdings existiert hier das Problem der internen Fragmentierung: Manche Sei- ten 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. 7 Da in den meisten Computersystemen das Paging verwendet wird und auch die Unter- suchungen in Kapitel 3.2 auf einem System mit Paging basieren, wird auf die Segmen- tierung im Folgenden nicht weiter eingegangen.

2.1.2 Die Seitentabelle

Abb. 2.1: Vereinfachter Seitentabelleneintrag Die Abbildung von einer virtuellen auf eine physische Adresse wird mit Hilfe einer Sei- tentabelle realisiert. Da jedes Programm seinen eigenen virtuellen Adressraum hat, be- sitz auch jedes Programm seine eigene Seitentabelle. Ein Eintrag in dieser Tabelle (Abb. 2.1) enthält zu einer virtuellen Seite den dazugehörigen physischen Seitenrahmen (falls die Seite im Hauptspeicher liegt), sowie ein Present/Absent-Bit 8 , das angibt, ob die vir- tuelle Seite im Hauptspeicher vorhanden ist (Present/Absent-Bit = 1) oder auf der Fest- platte liegt (Present/Absent-Bit = 0). Des Weiteren enthält ein Eintrag ein Modified 9 - und ein Referenced-Bit, die die Zugriffe auf eine Seite protokollieren und für das Ausla- gern einer Seite benötigt werden. Das Modified-Bit wird bei jedem Schreibzugriff und das Referenced-Bit bei jedem Schreib- und Lesezugriff gesetzt. 10 Der Ablauf ein er Umrechnung von einer virtuellen in eine physische Adresse ist in Abb.

2.2 dargestellt. Die umzurechnende virtuelle Adresse besteht aus einer virtuellen Seiten-

nummer (höherwertige Bits) und einem Offset (niederwertige Bits). Bei einer 16-Bit- Adresse und 8 KB (= 2 13 Bit) großen Seiten, würden die oberen drei Bit eine der 2 3 = 8 virtuellen Seiten und die unteren 13 Bit einen Eintrag bzw. ein Byte innerhalb der virtu-

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

8 Oft auch als Valid- oder Invalid-Bit bezeichnet. Vgl. Hennessy, Patterson (1996), S. 410.

9 Oft auch als Dirty-Bit bezeichnet.

10 Vgl. Tanenbaum (2002), S. 229ff.

– 4 –

ellen Seite auswählen. Die virtuelle Seitennummer dient als Index für die Seitentabelle. Besteht der Offset z. B. aus 010, wird in dem zweiten Eintrag nachgeschaut (1). Ist bei diesem Eintrag das Present/Absent-Bit gesetzt, wird die Seitenrahmennummer in die oberen zwei Bit des Ausgaberegisters kopiert (2). Der Offset der virtuellen Adresse wird unverändert in die unteren 13 Bit des Ausgaberegisters kopiert (3) und bildet zu- sammen mit den zwei Bit für die Seitenrahmennummer die 15-Bit lange physische Ad- resse. Die physische Adresse ist im Allgemeinen kleiner als die virtuelle Adresse, da der physische Hauptspeicher kleiner ist als der virtuelle Adressraum und somit weniger Seitenrahmen als virtuelle Seiten angesprochen werden müssen. 11

7

6

5

4

3

2

1

0

Abb. 2.2: Umrechnung von einer virtuellen in eine physische Adresse

Ist die virtuelle Seite nicht im Hauptspeicher vorhanden (Present/Absent-Bit = 0), liegt ein Seitenfehler vor. Das Betriebssystem suspendiert daraufhin das Programm und la- gert die angeforderte Seite von der Festplatte in den Hauptspeicher ein. Ist der Haupt- speicher bereits voll, muss das Betriebssystem entscheiden, welche Seite ausgelagert werden soll. Dabei ist es günstiger Seiten auszulagern, die selten genutzt werden, als solche, auf die ständig zugegriffen wird. Für dieses Problem existieren verschiedene Seitenersetzungsstrategien 12 . Ziel dieser Strategien ist es, möglichst die Seite zu entfer- nen, auf die in Zukunft als letztes zugegriffen wird, um so einen möglichen weiteren

11

Vgl. Tanenbaum (2002), S. 226.

12

Mögliche Seitenersetzungsstrategien sind neben LRU Not Recently Used (NRU), FIFO, Second Chance, Clock, Working Set und WSClock. Vgl. Tanenbaum (2002), S. 234-249.