Rechnerarchitektur (RA)
8. Prozessorarchitektur für Fortgeschrittene Prof. Dr. Christian Plessl
RA.8 2018 v1.0.0
1
8. Prozessorarchitektur für Fortgeschrittene ─ ein kurzer Überblick ─
8.1 ParallelitätaufWortebene
8.2 ParallelitätaufInstruktionsebene
8.3 ParallelitätaufThread-Ebene
8.4 ParallelitätaufTask-Ebene
8.5 WeiterführendeVeranstaltungen
RA.8 2018 v1.0.0
Inhaltsverzeichnis
2
8.1 Parallelität auf Wortebene
• Multimedia Instruktionssatzerweiterungen
– Multimedia-Anwendungen nutzen oft 8/16 Bit Datentypen, viel Parallelität
• Sub-Wort Ausführungsmodell
– die Register und ALUs werden partitioniert
– gleichzeitige Ausführung einer Instruktion auf mehreren Operanden,
SIMD Parallelität (single instruction, multiple data)
– Bsp. 64 Bit Architektur:
0
Packed half-word (4 x 16 bit) Packed byte (8 x 8 bit)
Long word (64 bit, native data type)
ADD R3, R1, R2 Packed word (2 x 32 bit) R1
a3
a2
a1
a0
1
0
b3
b2
b1
b0
R2 R3
====
3
2
1
0
a3+b3
a2+b2
a1+b1
a0+b0
7
6
5
4
3
2
1
0
RA.8 2018 v1.0.0
3
++++
SIMD Instruktionssatzerweiterungen
• x86 SIMD Instruktionssatzerweiterungen
– 1996:
– 1999:
MMX (multimedia extensions), benutzt 64 Bit FP Register
SSE (streaming SIMD extensions), 128 Bit Register, parallele SP FP Operationen
– 2001: SSE2
– 2004: SSE3 auch parallele DP FP Operationen
– 2007 SSE4
– 2010:
– 2013:
AVX (advanced vector extensions), 256 Bit Register AVX512, 512 Bit Register 16 SP FP Operationen gleichzeitig
Bsp.: AVX Instruktionen für DP FP (Auswahl)
RA.8 2018 v1.0.0
4
• Einzyklenimplementierung
CPI = 1
• Mehrzyklenimplementierung
Zyklen
8.2 Parallelität auf Instruktionsebene
IF
ID
EX
MEM
WB
IF
ID
EX
MEM
WB
CPI > 1
IF
ID
• Pipelining
IF
ID
EX
MEM
WB
IF
ID
EX
MEM
WB
IF
ID
EX
MEM
WB
IF
ID
EX
MEM
WB
IF
ID
EX
CPIideal = 1 CPIreal > 1
RA.8 2018 v1.0.0
5
Instruktionen
Tiefes Pipelining
• Die Operationen in der EX-Phase dauern oft deutlich länger als einen Taktzyklus → Performance der Pipeline sinkt.
– Abhilfe: mehrere Ausführungseinheiten mit unterschiedlichen Latenzen
– die Ausführungseinheiten können selbst in einer Pipeline implementiert sein
Beispiel
© Elsevier 2003
EX: 1 Taktzyklus
M1…M7: 7 Taktzyklen, Pipeline A1…A4: 4 Taktzyklen, Pipeline DIV: 24 Taktzyklen
RA.8 2018 v1.0.0
6
•
Pipelining mit parallelen Ausführungseinheiten
Implementierungsvariante: in-order execution
– Instruktionen werden in der ursprünglichen Programmreihenfolge den Ausführungseinheiten zugeteilt (in-order issue, in-order execution), die Resultate der Instruktionen können aber out-of-order erzeugt werden
– kann eine Instruktion nicht zugeteilt werden (wegen eines Hazards), müssen alle nachfolgenden Instruktionen warten
Beispiel
unabhängige Instruktionen, suffix “.D” = double precision floating point
RA.8 2018 v1.0.0
7
Pipelining mit parallelen Ausführungseinheiten
• Probleme durch unterschiedliche Latenzen der Ausführungseinheiten
– durch die tiefe Pipeline gibt es tendenziell mehr stalls durch data hazards → Lösungsmöglichkeiten wie bei der einfachen Pipelineimplementierung
– es können in einem Taktzyklus mehrere Instruktionen in der WB Phase sein (structural hazard bzgl. des Registerfiles) → Zugriffe in Reihenfolge der Priorität
– es können neue Konflikte entstehen, Bsp.: WAW (write-after-write) Hazards
Beispiel
WAW Hazard, wenn
L.D F2, 0(R2)
hier wäre
RA.8 2018 v1.0.0
8
Pipeline Scheduling
• Reduktion von Data Hazards durch Umordnen von Instruktionen
– durch die Software (Compiler): statisches Scheduling, zur Compilationszeit
– durch die Hardware (Prozessor): dynamisches Scheduling, zur Laufzeit
– meist wird eine Kombination verwendet
• Statisches Scheduling durch den Compiler
– die Eigenschaften der Prozessorimplementierung fliessen in den Compiler ein
– der Code ist nur für die konkrete Prozessorimplementierung effizient
– der Compiler kann nicht alle Abhängigkeiten erkennen und muss daher immer konservative Entscheidungen treffen
– Beispiele für Techniken: Verschieben von Instruktionen, Schleifen entfalten (loop unrolling), Software pipelining
• Dynamisches Scheduling durch den Prozessor (out-of-order execution)
– grosser Hardwareaufwand erforderlich, daher begrenzt komplexe Algorithmen zur
Umordnung von Instruktionen einsetzbar
– der Compiler wird einfacher
– der Code läuft effizient auf jeder Implementierung der ISA (!)
– Beispiel für Techniken: Scoreboarding, Algorithmus von Tomasulo
RA.8 2018 v1.0.0
9
Dynamisches Scheduling
• Erweiterungen der Architektur
– jede Ausführungseinheit bekommt eine reservation station
§ speichert die Instruktionen und die Operanden und wartet mit dem Start von Instruktionen bis die Konflikte aufgelöst sind
– nach den Ausführungseinheiten sorgt eine commit unit dafür, dass der Maschinenzustand (Register, Speicher) in einer korrekten Reihenfolge geändert wird (durch einen reorder buffer)
RA.8 2018 v1.0.0
10
•
Mehrfachzuordnung
Pipelinescheduling versucht, den realen möglichst nahe an den idealen CPI-Wert zu bringen.
– obwohl sich viele Instruktionen in den Ausführungseinheiten befinden, startet pro Taktzyklus maximal eine neue Instruktion → CPIideal = 1
Prozessoren mit Mehrfachzuordnung (multiple issue) starten mehr als eine Instruktion pro Taktzyklus.
– bei einer m-fach Zuordnung → CPIideal = 1/m
– es müssen mehrere Instruktionen pro Taktzyklus vom Cache geholt werden →
die Bandbreite zum Cache muss dementsprechend erhöht werden
•
Beispiel
IF
ID
EX
MEM
WB
IF
ID
EX1
EX2
EX3
MEM
WB
IF
ID
EX1
EX2
MEM
WB
IF
ID
EX
MEM
WB
IF
ID
EX
MEM
WB
IF
ID
EX1
EX2
MEM
2-fach Zuordnung
RA.8 2018 v1.0.0
WB
11
Prozessoren mit Mehrfachzuordnung
• Statische Mehrfachzuordnung (VLIW Prozessoren)
– die Zuordnung zu den Ausführungseinheiten wird vom Compiler durchgeführt
– die einzelnen Instruktionen müssen in Pakete gepackt werden (issue packets), ursprüngliche Bezeichnung: very long instruction word (VLIW)
– typischerweise können nicht alle Instruktionskombinationen parallel ausgeführt werden, Bsp.: nur eine ALU und eine load/store Einheit → sub/add nicht parallel
– Prozessorentwurf wird stark vereinfacht, der Compilerentwurf schwierig
– Code ist nicht binärkompatibel zu anderen Prozessoren mit derselben ISA !
– Bsp.: Intel IA-64 (Itanium, Itanium 2)
• Dynamische Mehrfachzuordnung (Superskalare Prozessoren)
– die Zuordnung zu den Ausführungseinheiten wird vom Prozessor durchgeführt, das dynamische Pipelinescheduling kann relativ einfach auf Mehrfachzuordnung erweitert werden
– Prozessorentwurf wird komplexer, der Compilerentwurf vereinfacht
– Code ist binärkompatibel zu anderen Prozessoren mit derselben ISA !
– Bsp.: Intel IA-32 (Pentium 4)
RA.8 2018 v1.0.0
12
Beispiel
Statische Mehrfachzuordnung
MIPS Pipeline mit statischer 2-fach Zuordnung: Ausführungseinheit #1: ALU, branches Ausführungseinheit #2: load/store
ursprünglicher Code: Loop: lw addu
sw addi bne
Code für 2-fache statische Zuordnung: ALU/branches
$t0, 0($s1)
$t0, $t0, $s2
$t0, 0($s1)
$s1, $s1, -4
$s1, $zero, Loop
CPIideal = 0,5
Loop:
load/store
lw $t0, 0($s1)
addi $s1, $s1, -4
addu $t0, $t0, $s2 nop
nop
bne $s1, $zero, Loop
CPI = ?
sw $t0, 4($s1)
RA.8 2018 v1.0.0
nop
13
Beispiel
Compileroptimierungen
• Loop unrolling: Entfalten von 4 Iterationen der Schleife, um mehr Potential für parallele Instruktionsausführung zu bekommen
• Register renaming: Umbenennen von Registern ($t0 → $t1, $t2, $t3), um unechte Datenabhängigkeiten zu eliminieren
• Statisches Pipelinescheduling: Instruktionen möglichst dicht packen, unter Berücksich- tigung der Datenhängigkeiten und Instruktionslatenzen
ALU/branches load/store
Loop: addi
nop
$s1, $s1, -16
lw $t0, 0($s1)
lw $t1, 12($s1)
lw $t2, 8($s1)
lw $t3, 4($s1)
sw $t0, 16($s1)
sw $t1, 12($s1)
sw $t2, 8($s1)
sw $t3, 4($s1)
addu $t0, $t0, $s2 addu $t1, $t1, $s2
addu $t2, $t2, $s2 addu $t3, $t3, $s2 nop
bne $s1, $zero, Loop
CPI = ?
RA.8 2018 v1.0.0
14
Beispiel
Schleife:
}
Teil des Schleifenrumpfs: (Pseudocode)
for (i=0; i<7; i++) {
b[i] = a[i] + 1;
Compileroptimierungen
load a[i]
add a[i], 1
store b[i]
Die drei Instruktionen im Schleifenrumpf sind abhängig und können deshalb nicht parallel ausgeführt werden
→ Software Pipelining: Umstrukturieren der Schleife, um die Parallelität im Schleifen- rumpf zu erhöhen
RA.8 2018 v1.0.0
15
Compileroptimierungen
Beispiel
0 Iteration:
prologue:
load a[0]
add a[0], 1
load a[1]
ursprüngliche
neue Iteration:
2
3
4
5
6
store b[i]
add a[i+1], 1
load a[i+2]
0
1
1
2
3
4
epilogue:
store b[5]
add a[6], 1
store b[6]
RA.8 2018 v1.0.0
16
Entwurfsraum (CPI x T)
tiefes Pipelining
Mehrfachzuordnung mit tiefem Pipelining
Mehrfachzuordnung mit Pipelining
Mehrzyklen Pipelining
Einzyklen
>1 1 <1 CPI
RA.8 2018 v1.0.0
17
lang
kurz
Taktperiode T
8.3 Parallelität auf Thread-Ebene
• Multithreaded (mehrfädige) Prozessoren
– mehrere Threads werden in einer Pipeline “überlappend” ausgeführt
– Vorteil: mehrere Threads können die Hardware besser auslasten
§ mehr Instruktions-Parallelität insgesamt
§ bei stalls können Instruktionen anderer Threads abgearbeitet werden
– benötigte Hardware
§ die Threads brauchen jeweils eigene Zustände (PCs, Registerfiles, ...)
§ Steuerung muss sehr schnell zwischen den Threads hin- und herschalten können (nicht vergleichbar mit Thread/Prozesswechsel durch das Betriebssystem)
– Multithreading auf einem superskalaren Prozessor bezeichnet man als Simultaneous Multithreading (SMT)
§ Bsp.: Intel Core i7 hat 4 Kerne (cores) mit jeweils 2 Threads
RA.8 2018 v1.0.0
18
Parallelität auf Thread-Ebene
• Multicore/Manycore Prozessoren
– die Threads werden auf unterschiedlichen cores ausgeführt – Terminologie
§ parallel processing: die Threads gehören alle zu einem Programm § request-level processing: die Threads sind unabhängig
• Shared memory Architektur
– die cores sind eng gekoppelt, dh. die Threads kommunizieren und
synchronisieren sich in einem gemeinsamen Adressraum
– eine einzige Betriebssystem-Instanz ist zuständig für alle cores
– zwei Realisierungsformen
§ symmetric multiprocessor (SMP): für single-chip Multiprozessoren
§ distributed shared memory multiprocessor (DSM): Multiprozessoren mit
mehreren Chips
– typische Kommunikationslatenzen
§ 35-50 Taktzyklen zwischen cores auf einem Chip
§ 100-500 Taktzyklen zwischen cores auf verschiedenen Chips
RA.8 2018 v1.0.0
19
Parallelität auf Thread-Ebene
• Symmetrische Multiprozessoren (SMP)
– auch bezeichnet als centralized shared memory multiprocessor
– es gibt einen zentralen Speicher, auf den alle cores gleichberechtigt und mit gleicher Zugriffszeit zugreifen könnenèuniform memory access (UMA)
RA.8 2018 v1.0.0
(lokale Caches)
gemeinsam genutztes Medium (Bus, etc.)
20
Parallelität auf Thread-Ebene
• Distributed shared memory Multiprozessoren (DSM)
– der Speicher ist physikalisch verteilt, sinnvoll für größere Anzahl von Cores /
Prozessoren
– die Zugriffszeit hängt davon ab, wo sich die Daten befindenènon-uniform memory access (NUMA)
RA.8 2018 v1.0.0
21
8.4 Parallelität auf Task/Programm-Ebene
• Multicomputer / Cluster (HPC)
– Computer mit vielen Knoten / Servern, die über ein Netzwerk verbunden sind
– für Anwendung in Science & Engineering (high-performance computing, HPC)
– Bsp. Noctua im PC2 an der UPB:
§ 10’880 Intel Skylake core
§ 52 TB Arbeitsspeicher
§ 720 TByte Paralleler Festplattenspeicher
§ 100 Gbit/s Omni-Path Netzwerk
§ 535 10E12 Floating-point Operationen / Sekunde
RA.8 2018 v1.0.0
22
Parallelität auf Task/Programm-Ebene
• Warehouse-scale Computer (WSC)
– Cluster mit riesiger Anzahl von Servern (typ. 50‘000 – 100‘000), die über ein
Netzwerk verbunden sind
– für Internet-Services (search, social networking, online maps, video sharing, online shopping, email services, ...) und Cloud-Services
RA.8 2018 v1.0.0
23
Parallelität auf Task/Programm-Ebene
• Vergleich HPC vs. WSC
– Preis/Leistungs-Verhältnis (Rechenleistung / $) § für HPC und WSC wichtig
– Energieeffizienz (Rechenleistung / Ws) § für HPC und WSC wichtig
– Zuverlässigkeit (dependability)
§ HPC: Einsatz teurer Komponenten mit hoher Zuverlässigkeit § WSC: Einsatz von günstigen, redundanten Servern
– Netzwerk und I/O
§ HPC: sehr leistungsfähige und teure Netzwerke
§ WSC: günstigere Netzwerke
§ beide benötigen einen sehr schnellen Anschluss nach „außen“ (border router)
– Workload-Characteristik
§ beide müssen interaktive und batch Workloads ausführen
RA.8 2018 v1.0.0
24
Parallelität auf Task/Programm-Ebene
• Vergleich HPC vs. WSC
– Parallelität in den Anwendungen
§ für HPC manchmal eine Herausforderung
§ WSC Anwendungen zeigen viel Parallelität
– interaktive Services haben Millionen unabhängiger user
– batch workloads, z.B. indexing, weisen auch Parallelität auf
– Kosten
§ HPC: früher Betriebskosten oft gegenüber Anschaffungskosten vernachlässigt, heute über Betriebsdauer (4-6J) in der gleichen Grössenordnung wie Anschaffungskosten
§ WSC: Betriebskosten sind ein großer Teil der Gesamtkosten, durch die riesige Anzahl von Knoten können die Anschaffungskosten drastisch gesenkt werden
RA.8 2018 v1.0.0
25
8.5 Weiterführende Veranstaltungen
• Bachelor: Eingebettete Systeme (6 LP) – Wahlpflichtbereich, Sommersemester
– Inhalt
§ Spezifikationsmodelle: Zustands-orientiert, Datenfluss-orientiert
§ Zielarchitekturen: General-Purpose Prozessoren, Digitale
Signalprozessoren, Mikrokontroller, ASIPs, FPGAs und ASICs, Fallstudien
§ Compiler und Codegenerierung: Compilerstruktur, Zwischencode, Codeoptimierung, Codegenerierung für spezialisierte Prozessoren, retargierbare Compiler
§ Software: Cyclic executive, Preemption, Multitasking
§ Hardware: Architektursynthese
§ Performance: Metriken, Worst-Case-Execution Time Analysis
§ Energie: Metriken, Techniken zur Energieminimierung
RA.8 2018 v1.0.0
26
Weiterführende Veranstaltungen
• Master: Advanced Computer Architecture
1. Fundamentals
2. MemoryHierarchyDesign
3. Instruction-levelParallelism:DynamicScheduling,Hardware Speculation, Multiple Issue, Multithreading on Uniprocessors
4. Data-levelParallelism:VectorArchitectures,SIMDExtensions, Graphic Processing Units
5. Thread-levelParallelism:CentralizedandDistributedShared Memory Multiprocessors, Cache Coherency, Synchronization
6. Request-levelParallelism:Wharehouse-scaleComputersfor Internet Services
RA.8 2018 v1.0.0
27
Weiterführende Veranstaltungen
• Vertiefende Veranstaltungen im Master
– High-performance Computing
– Architektur paralleler Rechnersysteme
– Reconfigurable Computing
– Hardware/Software Codesign
– Algorithms for Synthesis and Optimization of Digital Circuits
RA.8 2018 v1.0.0
28
• v1.0.1
– Folie 4 aktualisiert, AXV512
– Folien 26-28 aktualisiert
• v1.0.0
– Aktualisierung für WS 2018/19
– Neue Daten zur Entwicklung der Performance, Taktfrequenz und DRAM Kapazität
RA.8 2018 v1.0.0
Änderungen
29