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], 1store 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öhenRA.8 2018 v1.0.015 CompileroptimierungenBeispiel 0 Iteration:prologue:load a[0]add a[0], 1load a[1]ursprünglicheneue Iteration:23456store b[i]add a[i+1], 1load a[i+2]01123 4 epilogue:store b[5]add a[6], 1store b[6]RA.8 2018 v1.0.016 Entwurfsraum (CPI x T)tiefes PipeliningMehrfachzuordnung mit tiefem Pipelining Mehrfachzuordnung mit PipeliningMehrzyklen Pipelining Einzyklen>1 1 <1 CPIRA.8 2018 v1.0.017langkurzTaktperiode 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.018 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 undsynchronisieren 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 mitmehreren Chips– typische Kommunikationslatenzen§ 35-50 Taktzyklen zwischen cores auf einem Chip§ 100-500 Taktzyklen zwischen cores auf verschiedenen Chips RA.8 2018 v1.0.019 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.021 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 / SekundeRA.8 2018 v1.0.022 Parallelität auf Task/Programm-Ebene• Warehouse-scale Computer (WSC)– Cluster mit riesiger Anzahl von Servern (typ. 50‘000 – 100‘000), die über einNetzwerk verbunden sind– für Internet-Services (search, social networking, online maps, video sharing, online shopping, email services, …) und Cloud-ServicesRA.8 2018 v1.0.023 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ührenRA.8 2018 v1.0.024 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 werdenRA.8 2018 v1.0.025 8.5 Weiterführende Veranstaltungen• Bachelor: Eingebettete Systeme (6 LP) – Wahlpflichtbereich, Sommersemester– Inhalt§ Spezifikationsmodelle: Zustands-orientiert, Datenfluss-orientiert§ Zielarchitekturen: General-Purpose Prozessoren, DigitaleSignalprozessoren, 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.026 Weiterführende Veranstaltungen• Master: Advanced Computer Architecture1. Fundamentals2. MemoryHierarchyDesign3. Instruction-levelParallelism:DynamicScheduling,Hardware Speculation, Multiple Issue, Multithreading on Uniprocessors4. Data-levelParallelism:VectorArchitectures,SIMDExtensions, Graphic Processing Units5. Thread-levelParallelism:CentralizedandDistributedShared Memory Multiprocessors, Cache Coherency, Synchronization6. Request-levelParallelism:Wharehouse-scaleComputersfor Internet Services RA.8 2018 v1.0.027 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.028 • 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ätRA.8 2018 v1.0.0Änderungen 29
Reviews
There are no reviews yet.