MIN-FakultätFachbereich Informatik

64-040 Modul InfB-RS: Rechnerstrukturenhttps://tams.informatik.uni-hamburg.de/

lectures/2018ws/vorlesung/rs

– Kapitel 15 –

Andreas Mäder

Universität HamburgFakultät für Mathematik, Informatik und NaturwissenschaftenFachbereich InformatikTechnische Aspekte Multimodaler Systeme

Wintersemester 2018/2019

A. Mäder 1

Kapitel 1515 Parallelarchitekturen 64-040 Rechnerstrukturen

ParallelarchitekturenMotivationAmdahl’s GesetzSuperskalare RechnerKlassifikationSymmetric MultiprocessingLiteratur

A. Mäder 1091

Motivation: ständig steigende Anforderungen15.1 Parallelarchitekturen - Motivation 64-040 Rechnerstrukturen

I Simulationen, Wettervorhersage, Gentechnologie . . .I Datenbanken, Transaktionssysteme, Suchmaschinen . . .I Softwareentwicklung, Schaltungsentwurf . . .

I Performanz eines einzelnen Prozessors ist begrenzt⇒ Verteilen eines Programms auf mehrere Prozessoren

Vielfältige MöglichkeitenI wie viele und welche Prozessoren?I Kommunikation zwischen den Prozessoren?I Programmierung und Software/Tools?

A. Mäder 1092

Begriffe15.2 Parallelarchitekturen - Amdahl’s Gesetz 64-040 Rechnerstrukturen

I Antwortzeit: die Gesamtzeit zwischen Programmstart und-ende, inklusive I/O-Operationen, Unterbrechungen etc.(„wall clock time“, „response time“, „execution time“)performance = 1

execution time

I Ausführungszeit: reine CPU-ZeitUnix time-Befehl: 597.07u 0.15s 9:57.61 99.9%

597.07 user CPU time [sec.]0.15 system CPU time

9:57.61 elapsed time99.9 CPU/elapsed [%]

I Durchsatz: Anzahl der bearbeiteten Programme / Zeit

I Speedup: s = performance xperformance y = execution time y

execution time x

A. Mäder 1093

Wie kann man Performanz verbessern?15.2 Parallelarchitekturen - Amdahl’s Gesetz 64-040 Rechnerstrukturen

I Ausführungszeit = 〈Anzahl der Befehle〉 · 〈Zeit pro Befehl〉

I weniger BefehleI gute AlgorithmenI bessere CompilerI mächtigere Befehle (CISC)

I weniger Zeit pro BefehlI bessere TechnologieI Architektur: Pipelining, Caches . . .I einfachere Befehle (RISC)

I parallele AusführungI superskalare Architekturen, SIMD, MIMD

A. Mäder 1094

Amdahl’s Gesetz15.2 Parallelarchitekturen - Amdahl’s Gesetz 64-040 Rechnerstrukturen

Möglicher Speedup durch Beschleunigung einer Teilfunktion?1. System berechnet Programm P ,

darin Funktion X mit Anteil 0 < f < 1 der Gesamtzeit2. System berechnet Programm P ,

Funktion X ′ ist schneller als X mit Speedup SX

Amdahl’s Gesetz Gene Amdahl, Architekt der IBM S/360, 1967

I Speedup Sgesamt =1

(1− f ) + f =SX

A. Mäder 1095

Amdahl’s Gesetz (cont.)15.2 Parallelarchitekturen - Amdahl’s Gesetz 64-040 Rechnerstrukturen

Speedup Sgesamt =1

(1− f ) + f =SX

I nur ein Teil f des Gesamtproblems wird beschleunigt

(1-f)

. . .

aktiv

T

ff

parallelisierbarer aktivserieller1 CPU n CPUspotentiell

AnteilAnteil

(f/n)×T(1-f)×T

⇒ möglichst großer Anteil f⇒ Optimierung lohnt nur für relevante Operationen

allgemeingültig: entsprechend auch für Projektplanung, Verkehr . . .

A. Mäder 1096

Amdahl’s Gesetz (cont.)15.2 Parallelarchitekturen - Amdahl’s Gesetz 64-040 Rechnerstrukturen

I ursprüngliche Idee: Parallelrechner mit n-Prozessoren

Speedup Sgesamt =1

(1− f ) + k(n) + f =n

n #Prozessoren als Verbesserungsfaktorf Anteil parallelisierbarer Berechnung1− f Anteil nicht parallelisierbarer Berechnungk() Kommunikationsoverhead zwischen den Prozessoren

I Aufgaben verteilenI Arbeit koordinierenI Ergebnisse zusammensammeln

A. Mäder 1097

Amdahl’s Gesetz: Beispiele15.2 Parallelarchitekturen - Amdahl’s Gesetz 64-040 Rechnerstrukturen

SX f Sgesamt

10 0; 1 1=(0; 9 +0; 01) = 1; 12 0; 5 1=(0; 5 +0; 25) = 1; 332 0; 9 1=(0; 1 +0; 45) = 1; 821; 1 0; 98 1=(0; 02+0; 89) = 1; 14 0; 5 1=(0; 5 +0; 125) = 1; 6

4 536 0; 8 1=(0; 2 +0; 0 : : :) = 5; 09 072 0; 99 1=(0; 01+0; 0 : : :) = 98; 92

I Optimierung bringt nichts, wenn der nicht beschleunigte„serielle“ Anteil (1− f ) eines Programms überwiegt

− n-Prozessoren (große SX) wirken nicht linear− die erreichbare Parallelität in Hochsprachen-Programmen

ist gering, typisch Sgesamt ≤ 4

+ viele Prozesse/Tasks, unabhängig voneinander:Serveranwendungen, virtuelle Maschinen, Container . . .

A. Mäder 1098

Amdahl’s Gesetz: Beispiele (cont.)15.2 Parallelarchitekturen - Amdahl’s Gesetz 64-040 Rechnerstrukturen

0

2

4

6

8

10

0 0.2 0.4 0.6 0.8 1

f

Speedup 1/((1-f)+f/10)

SX = 10

A. Mäder 1099

Amdahl’s Gesetz: Beispiele (cont.)15.2 Parallelarchitekturen - Amdahl’s Gesetz 64-040 Rechnerstrukturen

0

2

4

6

8

10

1 2 3 4 5 6 7 8 9 10

n

Speedup n1/((1-0.9)+0.9/n)1/((1-0.8)+0.8/n)1/((1-0.5)+0.5/n)

A. Mäder 1100

Amdahl’s Gesetz: Beispiele (cont.)15.2 Parallelarchitekturen - Amdahl’s Gesetz 64-040 Rechnerstrukturen

0

20

40

60

80

100

0 0.2 0.4 0.6 0.8 1

f

Speedup 1/(1-f)

SX = ∞

A. Mäder 1101

Befehlspipeline15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

[TA14]

I Befehl in kleinere, schnellere Schritte aufteilen ⇒ höherer TaktI mehrere Instruktionen überlappt ausführen ⇒ höherer Durchsatz

A. Mäder 1102

Parallele Pipelines15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

[TA14]

I im Bild jeweils zwei Operationen pro PipelinestufeI parallele („superskalare“) Ausführung

I komplexe Hardware (Daten- und Kontrollabhängigkeiten)I Beispiel: Pentium

A. Mäder 1103

Superskalarer Prozessor15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

I mehrere Rechenwerke (ALUs)I Verwaltung über „Scoreboard“

Erkennung von Datenabhängigkeiten

I sehr komplexe HardwareI aber gute PerformanzI Beispiel: fast alle x86-Prozessoren

seit Pentium II [TA14]

A. Mäder 1104

Superskalar15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

I Superskalare CPUs besitzen mehrere Recheneinheiten: 4 . . . 10I in jedem Takt werden (dynamisch) mehrere Instruktionen eines

konventionell linearen Instruktionsstroms abgearbeitet⇒ ILP (Instruction Level Parallelism)

I Hardware verteilt initiierte Instruktionen auf RecheneinheitenI pro Takt kann mehr als eine Instruktion initiiert werden

Die Anzahl wird dynamisch von der Hardware bestimmt:0 . . . „Instruction Issue Bandwidth“

+ sehr effizient, alle modernen CPUs sind superskalar− Abhängigkeiten zwischen Instruktionen sind der Engpass,

das Problem der Hazards wird verschärft

A. Mäder 1105

Superskalar – Datenabhängigkeiten15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

DatenabhängigkeitenI RAW – Read After Write

Instruktion Ix darf Datum erst lesen, wenn Ix−n geschrieben hatI WAR – Write After Read

Instruktion Ix darf Datum erst schreiben, wenn Ix−n gelesen hatI WAW – Write After Write

Instruktion Ix darf Datum erst überschreiben, wenn Ix−ngeschrieben hat

Datenabhängigkeiten superskalarer ProzessorenI RAW: echte Abhängigkeit; Forwarding ist kaum möglich und in

superskalaren Pipelines extrem aufwändigI WAR, WAW: „Register Renaming“ als Lösung

A. Mäder 1106

Superskalar – Datenabhängigkeiten (cont.)15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

„Register Renaming“I Hardware löst Datenabhängigkeiten innerhalb der Pipeline aufI zwei Arten von Registersätzen

1. Architektur-Register: „logische Register“ der ISA2. viele Hardware-Register: „Rename Register“I dynamische Abbildung von ISA- auf Hardware-Register

I BeispielI Originalcode nach Renaming

tmp = a + b;res1 = c + tmp;tmp = d + e;res2 = tmp - f;

tmp1 = a + b;res1 = c + tmp1;tmp2 = d + e;res2 = tmp2 - f;tmp = tmp2;

I Parallelisierung des modifizierten Codestmp1 = a + b; tmp2 = d + e;res1 = c + tmp1; res2 = tmp2 - f; tmp = tmp2;

A. Mäder 1107

Superskalar – Pipeline15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

Aufbau der superskalaren Pipeline

I lange Pipelines mit vielen Phasen: Fetch (Prefetch, Predecode),Decode / Register-Renaming, Issue, Dispatch, Execute, Retire(Commit, Complete / Reorder), Write-Back

I je nach Implementation unterschiedlich aufgeteiltI entscheidend für superskalare Architektur sind die Schritte

vor den ALUs: Issue, Dispatch ⇒ out-of-order Ausführungnach -"- : Retire ⇒ in-order Ergebnisse

A. Mäder 1108

Superskalar – Pipeline (cont.)15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

I Dynamisches Scheduling⇒ out-of-order Reihenfolge

der Instruktionen

A. Mäder 1109

Superskalar – Pipeline (cont.)15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

I Issue: globale SichtDispatch: getrennte Ausschnitte in „Reservation Stations“

A. Mäder 1110

Superskalar – Pipeline (cont.)15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

I Reservation Station für jede FunktionseinheitI speichert: initiierte Instruktionen die auf Recheneinheit wartenI –"– zugehörige OperandenI –"– ggf. ZusatzinformationI Instruktion bleibt blockiert, bis alle Parameter bekannt sind und

wird dann an die zugehörige ALU weitergeleitet

I ggf. „Retire“-StufeI Reorder-Buffer: erzeugt wieder in-order ReihenfolgeI commit: „richtig ausgeführte“ Instruktionen gültig machen

abort: Instruktionen verwerfen, z.B. Sprungvorhersage falsch

I Dynamisches Scheduling: zuerst ’67 in IBM360 (R. Tomasulo)I ForwardingI Registerumbenennung und Reservation Stations

A. Mäder 1111

Superskalar – Probleme15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

Spezielle Probleme superskalarer Pipelines− weitere Hazard-Möglichkeiten

I die verschiedenen ALUs haben unterschiedliche LatenzzeitenI Befehle „warten“ in den Reservation Stations⇒ Datenabhängigkeiten können sich mit jedem Takt ändern

− Kontrollflussabhängigkeiten:Anzahl der Instruktionen zwischen bedingten Sprüngenlimitiert Anzahl parallelisierbarer Instruktionen

⇒ „Loop Unrolling“ besonders wichtig+ optimiertes (dynamisches) Scheduling: Faktor 3 möglich

A. Mäder 1112

Superskalar – Probleme (cont.)15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

Softwareunterstützung für Pipelining superskalarer Prozessoren„Software Pipelining“I Codeoptimierungen beim Compilieren als Ersatz/Ergänzung

zur Pipelineunterstützung durch HardwareI Compiler hat „globalen“ Überblick

⇒ zusätzliche Optimierungsmöglichkeiten

A. Mäder 1113

Superskalar – Ausnahmebehandlung15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

Interrupts, System-Calls und ExceptionsI Pipeline kann normalen Ablauf nicht fortsetzenI Ausnahmebehandlung ist wegen der Vielzahl paralleler Aktionen

und den Abhängigkeiten innerhalb der Pipelines extrem aufwändigI einige Anweisungen können verworfen werden− andere Pipelineaktionen müssen vollendet werden

benötigt zusätzliche Zeit bis zur Ausnahmebehandlung− wegen Register-Renaming muss viel mehr Information gerettet

werden als nur die ISA-Register

A. Mäder 1114

Superskalar – Ausnahmebehandlung (cont.)15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

Prinzip der InterruptbehandlungI keine neuen Instruktionen mehr initiierenI warten bis Instruktionen des Reorder-Buffers abgeschlossen sindI Verfahren ist von der „Art“ des Interrupt abhängig

I Precise-Interrupt: Pipelineaktivitäten komplett BeendenI Imprecise-Interrupt: wird als verzögerter Sprung

(Delayed-Branching) in Pipeline eingebrachtZusätzliche Register speichern Information über Instruktionendie in der Pipeline nicht abgearbeitet werden können(z.B. weil sie den Interrupt ausgelöst haben)

I Definition: Precise-InterruptI Programmzähler (PC) zur auslösenden Instruktion ist bekanntI alle Instruktionen bis zur PC-Instr. wurden vollständig ausgeführtI keine Instruktion nach der PC-Instr. wurde ausgeführtI Ausführungszustand der PC-Instruktion ist bekannt

A. Mäder 1115

Beispiel: Pentium 4 / NetBurst Architektur15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

I superskalare Architektur (mehrere ALUs)I CISC-Befehle werden dynamisch in „—OPs“ (1 . . . 3) umgesetztI Ausführung der —OPs mit „Out of Order“ Maschine, wenn

I Operanden verfügbar sindI funktionelle Einheit (ALU) frei ist

I Ausführung wird durch „Reservation Stations“ kontrolliertI beobachtet die Datenabhängigkeiten zwischen —OPsI teilt Ressourcen zu

I „Trace“ CacheI ersetzt traditionellen AnweisungscacheI speichert Anweisungen in decodierter Form: Folgen von —OPsI reduziert benötigte Rate für den Anweisungsdecoder

I „Double pumped“ ALUs (2 Operationen pro Taktzyklus)

A. Mäder 1116

Beispiel: Pentium 4 / NetBurst Architektur (cont.)15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

I große Pipelinelänge ⇒ sehr hohe Taktfrequenzen

1 2 3 4 5 6 7 8 9 010

tFetch F cFetch Decode D cDecode DDecode naRename ROB Rd Rdy/ h/Sch pa cDispatch Exec

asic Penti II Pr ce sor Basic Pentium III Processor is dic ionMisprediction Pi lin Pipeline

B s Pe tium Proc ss r Basic Pentium 4 Processor i pr d tionMisprediction pe e Pipeline

1 2 3 4 55 6 7 8 99 10 11 12

TC Nxt PIP tTC Fetch vDrive lAlloc Rename Que Sch Sch Sch

13 14

D pDisp Disp

15 616 117 118 19 20

RF Ex Flgs kBr Ck D iv Drive RF

I umfangreiches Material von Intel unter:ark.intel.com, www.intel.com

A. Mäder 1117

Beispiel: Pentium 4 / NetBurst Architektur (cont.)15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

A o o / er RenAllocator / Register Renamer

M o Memory uuop u Queue n g F atin Po t Integer/Floating Point p uop Queue

Reg / B p sFP Register / Bypass

FP

XMMX

SSSE

E2SSE2

PFP

veMove

Simple FP

ata ( byte 4-wL1 Data Cache (8Kbyte 4-way)

Memory Scheduler Fast Slow/General FP Scheduler

e i r Integer Register File / Bypass Network

mp xComplex

nstr.Instr.

S w LSlow ALU

i eSimple

Instr.

2 A2x ALU

eSimple

n tInstr.

2 A2x ALU

aLoad

Address

AAGU

S rStore

dAddress

A UAGU

2 6 bit256 bits

6 - s wide64-bits wide

Q adQuad

mpePumped

3 2 /3.2 GB/s

uBus

f eInterface

Unit

S s eSystem

BusBus

2 hL2 Cache

(256K Byte(256K Byte

8-way8-way)

448GB/s

I stru t oInstruction

LTLB/PrefetchPrefetchern Front-End BTB

(4 (4K Entries)

n i n De dInstruction Decoder

T ce chTrace Cache

1 (12K µµ pops)T C he BTTrace Cache BTB

( 12 n(512 Entries)

r c dMicrocode

RROM

µoop Q e e Queue

Figure 4: Pentium

® 4 processor microarchitecture Intel: Q1, 2001 [Intel]

A. Mäder 1118

Beispiel: Core 2 Architektur15.3 Parallelarchitekturen - Superskalare Rechner 64-040 Rechnerstrukturen

128 Entry ITLB

32 KB Instruction Cache(8 way)

32 Byte Pre-Decode, Fetch Buffer

InstructionFetch Unit

18 Entry Instruction Queue

7+ Entry µop Buffer

Register Alias Table and Allocator

96 Entry Reorder Buffer (ROB)Retirement Register File(Program Visible State)

Shared Bus Interface

Unit

Shared L2 Cache(16 way)

256 EntryL2 DTLB

Micro-code

ComplexDecoder

SimpleDecoder

SimpleDecoder

SimpleDecoder

32 Entry Reservation Station

ALU ALUSSE

ShuffleALU

SSEShuffleMUL

ALUBranch

SSEALU

128 BitFMULFDIV

128 BitFADD

StoreAddress

StoreData

LoadAddress

Memory Ordering Buffer(MOB)

32 KB Dual Ported Data Cache(8 way)

16 Entry DTLB

Port 0 Port 1 Port 2Port 3 Port 4Port 5

Internal Results BusLoadStore

128 Bit128 Bit

4 µops

4 µops

4 µops

4 µops 1 µop 1 µop 1 µop

128 Bit

6 Instructions

4 µops

256 Bit

Intel Core 2 Architecture

A. Mäder 1119

Parallelrechner mit mehreren Prozessoren15.4 Parallelarchitekturen - Klassifikation 64-040 Rechnerstrukturen

I Taktfrequenzen > 10GHz nicht sinnvoll realisierbarI hoher Takt nur bei einfacher Hardware möglichI Stromverbrauch bei CMOS proportional zum Takt

⇒ mehrere ProzessorenDatenaustausch: „Shared-memory“ oder Verbindungsnetzwerk

− Overhead durch Kommunikation− Programmierung ist ungelöstes ProblemI aktueller Kompromiss: bus-basierte „SMPs“ mit 2 . . . 16 CPUs

A. Mäder 1120

Flynn-Klassifikation15.4 Parallelarchitekturen - Klassifikation 64-040 Rechnerstrukturen

SISD „Single Instruction, Single Data“I jeder klassische von-Neumann Rechner (z.B. PC)

SIMD „Single Instruction, Multiple Data“I Vektorrecher/Feldrechner

z.B. Connection-Machine 2: 65 536 ProzessorenI Erweiterungen in Befehlssätzen: superskalare

Recheneinheiten werden direkt angesprochenz.B. x86 MMX, SSE, VLIW-Befehle: 2 . . . 8 fach parallel

MIMD „Multiple Instruction, Multiple Data“I Multiprozessormaschinen

z.B. Compute-Cluster, aber auch Multi-Core CPUMISD „Multiple Instruction, Single Data“ :-)

A. Mäder 1121

Detaillierte Klassifikation15.4 Parallelarchitekturen - Klassifikation 64-040 Rechnerstrukturen

MIMD

parallele Rechnerarchitektur

Multi-Computer

SISD SIMD

Gitter Hyper-würfel

MPPCOW

Multi-prozessoren

UMA COMA

Bus Switch CC-NUMA NC-NUMA

NUMA

gemeinsamer Speicher Nachrichtenaustausch

Vektor-prozessor

Array-prozessor

MISD

[TA14]

A. Mäder 1122

SIMD: Vektorrechner Cray-1 (1976)legendärer „Supercomputer“15.4 Parallelarchitekturen - Klassifikation 64-040 Rechnerstrukturen

I Prinzip: Anwendung eines Rechen-Befehls auf alle Elementevon Vektoren/Matrizen

I Adressberechnung mit „Stride“I „Chaining“ von VektorbefehlenI schnelle skalare BefehleI ECL-Technologie, Freon-KühlungI 1662 Platinen (Module),

über Kabel verbundenI 80MHz Takt, 136MFLOPS

A. Mäder 1123

SIMD: Feldrechner Illiac-IV (1964 . . . 1976)15.4 Parallelarchitekturen - Klassifikation 64-040 Rechnerstrukturen

[Tan06]

I ein zentraler SteuerprozessorI 64 Prozessoren/ALUs und Speicher, 8× 8 MatrixI Befehl wird parallel auf allen Rechenwerken ausgeführtI aufwändige und teure ProgrammierungI oft schlechte Auslastung (Parallelität Algorithmus vs. #CPUs)

A. Mäder 1124

MIMD: Konzept15.4 Parallelarchitekturen - Klassifikation 64-040 Rechnerstrukturen

[TA14]

I mehrere Prozessoren, über Bus/Netzwerk verbundenI gemeinsamer („shared“) oder lokaler SpeicherI unabhängige oder parallele Programme / MultithreadingI sehr flexibel, zunehmender Markterfolg

A. Mäder 1125

MIMD: Shared-Memory15.4 Parallelarchitekturen - Klassifikation 64-040 Rechnerstrukturen

[TA14]

I mehrere CPUs, aber gemeinsamer SpeicherI jede CPU bearbeitet nur eine TeilaufgabeI CPUs kommunizieren über den gemeinsamen SpeicherI Zuordnung von Teilaufgaben/Speicherbereichen zu CPUs

A. Mäder 1126

MIMD: Message-Passing15.4 Parallelarchitekturen - Klassifikation 64-040 Rechnerstrukturen

[TA14]

I jede CPU verfügt über eigenen (privaten) SpeicherI Kommunikation über ein VerbindungsnetzwerkI Zugriff auf Daten anderer CPUs evtl. recht langsam

A. Mäder 1127

Verbindungs-Netzwerke15.4 Parallelarchitekturen - Klassifikation 64-040 Rechnerstrukturen

[TA14]

A. Mäder 1128

Verbindungs-Netzwerke (cont.)15.4 Parallelarchitekturen - Klassifikation 64-040 Rechnerstrukturen

[TA14]

A. Mäder 1129

Kreuzschienenverteiler („Crossbar Switch“)15.4 Parallelarchitekturen - Klassifikation 64-040 Rechnerstrukturen

[TA14]

I jede CPU kann auf jeden Speicher zugreifenI hoher Hardwareaufwand: O(n2) Schalter und VerbindungenI Konflikte bei gleichzeitigem Zugriff auf einen Speicher

A. Mäder 1130

Omega-Netzwerk15.4 Parallelarchitekturen - Klassifikation 64-040 Rechnerstrukturen

[TA14]

I Schalter „gerade“ oder „gekreuzt“:I jede CPU kann auf jeden Speicher zugreifenI aber nur bestimmte Muster, Hardwareaufwand O(n · ln n)

A. Mäder 1131

Skalierbarkeit15.4 Parallelarchitekturen - Klassifikation 64-040 Rechnerstrukturen

[TA14]

Wie viele CPUs kann man an ein System anschliessen?I Bus: alle CPUs teilen sich die verfügbare Bandbreite⇒ daher normalerweise nur 2 . . . 8 CPUs sinnvoll

I Gitter: verfügbare Bandbreite wächst mit Anzahl der CPUs

A. Mäder 1132

Speedup15.4 Parallelarchitekturen - Klassifikation 64-040 Rechnerstrukturen

[TA14]

I Maß für die Effizienz einer Architektur / eines Algorithmus’I wegen Amdahl’s Gesetz maximal linearer ZuwachsI je nach Problem oft wesentlich schlechter

A. Mäder 1133

Parallelarchitekturen – Anmerkungen15.4 Parallelarchitekturen - Klassifikation 64-040 Rechnerstrukturen

I Programmierung: ein ungelöstes ProblemI Aufteilung eines Programms auf die CPUs/Rechenknoten?I insbesondere bei komplexen Kommunikationsnetzwerken

I Programme sind nur teilweise parallelisierbarI Parallelität einzelner Programme: kleiner 8

gilt für Desktop-, Server-, Datenbankanwendungen etc.⇒ hochgradig parallele Rechner sind dann Verschwendung

I Wohin mit den Transistoren aus „Moore’s Law“?⇒ SMP-/Mehrkern-CPUs (4 . . . 32 Proz.) sind technisch attraktiv

I Vektor-/Feld-Rechner für Numerik, Simulation . . .I Grafikprozessoren (GPUs) sind Feld-RechnerI neben 3D-Grafik zunehmender Computing-Einsatz (OpenCL)I hohe Fließkomma-Rechenleistung (single precision)

A. Mäder 1134

SMP: Symmetric Multiprocessing15.5 Parallelarchitekturen - Symmetric Multiprocessing 64-040 Rechnerstrukturen

I mehrere Prozessoren nutzen gemeinsamen HauptspeicherI Zugriff über Verbindungsnetzwerk oder BusI geringer Kommunikationsoverhead+ Bus-basierte Systeme sind sehr kostengünstig− aber schlecht skalierbar (Bus als Flaschenhals, s.o.)− Konsistenz der Daten

I lokale Caches für gute Performanz notwendigI Hauptspeicher und Cache(s): Cache-Kohärenz

MESI-Protokoll und „Snooping“ 18-Kern Xeon E7 v3 [Intel]

→ siehe Kapitel „16 Speicherhierarchie“I Registerinhalte: ? problematisch

− Prozesse wechseln CPUs: „Hopping“I Multi-Core Prozessoren sind „SMP on-a-chip“

A. Mäder 1135

SMP: Eigenschaften15.5 Parallelarchitekturen - Symmetric Multiprocessing 64-040 Rechnerstrukturen

Symmetric MultiprocessingI alle CPUs gleichrangig, Zugriff auf Speicher und I/OI Konsistenz: Gleichzeitiger Zugriff auf eine Speicheradresse?

P1

P2

P3

P4

read

write 200

write 100

read

read

CPUsMemory W1→ 100 W1→ 100 W2→ 200

W2→ 200 R3 ← 100 R4 ← 200R3 ← 200 W2→ 200 R3 ← 200R3 ← 200 R3 ← 200 W1→ 100R4 ← 200 R4 ← 200 R3 ← 100

⇒ „Locking“ Mechanismen und MutexeI spez. Befehle, atomare Operationen, Semaphore etc.I explizit im Code zu programmieren

A. Mäder 1136

SMP: Cache-Kohärenz15.5 Parallelarchitekturen - Symmetric Multiprocessing 64-040 Rechnerstrukturen

Cache für schnelle Prozessoren notwendigI jede CPU hat eigene Cache (L1, L2 . . . )I aber gemeinsamer Hauptspeicher

Problem der Cache-KohärenzI Prozessor P2 greift auf Daten zu, die im Cache von P1 liegen

I P2 Lesezugriff: P1 muss seinen Wert P2 liefernI P2 Schreibzugriff: P1 muss Wert von P2 übernehmen

oder seinen Cache ungültig machenI Was ist mit gleichzeitigen Zugriffen von P1, P2?

I diverse Protokolle zur Cache-Kohärenz→ siehe Kapitel „16 Speicherhierarchie“I z.B. MESI-Protokoll mit „Snooping“

Modified, Exclusive, Shared, InvalidI Caches enthalten Wert, Tag und 2 bit MESI-Zustand

A. Mäder 1137

SMP: volatile15.5 Parallelarchitekturen - Symmetric Multiprocessing 64-040 Rechnerstrukturen

I MESI-Verfahren garantiert Cache-Kohärenzfür Werte im Cache und im Hauptspeicher

Vorsicht: Was ist mit den Registern?I Variablen in Registern werden von MESI nicht erkanntI Compiler versucht, häufig benutzte Variablen soweit wie

möglich in Registern zu haltenI globale/shared-Variablen niemals in Registern haltenI Java, C: Deklaration als volatile

A. Mäder 1138

SMP: Erreichbarer Speedup (bis 32 Threads)15.5 Parallelarchitekturen - Symmetric Multiprocessing 64-040 Rechnerstrukturen

Figure 4. Maximum speedup achieved on up to 32 threads over single-

threaded execution (black bars) and minimum number of threads at which

the maximum speedup occurred (gray bars).

M.J .Bridges et.al.: Revisiting the Sequential Programming Model for the Multicore Era, IEEE Micro 2008 [Br+08]A. Mäder 1139

Literatur15.6 Parallelarchitekturen - Literatur 64-040 Rechnerstrukturen

[TA14] A.S. Tanenbaum, T. Austin: Rechnerarchitektur –Von der digitalen Logik zum Parallelrechner.6. Auflage, Pearson Deutschland GmbH, 2014.ISBN 978–3–8689–4238–5

[Tan06] A.S. Tanenbaum:Computerarchitektur – Strukturen, Konzepte, Grundlagen.5. Auflage, Pearson Studium, 2006. ISBN 3–8273–7151–1

[Intel] Intel Corp.; Santa Clara, CA.www.intel.com ark.intel.com

[HP17] J.L. Hennessy, D.A. Patterson:Computer architecture – A quantitative approach.6th edition, Morgan Kaufmann Publishers Inc., 2017.ISBN 978–0–12–811905–1

A. Mäder 1140

Literatur (cont.)15.6 Parallelarchitekturen - Literatur 64-040 Rechnerstrukturen

[PH17] D.A. Patterson, J.L. Hennessy: Computer Organizationand Design – The Hardware Software Interface – RISC-VEdition.Morgan Kaufmann Publishers Inc., 2017.ISBN 978–0–12–812275–4

[PH16b] D.A. Patterson, J.L. Hennessy: Rechnerorganisationund Rechnerentwurf – Die Hardware/Software-Schnittstelle.5. Auflage, Oldenbourg, 2016. ISBN 978–3–11–044605–0

[Br+08] M.J. Bridges [u. a.]: Revisiting the SequentialProgramming Model for the Multicore Era.in: IEEE Micro 1 Vol. 28 (2008), S. 12–20.

A. Mäder 1141