Metodi Software per ottenere ILP
Calcolatori Elettronici 2
http://www.dii.unisi.it/~giorgi/didattica/calel2
Scaletta
• Tecnologie nel compilatore
• BRANCH PREDICTION A SOFTWARE (nel compilatore)
- Gia’ vista nella lezione sulla branch prediction
• STATIC SCHEDULING + LOOP UNROLLING
- Scopo: migliorare le prestazioni della pipeline e dei processori multiple-issue
- Molto importanti per CPU static-issue (VLIW)
- Importanti per CPU dynamic issue con static scheduling
• SOFTWARE PIPELINING
• Processori VLIW (Very Long Instruction Word)
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 2
Scheduling Statico: obiettivo
• Trovare istruzioni non correlate da inserire proficuamente
negli stadi di esecuzione della pipeline
• Date due istruzioni dipendenti (la prima detta istruzione
produttrice e la seconda detta istruzione consumatrice di un dato),
per evitare stalli, la distanza (in cicli di clock) fra di esse dovrebbe
essere pari alla latenza all’interno della pipeline della prima delle
due istruzioni
• I problemi maggiori nascono a causa della latenze (variabili) delle
Unita’ Funzionali (FU)
• Il compilatore puo’ riordinare (staticamente) le istruzioni se
• Esiste sufficiente ILP
• La latenze delle Unita’ Funzionali (FU) sono note al compilatore
- Si crea un LEGAME tra software e microarchitettura che “oltrepassa” lo
strato di isolamento creato dall’Instruction Set !
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 3
Scheduling Statico: ipotesi sulla pipeline
• Pipeline standard a 5 stadi
• Unita’ Funzionali (FU) pipeline-izzate
• (o replicate tante volte quante sono gli stadi di pipe)
• in modo da lanciare un’istruzione ad ogni ciclo di clock
• Assenza di criticita’ strutturali
Istr. Produttrice
Istr. Consumatrice
CNSL
FP ALU op
FP ALU op
Load double
Branch
INT ALU op
Load double
INT ALU op
Another FP ALU op
Store double
FP ALU op / INT ALU op
--Branch
Store double
INT ALU op
3
2
1
1
1
0
0
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 4
CNSL = No-Stall
Latency Cycles
Esempio
for (k = 1000; k > 0; --k) x[k] = a + x[k];
• “Loop Parallelo”: il corpo di ogni iterazione e’ indipendente
• Traduzione in assembly MIPS:
R1 vale inizialmente 8000
Loop:
L.D
ADD.D
S.D
SUBI
BNEZ
F0, 0(R1)
F4,F0,F2
F4, 0(R1)
R1,R1,#8
R1, Loop
;F0=array elem.
;add scalar in F2
;store result
;decrement pointer
;branch
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 5
Versione-0: Loop NON-SCHEDULATO
Cissue
(clock cycles)
Loop: L.D
Stall
ADD.D
Stall
Stall
S.D
SUBI
Stall
BNEZ
Stall
F0, 0(R1)
F4,F0,F2
F4, 0(R1)
R1,R1,#8
R1, Loop
1
2
3
4
5
6
7
8
9
10
Istr. Produttrice
Istr. Consumatrice
CNSL
FP ALU op
FP ALU op
Load double
Branch
INT ALU op
Load double
INT ALU op
Another FP ALU op
Store double
FP ALU op / INT ALU op
--Branch
Store double
INT ALU op
3
2
1
1
1
0
0
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 6
10 cicli per iterazione (5 cicli di stallo)
Riscrivere il codice
per minimizzare gli stalli
Versione-1: Loop Schedulato
Cissue
(clock cycles)
Loop:
L.D
SUBI
ADD.D
Stall
BNEZ
S.D
F0, 0(R1)
R1,R1,#8
F4,F0,F2
R1, Loop
8(R1),F4
1
2
3
4
5
6
i) Anticipo la SUBI ma devo variare
l’indirizzo effettivo a cui faccio la
store 0(.) 8(.)
ii) Sposto S.D dopo BNEZ sfruttando il
delay-slot della branch
;delayed branch
;altered effective address
Istr. Produttrice
Istr. Consumatrice
CNSL
FP ALU op
FP ALU op
Load double
Branch
INT ALU op
Load double
INT ALU op
Another FP ALU op
Store double
FP ALU op / INT ALU op
--Branch
Store double
INT ALU op
3
2
1
1
1
0
0
6 cicli per iterazione (1 ciclo di stallo);
osservazione: solo 3 istruzioni fanno
effettivamente elaborazione sul
vettore x[.] (L.D, ADD.D, S.D)
Posso fare lo srotolamente del loop
4 volte, per migliorare le potenzialita’
di scheduling statico
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 7
Versione-2: Loop Srotolato 4 volte
L.D
ADD.D
S.D
L.D
ADD.D
S.D
L.D
ADD.D
S.D
L.D
ADD.D
S.D
SUBI
BNEZ
1 cycle stall
F0,0(R1)
2 cycles stall
F4,F0,F2
0(R1),F4 ; drop SUBI&BNEZ
F0,-8(R1)
F4,F0,F2
-8(R1),F4 ; drop SUBI&BNEZ
F0,-16(R1)
F4,F0,F2
-16(R1),F4 ; drop SUBI&BNEZ
F0,-24(R1)
F4,F0,F2
-24(R1),F4
R1,R1,#32 ; alter to 4*8
R1,Loop
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 8
Ipotesi: il numero di iterazioni totali
e’ multiplo di 4. OK nel nostro
caso (1000 iterazioni)
Questo loop richiede 28 cicli (di cui 14
cicli sono di stallo) per iterazione,
infatti:
-ogni L.D ha 1 ciclo di stallo
-ogni ADD.D ne ha 2
-la SUBI ne ha 1
-la BNEZ ne ha 1
Inoltre ho i 14 cicli di instructionissue ovvero 28/4 = 7 cicli per
elaborare ogni elemento dell’array (piu’
lento della versione-1 schedulata !)
Riscrivo il loop per ridurre gli stalli
Rimozione delle “Name Dependencies”
L.D
ADD.D
S.D
L.D
ADD.D
S.D
L.D
ADD.D
S.D
L.D
ADD.D
S.D
SUBI
BNEZ
F0,0(R1)
F4,F0,F2
0(R1),F4 ; drop SUBI&BNEZ
F0,-8(R1)
F4,F0,F2
-8(R1),F4 ; drop SUBI&BNEZ
F0,-16(R1)
F4,F0,F2
-16(R1),F4 ; drop SUBI&BNEZ
F0,-24(R1)
F4,F0,F2
-24(R1),F4
R1,R1,#32 ; alter to 4*8
R1,Loop
Come eliminarle?
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 9
Uso la Rinominazione STATICA dei Registri
L.D
ADD.D
S.D
L.D
ADD.D
S.D
L.D
ADD.D
S.D
L.D
ADD.D
S.D
SUBI
BNEZ
F0,0(R1)
F4,F0,F2
0(R1),F4 ; drop SUBI&BNEZ
F6,-8(R1)
F8,F6,F2
-8(R1),F8 ; drop SUBI&BNEZ
F10,-16(R1)
F12,F10,F2
-16(R1),F12 ; drop SUBI&BNEZ
F14,-24(R1)
F16,F14,F2
-24(R1),F16
R1,R1,#32 ; alter to 4*8
R1,Loop
Register Renaming
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 10
Versione-3: Loop Srotolato con meno stalli
Loop:
L.D
L.D
L.D
L.D
ADD.D
ADD.D
ADD.D
ADD.D
S.D
S.D
SUBI
S.D
BNEZ
S.D
F0,0(R1)
F6,-8(R1)
F10,-16(R1)
F14,-24(R1)
F4,F0,F2
F8,F6,F2
F12,F10,F2
F16,F14,F2
0(R1),F4
-8(R1),F8
R1,R1,#32
16(R1),F12
R1,Loop
8(R1),F4 ;
Questo loop gira in 14 cicli (senza stalli)
per iterazone;
ovvero
14/4 = 3.5 cicili per elemento!
Assumo che sia possibile:
- Spostare le L.D prima delle SD
- Spostare alcune S.D dopo SUBI e BNEZ
- Usare piu’ registri
Il compilatore puo’ effettuare queste
trasformazioni senza “effetti collaterali”?
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 11
Passi del compilatore per srotolare i loop
• Determinare se sia possibile spostare una S.D dopo la
SUBI che aggiorna l’offset del relativo indirizzo effettivo
-
In caso positivo, va aggiustato l’offeset della S.D opportunamente
• Determinare se e’ utile srotolare il loop, esaminando se ci
siano iterazioni indipendenti
• Rinominare i registri per eliminare le “name dependencies”
• Eliminare le istruzioni di “test” e di “branch” intermedie
e aggiustare la parte conclusiva del ciclo
• Determinare se load e store del loop srotolato possano
essere “distanziate” quando operano in modo indipendente
-
Cio’ richiede di analizzare gli indirizzi di memoria per vedere se NON si
riferiscano allo stesso indirizzo di memoria
• Schedulare il codice, conservando ogni dipendenza che sia
necessaria per ottenere lo stesso risultato del codice
originario
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 12
PROCESSORI VLIW
Roberto Giorgi, Universita’ di Siena, C208L01, Slide 13
Processori “Multiple Issue”
• Motivazione: superare le limitazioni della pipeline standard
in cui
CPI REAL Pipeline = CPIIDEAL Pipeline +
CStructural stalls + CRAW stalls + CWAR stalls + CWAW stalls + CControl stalls
• Punto d’azione: diminuire CPIIDEAL Pipeline(=1) per poter
lanciare piu’ istruzioni nello stesso ciclo
• Implementazioni di procesori Multiple Issue
• Superscalar
- Con scheduling statico (facendo uso di tecnologie nel compilatore, v. sopra)
- Con scheduling dinamico (facendo uso es. dell’algoritmo di Tomasulo)
• VLIW (Very Long Instruction Word)
- OGNI ISTRUZIONE INDICA ESPLCITAMENTE IL PARALLELISMO
- Anche indicato con “EPIC” (Explicit Parallel Instruction Computer)
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 14
MIPS Superscalare Staticamente Schedulato
• MIPS superscalare: lancia 2 istruzioni per ciclo
• 1 istruzione va nella pipeline Floating Point e
1 istruzione nella pipeline Integer (o Load/Store o Branch)
• Ad ogni ciclo di clock vengono prelevate 2 istruzioni
• La seconda istruzione puo’ essere lanciata solo va in una pipeline
diversa
- Se ho piu’ di una istruzione in attesa posso ad es. bloccare il fetch
10
5
Time [clocks]
I
F
D
X
M
W
FP
F
D
X
M
W
I
F
D
X
M
W
FP
F
D
X
M
W
F
D
X
M
W
F
D
X
M
W
I
FP
Instr.
Nota: le operazioni FP
possono allungare la
durata dello stadio X
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 15
Versione-4: Loop Unrolling nel caso Superscalare
Integer Instr.
1
Loop:
FP Instr.
L.D F0,0(R1)
2
L.D F6,-8(R1)
3
L.D F10,-16(R1)
ADD.D F4,F0,F2
4
L.D F14,-24(R1)
ADD.D F8,F6,F2
5
L.D F18,-32(R1)
ADD.D F12,F10,F2
6
S.D 0(R1),F4
ADD.D F16,F14,F2
7
S.D -8(R1),F8
ADD.D F20,F18,F2
8
S.D -16(R1),F12
9
SUBI R1,R1,#40
10
S.D 16(R1),F16
11
BNEZ R1,Loop
12
S.D 8(R1),F20
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 16
Srotolo 5 volte per
evitare stalli
Questo loop gira in
12 cicli per iterazione
(senza stalli)
ovvero 12/5 =2.4 cicli
per elemento del
vettore
Processori Multiple Issue prodotti
• Superscalari
• IBM PowerPC, Sun UltraSparc, DEC Alpha, HP 8000
- Il numero di istruzioni schedulate per ciclo (o vie) varia da 1 a 8
- Scheduling statico (compilatore) o dinamico (es. Tomasulo)
• (Very) Long Instruction Words (V)LIW
- Crusoe VLIW processor [www.transmeta.com]
- Intel Architecture-64 (IA-64) 64-bit address
- La maggior parte dei DSP (Digital Signal Processor): Texas Instrument
C6000, PowerPC ... , ST Microelectronics ...
- Il numero di operazioni inserite dal compilatore in UNA istruzione varia da 4
a 16
Nota: dato che vorremmo CPI > 1 conviene usare IPC
(Instructions Per Clock cycle)
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 17
Implementazione di processore VLIW
I-fetch
Functional
Functional
Unit
Unit
& issue
Functional
Unit
Memory
to Memory
Port
Multi-Ported
Register
to Memory
Memory
File
Port
from Memory
from Memory
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 18
Approccio VLIW
• Le operazioni usano direttamente varie unita’ funzionali
indipendenti
• L’ istruzione-lunga e’ composta da piu’ operazioni che vanno
in parallelo
• La scelta delle operazioni che vanno in parallelo e’ fatta dal
compilatore
Ii
IF
Ii+1
Instr.
ID
E
E
E
W
IF
ID
E
E
E
Time [clocks]
W
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 19
Versione-5: Loop Unrolling nel caso VLIW
Mem. Ref1
1
L.D F2,0(R1)
Mem Ref. 2
FP1
FP2
Int/Branch
L.D F6,-8(R1)
2
L.D F10,-16(R1)
L.D F14,-24(R1)
3
L.D F18,-32(R1)
L.D F22,-40(R1)
4
L.D F26,-48(R1)
5
6
S.D 0(R1),F4
S.D -8(R1),F8
7
S.D -16(R1),F12
S.D -24(R1),F16
8
S.D -32(R1),F20
S.D -40(R1),F24
9
S.D -48(R1),F28
ADD.D F4,F0,F2
ADD.D F8,F0,F6
ADD.D F12,F0,F10
ADD.D F16,F0,F14
ADD.D F20,F0,F18
ADD.D F24,F0,F22
ADD.D F28,F0,F26
Srotolo 7 volte
per evitare stalli
SUBI R1,R1,#56
BNEZ R1,Loop
Elaboro 7 elementi in 9 cicli di clock, ovvero 1.3 cicli di clock per
ogni elemento (1.8X rispetto al superscalare)
L’efficienza non e’ molto alta: solo 2.5 operazioni per ciclo 50%
Nota: il numero di registri FP usati e’ salito a 15
(contro i 12 del caso superscalare)
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 20
Problematiche dei processori “Multiple Issue”
• CPI=0.5 si ottiene soltanto se il compilatore produce
• Esattamente il 50% delle operazioni FP e 50 % Integer ogni 2 cicli
• Se non ci sono criticita’ (hazards)
• Per l’hardware e’ poi estremamente semplice dispacciare FP/INT
• Se piu’ istruzioni vengono lanciate allo stesso istante,
significa avere stadi di decodifica e lancio piu’ complessi
• Es. con 2-operazioni per ciclooccorre esaminare 2 opcode e 6
registri contemporaneamente e decidere se le due istruzioni
possono veramente essere lanciate in parallello
• VLIW: per semplificare la decodifica si riducono gli opcode
• Es. Per eseguire in parallelo 2 operazioni intere, 2 FP, 2 operazioni
in memoria e 1 branch occorrerebbero:
- 7 x 16 = 112 bit per istruzione se uso operazioni lunghe 16 bit
- 7 x 24 = 168 bit per istruzione se uso operazioni lunghe 24 bit
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 21
Dipendenze fra iterazioni (“Loop-Carried Dependence”)
• Consideriamo:
for (i=0; i<8; i=i+1) {
A = A + C[i];
/* S1 */
}
• In questo caso il parallelismo e’ generato dalla
natura associativa dell’addizione:
”Cycle 1”:
”Cycle 2”:
”Cycle 3”:
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 22
temp0 = C[0] + C[1];
temp1 = C[2] + C[3];
temp2 = C[4] + C[5];
temp3 = C[6] + C[7];
temp4 = temp0 + temp1;
temp5 = temp2 + temp3;
A = temp4 + temp5;
Iterazioni NON facilmente srotolabili
• Consideriamo il seguente codice
(A, B, C distinti e non sovrapposti in memoria):
for (i=0; i<100; i=i+1) {
A[i+1] = A[i] + C[i];
B[i+1] = B[i] + A[i+1];
}
/* S1 */
/* S2 */
• Esistono le seguenti dipendenze:
1) S2 usa il valore A[i+1] calcolato da S1 nella stessa iterazione
2) S1 usa il valore A[i] calcolato da S1 nell’iterazione precedente
(quando si chiamava A[i+i])
3) Analoga dipendenza in S2 per B[i] calcolato all’iterazione
precedente come B[i+1]
• Anche srotolando, le dipendenze creano stalli
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 23
Metodo per superare le dipendenze fra iterazioni
• Consideriamo il seguente codice:
for (i=1; i<=100; i=i+1) {
A[i] = A[i] + B[i];
B[i+1] = C[i] + D[i];
}
/* S1 */
/* S2 */
• Trasformazione per sovrapporre le iterazioni:
A[1] = A[1] + B[1];
for (i=1; i<100; i=i+1) {
B[i+1] = C[i] + D[i];
A[i+1] = A[i+1] + B[i+1];
}
B[101] = C[100] + D[100];
• In questo modo ho eliminato le dipendenze fra iterazioni
e posso usare proficuamente la tecnica di srotolamento
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 24
Un’altra possibilita’: Software Pipelining
• Osservazione: se le iterazioni fra loop sono indipendenti,
allora si puo’ ottenere maggior parallelismo fra le istruzioni
(ILP) prelevando istruzioni da differenti iterazioni
• Il Software Pipelining consiste appunto nel riorganizzare il
codice dei loop in modo tale che ogni iterazioni sia composta
da istruzioni provenienti da differenti iterazioni del ciclo
originale (alcuni equiparano questo metodo ad una sorta di
algoritmo di Tomasulo a software)
Iteration
0
Iteration
1
Iteration
2
Iteration
3
Softwarepipelined
iteration
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 25
Benefici del Software Pipelining
overlapped ops
• Massimizza la distanza fra produzione e consumo del
risultato
• Usa codice piu’ compatto rispetto all’unrolling
• Ho un solo “transitorio” di riempimento e svuotamento della
pipeline rispetto all’unrolling dove cio’ avviene ad ogni
iterazione srotolata
SW Pipeline
Time
Loop Unrolled
Time
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 26
Versione-6: Software Pipelining
V-2: srotolamento di 4 volte
1
2
3
4
5
6
7
8
9
10
11
12
13
14
L.D
ADD.D
S.D
L.D
ADD.D
S.D
L.D
ADD.D
S.D
L.D
ADD.D
S.D
SUBI
BNEZ
F0,0(R1)
F4,F0,F2
0(R1),F4
F0,-8(R1)
F4,F0,F2
-8(R1),F4
F0,-16(R1)
F4,F0,F2
-16(R1),F4
F0,-24(R1)
F4,F0,F2
-24(R1),F4
R1,R1,#32
R1,LOOP
L.D
ADD.D
L.D
SUBI
F0,0(R1)
F4,F0,F2
F0,-8(R1)
R1,R1,#16
V-6: Software Pipelining
1
2
3
4
5
S.D
ADD.D
L.D
SUBI
BNEZ
S.D
ADD.D
S.D
16(R1),F4 ; Store di X[i]
F4,F0,F2 ; Add di X[i-1]
F0,0(R1); Load di X[i-2]
R1,R1,#8
R1,LOOP
5 cicli per iterazione
e per elemento
16(R1),F4
F4,F0,F2
8(R1),F4
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 27
Tabella di Riepilogo
VERSIONE
CICLI x
ITERAZIONE
CICLI x
ELEMENTO
SPEEDUP COMMENTI
V-0
10
10
1
Versione base
V-1
6
6
1.67
Instr. Scheduling
V-2
28
7
1.42
Loop Unrolling x4
V-3
14
3.5
2.85
I.S. + L.U.x4
V-4
12
2.4
4.17
Superscalar (LUx5)
V-5
7
1.3
7.69
VLIW (LUx7)
V-6
5
5
2
Software Pipelining
Roberto Giorgi, Universita’ di Siena, C208L05, Slide 28