Pipeline del MIPS
Progettazione del datapath
•
Prima soluzione: Datapath SingleCycle
– Semplice da realizzare
– Condizionato dal worst case (istruzione più lenta)
– Ogni unità funzionale è usata una volta sola per ciclo
•
Seconda soluzione: Datapath Multicycle
• Suddivisione in fasi e registri intermedi
Il datapath a ciclo singolo
MemtoReg MemRead MemWrite ALUSrc RegDst PC Instruction memory Read address Instruction [31– 0] Instruction [20– 16] Instruction [25– 21] Add RegWrite 4 16 32 Instruction [15– 0] 0 Registers Write register Write data Write data Read data 1 Read data 2 Read register 1 Read register 2 Sign extend ALU result Zero Data memory Address Read data M u x 1 0 M u x 1 0 M u x 1 0 M u x 1 Instruction [15– 11] ALU Shift left 2 PCSrc ALU5 fasi per un’istruzione
•
IFetch
: Instruction Fetch e aggiornamento PC
•
Dec
: Registers Fetch e decodifica istruzione
•
Exec
:
Esecuzione (R-type)
Calcolo dell’indirizzo di memoria (I-type)
•
Mem
:
Dove si realizzano le varie fasi ?
Flusso di esecuzione
Eccezioni al flusso di esecuzione
Dal ciclo singolo al pipeline
o
Come permettere l’utilizzo dell’hardware da
più istruzioni in contemporanea ?
o
Si inseriscono registri tra i vari stadi
n
Mantengono le informazioni prodotte nel ciclo
precedente
Prime considerazioni
o I registri sono presenti tra le varie parti del datapath,
ognuna delle quali realizza una particolare fase.
o I registri separano una sezione dall’altra, evitando
così che le diverse istruzioni in esecuzione interferiscano tra loro.
o Il flusso dei dati è da sinistra verso destra con due
Prime considerazioni (2)
o Solo le istruzioni successive possono essere
influenzate da questi movimenti dati in “direzione opposta” al flusso consueto.
o Si verificano dei “conflitti” o “hazard” detti anche alee
o Esempi:
n WB -> ID può provocare
o data hazards (alea sui dati)
n MEM -> IF può provocare
Esecuzione di sw
l
Che cosa cambia ?
l
IF, ID uguali
l
In EX viene inoltrato il contenuto di Rt
l
In MEM viene scritto il valore in memoria
Istruzioni / Segnali di controllo
Branch Write Mem
l Sono raggruppati secondo lo stadio in cui sono attivi l I primi due stadi non contengono segnali di controllo
Distribuzione dei segnali di controllo
l I segnali vengono determinati durante la fase ID
l Vengono usati nelle tre fasi successive: vanno quindi
Pipeline: rappresentazione grafica
l Necessario rappresentare la situazione della pipeline in
un certo istante
l Quali istruzioni si stanno eseguendo ? In quale stadio?
l I diagrammi visti finora rappresentano la situazione in
un solo ciclo di clock (diagrammi a singolo ciclo)
l Sono necessari diagrammi che si riferiscano a più cicli
di clock (diagrammi a più cicli)
l A questo scopo si adopera una rappresentazione
Esempio
Consideriamo la sequenza di cinque istruzioni:
lw
$10, 20($1)
sub $11, $2, $3
add $12, $3, $4
lw $13, 24($1)
add $14, $5, $6
E supponiamo di voler considerare la loro
esecuzione sul datapath pipelined al
Confronto tra le implementazioni
lw IFetch Dec Exec Mem WB
Pipeline:
IFetch Dec Exec Mem WB
sw Clk
Ciclo singolo:
Load Store Waste
IFetch Dec Exec Mem WB
R-type
Cycle 1 Cycle 2
Ritardo del Write
• Si ritarda di un ciclo il write delle istruzioni R-type
– Tutte le istruzioni accedono al Write Port del R.F. nel 5° passo ànessun conflitto
– Il 4° passo (Mem) per le istr. R-type è in effetti un passo NOP
Clock
Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9
Ifetch Reg/Dec Mem Wr R-type
Ifetch Reg/Dec Mem Wr R-type
Ifetch Reg/Dec Exec Wr
R-type Mem
Exec
Exec
Il pipeline ottimizza il throughput
I n s t r. O r d e rTempo (cicli di clock)
Inst 0 Inst 1 Inst 2 Inst 3 ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM Reg ALU
Una volta che il pipeline è pieno, si completa
un’istruzione ad ogni ciclo
l’ISA MIPS favorisce il pipelining
o Tutte le istruzioni hanno la stessa lunghezza
n Più semplice il fetch nel 1° passo e il decode nel 2°
passo
o Pochi formati di istruzione (3) con simmetria tra i
formati
n Possibile cominciare la lettura del register file nel
2° passo
o Operazioni in memoria solo per load/store
Problemi dal pipelining ?
o
Alee o “hazards”
n
situazioni di conflitto che devono essere gestite
o conducono a malfunzionamenti
o
Tre tipi di Alee
n
Alee strutturali
n
Alee sui dati
n
Alee sul controllo
Incerti sulle Alee?
n Alee strutturali:
tentativo di usare contemporaneamente la stessa risorsa da parte di due istruzioni differenti
n Alee sui dati:
tentativo di usare i dati prima che siano disponibili
o Gli operandi sorgente di un’istruzione sono prodotti da
un’istruzione precedente che è ancora nel pipeline
o Istruzione di Load seguita immediatamente da un’istruzione
che richiede l’operando del load come sorgente per un’operazione sull’ALU
I n s t r. O r d e r
Tempo (cicli di clock)
lw
Inst 1 Inst 2 Inst 3
ALU
Mem Reg Mem Reg
ALU
Mem Reg Mem Reg
ALU
Mem Reg Mem Reg
ALU
Mem Reg Mem Reg
Alea strutturale 1: memoria unica
Lettura dati dalla memoria
Alea strutturale 1: memoria unica
o
Soluzione ideale: uso di due memorie
n
le memorie sono lente rispetto al processore e
complicate da costruire: inefficiente
o
Soluzione pratica: simuliamo la presenza
di due memorie tramite una memoria
Alea strutturale 2: accesso ai registri
I n s t r. O r d e r Inst 1 Inst 2 ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM Reg ALU add r1, add r2,r1,Alea strutturale 2: accesso ai registri
o
L’accesso ai registri è molto veloce:
richiede meno di metà del tempo
necessario ad un’operazione ALU
o
Soluzione: si introduce la convenzione
n
Scrittura sui registri durante la prima metà del
ciclo di clock
n
Lettura dai registri durante la seconda metà
Alea strutturale 2: accesso ai registri
I n s t r. O r d e r Inst 1 Inst 2 ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM Reg ALU add r1, add r2,r1,Alea sui dati
Consideriamo la sequenza di istruzioni
add
$t0
, $t1, $t2
sub $t4,
$t0
,$t3
Alea sui dati
L’influenza su fasi precedenti produce alee
I n s t r. O r d e r add $t0, $t1, $t2 sub $t4, $t0 ,$t3 and $t5, $t0 ,$t6 or $t7, $t0 ,$t8 ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM Reg
Alea sui dati:
Read Before Write
ALU IM Reg DM Reg ALU IM DM Reg ALU IM DM Reg ALU Reg Reg I n s t r. O r d add $t0, $t1, $t2 sub $t4, $t0 ,$t3 and $t5, $t0 ,$t6ALU
IM Reg DM Reg
Alea sui dati: soluzione 1
ALU IM Reg DM Reg ALU IM Reg DM Reg Possibile risolvere inserendo dei tempi morti (stall) ma peggiora il throughput add $t0, $t1, $t2 stall stall and $t5, $t0 ,$t6 sub $t4, $t0 ,$t3
Alea sui dati: soluzione 2
ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM Reg Si propagano i dati in avanti appena sono disponibili verso le unità che li richiedono (forwarding) ALU IM Reg DM Reg I n s t r. O r d e add $t0, $t1, $t2 sub $t4, $t0 ,$t3 and $t5, $t0 ,$t6 or $t7, $t0 ,$t8Alea sui dati: soluzione
2
ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM Reg ALU I n s t r. O r d e r add $t0, $t1, $t2 sub $t4, $t0 ,$t3 and $t5, $t0 ,$t6 or $t7, $t0 ,$t8 Si propagano i dati in avanti appena sono disponibili verso le unità che li richiedono (forwarding)Forwarding
l
Il risultato dell’istruzione sub è già disponibile al
termine dello stadio EX (CC3).
l
Le altre istruzioni hanno bisogno di quel dato
negli stadi CC4 (and) e CC5 (or)
l
Dove si trova il dato in quegli istanti ?
l CC4: nel registro EX/MEMl CC5: nel registro MEM/WB
l
Come è quindi possibile capire che è necessario
il forwarding ?
• 1a: EX/MEM.RegistroRd == ID/EX.Registro.Rs
Forwarding
Condizione 1a
Alea sui dati da Load
I n s t r. O r d e r lw r1,100(r2) sub r4,r1,r5 and r6,r1,r7 or r8, r1, r9 ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM Reg ALUAlea sui dati da Load: forwarding
I n s t r. O r d e r lw r1,100(r2) sub r4,r1,r5 and r6,r1,r7 xor r4,r1,r5 or r8, r1, r9 ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM Reg ALU IM Reg DM RegIl controllo deve bloccare il pipeline:
interlock
Alea sui dati da Load
sub $t3,
$t0
,$t2
I$ Reg bub ALU D$ Regble
and $t5,
$t0
,$t4
A
LU
I$ bub Reg D$ Reg
lw
$t0
, 0($t1)
IF ID/RF EX ALU MEM WBAlea da Load: introduzione di stall
l
Condizione per la verifica dell’hazard:
(ID/EX.MemRead and
((ID/EX.RegistroRt=IF/ID.RegistroRs)or
(ID/EX.RegistroRt=IF/ID.RegistroRt))
l
Unità di rilevamento dell’hazard
l
Meccanismo:
Alea sui dati da Load
o
Lo spazio per l’istruzione dopo un load è
chiamato “
load delay slot
”
o
L’inserimento dello stall è inevitabile se
l’istruzione usa il risultato del load.
o
Non necessario se il traduttore inserisce nello
slot un’istruzione non dipendente dal load
n (reordering) à traduttore cosciente del pipelining
Alea sui dati da Load
Lo stall è equivalente ad un NOP
sub $t3
,$t0
,$t2
and $t5,
$t0
,$t4
lw
$t0
, 0($t1)
ALU I$ Reg D$ Reg bub ble bub ble bub ble bub ble bub ble A LU I$ Reg D$ Reg A LU I$ Reg D$ Regnop
Nota storica
o
Il MIPS è stato il primo progetto di
processore a risolvere il conflitto sui dati
proveniente dalle istruzioni load senza
tulizzare interlock e stall
o
Acronimo reale per il MIPS:
Microprocessor without
Interlocked
Alea di controllo: salto
I$beq
Instr 1
Instr 2
Instr 3
Instr 4
A LU I$ Reg D$ Reg A LU I$ Reg D$ Reg A LU I$ Reg D$ Reg A LU Reg D$ Reg A LU I$ Reg D$ Reg I n s t r. O r d e rAlea di controllo: salto
o
L’unità per il confronto e la decisione è nel
terzo stage (ALU stage)
n
Quindi altre due istruzioni dopo il
beq
entreranno nel pipeline, quale che sia il
risultato del confronto
o
Comportamento (desiderato) del salto
n
Se il confronto fallisce continua la normale
Alea di controllo: salto. Soluzione 1
•
Blocco del pipeline finchè il confronto non
sia stato realizzato
–
Inserimento di NOP
–
Conseguenza: i salti richiedono 3 cicli di clock
(assumendo che il confronto si faccia nel 3°
stage)
Alea di controllo: Soluzione 2.1
o
Soluzione 2.1:
n
Anticipazione del confronto al passo 2
n
Appena l’istruzione è decodificata, si può
decidere immediatamente e modificare il PC
(se necessario)
n
In questo modo entra solo un’istruzione nel
Alea di controllo. Soluzione 2.1
Inserimento di una bolla
add
beq
lw
A LU I$ Reg D$ Reg A LU I$ Reg D$ Reg A LU Reg D$ Reg I$ I n s t r. O r d e rTime (clock cycles)
bub ble
Alea di
controllo
Alea di controllo: Soluzione 2.2
o
Soluzione 2.2 (ridefinizione del salto)
n
Vecchia definizione: in caso di salto, nessuna
istruzione successiva al branch deve essere
eseguita
n
Nuova definizione: in ogni caso, viene
eseguita l’istruzione che segue
immediatamente il branch (definita
Note sul Branch-Delay Slot
•
Caso peggiore
–
Inserimento di un nop nello slot
•
Caso migliore
–
È possibile trovare un’istruzione precedente al
branch che possa essere posticipata al branch
senza alterare il flusso di controllo (e dei dati)
–
Dipende dalle capacità del traduttore
Nondelayed vs. Delayed Branch
add $1 ,$2,$3
sub $4, $5,$6
beq $1, $4, Exit
or $8, $9 ,$10
Nondelayed Branch
add $1 ,$2,$3
sub $4, $5,$6
beq $1, $4, Exit
or $8, $9 ,$10
Delayed Branch
Riassumendo ...
l
Il pipelining migliora le prestazioni incrementando
il throughput delle istruzioni: sfrutta l’Instruction
Level Parallelism
l Esegue più istruzioni in parallelo
l Ogni istruzione ha la stessa latenza
l
E’ soggetto ad alee
l Strutturali, di dati, di controllo
l
Gli stalli riducono le prestazioni
l Ma sono necessari per ottenere risultati corretti
l
Il compilatore può riorganizzare il codice per
Come aumentare l’ILP ?
l Esecuzione parallela (Multiple Issue) superscalare
l Replica degli stadi di pipeline (pipeline multiple)
l Si avviano più istruzioni nel ciclo di clock
l Parallelizzazione statica dell’esecuzione (Static MI)
l Il compilatore raggruppa le istruzioni da eseguire
insieme
l Le impacchetta in insiemi di esecuzione (issue slots)
l Individua ed evita le alee
l Parallelizzazione dinamica dell’esecuzione (Dynam. MI)
l La CPU esamina il flusso di istruzioni e sceglie quali
eseguire in ogni ciclo
Parallelizzazione statica
l
Il compilatore raggruppa le istruzioni in
pacchetti di esecuzione
l
Gruppi di istruzioni che possono partire
nello stesso ciclo
l
Determinati dalle risorse richieste
l
Ogni pacchetto può essere visto come
Parallelizzazione statica
l
Il compilatore deve impedire alee (se
possibile)
l
Riordina le istruzioni nei pacchetti
l
Nessuna dipendenza all’interno del
pacchetto
l
Possibili dipendenze tra pacchetti
Parallelizzazione dinamica
l
Processori “superscalari”
l
La CPU decide quante e quali istruzioni avviare
in un ciclo (0, 1, 2, …)
l Da evitare alee strutturali e di dati
l
Non necessario lo scheduling da parte del
compilatore
l Anche se può aiutare …
l La CPU deve garantire che l’esecuzione sia
Predizione...
l
Permette di “indovinare” le caratteristiche di
un’istruzione
l
Inizia l’operazione appena possibile
l
Verifica se la previsione è stata corretta
l
Se OK, completa l’operazione; altrimenti
torna indietro
l
Esempi: branch prediction
l
E’ comune alla parallelizzazione statica e
Organizzazione di una CPU superscalare
l
La pipeline è divisa in tre unità principali
l
Una unità per l’instruction fetch e avvio
dell’esecuzione
l Istruzioni avviate in ordine
l
Un gruppo di più unità funzionali in parallelo
l Ogni unità ha una Reservation Station che
mantiene gli operandi e memorizza l’operazione
l Può eseguire istruzioni fuori ordine
