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.
Inhaltsverzeichnis
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
Zielsetzung & Themen
Die vorliegende Arbeit untersucht die Diskrepanz zwischen der rasant steigenden CPU-Leistung und der vergleichsweise langsamen Hauptspeichergeschwindigkeit. Ziel ist es, den Radix-Sort Algorithmus durch gezielte Berücksichtigung hardwaretechnischer Speicherhierarchien (Caches und TLB) zu optimieren, um die Laufzeit des Sortierprozesses im Vergleich zu Standardmodellen signifikant zu verbessern.
- Analyse der Speicherhierarchien (Virtueller Speicher, Cache-Architekturen)
- Untersuchung von Cache-Miss-Kategorien und deren Auswirkungen
- Optimierung von Radix-Sort für das RAM-, CMM- und IMM-Modell
- Einführung des Pre-Sorting LSB (PLSB) Radix-Sort Verfahrens
- Vergleichende Laufzeitanalyse verschiedener Sortieralgorithmen
Auszug aus dem Buch
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 B liegt, wobei B die Anzahl der Daten in einem Block bezeichnet.
Bei einem direkt abbildenden Cache können die Daten eines Blocks nur in den Cache-Block 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 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)).
Zusammenfassung der Kapitel
1 Entwicklung der CPU- und Hauptspeichergeschwindigkeit: Einführung in die Problematik der Geschwindigkeitsdiskrepanz zwischen modernen Prozessoren und Speicherarchitekturen sowie deren Auswirkung auf algorithmische Effizienz.
2 Virtueller Speicher und Hardware Caches: Detaillierte Darstellung der Funktionsweise von virtuellem Speicher, Paging, TLB sowie der verschiedenen Architekturen und Strategien (Blockplatzierung, Write-Strategien, Cache-Miss-Klassen) von Hardware Caches.
3 Optimierter Radix-Sort für Hardware Caches und TLB: Mathematische Herleitung und Optimierung des Radix-Sort Algorithmus durch Parameteranpassung für unterschiedliche Speichermodelle (RAM, CMM, IMM) sowie Vorstellung der PLSB-Variante.
4 Fazit: Zusammenfassende Bewertung der verschiedenen Optimierungsansätze und deren Leistungsfähigkeit im Vergleich zum Quicksort-Algorithmus.
Schlüsselwörter
Radix-Sort, Hardware Caches, Translation Lookaside Buffer, TLB, Virtueller Speicher, Cache Memory Model, Speicherhierarchie, Laufzeitoptimierung, Paging, Cache Misses, Blockplatzierung, PLSB Radix-Sort, Algorithmenanalyse, RAM-Modell, Internal Memory Model
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Ausarbeitung analysiert, wie moderne Sortieralgorithmen, insbesondere Radix-Sort, an die hardwareseitigen Gegebenheiten der Speicherhierarchien angepasst werden können, um die Performance zu steigern.
Was sind die zentralen Themenfelder der Analyse?
Die Arbeit behandelt die Funktionsweise von Caches und TLBs sowie deren Rolle bei Speicherzugriffen und untersucht, wie Algorithmen durch die Minimierung von Cache- und TLB-Misses effizienter gestaltet werden.
Was ist das primäre Ziel der Arbeit?
Das primäre Ziel ist es, durch eine präzise Wahl der Ziffernlänge r und algorithmische Modifikationen die Gesamtlaufzeit bei der Sortierung großer Datenmengen signifikant zu verringern.
Welche wissenschaftlichen Methoden werden verwendet?
Der Autor nutzt theoretische Laufzeitabschätzungen (O-Notation) sowie Worst-Case- und Average-Case-Analysen unter Anwendung verschiedener Speichermodelle (RAM, CMM, IMM).
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in eine theoretische Einführung in Speicherarchitekturen und eine praktische Optimierung des Radix-Sort-Algorithmus unter Berücksichtigung von TLB- und Cache-Eigenschaften.
Welche Begriffe charakterisieren die Arbeit am stärksten?
Die zentralen Charakteristika sind die Optimierung von Speicherzugriffen, die Modellierung von Speicherhierarchien (Caches/TLB) und die Anpassung von Sortieralgorithmen wie Radix-Sort.
Warum ist eine TLB-Optimierung für Radix-Sort wichtig?
Da der TLB bei großen Datenmengen zum Flaschenhals werden kann, reduziert eine gezielte Parameterwahl die Anzahl der TLB-Misses, was die Gesamtlaufzeit der Sortierung maßgeblich senkt.
Was ist das Besondere am PLSB Radix-Sort?
PLSB (Pre-Sorting LSB) Radix-Sort sortiert die zu verarbeitenden Daten in lokalen Segmenten vor, um die räumliche Lokalität zu erhöhen und dadurch TLB- und Cache-Misses effektiver zu reduzieren.
- Quote paper
- Andreas Toeche-Mittler (Author), 2004, Algorithmen für Hardware Caches und TLB, Munich, GRIN Verlag, https://www.grin.com/document/38692
