64-040- Modul IP7: Rechnerstrukturen - uni-hamburg.de · UniversitätHamburg MIN-Fakultät FachbereichInformatik Computerarchitektur-SequenzielleBefehlsabarbeitung 64-040Rechnerstrukturen

Universität Hamburg

MIN-FakultätFachbereich Informatik

64-040 Rechnerstrukturen

64-040 Modul IP7: Rechnerstrukturenhttp://tams.informatik.uni-hamburg.de/

lectures/2011ws/vorlesung/rs

Kapitel 20

Andreas Mäder

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

Wintersemester 2011/2012

A. Mäder 1

http://tams.informatik.uni-hamburg.de/lectures/2011ws/vorlesung/rs

http://tams.informatik.uni-hamburg.de/lectures/2011ws/vorlesung/rs



Computerarchitektur 64-040 Rechnerstrukturen

Kapitel 20Computerarchitektur

Befehlssätze / ISASequenzielle BefehlsabarbeitungPipeliningSuperskalare ProzessorenBeispiele

A. Mäder 2



Computerarchitektur - Befehlssätze / ISA 64-040 Rechnerstrukturen

Bewertung der ISA

Kriterien für einen guten BefehlssatzI vollständig: alle notwendigen Instruktionen verfügbarI orthogonal: keine zwei Instruktionen leisten das GleicheI symmetrisch: z.B. Addition ⇔ SubtraktionI adäquat: technischer Aufwand entsprechend zum NutzenI effizient: kurze AusführungszeitenStatistiken zeigen: Dominanz der einfachen Instruktionen

A. Mäder 3




Bewertung der ISA (cont.)I x86-Prozessor

Anweisung Ausführungshäufigkeit%1. load 22%2. conditional branch 20%3. compare 16%4. store 12%5. add 8%6. and 6%7. sub 5%8. move reg-reg 4%9. call 1%10. return 1%Total 96%

A. Mäder 4




Bewertung der ISA (cont.)nInstruction compress eqntott espresso gcc (cc1) li Int. average

load 20.8% 18.5% 21.9% 24.9% 23.3% 22%

store 13.8% 3.2% 8.3% 16.6% 18.7% 12%

add 10.3% 8.8% 8.15% 7.6% 6.1% 8%

sub 7.0% 10.6% 3.5% 2.9% 3.6% 5%

mul 0.1% 0%

div 0%

compare 8.2% 27.7% 15.3% 13.5% 7.7% 16%

mov reg-reg 7.9% 0.6% 5.0% 4.2% 7.8% 4%

load imm 0.5% 0.2% 0.6% 0.4% 0%

cond. branch 15.5% 28.6% 18.9% 17.4% 15.4% 20%

uncond. branch 1.2% 0.2% 0.9% 2.2% 2.2% 1%

call 0.5% 0.4% 0.7% 1.5% 3.2% 1%

return, jmp indirect 0.5% 0.4% 0.7% 1.5% 3.2% 1%

shift 3.8% 2.5% 1.7% 1%

and 8.4% 1.0% 8.7% 4.5% 8.4% 6%

or 0.6% 2.7% 0.4% 0.4% 1%

other (xor, not, . . .) 0.9% 2.2% 0.1% 1%

load FP 0%

store FP 0%

add FP 0%

sub FP 0%

mul FP 0%

div FP 0%

compare FP 0%

mov reg-reg FP 0%

other (abs, sqrt, . . .) 0%

Figure D.15 80x86 instruction mix for five SPECint92 programs.

A. Mäder 5




Bewertung der ISA (cont.)I MIPS-Prozessor

0 % 5 % 10% 15% 20% 25% 30% 35% 40%

load

and /o r / xo r

add/sub

cond branch

store

compare

cal l / return gap gcc gzip mcf perl

37%

12%

10%

5 %

13%

16%

3 %

0 % 5 % 10% 15% 20% 25% 30% 35% 40%

load int

add/sub int

load FP

add/sub FP

mul FP

store FP

cond branch

and /o r / xo r

compare int

store int applu a r t equake lucas swim

26%

15%

20%

10%

8 %

7 %

4 %

4 %

2 %

2 %

SPECint2000 (96%) SPECfp2000 (97%)

A. Mäder 6




Bewertung der ISA (cont.)I ca. 80% der Berechnungen eines typischen Programms

verwenden nur ca. 20% der Instruktionen einer CPUI am häufigsten gebrauchten Instruktionen sind einfache

Instruktionen: load, store, add. . .⇒ Motivation für RISC

A. Mäder 7




CISC – Befehlssätze

Complex Instruction Set ComputerI aus der Zeit der ersten Großrechner, 60er JahreI Programmierung auf AssemblerebeneI Komplexität durch sehr viele (mächtige) Befehle umgehenCISC BefehlssätzeI Instruktionssätze mit mehreren hundert Befehlen (> 300)I sehr viele Adressierungsarten, -KombinationenI verschiedene, unterschiedlich lange InstruktionsformateI fast alle Befehle können auf Speicher zugreifen

I mehrere Schreib- und Lesezugriffe pro BefehlI komplexe Adressberechnung

A. Mäder 8




CISC – Befehlssätze (cont.)I Stack-orientierter Befehlssatz

I Übergabe von ArgumentenI Speichern des ProgrammzählersI explizite „Push“ und „Pop“ Anweisungen

I Zustandscodes („Flags“)I gesetzt durch arithmetische und logische Anweisungen

Konsequenzen+ nah an der Programmiersprache, einfacher Assembler+ kompakter Code: weniger Befehle holen, kleiner I-Cache− Pipelining schwierig− Ausführungszeit abhängig von: Befehl, Adressmodi. . .− Instruktion holen schwierig, da variables Instruktionsformat− Speicherhierarchie schwer handhabbar: Adressmodi

A. Mäder 9




CISC – Mikroprogrammierung

I ein Befehl kann nicht in einem Takt abgearbeitet werden⇒ Unterteilung in Mikroinstruktionen (∅ 5. . . 7)

I Ablaufsteuerung durch endlichen AutomatenI meist als ROM (RAM) implementiert, das

Mikroprogrammworte beinhaltet

1. horizontale MikroprogrammierungI langes Mikroprogrammwort (ROM-Zeile)I steuert direkt alle OperationenI Spalten entsprechen: Kontrollleitungen und Folgeadressen

A. Mäder 10




CISC – Mikroprogrammierung (cont.)

2. vertikale MikroprogrammierungI kurze MikroprogrammworteI Spalten enthalten MikrooperationscodeI mehrstufige Decodierung für Kontrollleitungen

+ CISC-Befehlssatz mit wenigen Mikrobefehlen realisieren+ bei RAM: Mikrobefehlssatz austauschbar− (mehrstufige) ROM/RAM Zugriffe: zeitaufwändig

I horizontale Mikroprog. vertikale Mikroprog.

A. Mäder 11




horizontale Mikroprogrammierung

MikroprogrammierungA. Mäder 12




vertikale Mikroprogrammierung

Mikroprogrammierung

A. Mäder 13




RISC – Befehlssätze

Reduced Instruction Set ComputerI Grundidee: Komplexitätsreduktion in der CPUI internes Projekt bei IBM, seit den 80er Jahren: „RISC-Boom“

I von Hennessy (Stanford) und Patterson (Berkeley) publiziertI Hochsprachen und optimierende Compiler⇒ kein Bedarf mehr für mächtige Assemblerbefehle⇒ pro Assemblerbefehl muss nicht mehr „möglichst viel“ lokal

in der CPU gerechnet werden (CISC Mikroprogramm)

A. Mäder 14




RISC – Befehlssätze (cont.)

RISC BefehlssätzeI reduzierte Anzahl einfacher Instruktionen (z.B. 128)

I benötigen in der Regel mehr Anweisungen für eine AufgabeI werden aber mit kleiner, schneller Hardware ausgeführt

I Register-orientierter BefehlssatzI viele Register (üblicherweise ≥ 32)I Register für Argumente, „Return“-Adressen, Zwischenergebnisse

I Speicherzugriff nur durch „Load“ und „Store“ AnweisungenI alle anderen Operationen arbeiten auf RegisternI keine Zustandscodes (Flag-Register)

I Testanweisungen speichern Resultat direkt im Register

A. Mäder 15




RISC – Befehlssätze (cont.)

Konsequenzen+ fest-verdrahtete Logik, kein Mikroprogramm+ einfache Instruktionen, wenige Adressierungsarten+ Pipelining gut möglich+ Cycles per Instruction = 1

in Verbindung mit Pipelining: je Takt (mind.) ein neuer Befehl− längerer Maschinencode− viele Register notwendigI optimierende Compiler nötig / möglichI High-performance Speicherhierarchie notwendig

A. Mäder 16




CISC vs. RISC

ursprüngliche DebatteI streng geteilte LagerI pro CISC: einfach für den Compiler; weniger Code BytesI pro RISC: besser für optimierende Compiler;

schnelle Abarbeitung auf einfacher Hardwareaktueller StandI Grenzen verwischen

I RISC-Prozessoren werden komplexerI CISC-Prozessoren weisen RISC-Konzepte oder gar RISC-Kern auf

I für Desktop Prozessoren ist die Wahl der ISA kein ThemaI Code-Kompatibilität ist sehr wichtig!I mit genügend Hardware wird alles schnell ausgeführt

I eingebettete Prozessoren: eindeutige RISC-Orientierung+ kleiner, billiger, weniger Leistungsverbrauch

A. Mäder 17




ISA Design heute

I Restriktionen durch Hardware abgeschwächtI Code-Kompatibilität leichter zu erfüllen

I Emulation in Firm- und HardwareI Intel bewegt sich weg von IA-32

I erlaubt nicht genug ParallelitätI hat IA-64 eingeführt („Intel Architecture 64-bit“)⇒ neuer Befehlssatz mit expliziter Parallelität (EPIC)⇒ 64-bit Wortgrößen (überwinden Adressraumlimits)⇒ benötigt hoch entwickelte Compiler

A. Mäder 18



Computerarchitektur - Sequenzielle Befehlsabarbeitung 64-040 Rechnerstrukturen

Sequenzielle Hardwarestruktur

I interner Zustand

Instructionmemory

PCincrement

CC ALU

Datamemory

Fetch

Decode

Execute

Memory

Write back

icode ifunrA , rB

valC

Registerfile

A BM

E

Registerfile

A BM

E

PC

valP

srcA, srcBdstA, dstB

valA, valB

aluA, aluB

Bch

valE

Addr, Data

valM

PCvalE, valM

newPC

I Programmzähler Register PCI Zustandscode Register CCI RegisterbankI Speicher

I gemeinsamer Speicherfür Daten und Anweisungen

I von-Neumann AbarbeitungI Befehl aus Speicher laden

PC enthält AdresseI Verarbeitung durch die StufenI Programmzähler aktualisieren

A. Mäder 19



Computerarchitektur - Sequenzielle Befehlsabarbeitung 64-040 Rechnerstrukturen

Sequenzielle Befehlsabarbeitung

I Befehl holen „Fetch“

Instructionmemory

PCincrement

CC ALU

Datamemory

Fetch

Decode

Execute

Memory

Write back

icode ifunrA , rB

valC

Registerfile

A BM

E

Registerfile

A BM

E

PC

valP


valA, valB

aluA, aluB

Bch

valE

Addr, Data

valM

PCvalE, valM

newPC

I Anweisung aus Speicher lesenI Befehl decodieren „Decode“

I Befehlsregister interpretierenI Operanden holen

I Befehl ausführen „Execute“I berechne Wert oder Adresse

I Speicherzugriff „Memory“I Daten lesen oder schreiben

I Registerzugriff „Write Back“I in Registerbank schreiben

I Programmzähler aktualisierenI inkrementieren –oder–I Speicher-/Registerinhalt bei Sprung

A. Mäder 20



Computerarchitektur - Pipelining 64-040 Rechnerstrukturen

Pipelining / Fließbandverarbeitung

GrundideeI Operation F kann in Teilschritte zerlegt werdenI jeder Teilschritt fi braucht ähnlich viel ZeitI alle Teilschritte fi können parallel zueinander ausgeführt werdenI Trennung der Pipelinestufen („stage“) durch RegisterI Zeitbedarf für Teilschritt fi � Zugriffszeit auf Register (tco)

A. Mäder 21




Pipelining / Fließbandverarbeitung (cont.)

Pipelining-KonzeptI Prozess in unabhängige Abschnitte aufteilenI Objekt sequenziell durch diese Abschnitte laufen lassenI zu jedem gegebenen Zeitpunkt werden zahlreiche Objekte

bearbeitetKonsequenzI lässt Vorgänge gleichzeitig ablaufenI „Real-World Pipelines“: Autowaschanlagen

A. Mäder 22




Pipelining / Fließbandverarbeitung (cont.)

Arithmetische PipelinesI Idee: lange Berechnung in Teilschritte zerlegen

wichtig bei komplizierteren arithmetischen OperationenI die sonst sehr lange dauern (weil ein großes Schaltnetz)I die als Schaltnetz extrem viel Hardwareaufwand erfordernI Beispiele: Multiplikation, Division, Fließkommaoperationen. . .

+ Erhöhung des Durchsatzes, wenn Berechnung mehrfachhintereinander ausgeführt wird

(RISC) ProzessorpipelinesI Idee: die Phasen der von-Neumann Befehlsabarbeitung

(Befehl holen, Befehl decodieren . . . ) als Pipeline implementieren

A. Mäder 23




Berechnungsbeispiel: ohne Pipeline

Combinationallogic

Reg

300 ps 20 ps

Clock

Delay = 320 psThroughput = 3.12 GOPS

SystemI Verarbeitung erfordert 300 psI weitere 20 ps um das Resultat im Register zu speichernI Zykluszeit: mindestens 320 ps

A. Mäder 24




Berechnungsbeispiel: Version mit 3-stufiger Pipeline

Reg

Clock

Comb.logic

A

Reg

Comb.logic

B

Reg

Comb.logic

C

100 ps 20 ps 100 ps 20 ps 100 ps 20 ps


SystemI Kombinatorische Logik in 3 Blöcke zu je 100 ps aufgeteiltI neue Operation, sobald vorheriger Abschnitt durchlaufen wurde⇒ alle 120 ps neue Operation

I allgemeine Latenzzunahme⇒ 360 ps von Start bis Ende

A. Mäder 25




Funktionsweise der Pipeline

I ohne Pipeline

Time

OP1OP2OP3

I 3-stufige Pipeline

Time

A B CA B C

A B C

OP1OP2OP3

A. Mäder 26




Beispiel: 3-stufige Pipeline

Time

OP1OP2OP3

A B CA B C

A B C

0 120 240 360 480 640

Clock

Reg

Clock

Comb.logic

A

Reg

Comb.logic

B

Reg

Comb.logic

C

100 ps 20 ps 100 ps 20 ps 100 ps 20 ps

239

A. Mäder 27





Time

OP1OP2OP3

A B CA B C

A B C

0 120 240 360 480 640

Clock

Reg

Clock

Comb.logic

A

Reg

Comb.logic

B

Reg

Comb.logic

C

100 ps 20 ps 100 ps 20 ps 100 ps 20 ps

241

A. Mäder 27





Time

OP1OP2OP3

A B CA B C

A B C

0 120 240 360 480 640

Clock

Reg

Reg

Reg

100 ps 20 ps 100 ps 20 ps 100 ps 20 ps

Comb.logic

A

Comb.logic

B

Comb.logic

C

Clock

300

A. Mäder 27





Time

OP1OP2OP3

A B CA B C

A B C

0 120 240 360 480 640

Clock

Reg

Clock

Comb.logic

A

Reg

Comb.logic

B

Reg

Comb.logic

C

100 ps 20 ps 100 ps 20 ps 100 ps 20 ps

359

A. Mäder 27




Probleme: nicht uniforme Verzögerungen

Reg

Clock

Reg

Comb.logic

B

Reg

Comb.logic

C

50 ps 20 ps 150 ps 20 ps 100 ps 20 ps


Comb.logicA

Time

OP1OP2OP3

A B CA B C

A B C

I größte Verzögerung bestimmt Taktfrequenz

A. Mäder 28




Probleme: Register „Overhead“

Delay = 420 ps, Throughput = 14.29 GOPSClock

Reg

Comb.logic

50 ps 20 ps

Reg

Comb.logic

50 ps 20 ps

Reg

Comb.logic

50 ps 20 ps

Reg

Comb.logic

50 ps 20 ps

Reg

Comb.logic

50 ps 20 ps

Reg

Comb.logic

50 ps 20 ps

I registerbedingter Overhead wächst mit PipelinelängeI (anteilige) Taktzeit für das Laden der Register

Overhead Taktperiode1-Register: 6,25% 20 ps 320 ps3-Register: 16,67% 20 ps 120 ps6-Register: 28,57% 20 ps 70 ps

A. Mäder 29




Probleme: Datenabhängigkeiten / „Daten Hazards“

Clock

Combinationallogic

Reg

Time

OP1OP2OP3

I jede Operation hängt vom Ergebnis der Vorhergehenden ab

A. Mäder 30




Probleme: Datenabhängigkeiten / „Daten Hazards“ (cont.)

Reg

Clock

Comb.logic

A

Reg

Comb.logic

B

Reg

Comb.logic

C

Time

OP1OP2OP3

A B CA B C

A B COP4 A B C

⇒ Resultat-Feedback kommt zu spät für die nächste Operation⇒ Pipelining ändert Verhalten des gesamten Systems

A. Mäder 31




RISC Pipelining

Schritte der RISC Befehlsabarbeitung (von ISA abhängig)I IF Instruction Fetch

Instruktion holen, in Befehlsregister ladenID Instruction Decode

Instruktion decodierenOF Operand Fetch

Operanden aus Registern holenEX Execute

ALU führt Befehl ausMEM Memory access

Speicherzugriff bei Load-/Store-BefehlenWB Write Back

Ergebnisse in Register zurückschreibenA. Mäder 32




RISC Pipelining (cont.)I je nach Instruktion sind 3-5 dieser Schritte notwendigI Beispiel ohne Pipelining:

Patterson, Hennessy, Computer Organization and Design

A. Mäder 33




RISC Pipelining (cont.)

Pipelining in ProzessorenI Beispiel mit Pipelining:

Patterson, Hennessy, Computer Organization and Design

I Befehle überlappend ausführenI Register trennen Pipelinestufen

A. Mäder 34




RISC Pipelining (cont.)I RISC ISA: Pipelining wird direkt umgesetzt

WBMEMEXIDIF

Pipelinestufen21 3 4 5

I MIPS-Architektur (aus Patterson, Hennessy)MIPS ohne Pipeline MIPS Pipeline Pipeline Schema

I Bryant, O’Hallaron, Computer systemsPipeline – Register Pipeline – Architektur

A. Mäder 35




RISC Pipelining (cont.)I CISC ISA (x86): Umsetzung der CISC Befehle in Folgen

RISC-ähnlicher Anweisungen

+ CISC-Software bleibt lauffähig+ Befehlssatz wird um neue RISC Befehle erweitert

A. Mäder 36




RISC Pipelining

A. Mäder 37




MemoryPC

Ad

der

RegisterFile

SignExtend

IF / ID

ID / E

X

Imm

RS1

RS2Zero?

ALU

MU

X

EX

/ MEM

Memory

MU

X

MEM

/ WB

MU

X

MU

X

Next SEQ PC Next SEQ PC

WB Data

Branchtaken

IR

Instruction Fetch

Next PC

Instruction DecodeRegister Fetch

ExecuteAddress Calc.

Memory Access Write Back

IF ID EX MEM WB

RISC PipeliningA. Mäder 38




RegDMALURegIM

RegDMALURegIM

RegDMALURegIM

RegDMALURegIM

RegDMALURegIM

Taktzyklen21 3 4 5 6 7 8

sub $11, $2, $3

add $12, $3, $4

lw $13, 24($1)

add $14, $5, $6

Instruktionen

lw $10, 20($1)





Instructionmemory

PCincrement

CC ALU

Datamemory

Fetch

Decode

Execute

Memory

Write back

icode, ifunrA, rB

valC

Registerfile

A BM

E

Registerfile

A BM

E

pState

valP


valA, valB

aluA, aluB

Bch

valE

Addr, Data

valM

PC

valE, valM

valM

icode, valCvalP

PC

PCincrement

CC ALU

Datamemory

Fetch

Decode

Execute

Memory

Write back

Registerfile

A BM

E

Registerfile

A BM

E

d_srcA, d_srcB

valA, valB

aluA, aluB

Bch valE

Addr, Data

valM

PC

W_valE, W_valM, W_dstE, W_dstMW_icode, W_valM

icode, ifun,rA, rB, valC

E

M

W

F

D

valP

f_PC

predPC

Instructionmemory

M_icode, M_Bch, M_valA





E

M

W

F

D

Instructionmemory

PCincrement

Registerfile

ALU

Datamemory

SelectPC

rB

dstE dstMSelectA

ALUA

ALUB

Mem.control

Addr

srcA srcB

read

write

ALUfun.

Fetch

Decode

Execute

Memory

Write back

icode

data out

data in

A BM

E

M_valA

W_valM

W_valE

M_valA

W_valM

d_rvalA

f_PC

PredictPC

valE valM dstE dstM

Bchicode valE valA dstE dstM

icode ifun valC valA valB dstE dstM srcA srcB

valC valPicode ifun rA

predPC

CC

d_srcBd_srcA

e_Bch

M_Bch





Prozessorpipeline – Begriffe

BegriffeI Pipeline-Stage: einzelne Stufe der PipelineI Pipeline Machine Cycle:

Instruktion kommt einen Schritt in Pipeline weiterI Durchsatz: Anzahl der Instruktionen, die in jedem Takt

abgeschlossen werdenI Latenz: Zeit, die eine Instruktion benötigt, um alle

Pipelinestufen zu durchlaufen

A. Mäder 42




Prozessorpipeline – Bewertung

Vor- und Nachteile+ Pipelining ist für den Programmierer nicht sichtbar!+ höherer Instruktionsdurchsatz ⇒ bessere Performanz− Latenz wird nicht verbessert, bleibt bestenfalls gleich− Pipeline Takt limitiert durch langsamste Pipelinestufe

unausgewogene Pipelinestufen reduzieren den Takt unddamit die Performanz

− zusätzliche Zeiten, um Pipeline zu füllen bzw. zu leeren

A. Mäder 43




Prozessorpipeline – Speed-Up

Pipeline Speed-UpI N Instruktionen; K PipelinestufenI ohne Pipeline: N · K TaktzyklenI mit Pipeline: K + N − 1 TaktzyklenI Speed-Up = N·K

K+N−1 , limN→∞ S = K

⇒ ein großer Speed-Up wird erreicht durch1. große Pipelinetiefe: K2. lange Instruktionssequenzen: N

A. Mäder 44




Prozessorpipeline – Speed-Up (cont.)

0

2

4

6

8

10

0 20 40 60 80 100N Befehle

Speed-Up, 10 Pipelinestufen (N*10)/(10+N-1)

Speed-Up

A. Mäder 45




Prozessorpipeline – Dimensionierung

Dimensionierung der PipelineI Längere PipelinesI Pipelinestufen in den Einheiten / den ALUs (superskalar)⇒ größeres K wirkt sich direkt auf den Durchsatz aus⇒ weniger Logik zwischen den Registern, höhere TaktfrequenzenI Beispiele

CPU Pipelinestufen Taktfrequenz [MHz ]Pentium 5 300Motorola G4 4 500Motorola G4e 7 1000Pentium II/III 12 1400Athlon XP 10/15 2500Athlon 64, Opteron 12/17 ≤ 3000Pentium 4 20 ≤ 5000

A. Mäder 46




Prozessorpipeline – Auswirkungen

Architekturentscheidungen, die sich auf das Pipelining auswirkengut für Pipelining

I gleiche InstruktionslängeI wenige InstruktionsformateI Load/Store Architektur

BASIC INSTRUCTION FORMATS

R opcode rs rt rd shamt funct

31 26 25 21 20 16 15 11 10 6 5 0

I opcode rs rt immediate

31 26 25 21 20 16 15 0

J opcode address

31 26 25 0

FR opcode fmt ft fs fd funct

31 26 25 21 20 16 15 11 10 6 5 0

FI opcode fmt ft immediate

31 26 25 21 20 16 15 0

FLOATING-POINT INSTRUCTION FORMATS

MIPS-Befehlsformate

A. Mäder 47




Prozessorpipeline – Auswirkungen (cont.)

schlecht für Pipelining: Pipelinekonflikte / -HazardsI Strukturkonflikt: gleichzeitiger Zugriff auf eine Ressource

durch mehrere PipelinestufenI Datenkonflikt: Ergebnisse von Instruktionen werden

innerhalb der Pipeline benötigtI Steuerkonflikt: Sprungbefehle in der Pipelinesequenz

sehr schlecht für PipeliningI Unterbrechung des Programmkontexts: Interrupt,

System-Call, Exception. . .I (Performanz-) Optimierungen mit „Out-of-Order

Execution“ etc.

A. Mäder 48




Pipeline Strukturkonflikte

Strukturkonflikt / Structural HazardI mehrere Stufen wollen gleichzeitig auf eine Ressource zugreifenI Beispiel: gleichzeitiger Zugriff auf Speicher Beispiel

⇒ Mehrfachauslegung der betreffenden RessourcenI Harvard-Architektur vermeidet Strukturkonflikt aus BeispielI Multi-Port RegisterI mehrfach vorhandene Busse und Multiplexer. . .

A. Mäder 49




RegMemALURegMem

RegMemALURegMem

RegMemALURegMem

RegMemALURegMem

Taktzyklen21 3 4 5 6 7

lw $10, 20($1)

sub $11, $2, $3

add $12, $3, $4

lw $13, 24($1)

Instruktionen

Strukturkonflikte

A. Mäder 50




Pipeline Datenkonflikte

Datenkonflikt / Data HazardI eine Instruktion braucht die Ergebnisse einer vorhergehenden,

diese wird aber noch in der Pipeline bearbeitetI Datenabhängigkeiten der Stufe „Befehl ausführen“ Beispiel

ForwardingI kann Datenabhängigkeiten auflösen, s. BeispielI extra Hardware: „Forwarding-Unit“I Änderungen in der Pipeline SteuerungI neue Datenpfade und Multiplexer

A. Mäder 51




Pipeline Datenkonflikte (cont.)

MIPSDatenpfad

A. Mäder 52





MIPSForwarding

A. Mäder 53





RückwärtsabhängigkeitenI spezielle Datenabhängigkeit Beispiel

I Forwarding-Technik funktioniert nicht, da die Daten erst späterzur Verfügung stehenI bei längeren PipelinesI bei Load-Instruktionen (s.u.)

Auflösen von Rückwärtsabhängigkeiten1. Softwarebasiert, durch den Compiler, Reihenfolge der

Instruktionen verändern Beispiel

I andere Operationen (ohne Datenabhängigkeiten) vorziehenI nop-Befehl(e) einfügen

A. Mäder 54





2. „Interlocking“ Beispiel

I zusätzliche (Hardware) KontrolleinheitI verschiedene StrategienI in Pipeline werden keine neuen Instruktionen geladenI Hardware erzeugt: Pipelineleerlauf / „pipeline stall“

„Scoreboard“I Hardware Einheit zur zentralen Hazard-Erkennung und

-AuflösungI Verwaltet Instruktionen, benutzte Einheiten und Register

der Pipeline

A. Mäder 55




RegDMALURegIM

RegDMALURegIM

RegDMALURegIM

RegDMALURegIM

RegDMALURegIM


sub , $1, $3

$2

$2

sw $15, 100( )

Instruktionen

$2 $2

or $13, $6,

$2

$2

add $14, ,

and $12, , $5

DatenkonflikteA. Mäder 56




RegDMALURegIM

RegDMALURegIM

RegDMALURegIM

RegDMALURegIM

Taktzyklen21 3 4 5 6 7

lw , 20($1)

Instruktionen

$4 $2

$2

add $9, ,

$4 $2and , , $5

$2or $8, , $6

Datenkonflikte

A. Mäder 57




RegDMALURegIM

RegDMALURegIM

RegDMALURegIM

RegDMALURegIM

lw , 20($1)

Instruktionen

$2

RegDMALURegIM


$4 $2

$4 $2and , , $5

$2or $8, , $6

add $9, ,

nop

DatenkonflikteA. Mäder 58




RegDMALURegIM

IM

lw , 20($1)

Instruktionen

$2


and , , $5 RegDMALU

RegDMALURegIM

RegDMALURegIM $4 $2

$2or $8, , $6

add $9, ,

Reg $4 $2

Datenkonflikte

A. Mäder 59




Pipeline Steuerkonflikte

Steuerkonflikt / Control HazardI Sprungbefehle unterbrechen den sequenziellen Ablauf

der InstruktionenI Problem: Instruktionen die auf (bedingte) Sprünge folgen,

werden in die Pipeline geschoben, bevor bekannt ist,ob verzweigt werden soll

I Beispiel: bedingter Sprung Beispiel

A. Mäder 60




Pipeline Steuerkonflikte (cont.)

Lösungsmöglichkeiten für SteuerkonflikteI ad-hoc Lösung: „Interlocking“ erzeugt Pipelineleerlauf− ineffizient: ca. 19% der Befehle sind Sprünge

1. Annahme: nicht ausgeführter Sprung / „untaken branch“+ kaum zusätzliche Hardware− im Fehlerfall

I PipelineleerlaufI Pipeline muss geleert werden / „flush instructions“

2. Sprungentscheidung „vorverlegen“I Software: Compiler zieht andere Instruktionen vor

Verzögerung nach Sprungbefehl / „delay slots“I Hardware: Sprungentscheidung durch Zusatz-ALU

(nur Vergleiche) während Befehlsdecodierung (z.B. MIPS)

A. Mäder 61





3. Sprungvorhersage / „branch prediction“I Beobachtung: ein Fall tritt häufiger auf:

Schleifendurchlauf, Datenstrukturen durchsuchen etc.I mehrere Vorhersageverfahren; oft miteinander kombiniert+ hohe Trefferquote: bis 90%Statische Sprungvorhersage (softwarebasiert)I Compiler erzeugt extra Bit in Opcode des SprungbefehlsI Methoden: Codeanalyse, Profiling. . .

Dynamische Sprungvorhersage (hardwarebasiert)I Sprünge durch Laufzeitinformation vorhersagen:

Wie oft wurde der Sprung in letzter Zeit ausgeführt?I viele verschiedene Verfahren:

History-Bit, 2-Bit Prädiktor, korrelationsbasierte Vorhersage,Branch History Table, Branch Target Cache. . .

A. Mäder 62




Pipeline Steuerkonflikte (cont.)I Beispiel: 2-Bit Sprungvorhersage + Branch Target Cache

SprungadresseTag-Bits vorhergesagte

Index-

Tag-Bits=

gültig2-Bit

Vorhersage

PC

VHH

orhersage bitVistorie bitprung ausgeführtSS=0/1

00 01

1110S=0 S=1

S=0 S=1

S=1S=0

S=1S=0

A. Mäder 63





I Schleifen abrollen / „Loop unrolling“I zusätzliche Maßnahme zu allen zuvor skizzierten VerfahrenI bei statische Schleifenbedingung möglichI Compiler iteriert Instruktionen in der Schleife (teilweise)− längerer Code+ Sprünge und Abfragen entfallen+ erzeugt sehr lange Codesequenzen ohne Sprünge⇒ Pipeline kann optimal ausgenutzt werden

A. Mäder 64




RegDMALURegIM

RegDMALURegIM

RegDMALURegIM

RegDMALURegIM

beq $1, $3, 28

Instruktionen

RegDMALURegIM


or $13, $6, $2

add $14, $3, $2

and $12, $2, $5

lw $4, 50($7)

SteuerkonflikteA. Mäder 65



Computerarchitektur - Superskalare Prozessoren 64-040 Rechnerstrukturen

Superskalare Prozessoren

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

konventionell linearen Instruktionsstroms abgearbeitet: CPI < 1ILP (Instruction Level Parallelism) ausnutzen!

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 66




Superskalar – Datenabhängigkeiten

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

A. Mäder 67




Superskalar – Datenabhängigkeiten (cont.)

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

„Register Renaming“I Hardware löst Datenabhängigkeiten innerhalb der Pipeline aufI Zwei Registersätze sind vorhanden

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

A. Mäder 68




Superskalar – Datenabhängigkeiten (cont.)I Beispiel

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

tmp = tmp2;

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

A. Mäder 69




Superskalar – Pipeline

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 70




Superskalar – Pipeline (cont.)

Scheduling der Instruktionen

A. Mäder 71




Superskalar – Pipeline (cont.)I Dynamisches Scheduling erzeugt out-of-order Reihenfolge

der InstruktionenI Issue: globale Sicht

Dispatch: getrennte Ausschnitte in „Reservation Stations“

A. Mäder 72




Superskalar – Pipeline (cont.)

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 weitergeleitetI Dynamisches Scheduling: zuerst ’67 in IBM360

(Robert Tomasulo)I ForwardingI Registerumbenennung und Reservation Stations

A. Mäder 73




Superskalar – Scoreboard

Zentrale Verwaltungseinheit: „Scoreboard“

A. Mäder 74




Superskalar – Scoreboard (cont.)

Scoreboard erlaubt das Management mehrererAusführungseinheitenI out-of-order Ausführung von MehrzyklusbefehlenI Auflösung aller Struktur- und Datenkonflikte:

RAW, WAW, WAR

EinschränkungenI single issue (nicht superskalar)I in-order issueI keine Umbenennungen; also Leerzyklen bei WAR- und

WAW-KonfliktenI kein Forwarding, daher Zeitverlust bei RAW-Konflikten

A. Mäder 75




Superskalar – Retire-Stufe

„Retire“I erzeugt wieder in-order ReihenfolgeI FIFO: Reorder-BufferI commit: „richtig ausgeführte“ Instruktionen gültig machenI abort: Sprungvorhersage falsch

Instruktionen verwerfen

A. Mäder 76




Probleme superskalarer Pipelines

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 zwischenbedingten Sprüngen limitiert Anzahl parallelisierbarerInstruktion

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

A. Mäder 77




Software Pipelining

Softwareunterstützung für Pipelining superskalarer ProzessorenI Codeoptimierungen beim Compilieren: Ersatz für, bzw.

Ergänzend zu der Pipelineunterstützung durch HardwareI Compiler hat „globalen“ Überblick⇒ zusätzliche Optimierungsmöglichkeiten

I symbolisches Loop UnrollingI Loop FusionI . . .

A. Mäder 78




Superskalar – Interrupts

Exceptions, Interrupts und System-CallsI Interruptbehandlung ist wegen der Vielzahl paralleler Aktionen

und den Abhängigkeiten innerhalb der Pipelines extremaufwändigI da unter Umständen noch Pipelineaktionen beendet werden

müssen, wird zusätzliche Zeit bis zur Interruptbehandlungbenötigt

I wegen des Register-Renaming muss sehr viel mehr Informationgerettet werden als nur die ISA-Register

I Prinzip der InterruptbehandlungI keine neuen Instruktionen mehr initiierenI warten bis Instruktionen des Reorder-Buffers abgeschlossen sind

A. Mäder 79




Superskalar – Interrupts (cont.)I 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 Instruktionen diein der Pipeline nicht abgearbeitet werden können (z.B. weil sieden Interrupt ausgelöst haben)

I Definition: Precise-InterruptI Programmzähler (PC) zur Interrupt auslösenden Instruktion

ist bekanntI Alle Instruktionen bis zur PC-Instruktion wurden vollständig

ausgeführtI Keine Instruktion nach der PC-Instruktion wurde ausgeführtI Ausführungszustand der PC-Instruktion ist bekannt

A. Mäder 80




Ausnahmebehandlung

Ausnahmebehandlung („Exception Handling“)I Pipeline kann normalen Ablauf nicht fortsetzenI Ursachen

I „Halt“ AnweisungI ungültige Adresse für Anweisung oder DatenI ungültige AnweisungI Pipeline Kontrollfehler

I erforderliches VorgehenI einige Anweisungen vollenden

Entweder aktuelle oder vorherige (hängt von Ausnahmetyp ab)I andere verwerfen

I „Exception Handler“ aufrufen: spez. Prozeduraufruf

A. Mäder 81



Computerarchitektur - Beispiele 64-040 Rechnerstrukturen

Pentium 4 / NetBurst Architektur

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

A. Mäder 82




Pentium 4 / NetBurst Architektur (cont.)I „Double pumped“ ALUs (2 Operationen pro Taktzyklus)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, techresearch.intel.com

A. Mäder 83

http://ark.intel.com

http://techresearch.intel.com




Pentium 4 / NetBurst Architektur (cont.)

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

IntelQ1, 2001

A. Mäder 84




Core 2 Architektur128 Entry

ITLB32 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 85

Documents

64-040- Modul IP7: Rechnerstrukturen - uni-hamburg.de · UniversitätHamburg MIN-Fakultät FachbereichInformatik Computerarchitektur-SequenzielleBefehlsabarbeitung 64-040Rechnerstrukturen