Algorithmen für Hardware Caches und TLB

Inhaltsverzeichnis

Abbildungsverzeichnis

Abkürzungsverzeichnis

Symbolverzeichnis

1 Entwicklung der CPU- und Hauptspeichergeschwindigkeit

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

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

4 Fazit

Literaturverzeichnis

Abbildungsverzeichnis

Abb. 2.1: Vereinfachter Seitentabelleneintrag

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

Abb. 2.3: Vollassoziativer, direkt abbildender und 2-Wege teilassoziativer Cache

Abb. 2.4: Aufbau einer Cacheadresse

Abb. 2.5: Cache miss rate in Abhängigkeit von Ursache, Cachegröße und -typ

Abb. 3.1: Aufteilung einer Integerzahl in Ziffern

Abb. 3.2: Radix-Sort bei sieben Zahlen mit je drei Ziffern

Abb. 3.3: Der Counting-Sort Algorithmus in Java

Abb. 3.4: Anzahl an Cache misses pro Ziffer in Abhängigkeit von r

Abb. 3.5: Working Set von Radix-Sort in den verschiedenen Phasen

Abb. 3.6: TLB misses bei W > T

Abb. 3.7: TLB misses bei W ≤ T

Abb. 3.8: Zugriffe auf die Arrays der permute phase

Abb. 3.9: Arrays einer lokalen Sortierung in PLSB Radix-Sort

Abb. 4.1: Gesamtlaufzeiten der unterschiedlich optimierten Radix-Sort Varianten

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

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 arithmetische 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 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.^[3]

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.^[4]

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^[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 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^[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ö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 : 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.^[7]

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.

2.1.2 Die Seitentabelle

Abbildung in dieser Leseprobe nicht enthalten

Quelle: Vgl. Tanenbaum (2002), S. 230.

Abb. 2.1: Vereinfachter Seitentabelleneintrag

Die Abbildung von einer virtuellen auf eine physische Adresse wird mit Hilfe einer Seitentabelle realisiert. Da jedes Programm seinen eigenen virtuellen Adressraum hat, besitz 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 virtuelle Seite im Hauptspeicher vorhanden ist (Present/Absent-Bit = 1) oder auf der Festplatte 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 Auslagern 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 einer Umrechnung von einer virtuellen in eine physische Adresse ist in Abb. 2.2 dargestellt. Die umzurechnende virtuelle Adresse besteht aus einer virtuellen Seitennummer (höherwertige Bits) und einem Offset (niederwertige Bits). Bei einer 16-Bit-Adresse und 8 KB (= 213 Bit) großen Seiten, würden die oberen drei Bit eine der 23 = 8 virtuellen Seiten und die unteren 13 Bit einen Eintrag bzw. ein Byte innerhalb der virtuellen 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 zusammen mit den zwei Bit für die Seitenrahmennummer die 15-Bit lange physische Adresse. 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]

Abbildung in dieser Leseprobe nicht enthalten

Quelle: Vgl. Tanenbaum (2002), S. 226.

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 vor. Das Betriebssystem suspendiert daraufhin das Programm und lagert die angeforderte Seite von der Festplatte in den Hauptspeicher ein. Ist der Hauptspeicher 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^[12]. Ziel dieser Strategien ist es, möglichst die Seite zu entfernen, auf die in Zukunft als letztes zugegriffen wird, um so einen möglichen weiteren Seitenfehler möglichst weit herauszuzögern. Da diese Strategie unmöglich zu implementieren ist, wird am häufigsten Least Recently Used (LRU) verwendet. LRU entfernt diejenige Seite, die am längsten unbenutzt ist, in der Hoffnung, dass sie auch in Zukunft nicht direkt wieder benötigt wird. Dabei bedient sich das Betriebssystem dem Referenced-Bit. Diese Strategie hat ihre Berechtigung, da man beobachtet hat, dass Programme in einem kurzen Zeitintervall oft auf dieselbe Speicheradresse zugreifen. Dieses Phänomen wird zeitliche Lokalität genannt. Ist bei der mittels LRU ermittelten Seite das Modified-Bit gesetzt, muss sie zurück auf die Festplatte geschrieben werden, da sie aktueller ist, als die Kopie auf der Festplatte. Ist das Bit nicht gesetzt, kann die Seite einfach überschrieben werden. Danach wird die Seitentabelle aktualisiert und das Programm wieder aktiviert.

2.1.3 Der Translation Lookaside Buffer (TLB)

Ein Computer mit virtuellem Speicher benötigt bei jedem Befehl zwei Hauptspeicherzugriffe: einen für die Seitentabelle und einen um die benötigten Daten zu holen. Damit die Befehlsausführung nicht zu langsam wird, muss die Umwandlung der virtuellen Adresse sehr schnell gehen.^[13]

Aus diesem Grund besitzen moderne Computer einen Translation Lookaside Buffer (TLB), der vollständig unter der Kontrolle der Hardware liegt. Dies ist ein sehr schneller voll assoziativer Speicher, der eine virtuelle Adresse ohne Umweg über die Seitentabelle auf eine physische Adresse abbildet. Mit voll assoziativ ist gemeint, dass solch ein Umrechnungstupel in jedem Eintrag des TLB stehen kann. Sind also alle bis auf einen Eintrag im TLB besetzt, kann jedes mögliche Tupel den freien Eintrag nutzen.^[14] Der TLB besteht aus den gleichen Feldern, wie die Seitentabelle (Abb. 2.1), besitzt allerdings aus Kostengründen i. d. R. selten mehr als 64 Einträge und kann damit nur einen kleinen Teil aller Seitentabelleneinträge aufnehmen. Diese kleine Anzahl an Seiten reicht aber aufgrund der räumlichen und der oben beschriebenen zeitlichen Lokalität meist aus. Die räumliche Lokalität beschreibt das Phänomen, dass Programme bei aufeinander folgenden Speicherzugriffen auf Adressen zugreifen, die nah beieinander liegen. Da eine Seite aus mehreren aufeinander folgenden Speicheradressen besteht, wird auf eine Seite öfters hintereinander zugegriffen, so dass auch der zugehörige TLB-Eintrag oft hintereinander benutzt wird. Hinzu kommt, dass die Anzahl der Seiten, auf die ein Programm in einem größeren Zeitintervall zugreift auf wenige beschränkt ist. Passt dieser so genannte Working Set in den TLB, wird es auch über einen längeren Zeitraum keinen TLB miss geben.^[15]

Ein solcher TLB miss liegt vor, wenn die umzurechnende virtuelle Seite nicht im TLB steht. In diesem Fall wird die zugehörige physische Adresse mit Hilfe der Seitentabelle ermittelt und in den TLB aufgenommen. Ist der TLB voll, wird mittels LRU die Seite ermittelt, die überschrieben wird. Das Modified-Bit dieser Seite wird in den zugehörigen Seitentabelleneintrag zurückkopiert, damit die Seitentabelle weiß, ob die Seite inzwischen verändert wurde und ggf. bei einer Auslagerung auf die Festplatte zurückgeschrieben werden muss. Liegt dagegen ein TLB hit vor, d.h. die umzurechnende Seite ist im TLB vorhanden, wird die zugehörige physische Adresse sofort zurückgegeben, da alle Einträge gleichzeitig (d.h. parallel) überprüft werden.^[16]

2.2 Hardware Caches

Um das Problem der Diskrepanz zwischen der schnellen CPU und dem langsamen Hauptspeicher zu lösen, existiert eine Hierarchie von Caches zwischen der CPU und dem Hauptspeicher. Diese Caches der so genannten internen Speicherhierarchie sind unterschiedlich schnell und groß. So sind Caches, die näher an der CPU liegen schneller und (aus Kostengründen) kleiner als solche, die näher an dem Hauptspeicher liegen. Für die weiteren Betrachtungen, wird allerdings von einer internen Speicherhierarchie ausgegangen, die aus nur einem Cache besteht.

Ein Cache enthält Daten, auf die zuletzt zugegriffen wurde. Aufgrund der temporalen Lokalität ist davon auszugehen, dass diese Daten direkt wieder benutzt werden, so dass sie ohne große Verzögerung aus dem Cache geladen werden können (cache hit). Sind die benötigten Daten nicht im Cache vorhanden, müssen sie aus dem Hauptspeicher in den Cache geladen werden und von dort aus in die CPU-Register (cache miss). Um die Kosten für einen Cache miss zu amortisieren, wird nicht nur ein einzelnes Datum, sondern ein ganzer Block von aufeinander folgender Daten in den Cache geladen. Der Hauptanteil der Kosten bildet der Zugriff auf den Hauptspeicher, so dass das Auslesen benachbarter Daten im Vergleich zum Auslesen eines Datums nicht viel länger dauert. Da viele Programme auch die bereits erwähnte räumliche Lokalität aufweisen, ist die Wahrscheinlichkeit groß, dass die benachbarten Daten ebenfalls benötigt werden.^[17]

2.2.1 Blockplatzierung

Im Vergleich zum Hauptspeicher oder dem TLB, bei denen Einträge überall gespeichert werden können (vollassoziativ), existieren bei Caches drei verschiedene Architekturen und damit drei verschiedene Möglichkeiten einen Block zu platzieren. Allen drei ist gemein, dass ein Datum mit der Speicheradresse x in dem Hauptspeicher-Block y = x div^[18] B liegt, wobei B die Anzahl der Daten in einem Block bezeichnet:^[19]

- Bei einem direkt abbildenden Cache^[20] können die Daten eines Blocks nur in den Cache-Block^[21] z mod M/B abgebildet werden, wobei M die Anzahl der Daten, die der Cache speichern kann, und somit M/B die Anzahl der Blocks darstellt. So kann in Abb. 2.3 a) Block 12 nur auf Cache-Block 4 abgebildet werden.
- Bei einem vollassoziativen Cache kann ein Block dagegen auf jeden Cache-Block abgebildet werden. Block 12 in Abb. 2.3 b) kann somit in irgendeinen Cache-Block gespeichert werden.
- Der a-Wege teilassoziative Cache^[22] stellt eine Mischform der beiden anderen Architekturen dar. Dabei werden a Cache-Blöcke zu so genannten Sets zusammengefasst. Ein Block y wird nun zunächst auf genau einen der (M/B)/a Sets abgebildet (y mod ((M/B)/a)), ähnlich wie beim direkt abbildenden Cache. Innerhalb des Sets kann der Block dann aber in irgendeinen der a Cache-Blöcke gespeichert werden, ähnlich wie beim vollassoziativen Cache. So kann Block 12 bspw. in Cache-Block 0 oder 1 gespeichert werden (Abb. 2.3 c)).

Abbildung in dieser Leseprobe nicht enthalten

Quelle: Vgl. Hennessy, Patterson (1996), S. 409.

Abb. 2.3: Vollassoziativer, direkt abbildender und 2-Wege teilassoziativer Cache

Das Spektrum der Caches von direkt abbildenden zum vollassoziativen Cache kann als Kontinuum von a-Wege teilassoziativen Caches aufgefasst werden: Der direkt abbildenden Cache stellt dabei einen 1-Weg und der vollassoziative Cache einen M/B-Wege teilassoziativen Cache dar.^[23]

[...]

^[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.

^[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.

^[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.

^[13] Vgl. Hennessy, Patterson (1996), S. 437.

^[14] Vgl. Kapitel 2.2.1

^[15] Vgl. Tanenbaum (2002), S. 231.

^[16] Vgl. Tanenbaum (2002), S. 232.

^[17] Vgl. Rahman (2003), S. 171.

^[18] Ganzzahlige Division.

^[19] Vgl. Rahman (2003), S. 174; Hennessy, Patterson (1996), S. 408f.

^[20] Engl. direct mapped cache.

^[21] Oft auch als Cache-Zeile (engl. cache-line) bezeichnet.

^[22] Engl. a-way set-associative cache.

^[23] Vgl. Hennessy, Patterson (1996), S. 409.