Rechnerarchitekturen 2
| Rechnerarchitekturen 2 (RA2) | |
|---|---|
| Vertiefungsrichtung | II |
| Vorlesung | |
| Vorlesender |
Prof. Fengler |
| Abschluß | |
| Art | k.A. |
Die Studierenden verstehen detailliert Aufbau und Funktionsweise von fortgeschrittenen Prozessoren und Rechnern. Die Studierenden verstehen Entwicklungstendenzen der modernen Rechner- und Systemarchitektur. Methodenkompetenz:
- Die Studierenden sind in der Lage, Anwendungsbeispiele und Architekturvarianten zu entwickeln. Die Studierenden analysieren Leistungskennwerte von Rechnern und Rechnersystemen.
Systemkompetenz:
- Die Studierenden verstehen das Zusammenwirken der Funktionsgruppen von fortgeschrittenen Rechnern als System und in Rechnersystemen. Sie erkennen den Zusammenhang zwischen Architektur, Leistung und Anwendung anhand praktischer Übungen.
Sozialkompetenz:
- Die Studierenden sind in der Lage, praktische Problemstellungen der Rechnerarchitektur in der Gruppe zu lösen. Entwicklung der Prozessorarchitektur: Complex-Instruction-Set-Computing (CISC), Reduced Instruction-Set-Computing (RISC); Befehls-Pipelining; Skalare Prozessorarchitektur, Very-Long-Instruction-Word-Architektur, Out of Order-Execution; Simultaneous Multithreading.
Entwicklung der Speicherarchitektur:
- Adresspipelining, Burst Mode und Speicher-Banking; Speicherhierarchie, Cache-Prinzip, Cache-Varianten; Beispielarchitekturen;
Spezialrechner:
- Aufbau eines Einchip-Controllers; Einchipmikrorechner des mittleren Leistungssegments, Erweiterungen im E/A-Bereich; Prinzip der digitalen Signalverarbeitung, Digitale Signalprozessoren (DSP), Spezielles Programmiermodell;
Leistungsbewertung:
- MIPS, MFLOPS; Speicherbandbreite; Programmabhängiges Leistungsmodell (Benchmarkprogramme); Parallele Rechnerarchitekturen: Single Instruction Multiple Data, Multiple Instruction Single Data, Multiple Instruction Multiple Data; Enge und Lose Kopplung, Verbindungstopologien Entwicklung von Anwendungsbeispielen, Architekturvarianten und Berechnung von Leistungskennwerten
Prüfung
| Klausur | |
|---|---|
| Termin | |
| Datum: | 23.02.2011 |
| Zeit: | 00:00 - 00:00 |
| Ort: | k.A. |
Am Ende des Semester gibt es eine Klausur die über 90 Minuten geht.
Einführung
RA1/ TI2:
- Grundlagen Prozessor, Speicher, E/A, Maschinenbefehle
RA2:
- Weiterführung zu modernen Prinzipien
- Parallelität
- Konkret Architekturen
- Leistung
Problem:
- Zeit
- Befehle
- Zeit
* Arbeit * Leistung ⇒ =
Ziel:
- Leistungserhöhung
Warum: • komplexerer Applikationen
• moderne Software-Technik braucht mehr Hardware Ressourcen
Möglichkeiten: 1. Variante: Takterhöhung (bei gleicher Architektur)
T kann nicht kleiner sein als Durchlaufzeit der kombinatorischen Logik
→ Logik wird schneller durch Halbleitertechnologie → T kleiner
→ f größer
z.Z.: • Frequenzerhöhung begrenzt aufgrund Taktlaufzeiten auf IC (Integrated Circuit) • Takt muss bei allen Teilen des Prozessors (in bestimmter Toleranz) gleich sein.
→ Laufzeitunterschiede sind problematisch
2. Variante: effektivere Architektur, möglichst ohne Verringerung von T
--> Parallele Strukturen
n-stufige Kombinatorik m-FlipFlops Kombinatorik Z k X Z Y Takt Periode T Rechnerarchitekturen Mitschrift 2. Prozessorarchitektur
- 3 -
2. Prozessorarchitektur 2.1 Ausgangspunkt Grundstruktur aus TI2 (Folie 3_20)
OR - Operanden Register
ALE - Arithmetik Logik Einheit, Ex-Einheit
BR - Befehlsregister
AST - Ablaufsteuerung
BA - Befehlsadressregister
BD - Befehlsdecoder
Befehlsablauf 1. Befehl lesen Instruction Fetch IF 2. Befehl dekodieren Instruction Decode ID 3. Operand lesen (aus Register) Operand Fetch OF 4. Befehl ausführen Execute EX 5. Operand rückschreiben (nach Register) Write Back WB
Zeitbedarf der Phasen IF Zeit für Speicherlesen --> siehe auch Kapitel 3 BD Zeitverbrauch steigt mit komplexerer Logik OF, WB Zeitverbrauch weniger dominant EX Zeitverbrauch steigt mit komplexer Logik
AST Steuerwerk/Rechenwerk (=Datenpfad) BD BR BA OR ALE Rechnerarchitekturen Mitschrift 2. Prozessorarchitektur
- 4 -
2.2 RISC – Architektur „Reduced Instruction Set Computer“ (Rechner mit reduziertem Befehlssatz) Grundidee: nur einige wenige einfache Befehle → für komplexe Funktionen werden mehr Befehle in der Abarbeitung notwendig → Einfacher schnellere Logik (vor allem ID, EX) → gleichartiger Ablauf fast aller Phasen und Befehle → weniger Maschinenbefehl zur Verfügung --> Compiler hat das zu lösen → nur 2 Gruppen von Befehlen I) verarbeitende Befehle ohne Operandenspeicherzugriffe (d.h. Operanden, Resultate nur in Registern) II) Operandenspeichertransport Load Speicher → Register Store Register → Speicher 2.3 CISC – Architektur „Complex Instruction Set Computer“ (Rechner mit komplexen Befehlssatz) Grundidee: viele, verschieden Befehle, von sehr einfach bis komplex → bis an das Niveau einer höheren Programmiersprache Ziel: Weniger Befehle leisten (funktionell) mehr Bsp.: • i86 – Befehlssatz
• Pico – Java – Prozessor: Byte – Code -> Maschinenbefehlsniveau (ausgestorben)
CISC Befehle werden typischerweise durch „Mikroprogrammierung“ realisiert. (Grundidee F_4)
Dekoder: zeigt auf 1. Befehl der zum Makrobefehl gehörigen Mikrobefehlssequenz (MS) µSequenzer: Arbeitet MS sequentiell auf, Makrobefehle erzeugen Steuersignale für Rechenwerk, können evtl. in Abhängigkeit von Statussignalen des Rechenwerks verzweigen Bsp. Ablauf IF Makrobefehl Makrobefehl Dekoder 1. Befehl der Mikrosequenz Nächster Befehl der Mikrosequenz → Ausgabe Steuersignal Verzweigung bei Statussignal ja Befehl der Mikrosequenz Ende der Mikrosequenz IF des nächsten Mikrobefehls Rechnerarchitekturen Mitschrift 2. Prozessorarchitektur
- 5 -
Operandenadressierung: 0 – Operandenadressierung: Es gibt eine Vereinbarung wo Operanden prinzipiell stehen (Bsp. F_5: Oberste Stackposition TOS: Top of stack) 1 – Operandenadressierung: Es gilt die Vereinbarung dass der 1. Operand und somit das Ergebnis immer in einem festen Register steht (Akkumulator)
Der 2. Operand ist in den Registern adressierbar
2/3 – Operandenadressierung: Bei 2 – Operandenadressierung sind die Operanden in Registern frei wählbar wobei das Ergebnis den 1. Operanden überschreibt
Bei 3 - Operandenadressierung sind die Operanden und das Ergebnis
frei wählbar
→ Daher können bei CISC die Operanden auch direkt im Speicher stehen
(Also nicht in den Prozessorregistern)
Vor und Nachteile RISC/CISC
CISC (komplexere Befehle) RISC (einfachere Befehle) Leistungsfähige Maschinenbefehle (+) → Compiler wird einfacher → kleinerer Programmcode (ca. halb so groß) → Optimierung in μ -Befehlsebene nicht möglich Weniger Leistungsfähige Befehle (-) → Compiler erzeugt leistungsfähigere
Funktionalität
→ größere Programmcode → bessere Möglichkeiten zur Optimierung Steuerwerk, μ -Sequenzer, Befehlsdecoder → Aufwendige Logik notwendig → mehr Chipfläche → mehr Leistungsverbrauch Evtl. Niedrigere Taktfrequenz
Relativ einfache Logik → kleinere Chipfläche → weniger Leistungsverbrauch Höhere Taktfrequenz möglich Unregelmäßige Ausführungszeit Regelmäßige Ausführungszeit → ungünstig für μ - Parallelität → günstig für μ - Parallelität
µ - Parallelität: Fähigkeit, Teile der Befehle in Prozessor parallel abzuarbeiten.
Warum CISC? CISC besitzt Aufwärtskompatibilität (ältere Programme sollen als
Maschinencode dennoch lauffähig sein). Deshalb gibt es Prozessoren, die
CISC und RISC mischen
Siehe konkrete Architektur (Pentium) Rechnerarchitekturen Mitschrift 2. Prozessorarchitektur - 6 -
2.4 Pipelining Grundidee: • Konventionell: Alle Phasen eines Befehls werden sequentiell
abgearbeitet, erst danach folgt der nächste Befehl
• Dies ist jedoch Verschwendung, da immer nur bestimmte Teile des
Prozessors pro Phase aktiv sind.
• Daher ist es möglich mehrere Befehle in unterschiedlichen Phasen
gleichzeitig im Prozessor zu bearbeiten
F_6 oberes Schema: Befehle werden nacheinander komplett abgearbeitet F_6 mittleres Schema: Die 5-fache Anzahl von Zeit Befehle sind möglich. F_6 unteres Schema: Superpipelining ermöglicht die 10-fache Anzahl von Zeit Befehle
Aufgrund der kürzeren Taktphasen ist hier auch höherer Takt möglich
Reale Probleme bei der Pipeline: 1. Datenkonflikte (F_7 oben) Folgebefehle benötigen unter Umständen ein vorangegangenes noch nicht berechnetes Ergebnis:
→ Das Ergebnis wird erst in der WB - Phase verfügbar
→ Somit kann OF des Folgebefehls erst 2 Phasen später durchgeführt werden Lösung(einfach): erkennen und Lücken einfügen
2. Sprungkonflikte entstehen insbesondere durch bedingte Sprünge (Schleifen). Erst in WB – Phase bekannt, ob und wohin gesprungen wird I) Es wird nicht gesprungen, da die Sprungbedingung nicht erfüllt war. Es liegt somit kein Problem vor, die in der Pipeline befindlichen Befehle werden weiter linear bearbeitet II) Es wird gesprungen, da die Sprungbedingung erfüllt war. Somit ist es notwendig, die in der Pipeline befindlichen Befehle abzubrechen. Da kein Befehl in der WB – Phase war, gibt es auch keine falschen Ergebnisse. Es entsteht jedoch eine Lücke von 4 Phasen
Konflikte führen zu Leistungseinbußen → Verbesserungen sind notwendig Rechnerarchitekturen Mitschrift 2. Prozessorarchitektur
- 7 -
Verbesserungsmöglichkeiten: 1. Datenkonflikte Result Forwarding (Bypass)
Ergebnis der ALU des Vorbefehls wird über Multiplexer (MUX) direkt auf einen ALU-
Eingang für Folgebefehle geschaltet, WB findet parallel statt
2. Sprungkonflikte • Wird gesprungen? → spekulieren • Wohin wird gesprungen? → Speicher für Sprungziele
Sprungvorhersage:
1 – Bit – Vorhersage (F_9 links, Mitte) • BHT (auch BPB): Speichertabelle mit Adressen der letzten durchgeführten
Sprungbefehle und 1-Bit zur Vorhersage
• Bei Auftreten einer dieser Adressen Auslesen und Vorhersage
• Bei falscher Vorhersage Korrektur • Zur Begrenzung der Tabellengröße und zur Begrenzung der Vergleichszeit werden nur
einige untere Bits der Adresse verwendet
2 – Bit – Vorhersage:
• Vorhersage wird erst bei zweiter falscher Vorhersage verändert
Beispiel F_10:
1 – Bit Vorhersage: 2 falsche pro Schleifendurchlauf
2 – Bit Vorhersage: 1 falsche pro Schleifendurchlauf
Schleifenzahl dekrementieren Sprung bei nicht Null ja nein n-ma l OF EX WB OF EX WB ↓ ohne Forewarding ↓ mit Forewarding Rechnerarchitekturen Mitschrift 2. Prozessorarchitektur
- 8 -
Weitere Sprungvorhersage • Mit Branch Target Buffer (F_11)
F_12 oben: • bei Zieladresse verfügbar in ID-Phase → ein ungültiger Befehl bei gesprungen
• bei Verfügbarkeit Zieladresse in Phase IF → kein falscher Befehl bei gesprungen
Schlecht balancierte Pipeline • Bei gleichen Phasenlängen (z.B. 1 Takt je Phase → Takt Befehl 1 ) • Fertige Befehlsabarbeitung nach 5 Takten
Bsp.: IF: 0,5 T
ID: 0,5 T
OF: 1 T Befehlsabarbeitung 5 Takte
EX: 2 T 1 Befehl alle 2 Takte fertig
WB: 1 T
Lösungsmöglichkeiten
• Superpipeline, wobei nur Phasen mit höheren Zeitverbrauch in Teilphasen zerlegt werden
• Parallelisierung der Hardware für die zeitaufwändigen Phasen
z.B. 2 oder mehr Ex - Einheiten (genauer in Folgepunkten)
Frühzeitig im Befehlsablauf verfügbar Schon zum ID Adresse des Befehls Sprungzieladresse Vorhersage Vergleich Rechnerarchitekturen Mitschrift 2. Prozessorarchitektur
- 9 -
2.5 Superskalare Architektur (F_14) • IF, ID wie normale Pipeline • danach Instruction Sheduler (IS) • Aufteilung der Befehle auf die folgenden parallelen Einheiten nach 1. Einheit ist frei 2. Befehl passt auf spezialisierte Einheit
• OF, EX, WB parallel für die Befehle
• Ex – Einheiten typspezialisiert
Bsp.: 5 Einheiten
2x Integer Einheit
2x FP – Einheit
1x Load-Store-Einheit
Alternativ bei Superskalar
• ID aufteilen in
ID1 → für welchen Ex-Einheiten-Typ
(schneller kleiner Dekoder)
ID2 → vollständiges Dekodieren der Operation
(langsamere parallele komplexe Dekoder) Rechnerarchitekturen Mitschrift 2. Prozessorarchitektur
- 10 -
2.6 Very Long Instruktion Word – Architektur (VLIW, F_16)
• Befehls Wort enthält n Einzelbefehle, die parallel vom Speicher gelesen werden
• Befehle stehen so im Speicher, wie sie direkt zur passenden EX-Einheit zugeordnet
werden müssen (z.B. durch geeigneten Compiler)
Falls kein passender Befehl vorhanden → Leerbefehl (NOP) einfügen
• paralleles Durchlaufen durch alle Phasen
• zeitlich unterschiedliche Phasenlänge hier kein Problem
Bsp.: IF, ID: je 0,5 T 5 EX-Einheiten
OF,WB: je 1 T alle 5 Takte → 5 Befehle fertig
EX: 2 T
1 Befehl: 5T
• bei Kombination von Pipeline und VLIW gilt das nicht mehr:
Pipeline → alle 2 Takte eine Befehlsgruppe
VLIW: 5 Befehle je Befehlsgruppe → alle 2 Takte 5 Befehle
VLIW – dynamischer
• nach parallelen Einlesen des verkürzten VLIW Befehlswortes Zuordnung auf parallele Einheiten durch spezielle Einheiten. (Instruction Queue und Multi-Issue, F_17), kein Umsortieren
• Vorteil: geringere Befehlsspeicherbedarf durch nicht notwendige NOPs
Typische Anwendung VLIW
• IA - 64
• Digitale Signalprozessoren
Probleme Superskalarer VLIW
• Datenabhängigkeiten:
Parallel auf EX-Einheiten können nur Befehle sein, die nicht datenabhängig sind.
• Lösung: Superskalar → Scheduler (Hardware)
VLIW → Compiler Rechnerarchitekturen Mitschrift 2. Prozessorarchitektur - 11 -
2.7 Out of Order „Außerhalb der Reihenfolge“ Grundidee: Befehle der laufenden Befehlsfolge werden vorgezogen, falls Ex-Einheiten frei sind, weil der aktuelle Befehl auf eine belegte spezialisierte Ex-Einheit wartet.
Erweiterungen gegenüber Superskalar (F_18) gegenüber Folie 14: • Instruction Pool: Puffer für eingelesene abarbeitungsfähige Befehle für die verschiedenen Ex-Einheiten. • Scheduler + Zuordnung von Befehlen aus dem Instruction Pool zu freien
Retirement Unit: Ex-Einheiten nach folgenden Kriterien: ♦ Befehl passt auf Ex-Einheiten
♦ Bef. nicht datenabhängig von noch nicht beendeten Befehlen → Hardware ermittelt zur Laufzeit Datenabhängigkeiten • Recorder – Buffer: Sortieren der beendeten Befehle in die Reihenfolge des Programmcodes im Befehlsspeicher
d.h. WB erfolgt in dieser Reihenfolge
• Registerrenaming (RR): Zuordnung logischer Register zu physischen Registern.
Grund: Benutzen vorgezogener Befehle die gleichen logischen
Register, sind aber nicht datenabhängig, erhalten sie andere physische Register
Vergleich Superskalar mit Out of Order (F_21, F_22) • Modellprozessor mit 4 Befehlsarten (F_21 oben links) • Registersatz A – H (F_21 unten rechts) • Bsp. Programm (F_21 oben rechts) • Ablauf Superskalar (F_21 unten links) • Hier 2 Ex – Einheiten → 2 Befehle parallel möglich, die nächsten 2 erst nach deren Ende.
Rechnerarchitekturen Mitschrift 2. Prozessorarchitektur - 12 -
Ablauf Superskalar Ablauf Out of Order (F_22) • Befehl 1, 2 gleichzeitig in Abarbeitung
Ende für beide nach 3 Takten, da einer LOAD (3 Takte)
• Befehl 4 ist datenabhängig von Befehl 3 (Register A)
→ Befehl 3 abarbeiten, Befehl 4 wartet (eine Ex-
Einheit nicht benutzt)
• Befehle 4,5 gleichzeitig in Abarbeitung • Befehle 6,7 gleichzeitig in Abarbeitung
Ende für beide nach 3 Takten, da einer LOAD
• Befehle 8,9 gleichzeitig in Abarbeitung • Befehl 10 in Abarbeitung (letzter vom Ausschnitt) • 1, 2 starten parallel
1 nach 1. Takt fertig, 2. nach 3 Takten fertig
• 5, 6 starten parallel im 2. Takt
2 läuft weiter; 2 LOAD – Befehle können um einen Takt versetzt parallel arbeiten (LOAD – Pipeline)
• 7,8 starten im 3. Takt parallel, 7 weil 5 fertig, 8
nicht abhängig
• 3, 9 starten parallel im 4. Takt, 3 weil 2 fertig
ist, 9 ist nicht abhängig
• 4 und 10 starten parallel im 5. Takt, 4 weil 3
fertig ist, 10 weil 8, 9 fertig
Gesamt 10 Takte: Nichtausnutzung einer Einheit → 5 Takte Gesamt 5 Takte Beide Einheiten immer ausgelastet (gilt nicht immer)
Dicke schwarze Linie in F_21, F_22 • logische Befehlsende, immer in Reihenfolge, wie im Programmkode,
d.h. bei F_22 Befehle 5 bis 10 erst nach 5. Takt
Vergleich VLIW statisch, dynamisch und Out of Order (F_19)
Verfügbar: 4 Ex-Einheiten
VLIW statisch: kein Befehl für EX-Einheit → Einfügen NOP (No Operation)
VLIW dynamisch: keine NOP nötig aber leere EX-Einheiten können nicht genutzt Werden (evtl. Erzeugt Compiler sowas wie Out of Order)
Out of Order: freie Einheiten können genutzt werden Rechnerarchitekturen Mitschrift 2. Prozessorarchitektur - 13 -
2.8 Simultan Multithreading (SMT)-Architektur Grundidee: • Prozessor bearbeitet nicht einen sequentiellen Befehlsstrom, sondern 2 (oder
mehrere), die datenunabhängig sind.
• 1 Befehlsstrom ≙ 1 Thread (sequentiell ausführbares Teilprogramm, parallel zu
anderen Threads ausführbar)
• Threads sind abschnittsweise datenunabhängig.
Struktur: • F_20: Hier für parallele Abarbeitung von 2 Threads • 2x IF / ID + RR, WB, Reg Satz
→ je Thread sind diese Phasen unabhängig parallel
• Instruction Pool: Wartende Befehle beider Threads
enthält durch 2 Threads deutlich mehr unabhängige Befehle.
• Scheduler belegt EX - Einheiten nach Bedarf
Datenunabhängigkeit, sonst gleichberechtigt für beide Threads
• Recorderbuffer → zeitlich richtige Reihenfolge plus Zuordnungen zu dem
richtigen Thread
Globale Gegenüberstellung zur Mikroparallelität
Rechnerarchitekturen Mitschrift 3. Speicherarchitektur - 14 -
Speicherarchitektur
IF → Speicherzugriff Load/Store → Speicherzugriff
• Nicht mehr Befehle bearbeitbar als aus Programmspeicher lesbar • Befehle mit Speicheroperanden bremsen Prozessor, falls diese deutlich langsamer sind
VLIW löst das über paralleles Lesen von n Befehlen gleichzeitig
→ aber sehr breiter Befehlsbus (256 bit)
andere Verbesserungen: • schnellere Speicher • günstigere Architekturen
3.1 Speicherhierarchie F_24: je näher am Prozessor • desto schneller • desto kleiner • desto teurer pro bit
Prozessor Register: unmittelbar bearbeitete Operanden Pipeline kleine Befehlsgruppe
Cache (evtl. mehrere Ebenen): Untermenge des Hauptspeicherinhaltes
Möglichst die Inhalte, die aktuell oft gebraucht werden.
Hauptspeicher: Alle aktuell geladenen Programme und Daten
Hintergrundspeicher: lokale ladbare Programme und Daten
LAN-Server: Ladbare Programme und Daten mehrerer Nutzen
Internet: Programme und Daten der Welt Rechnerarchitekturen Mitschrift 3. Speicherarchitektur
- 15 -
DW 2 DW 1 Abstand Speicherzugriffsende DW 3 DW 4 DW 5 DW 6 DW 7 DW 8 3.2 Mikroparalleltität im Speicher 3.2.1 Adresspipeline (F_25) Speicherzugriff:
A: Adresse übertragen
AD: Adresse Dekodieren
DT: Datentransfer
• j ist unabhängig von i, dann 50 % Zugriff • Phasen möglichst gleichlang 3.2.2 Interleaving (F_26) DRAM- Bänke → getrennte physische Speicher mit eigener AD, DT Fortlaufendes Lesen 32 bit-Word
• Zugriffszeit bleibt gleich, aber 4 x mehr Zugriffe in der gleichen Zeit
• geht nur, falls Speicherworte aufeinander folgen
A2 A3
0 0 Bank 0
1 0 Bank 1
0 1 Bank 2
1 1 Bank 3
1
2
3
4
5
6
7
8
Speicherzugriff
A, AD DT
A i DT i
A j DT j Rechnerarchitekturen Mitschrift 3. Speicherarchitektur
- 16 -
3.2.3 Burst Mode Grundidee: • Prozessor gibt Anfangsadresse aus
• Speicher liefert Inhalt dieser und der nächsten n (z.B.4) Datenworte
ohne neue Adressierung
Effekt: • Einsparung Ausgabe der Folgeadressen
• Geht nur bei kontinuierlichem Lesen
F_27 oben: • Adresse (Zeile, Spalte) mit Adresstaktsignalen RAS, CAS vom Prozessor
zum Speicher • Speicher liefert 4 Datenworte (D1 – D4) unmittelbar hintereinander zurück. • Ready kennzeichnet gültige Daten
F_27 unten: • Burst + Interleaving
• Nach Ausgabe Zeile, Spalte für 1. Bank.
→ Sofort Ausgabe Zeile, Spalte für 2. Bank → danach fast unmittelbar hintereinander 4 DW der 1. Bank + 4 DW der 2.Bank 3.3 Cache – Speicher Bisher: Systembus
Neu: System- System-
bus bus’ • kleiner, prozessornaher Speicher ist schneller • aktuell oft verwendete Befehle + Daten sind im Cache (hohe Wahrscheinlichkeit, dass sie mehrfach verwendet werden) • Cache enthält Kopien von HS – Inhalten
Prozessor Hauptspeicher Prozessor Hauptspeicher Cachespeicher mit Cachelogik
Rechnerarchitekturen Mitschrift 3. Speicherarchitektur - 17 -
3.3.1 Vollassoziativer Cache:
• Zu jedem Datenwort ist im Cache die volle Hauptspeicheradresse abgespeichert • Bei der Suche, ob Datenwort im Cache vorhanden sind mit der gewünschten Adresse parallel Schritte bei Cache – Treffer (DW im Cache) entsprechend
F_28:
Treffer – A(j) im Cache Kein Treffer – A(j) nicht im Cache
1. A(j) vom Prozessor zum Cache – Controller 2. Vergleich von A(j) mit allen Adressen im Tag – Bereich des Caches 3. A(j) gefunden A(j) nicht gefunden 4. D(j) zum Controller A(j) zum Hauptspeicher 5. D(j) zum Prozessor D(j) zum Cache – Controller 6. D(j) zum Prozessor und parallel in den Cache schreiben
Grundprinzip beim Schreiben:
Treffer Kein Treffer
1. A(j) + D(j) zum Cache – Controller 2. A(j) zum Cache mit Adressvergleich 3. A(j) gefunden, neue D(j) auf Speicherplatz mit A(j) schreiben A(j) nicht gefunden, A(j), D(j) zusammen eintragen 4. Paralleler Start mit 2. A(j) + D(j) zum Hauptspeicher und dort schreiben
F_29: • Im Cache HS-Adressen in beliebiger Reihenfolge
• jeder Eintrag im Cache zeigt auf genau einem Hauptspeicherplatz
F_30: • Bsp. für Tag- Vergleich F_31: • Interne Struktur voll assoziativer Cache
Je Tag / Datenwert für Vergleicher ( ) notwendig
→ Im Folgendem: Strukturen mit verringertem Vergleichsaufwand = Rechnerarchitekturen Mitschrift 3. Speicherarchitektur
- 18 -
3.3.2 Direct Mapped Cache F_32 → Datensicht
A n-1
Seite m
• • •
Seite 1
Seite 0
A 0
Zuordnung: • Cache – Eintrag zu HS-Eintrag (F_32)
• Tag → Teil Seitenadresse der Gesamtadresse
• Datenbereich im Cache ist physisch normal adressiert: A0, A1, A.....A k-1
Eintrag Seitenadresse = Tag k mit physischer Adresse in der Seite Idx i zeigt auf Hauptspeicheradresse Tag k , Idx i
z.B.. A31...A25, A24...A0
→ gleiche physikalische Adresse nur von einer Seite möglich!
Bereiche mehrerer HS-Datenworte hintereinander → mehrere Cache-Datenworte hintereinander mit gleichem Tag
Vergleich mit Tag nur in der Zeile, wo die physische Adresse mit der gesuchten Adresse (Teil Adresse in der Seite übereinstimmt) (F_33); → d.h. nur 1 Vergleich Adresse
A31 – A25 A24 – A0 Seitenadresse Offset der Seite Rechnerarchitekturen Mitschrift 3. Speicherarchitektur
- 19 -
3.3.3 Mehrwege-Caches (n-way-set-associative caches) Direct mapped 2-way steigende Effektivität, . steigender Aufwand . n-way fully associative
Spezialisierte Caches z.B.: • Trace Cache, für Sprungvorhersage
• TLC (translation lookaside cache); für MMU
Cache-Strategien
• Lade – Strategie: Zeitpunkt der Cache-Eintragung demand/predemand • Ersetzungs-Startegie: Auswahl der zu ersetzenden Eintragung • Schreib-Strategie: Verhalten beim Speicherschreiben
Lokalität: • räumlich (spatial)
• zeitlich (temporal)
Ersetzungsstrategien
• LRU (Last recently used) benötigte Bits: ! log 2 n
• Pseudo-LRU
• Random: „untere Schranke“
• A priori optimal „obere Schranke“
„Kohärenz-Bit“ / „Dirty-Bit“
Zugriffszeiten: • Arbeitsspeicher: t A
• Cache: t C (t C < t A )
Mittlere resultierende Zeit: A C m t T t T T ⋅ − + ⋅ = ) 1( t Cachegröße 1 Direct Mapped 2 way Rechnerarchitekturen Mitschrift 3. Speicherarchitektur
- 20 -
3.3.8 Cache und Harvard- Architektur
aus RA1:
Vorteil:
F_41 links: • bis Caches Harvard • danach zum Hauptspeicher Princeton → bei Treffer Vorteil Harvard
• Erhöhter Verbindungsaufwand nur im Prozessor-IC
→ fällt kaum ins Gewicht
F_41 rechts: Harvard, auch außen hoher Verbindungsaufwand
3.4 Prinzipien von Kapitel 2 und 3 in einem Bsp. Prozessor (Pentium)
Princeton - Architektur Harvard - Architektur
geringerer Schnittstellenaufwand Daten- und Programmzugriffe parallel Rechnerarchitekturen Mitschrift 4. Microcontroller und Digitale Signalprozessoren
- 21 -
4. Microcontroller und Digitale Signalprozessoren
Einchip-Rechner (µC, DSP)
• Alle wesentlichen Funktionseinheiten auf 1 IC
→ typischen Anwendung im eingebetteten Rechner NS: Nutzerschnittstelle
Nutzer
Bsp.: Motorsteuergerät (Automobil): Eingebettetes System: Motor Sensoren: Drehwinkel Kurbelwelle Aktoren: Einspritzung Kraftstoff
Zündkerzenansteuerung
Zusätzliche digitale Hardware: Leitungsansteuerung
Aktoren + digitale Schutzverriegelung
Nutzerinterface: Gaspedal, Drehzahlmesser Rechennetz: CAN-Bus zu den anderen Steuergeräten → Rechner-IC typisch sehr leistungsfähig
z.B. Tri-Core (Infinineon)
Einchip – Rechner mit DSP-Eigenschaften Merkmale • autonom • spezieller Rechner → auf Anwendung zugeschnitten • hohe Typenvielfalt • große Unterschiede in der Leistung
Globale Unterschiede µC DSP Steuerungsaufgaben • binäre Steuerung + einfache Regelung
geringe Rechenleistung E/A i.A. komplexer Kleinerer Speicher Typ. Befehle: bit-Befehle
Preis: niedriger Stromaufnahme: niedriger Signalverarbeitung • komplexe Regelung • Filter usw. hohe Rechenleistung E/A eingeschränkter Größerer Speicher Typ. Befehle: MAC (multiply and accumulate) Begrenzende Arithmetik Preis: höher Stromaufnahme: höher
Rechnernetz
Rechner IC Zusätzliche digitale und analoge Hardware NS Sensoren, Aktoren Eingebettetes System (Mechanik, Elektromechanik) Rechnerarchitekturen Mitschrift 4. Microcontroller und Digitale Signalprozessoren
- 22 -
4.1 µC der unteren Leistungsklasse Bsp.: F_43 ATtiny 15L • Prozessor – Core: Prozessor und internes Registerfeld (nutzbarer Datenspeicher); Datenbreite 8 bit
• Flash – ROM: Programmspeicher: mehrfach beschreibbarer ROM und
Programmierlogik (realisiert das mehrfach mögliche Programmieren)
• Daten – EEPROM: elektrisch programmier- und löschbarer ROM: stabile Daten
(Anfangswerte; Werte, die ohne U B erhalten bleiben sollen)
Nicht im Zeitraster Maschinentakt les- und schreibbar
• E/A: Prinzip: alle E/A – Funktionen benutzen die Anschlüsse, die sonst als parallel digital (siehe RA1, Kap. 5) genutzt werden Ø PortB 6 binäre E/A – Anschlüsse Ø Timer/ Counter 0/1: Funktion siehe RA1, Kapitel 5 Ø Analog – Comparator: vergleicht 2 kontinuierliche Eingangsspannungen U 1 und U 2 I. U 1 > U 2 à Ausgang “1“ II. U 2 > U 1 à Ausgang “0“ III. 2 1 U U ≈ à Ausgang nicht exakt angebbar • ADC: Analog Digital Converter
Umwandlung analoge Spannung in Binärzahl
• Analog MUX: Multiplexer; Durchschalten von Eingängen auf ADC • Interrupt Unit: Einfacher Interrupt – Controller für Ø ADC Ø Digitale Eingänge Ø Analog Comparator Ø Timer • Watchdog - Überwachung der Prozessorfunktion und Fehlerbehandlung
Timer : (Interrupt, Reset) Prinzip:
• Oszillator: Erzeugt Takt für µC
• Timing & Controll: Logische und Zeitsteuerung des gesamten Controllers
Max Wert Zählerstand WD-Timer RSP fällt auf Grund Programm- fehlers aus Interrupt bzw. Reset Rücksetzen durch Programm (RSP) RSP Rechnerarchitekturen Mitschrift 4. Microcontroller und Digitale Signalprozessoren
- 23 -
4.2 µC der oberen Leistungsklasse Bsp.: F_44 Infineon C167 Unterschiede gegenüber 4.1: • Prozessor: 16 bit Daten, leistungsfähigerer Befehlssatz • Programmspeicher: größer, hier als Rom, aber auch programmierbare
(intern, extern möglich) Varianten existent
• Datenspeicher: 2x RAM/ zusätzlich zu Registern, einer für Datenaustausch mit
CAN-Controller
• Harvard – Architektur: getrennte Busse zu Programm/ Datenspeicher und EA • E/A: große Pin-Anzahl (112)
Alle parallel digital möglich, andere E/A-Funktionen benutzen sie mit
• EBC: Externes Speicherinterface
ca.
3 1
der EA – Pins notwendig
• ADC: wie 4.1 geringe Auflösung (16 Kanäle über analoge MUX) • 2 serielle E/A Controller (universell) • 5 Zähler/ Zeitgeber (GPT, general purpose timer) • PWM – Einheit (Puls – Weiten – Modulation)
• CCOM (Capture and Compare)
Timer von CAPCOM
Bei “*” z.B. Interrupt, Signalwechsel binärer Ausgang, Einlesen t T=const. t = variabel zwischen 0 und T t t t T T T Tiefpass PWM analoge U als Analog - U Vergleichsspannung (variabel) Zähler- stand t T t t t 0
1*
t variabel t ~ U Rechnerarchitekturen Mitschrift 4. Microcontroller und Digitale Signalprozessoren
- 24 -
• Interrupt – Controller+ PEC (peripheral event Controller)
relativ komplex im Vergleich zu 4.1, aber auch zu Universalrechnern
• CAN – Controller Nicht bei allen Infineon C16x- Varianten
Controller für CAN (controller area network) Kommunikationssystem im Automobil (Bosch, 80er Jahre) mit angeschlossenem RAM (xRAM)
• WDT Watchdog Timer à 4.1 • OSC/PLL (Oszillator + Phase look loop) à Takterzeugung • XTAL Anschluss für externen Quarz als frequenzbestimmendes Bauelement
Zusammenfassung:
µC der unteren Leistungsklasse µC der oberen Leistungsklasse • Voll funktionsfähiger Controller auf 1 IC • Keine externe Speichererweiterung • Applikationen begrenzt durch internen Speicher) • Sehr eingeschränkte E/A Pins à E/A Fkt. teilen sich diese • Leistungsfähig • Besonders geeignet für Automotive Steuergeräte
4.3 Einchip – Rechner der obersten Leistungsklasse (z.Z.)
Bsp.: ARM7TDMI F_45/46 F_45: • Prozessorkern § 32 bit-Daten § Einige Eigenschaften eines DSP à siehe im Folgenden F_46: • µC mit 2x Prozessorkern je Prozessor
• 1 Cache
• 1 x RAM >> C167 RAM (siehe 4.2)
• Externer RAM über DMA – Schnittstelle (Direct Memory Access)
• Boot – BIOS extern • Kein interner ROM à Applikationsprogramme werden geladen • Peripherie: typisch für Multimedia – Anwendungen • Mit PC – Kopplung (USB – Schnittstelle) Rechnerarchitekturen Mitschrift 4. Microcontroller und Digitale Signalprozessoren
- 25 -
4.4 Digitale Signalprozessoren Grundidee digitale Signalverarbeitung:
• Durchgeführt durch Analog - Digitalumsetzer • T t , U bit abhängig von Kenngrößen des
Eingangssignals
• max 2 1 f T f T ≥ = (Abtasttheorem Shannon; max. im Signalspektrum vorkommende Frequenz)
Bsp. für Abtastfehler
• Differentialgleichungen werden Differenzengleichungen
Typische Gleichung ... 2 1 − − + + = k k k K cx bx ax y
• Berechnung in Echtzeit: Berechnung von Zeitpunkt k muss K+1 abgeschlossen sein
à Architektur von DSP auf diese Art der Berechnung spezialisiert, um möglist kleines T t zu erzielen
U t T t U bit Rekonstruierte Kurve (Interpolation) Rechnerarchitekturen Mitschrift 4. Microcontroller und Digitale Signalprozessoren
- 26 -
4.5 Bsp. DSP Texas Instruments TMS 320 C24x • Prozessor: 32 bit Daten • Mehrere Shifter à Multiplikation mit 2-er Potenzen
(z.B. zur Zahlenbereichsanpassung + Multiplizieren)
• ALU – Besonderheiten - MAC – Befehle (Multiply and Accumulate)
à für Polynomberechnung
- Begrenzende Arithmetik
• Programmspeicher geht nach Typ ROM oder FlashROM • 2 parallele RAM’s • Peripherie à ähnlich C167… aber weniger parallele E/A • ITAG: spezielles serielles Testinterface à für HW- Unterstützung von Programminbetriebnahme und Test unter Echtzeitbedingungen
4.6 Beispiel TigerSHARC (Analog Device) F_49/50
• 2 Verarbeitungsblöcke mit typischen DSP – Architektur 32 bit, nach außen 128 bit Daten
• 2 Adressierungseinheiten + Programmsequenzer mit Sprungvorhersage
• Interner Speicher mit 4 Kreuzschinenschalter (Crossbar) – Anschlüssen à s. Kapitel 5 • 4 Bussysteme parallel mit je 128 bit Daten und 32 bit (1xnur 21 bit) Adressen • Peripherie (F_50) über SOC-Bus (System on Chip) • Keine Standard Peripherie, sondern 4 Links für entweder schnelle
Prozessorkernmultiplikation oder Peripherie
• Interface zu übergeordneten Prozessor und externen RAM + ITAG (w.o.)
maximal darstellbarer Zahlenbereich Ergebnisse Rechnerarchitekturen Mitschrift 4. Microcontroller und Digitale Signalprozessoren
- 27 -
Beispielprogramm PID – Regelalgorithmus für Elektrometer r(n): Solldrehzahl u(n): Steuergröße y(n): Istdrehzahl e(n) = r(n) – y(n): Regelabweichung P: Proportionalanteil à K p I: Integralanteil à K I D: Differentialanteil à K D
K p, K I , K D entsprechend regelungstechnischen Verfahren Motorwerk anpassen
Diskrete Gleichung
14 ns Ausführungszeit da einige 1 - Takt- und einige 2 – Taktbefehle
MHz f f MHz ns f T T 35 2 70 14 1 max ≈ ≤ ≈ ≤
Verschiebung nach Takt
n-2 n-1 n
t
n-2 n-1 n
t
ASM – Programm
à F_53 Rechnerarchitekturen Mitschrift 5. Parallele Architekturen
- 28 -
5. Parallele Architekturen
Makroparallelität, d.h. nicht im Prozessor, sondern mehrere Prozessoren Klassifikation nach Flynn:
S: Single I: Instruction M: Multiple D: Data
SISD: Einprozessorrechner à kein Parallelrechner SIMD: Der gleiche Befehl wirkt zu einem Zeitpunkt auf unterschiedliche Daten MISD: mehrere Befehle wirken gleichzeitig auf dieselben Daten MIMD: mehrere Befehle wirken auf mehrere (unterschiedliche) Daten
Befehls- und Datenspeicher können gemeinsam aber auch getrennt sein
Wichtige Klassen
• SIMD: z.B. Vektorprozessoren
• MIMD: z.B. Multicore, Rechnernetz
SIMD – Prinzip
• z.B. PC – Prozessoren
• z.B. MMX – Entwicklung (F_63)
hier vorwiegend für Bearbeitung von Multimedia-Daten z.B. Bilder, Bildsequenzen u.a.
Synchronisation: Programmabläufe auf verschiedenen Prozessoren beeinflussen sich gegenseitig Kommunikation: Programme unterschiedlicher Prozessoren tauschen Daten aus Synchronisation: Spezialfall der Kommunikation à Austausch von Steuervariablen
Mögliche Strukturen • Variante Kommunikation über Speicher Grundvariante Shared Memory 1 n-Tor-Speicher + n Prozessoren (F_59 oben links) Problem: n größer → häufiges Warten der Prozessoren
→ Alternativ
P P
SP SP
Kommunikation u.
Synchronisation Shared Memory P local Memory P local Memory Unterschiedlicher Adressbereich Rechnerarchitekturen Mitschrift 5. Parallele Architekturen
- 29 -
• Distributed Memory (F_59 oben rechts) Ø Jeder Prozessor hat lokalen Speicher, Kommunikiation über andere Mechanismen • Virtual Shared Memory (F_59 unten links) Ø Distributed Shared Memory mit gemeinsamen Adressraum: Ø Zugriff mit Adresse Speicher m durch Prozessor m → normaler Speicherzugriff Ø Zugriff von Prozessor m auf Speicher k mit m ≠ k → Abwicklung über zusätzliche Kommunikation • Shared memory Variante (Distributed Shared Memory) Ø m * n – Tor – Speicher
→ deutlich kürzere Wartezeiten
• Shared memory + Distributed Shared memory
→ konzentrierter Aufbau aufgrund - hoher Verbindungsaufwand
- notwendige kurze Leitungslängen
Ø Enge Kopplung: gemeinsamer Speicher → hohe Kommunikationslast möglich Ø Lose Kopplung Kommunikation über E/A → niedriger Kommunikationsumfang
• Verbindungsnetzwerke
F_61
P/S: Prozessor/Speicher
L: Link zur Kommunikation
Max. Kommunikationslänge (MKL) = max. notwendigen Verbindungen für die Kommunikation von 2 Prozessoren (MKL à KL 2007 ) a) Linie (F_61) MKL = n-1 n: Anzahl der Prozessoren b) Ring MKL =
(ganzzahliger Teil)
Ø Linie mit verbundenen Anfangs- und Endelement c) Zweidimensionaler Torus MKL = √
(s. Literatur)
Ø Matrix mit verbundenen Randelementen Ø mit 6 Links → dreidimensionale Strukturen
P/S P/S Verbindungsnetzwerk P/S L1 L2 L3 L4 Rechnerarchitekturen Mitschrift 5. Parallele Architekturen
- 30 -
Crossbar (Kreuzschinenschalter) F_62 links Ø Knoten: Prozessoren, Speicher Bsp.: Waagerecht: P Senkrecht: SP Ø Jeder Prozessor kann auf jeden Speicher geschaltet werden: Alle P gleichzeitig auf einen SP (schlechtester Fall) → max. Wartezeit n * Zugriffszeit Alle P gleichzeitig auf unterschiedliche Speicher → max. Wartezeit 1 * Zugriffszeit Im Realen: → dazwischen
Ø Sonderfall: Crossbar nur für Prozessoren
Hypercube Ø n – dimensionaler Würfel
n=3 Links/Prozessor: n
Aufwand MKL = 3 = n
→ relativ kurze MKL bei vergleichsweise geringem Verbindungsaufwand
P 1 P 2 P 1 P 2 physikalisch 1P Rechnerarchitekturen Mitschrift 5. Parallele Architekturen
- 31 -
5.2 Wichtige Parallele Architekturmerkmale in heutigen Rechnerkonzepten SIMD: • Erweiterung im Universalprozessor
Register: • Segmentieren in Vektorregister (bei reduzierter Operandengenauigkeit)
Operationen mit 2 Registern parallel auf alle Teile 1 Befehl, 1 BA → n (Bsp4) Operationen und Ergebnisse
• Anwendung vorwiegend für Multimediadaten
n-Core – Prozessoren:
• z.B. 2/4 – Core – Prozessoren
• je Prozessor separate Caches
• Hauptspeicher, EA gemeinsam
• Verbindungsnetzwerk zw. Prozessoren und Speicher/Buscontroller
Crossbar
• Problem der separaten Caches: Konsistenz gemeinsam genutzter Daten
• Spezielle Protokolle sichern Konsistenz ab
Bsp.: MESI – Protokoll (F_65) Zustände
M: Verändert
E: Exklusiv (nur 1 Prozessor)
S: Geteilt (mehrere Prozessoren)
I: Invalid (nicht verwendbar)
Übergänge (nicht ausführlich)
→ durch Protokoll wird Zugriff langsamer
Mehrprozessorboard: • Prozessoren mit Speicherinterface und Buscontroller (Anschluss E/A) oder
Prozessorkommunikation
• jeder Prozessor hat separaten RAM • untere äußere Prozessoren haben EA(IO)-Anschluss • Verbindung: Matrix 4x2 • aus konstruktiven Gründen 2 boards
Rechnerarchitekturen Mitschrift 5. Parallele Architekturen - 32 -
Hochleistungrechner (Massiv Parallel) • Hauptanwendung z.B. Wettervorhersage
Komplexe Simulation
• Hauptkonkurrenz: Grids
Bsp.: IBM Blue Gene/L
Verbindungsarchitektur: Mischarchtitektur • Direkte Kopplung der Prozessoren Torus (F_68)
Jeder Prozessor im Torus ist auch Prozessor in der weiteren Verbindungsstruktur
Weitere Verbindungen:
• Gbit – Ethernet (Baum)
• Jtag: Verbindungen zur Knotensteuerung
(eigentlich spezielles Interface zur Teststeuerung und Auswertung in der IC-Produktion)
Knotenarchitektur: • 2 Prozessoren, je mit Level 1 (L1)-Cache und Floating Point Unit (FPU) • Je ein L2 – Puffer • L3: Cache gemeinsam oder Speicher • Gemeinsamer externer Speicher (RAM – Controller) • Schnittstellen • Verbindung: JTAG, Ethernet, Torusverbindung • Zusätzliche globale Verbindung (z.B. Globale Interrupts)Rechnerarchitekturen Mitschrift 6. Leistungsbewertung
- 33 -
6. Leistungsbewertung
Physikalisch
Wozu?
Ø Hersteller: Verkaufsargument
Ø Anwender: eigene Anwendungen im akzeptierten Zeitaufwand
Leistungsentwicklung
L* Rechnerleistung
L** Leistungsbedarf Standardsoftware
Gründe für höheren Leistungsbedarf
Ø Komplexität der Anwendungen steigt
Ø Moderne Softwaretechnik braucht mehr Leistung
Befehlsanzahl → Arbeit Ø Messen? Ø Welches Programm? Ø Oder F_70 • RISC: Gleich lange Befehle außer Load/Store • CISC: Welche Befehle der Länge 1,2,3 Takte treten wie häufig auf • Programmmix untersuchen → relative Häufigkeit p i für Befehlsgruppe i
Durchschnittsbefehlsdauer
Bsp.: Normalbefehle CPI = 1 p NB = 0,7
Load/Store CPI = 3 p LS = 0,3
CPI G = 0,7 × 1 + 0,3 × 3 = 0,7 + 0,9 = 1,6 d.h. 1,6 Takte/Befehl Taktperiode T P [µs] Frequenz f=1GHz = 10³ MHz
2000 2005 2010 L* LB** Rechnerarchitekturen Mitschrift 6. Leistungsbewertung
- 34 -
Relative MIPS Ø Bezogen auf die historische VAX 11/780 (1 MIPS) Ø Bsp. 625 MIPS absolut = 625 relativ
Probleme von MIPS – Leistung Ø Befehlsmix repräsentativ? Ø Cache? Befehle haben kontextabhängig unterschiedliche Ausführungszeiten Ø Einflüsse von Betriebssystem, Compiler u.ä. → Alternative: Benchmark Programme • Synthetische oder Sammlung realer Programme
→ deren Ausführung messen
→ Vergleich
• Ausgangspunkt Hochsprachenprogramm + Abarbeitung unter Betriebssystem möglich
Gleitkommaleistung Floating Point Operations per Second (FLOPS) Ø Berechnung ähnlich MIPS Ø Aber ausschließlich Gleitkomma – Operationen (i.a. gewichtet) Ø F_72
Speedup Parallele Architekturen Ø Wie viel wird ein Programm schneller abgearbeitet, wenn es von einem Prozessor ausgehend auf n Prozessoren aufgeteilt wird Ø ideal
Ø real
Serieller Anteil → nicht parallelisierbar
→ Kommunikationsoverhead
i.a. größer bei Aufteilung auf mehr Prozessoren
1 1 2 3 4 2 3 4 optimale Prozessoranzahl o(n) überwiegt n Prozessoren
Vorträge
Nochmal alle Vorträge zusammen: Klick
