Instruction Level Parallelism statico
• 
• 
• 
• 
• 
• 
Concetti di base dell’ILP statico
Pipeline scheduling e loop unrolling
Multiple issue statico: l’approccio VLIW
Le istruzioni predicative
L’architettura IA-64: l’Itanium II
L’architettura Trimedia TM32
1
ILP statico
•  Abbiamo fin’ora visto come lo sfruttamento del parallelismo presente
fra le istruzioni di un programma possa avvenire durante l’esecuzione
del programma stesso.
•  Scheduling dinamico della pipeline, register renaming, branch
prediction, speculazione hardware, multiple issue (dinamico), sono
tutte tecniche utilizzate a run-time.
•  E’ per questo che le tecniche che sfruttano in questo modo il
parallelismo insito nelle istruzioni di un programma vengono raccolte
sotto il nome di ILP dinamico
2
ILP statico
•  Ma un aiuto allo sfruttamento dell’ILP può venire anche dal
compilatore, il quale può riordinare le istruzioni macchina che
genera in modo da migliorare lo sfruttamento della pipeline e delle
unità funzionali della CPU quando le istruzioni verranno eseguite.
•  Naturalmente, nel manipolare le istruzioni macchina generate,
il compilatore deve lasciare inalterato il funzionamento del
programma scritto dal programmatore
•  Proprio perché queste tecniche cercano di evidenziare il parallelismo
presente nelle istruzioni di un programma prima che questo vada in
esecuzione, tali tecniche vengono raggruppate sotto il nome di ILP
statico
3
1
ILP statico
•  L’ILP statico è particolarmente importante nei processori embedded,
che devono costare e consumare poco, e non si possono permettere
l’enorme numero di transistors neccessari per implementare le
tecniche di ILP dinamico.
•  Ma, come vedremo, l’ILP statico è anche alla base dell’ISA
(architettura + set di istruzioni) IA-64, puramente RISC, sviluppata da
Intel e HP a partire dal 2000 e su cui sono basati i processori Itanium
e Itanium II
•  Di fatto, il confine tra ILP statico e dinamico non è netto, e in generale
molte architetture moderne usano una qualche combinazione dei due
gruppi di tecniche.
4
ILP statico: idea di base
•  Idea di base dell’ILP statico: tenere il più possibile occupata la
pipeline (quindi evitare gli stall) cercando, nella fase di compilazione
del programma, (sequenze di) istruzioni fra loro indipendenti che
possano sovrapporsi nella pipeline.
•  Per evitare gli stall, una istruzione B che dipende da una istruzione A
deve essere separata da A di una “distanza” in cicli di clock pari
almeno al numero di cicli di clock necessari ad A per produrre il
risultato che dovrà essere usato da B.
•  Per massimizzare la produttività della pipeline, il compilatore cerca
di inserire tra A e B altre istruzioni, utilizzando lo stesso criterio
adottato per A e B.
5
ILP statico: idea di base
•  E’ evidente che la capacità di un compilatore di compiere questa
forma di scheduling (ossia di riordino) delle istruzioni dipende:
–  dalla quantità di ILP presente nel programma in compilazione
–  dalla lunghezza della pipeline, dal numero e tipo di unità
funzionali disponibili, dai tempi di esecuzione delle varie istruzioni
–  dal fatto che il compilatore conosca queste informazioni sulla
CPU per cui sta generando il codice.
•  due CPU con identico livello ISA ma diversa microarchitetture (ossia
un diverso datapath, un diverso set di unità funzionali, un diverso
numero di stage della pipeline), possono fornire prestazioni
completamente diverse su un programma generato con un compilatore
che sfrutta l’ILP statico, e che opera tenendo presente una ben precisa
microarchitettura. Notate una differenza con l’ILP dinamico? 6
2
Tecniche di base di Compilazione
•  Consideriamo un compilatore che genera codice per una CPU con
pipeline a 5 stage e le seguenti caratteristiche:
–  Le varie UF sono a loro volta pipelined, e una qualsiasi istruzione
può essere lanciata ad ogni ciclo di clock
–  I branch vengono eseguiti in due cicli di clock
–  Prima che una istruzione B possa usare il risultato prodotto da una
istruzione A, occorre attendere i seguenti cicli di clock (H-P3, Fig.
4.1):
(A) instruction producing result
(B) instruction using result
latency (clock cycles)
FP ALU op
another FP ALU op
3
FP ALU op
Store double
2
double ALU op
branch
1
Load double
FP ALU op
1
7
Tecniche di base: pipeline scheduling
•  consideriamo questo for, che somma uno scalare ad un vettore di 1000
elementi:
for ( i = 1000; i > 0; i = i-1 )
x[i] = x[i] + s;
•  e la sua traduzione in codice MIPS (assumiamo che il valore iniziale
di R1, ed R2, siano stati calcolati in precedenza):
LOOP: LD
F0, 0 (R1)
// F0 = array element
FADD F4, F0, F2
// scalar is in F2
SD
// store result
F4, 0 (R1)
DADD R1, R1, #-8
// pointer to array is in R1 (DW)
BNE
// suppose R2 precomputed
R1, R2, LOOP
8
Tecniche di base: pipeline scheduling
•  ecco una “esecuzione” del loop senza nessuna forma di scheduling:
LOOP:
LD
stall
FADD
stall
stall
SD
DADD
stall
BNE
stall
F0, 0 (R1)
F4, F0, F2
F4, 0 (R1)
R1, R1, #-8
R1, R2, LOOP
clock cycle issued
1
2
3
4
5
6
7
8
9
No branch
prediction
10
•  Ossia, i tre RAW hazard costringono a vari stall della pipeline, e sono
9
necessari 10 cicli di clock per eseguire un ciclo del for
3
Tecniche di base: pipeline scheduling
•  ma ecco come un compilatore “intelligente”, conoscendo i valori della
tabella precedente, e sapendo di poter sfruttare la tecnica del delayed
branch, può applicare una forma di pipeline scheduling (statico):
ossia riordinare le istruzioni in modo da diminuire il numero di stall:
LOOP: LD
F0, 0 (R1)
DADD R1, R1, #-8
FADD F4, F0, F2
stall
BNE R1, R2, LOOP
SD
F4, 8 (R1)
clock cycle issued
1
2 // one stall “filled”
3
4
5 // delayed branch
6 // altered &
interchanged
with DADD
10
Tecniche di base: pipeline scheduling
LOOP:
•  Quali modifiche sono state fatte?
1
2
3
4
5
6
LD
DADD
FADD
stall
BNE
SD
F0, 0 (R1)
R1, R1, #-8
F4, F0, F2
R1, R2, LOOP
F4, 8 (R1)
–  con la DADD spostata in seconda posizione, si sono eliminati gli
stall (e quindi i ritardi) tra LD e FADD e tra DADD e BNE
–  spostando la SD dopo la BNE si elimina lo stall di un ciclo dovuto
alla BNE e si riduce di uno lo stall tra la FADD e la SD
–  siccome SD e DADD sono stati scambiati, l’offset nella SD deve
ora essere 8 anziché 0
–  Notate che questa forma di scheduling è possibile solo se il
compilatore conosce la latenza in cicli di clock di ogni istruzione
che genera (ossia se conosce i dettagli interni dell’architettura per
cui genera codice)
11
Tecniche di base: loop unrolling
•  Abbiamo ottenuto un miglioramento notevole, ma possiamo notare
che dei 6 cicli di clock necessari per eseguire una iterazione del for:
–  3 sono usati per operare sugli elementi dell’array (LD,ADD,SD)
–  3 sono semplice loop overhead (DADD, BNE, stall)
•  Un approccio alternativo al pipeline scheduling è aumentare il numero
di istruzioni che effettivamente operano sull’array, rispetto a quelle
che servono solo a gestire il ciclo. Come?
•  Possiamo raggruppare le istruzioni di iterazioni consecutive che
operano sull’array all’interno di un unico macrociclo, gestito da un
unico controllo di terminazione (un’unica BNE). Operiamo cioé sul
ciclo una forma di loop unrolling (srotolamento del loop) statico.
12
4
Tecniche di base: loop unrolling
ad esempio, se il numero di iterazioni nel loop è divisibile per 4,
il loop originale può essere “srotolato” 4 volte ottenendo:
LD
FADD
SD
LD
FADD
SD
LD
FADD
SD
LD
FADD
SD
DADD
BNE
F0, 0 (R1)
F4, F0, F2
F4, 0 (R1)
F6, -8 (R1)
F8, F6, F2
F8, -8 (R1)
F10, -16 (R1)
F12, F10, F2
F12, -16 (R1)
F14, -24 (R1)
F16, F14, F2
F16, -24 (R1)
R1, R1, #-32
R1, R2, LOOP
// drop DADD & BNE
// drop DADD & BNE
// drop DADD & BNE
13
Tecniche di base: loop unrolling
•  Ignoriamo per un momento il fatto che il compilatore abbia anche
dovuto gestire una forma di rinominazione dei registri.
•  Se il codice del lucido precedente viene eseguito così com’è,
l’esecuzione richiede 28 cicli di clock, a causa delle latenze tra le
istruzioni , che impongono alcuni stall della pipeline. Dalla tabella
vista infatti, abbiamo:
–  1 ciclo di clock di stall tra ogni LD e la relativa FADD
–  2 cicli di clock di stall ogni FADD e la relativa SD
–  1 ciclodi clock di stall tra la DADD e la BNE
•  come risultato, ora ogni iterazione del for dura in media 7 cicli di
clock: meglio della situazione iniziale, ma peggio della tecnica di
14
pipeline scheduling appena vista.
Tecniche di base:
loop unrolling & pipeline scheduling
•  l’eliminazione di alcuni branch attraverso il loop unrolling permette di
considerare parte di un unico macrociclo istruzioni che prima
appartenevano a iterazioni successive del for.
•  Inoltre, la rinominazione dei registri ha generato, all’interno del
macrociclo, un maggior numero di operazioni fra loro indipendenti,
che possono essere riordinate in modo vantaggioso.
•  In altre parole, possiamo cercare di combinare il loop unrolling e il
pipeline scheduling per ottimizzare ulteriormente il codice.
15
5
loop unrolling & pipeline scheduling
LD
LD
LD
LD
FADD
FADD
FADD
FADD
SD
SD
DADD
SD
BNE
SD
F0, 0 (R1)
F6, -8 (R1)
F10, -16 (R1)
F14, -24 (R1)
F4, F0, F2
F8, F6, F2
F12, F10, F2
F16, F14, F2
F4, 0 (R1)
F8, -8 (R1)
R1, R1, #-32
F12, 16 (R1)
R1, R2, LOOP
F16, 8 (R1)
ecco come ora le istruzioni
srotolate (loop unrolling)
possono essere riordinate
(pipeline scheduling) per
eliminare tutti gli stall presenti
lo spostamento di
queste istruzioni serve
per eliminare gli
ultimi due stall
// 8 – 32 = -24 (?)
16
Tecniche di base:
loop unrolling & pipeline scheduling
•  Con un po’ di pazienza, si può verificare che questo codice è
equivalente all’esecuzione di quattro iterazioni del for iniziale.
•  Ma ora, 4 iterazioni successive del for iniziale vengono eseguite in 14
cicli di clock, ossia 3,5 cicli di clock per iterazione, contro i 10 della
versione iniziale
17
Tecniche di base di compilazione
•  Un compilatore dotato di sofisticate tecniche di analisi è in grado di
produrre codice ottimizzato come abbiamo visto nell’esempio
precedente, usando le informazioni sulla microarchitettura per cui il
codice deve essere generato.
•  Ciò si paga evidentemente con un maggior tempo necessario per
generare codice così ottimizzato.
•  Ma si può pagare anche in termini di prestazioni del codice in
esecuzione, se viene fatto girare su macchine con lo stesso ISA ma
microarchitetture diverse. Ad esempio, tempi diversi per la pipeline.
•  Secondo voi, su altre architetture (ma stesso ISA), il codice
ottimizzato potrebbe addirittura non funzionare correttamente?
18
6
Tecniche di base di compilazione
•  In più vi sono vari problemi che abbiamo volutamente ignorato, ma
che il compilatore deve considerare:
–  quanti nomi di registri diversi si possono usare nel loop unrolling?
(ossia quanti ne sono disponibili a livello ISA?) Se si esauriscono
tutti i registri, può essere necessario usare la RAM come deposito
temporaneo, il che è molto inefficiente.
–  Come si possono gestire i loop quando non si sa a priori quante
volte saranno eseguiti (ad esempio, un while-do o un repeat-until)?
–  Il loop-unrolling genera codice più lungo di quello originale.
Quindi aumenta la probabilità di cache miss nella Instruction
Memory, eliminando parte dei vantaggi dell’unrolling.
19
Multiple issue statico
•  Tralasciando questi e altri problemi, i vantaggi che ci possono essere
da uno sfruttamento dell’ILP a livello di compilazione sono ancora
maggiori nel caso di processori multiple issue.
•  Consideriamo di nuovo la versione MIPS superscalare che avevamo
usato in un esempio del capitolo precedente, che era in grado di
lanciare due istruzioni per ciclo di clock:
–  una operazione di load / store / branch / integer ALU e
–  una qualsiasi operazione FP
•  Supponiamo che l’unrolling dell’esempio precedente sia stato fatto
per 5 cicli, e assumiamo le stesse latenze tra le istruzioni riportate
nella tabella del lucido 7.
20
Multiple issue statico
•  Ecco il risultato dell’esecuzione: sono necessari 12 cicli di clock, con
2,5 cicli di clock per ciclo del for, rispetto ai 3,5 dello stesso
processore senza multiple issue (H-P3, Fig. 4.2):
loop:
int. instruction
FP instruction
LD F0, 0 (R1)
clock cycle
1
LD F6, -8 (R1)
2
LD F10, -16 (R1)
FADD F4, F0, F2
3
LD F14, -24 (R1)
FADD F8, F6, F2
4
LD F18, -32 (R1)
FADD F12, F10, F2
5
SD F4, 0 (R1)
FADD F16, F14, F2
6
SD F8, -8 (R1)
FADD F20, F18, F2
7
SD F12, -16 (R1)
8
DADD R1, R1, #-40
9
SD F16, 16 (R1)
10
BNE R1, R2, Loop
11
SD F20, 8 (R1)
12
21
7
Multiple issue statico:
l’approccio VLIW
•  Nei processori superscalari, che implementano l’ILP dinamico, il
numero di istruzioni da avviare per ciclo di clock viene deciso a run
time. Questi processori usano compilatori meno sofisticati, ma hanno
bisogno di più hardware, per minimizzare le alee e massimizzare il
numero di istruzioni che avviano all’esecuzione.
•  I processori con multiple issue statico invece, avviano un numero
prefissato di instruzioni da eseguire, ed è responsabilità del
compilatore presentare le istruzioni alla CPU in un ordine adatto a
massimizzare le prestazioni, usando le tecniche appena viste (e altre
più sofisticate)
•  Di fatto, il compilatore genera una serie di pacchetti contententi un
numero prefissato di istruzioni ciascuno (anche se, eventualmente,
22
alcune istruzioni posso essere delle no-op).
Multiple issue statico:
l’approccio VLIW
•  Ognuno di questi issue packet, contiene istruzioni fra loro
indipendenti, che possono quindi essere eseguite in parallelo nella
pipeline.
•  E’ il compilatore che genera i pacchetti riordinando le istruzioni
(come nell’esempio visto), verificando ed eliminando le dipendenze,
per cui il lavoro non deve più essere fatto dalla CPU.
•  La CPU ha quindi una architettura più semplice, e la fase di issue
delle istruzioni può avvenire in minor tempo, perché non è più
necessario controllare a run-time eventuali dipendenze fra le
istruzioni: questo lavoro è già stato fatto da compilatore.
23
Multiple issue statico:
l’approccio VLIW
•  Questo approccio prende il nome di VLIW (Very Long Instruction
Word), in quanto le prime architetture che lo adottavano (inzio anni
‘80), usavano in realtà istruzioni macchina molto lunghe (128 bit o
più) ognuna delle quali specificava più operazioni fra loro
indipendenti che potevano essere eseguite in parallelo dalla CPU.
•  Il termine EPIC (Explicitly Parallel Instruction Computer) usato
dall’Intel nel contesto dell’architettura IA-64 si riferisce allo stesso
approccio.
24
8
Multiple issue statico:
l’approccio VLIW
•  Quanto più è alto il numero di istruzioni che un processore può
avviare contemporaneamente, tanto più l’approccio VLIW è
vantaggioso.
•  Infatti, l’overhead che un processore superscalare deve sopportare per
controllare a run-time le dipendenze fra le istruzioni da avviare in
parallelo cresce quadraticamente col numero di istruzioni. (ogni
istruzione deve essere confrontata con tutte le altre potenzialmente
avviabili)
25
l’approccio VLIW: un esempio
•  Consideriamo un processore VLIW che possa avviare 5 istruzioni
contemporaneamente, con le seguenti unità funzionali:
–  una unità intera (ALU) in grado di gestire anche i branch
–  due unità floating point
–  due unità per i riferimenti in memoria
•  Naturalmente, per sfruttare a pieno queste unità il codice da eseguire
deve manifestare sufficiente parallelismo tra le istruzioni, e il
compilatore deve essere in grado di metterlo in evidenza, con le
tecniche di loop unrolling e pipeline scheduling viste in precedenza.
•  Consideriamo l’esempio già visto, assumendo un unrolling di 7 cicli
del for. Ecco come potrebbe essere eseguito il codice, suddiviso in
pacchetti indipendenti dal compilatore e eseguiti dalla CPU
26
l’approccio VLIW: un esempio
H-P3, Fig 4.5:
pack
et /
n.
clock
memory ref. 1
memory ref. 2
LD F6,-8(R1)
FP op. 1
FP op. 2
integer / branch
op.
1
LD F0,0(R1)
no-op
no-op
no-op
2
LD F10,-16(R1) LD F14,-24(R1)
no-op
no-op
no-op
3
LD F18,-32(R1) LD F22,-40(R1)
FADD F4,F0,F2
FADD F8,F6,F2
no-op
4
LD F26,-48(R1) no-op
FADD F12,F10,F2
FADD F16,F14,F2
no-op
5
no-op
no-op
FADD F20,F18,F2
FADD F24,F22,F2
no-op
6
SD F4,0(R1)
SD F8,-8(R1)
FADD F28,F26,F2
no-op
no-op
7
SD F12,-16(R1)
SD F16,-24(R1)
no-op
no-op
DADD R1,R1,#-56
8
SD F20,24(R1)
SD F24,16(R1)
no-op
no-op
no-op
9
SD F28,8(R1)
no-op
no-op
no-op
BNE R1,R2,Loop
27
9
l’approccio VLIW: un esempio
•  Notiamo alcune cose:
•  non tutti gli slot di ogni pacchetto sono occupati, e vengono riempiti
da no-op. A seconda del codice e del tipo di architettura, non è sempre
possibile sfruttare tutti gli slot di ogni pacchetto. Nel nostro esempio
circa il 60% degli slot viene sfruttato.
•  Ci vogliono 9 cicli di clock per eseguire 7 cicli del for, con una media
di 9/7 = 1.29 cicli di clock per ciclo del for.
•  Come già osservato in precedenza, una macchina con architettura
diversa (ad esempio, diverse U.F. o diverse latenze per istruzione),
fornirebbe prestazioni diverse eseguendo lo stesso codice.
28
Tecniche più sofisticate
•  Naturalmente, l’approccio VLIW usa anche tecniche di compilazione
più sofisticate di quelle viste per mettere in evidenza in fase di
compilazione l’ILP. Tra queste ricordiamo:
–  Static branch prediction. Assume che i branch abbiano sempre
un certo tipo di comportamento, o analizza il codice per cercare di
dedurne il comportamento
–  Loop Level Parallelism. Tecniche per evidenziare il parallelismo
in iterazioni successive di un loop, quando i vari cicli non sono
indipendenti fra loro
–  Symbolic loop unrolling. Il loop non viene “srotolato”, ma si
cerca di mettere in ogni pacchetto istruzioni fra loro indipendenti,
anche appartenenti a cicli diversi
–  Global code scheduling. Cerca di compattare codice proveniente
da diversi basic block (quindi istruzioni separate da varie istruzioni
condizionali, inclusi i cicli) in sequenze di istruzioni indipendenti
29
Supporti hardware all’ILP statico:
istruzioni predicative
•  le tecniche usate dal compilatore per mettere in evidenza l’ILP
funzionano bene soprattutto quando il comportamento dei branch è
facilmente predicibile (come ad esempio nei cicli for).
•  Quando il comportamento dei branch non è ben chiaro invece, le
dipendenze dal controllo limitano fortemente la possibilità di sfruttare
a fondo il parallelismo fra istruzioni.
•  Per limitare questo problema è di estendere l’insieme di istruzioni
macchina aggiungendo un insieme di istruzioni predicative o
condizionali.
30
10
Supporti hardware all’ILP statico:
istruzioni predicative
•  Queste istruzioni possono essere usate per eliminare alcuni branch,
convertendo una dipendenza dal controllo in una dipendenza dai dati,
e aumentando così potenzialmente le prestazioni del processore.
•  Di fatto le istruzioni predicative sono utili anche per le tecniche di ILP
dinamico, perché in ogni caso permettono di eliminare alcuni branch.
31
istruzioni predicative o condizionali
•  Nota: nel seguito useremo indifferentemente le espressioni istruzione
predicativa e istruzione condizionale.
•  Una istruzione predicativa è una istruzione che contiene una
condizione che viene valutata come parte dell’esecuzione
dell’istruzione stessa.
–  se la condizione è vera il resto dell’istruzione viene eseguito
normalmente.
–  se la condizione è falsa l’istruzione viene trasformata in una no-op.
•  Molte architetture recenti contengono una qualche forma di istruzione
condizionale.
32
istruzioni predicative o condizionali
•  l’esempio più semplice di istruzione predicativa è la move
condizionale: sposta il contenuto di un registro in un’altro se la
condizione associata è vera. Una tale istruzione si può usare per
eliminare i branch in alcuni casi.
•  Consideriamo l’istruzione C “if (A == 0) S = T;” e assumiamo che
R1, R2, R3 contengano rispettivamente i valori di A, S, e T. Il codice
può essere convertito nelle seguenti istruzioni MIPS:
BNEZ R1, Jump
// branch if not zero
ADD R2, R3, R0
// R0 always contains 0
Jump:
33
11
istruzioni predicative o condizionali
•  Usando invece una move condizionale, che viene completata solo se il
terzo operando è uguale a zero, l’if potrebbe essere tradotto nella
seguente istruzione:
CMOVZ R2, R3, R1
// mov R3 in R2 if R1 == 0
•  Notate che la dipendenza sul controllo certa (la ADD dipende dalla
BNEZ) viene così trasformata in una dipendenza sui dati solo
eventuale, dipendentemente dalle istruzioni che precedono la
CMOVZ.
•  Eliminare questi tipi di branch può avere un effetto notevole sulle
prestazioni delle pipeline reali, in cui l’esecuzione del branch richiede
molti cicli di clock. Infatti, tali branch non sono facilmente predicibili
e il più delle volte non lo sono affatto: una qualsiasi forma di
34
predizione rischia di sbagliare nel 50% dei casi!
istruzioni predicative o condizionali
•  Nei processori multiple issue poi, è possibile che più branch possano
dover essere eseguiti in un unico ciclo di clock, ma la predizione dei
branch diviene ancora più aletoria, perché i branch possono dipendere
l’uno dall’altro.
if (A == B) {A = A+1} else if (C == D) {C = C+1}
in questo esempio, il secondo if dipende dal primo, ed è possibile
che tutte le istruzioni vengano avviate nello stesso ciclo di clock.
Come si fa a sapere se eseguire o no il secondo if, mentre si sta
valutando ancora il primo?
•  per risolvere il problema, molte architetture non permettono l’avvio di
più branch in un unico ciclo di clock.
•  Le move condizionali permettono di eliminare alcuni branch,
aumentando così l’issue rate della CPU.
35
istruzioni predicative o condizionali
•  Ad esempio, ecco come del codice controllato da un if-then-else (a)
può essere trasformato in codice macchina con due salti (b) o in
quattro istruzioni predicative (c) (Tanenbaum, Fig. 5.52):
36
12
istruzioni predicative o condizionali
•  Le semplici move condizionali non permettono però di eliminare i
branch che controllano blocchi di istruzioni diverse dalle move.
•  Per questo, alcune architetture supportano la full predication: tutte le
istruzioni possono essere controllate da un predicato.
•  per funzionare correttamente, queste architetture hanno bisogno di
opportuni registri predicativi (ciascuno formato da un solo bit), che
memorizzano il risultato di test effettuati da istruzioni precedenti, in
modo che il valore possa essere usato per controllare l’esecuzione di
istruzioni successive (che quindi divengono predicative).
37
istruzioni predicative o condizionali
•  Ad esempio, nell’Itanium, sono disponibili dei registri predicativi
usati a coppie (P1, P2, ...) e delle istruzioni per settare tali registri.
•  Ad esempio, “CMPEQ R1, R2, P4” setta P4 = 1 e P5 = 0 se R1 ==
R2. Altrimenti, l’istruzione setta P4 = 0 e P5 = 1.
•  I registri predicativi sono poi usati per controllare l’esecuzione di
altre istruzioni. Ecco un esempio (Tanenbaum, Fig. 5.53):
38
istruzioni predicative o condizionali
•  In generale, le istruzioni predicative sono particolarmente utili per
implementare piccoli if-then-else eliminando branch difficilmente
predicibili e quindi per semplificare le tecniche di ILP statico più
sofisticate.
•  L’utilità della predicazione è comunque limitata da alcuni fattori:
–  le istruzioni predicative poi annullate hanno comunque utilizzato
risorse della CPU, limitando l’esecuzione di altre istruzioni.
–  Combinazioni complesse di branch non sono facilmente
convertibili in istruzioni condizionali
–  le istruzioni condizionali possono essere più lente delle
corrispondenti non condizionali
39
13
istruzioni predicative o condizionali
•  Per queste ragioni, molte architetture usano solo alcune semplici
istruzioni condizionali, e in particolare la move condizionale.
•  Le architetture delle macchine MIPS, SPARC, Alpha, PowerPC,
Pentium, dual core e successivi, supportano la move condizionale.
•  l’architettura IA-64 supporta la full predication.
40
ILP statico vs ILP dinamico
•  Inizialmente molto differenti fra loro, i due approcci all’ILP si sono
fra loro avvicinati con lo sviluppo della tecnologia software e
hardware.
•  In ogni caso, gli approcci dinamici all’ILP sembrano più adatti ai
processori general purpose, dove ci si può permettere un hardware più
complesso, e quindi costi e consumi maggiori.
•  Al contrario, l’ILP statico rimane fondamentale nei processori per
applicazioni embedded, dove è più importante che il processore
consumi poco, e dove i programmi da usare sono spesso limitati e
possono essere sviluppati in modo da poter sfruttare al massimo il
parallelismo tra istruzioni usando appunto le tecniche dell’ILP statico.
41
L’architettura IA-64: l’Itanium II
•  “Intel is rapidly getting to the point where it has just squeezed every
last drop of juice out of the IA-32 ISA and the Pentium 4 line of
processors”
A. Tanenbaum, Structured
Computer Architecture, 5th ed.
•  Alla fine degli anni ‘90, in previsione di raggiungere quel punto l’Intel
si è mossa in due direzioni:
1 
Sviluppo dell’ISA e della microarchitettura Intel 64
2 
dal 2000 insieme all’Hp, sviluppo di un ISA e di una
microarchitettura completamente nuova, nota come IA-64
42
14
L’architettura IA-64: l’Itanium II
• 
L’Itanium e l’Itanium II sono i primi processori Intel
completamente RISC, e sono basati sull’ISA noto come IA-64.
• 
L’ISA IA-64 non è compatibile con la vecchia IA-32 e con la nuova
Intel 64.
• 
Intel chiama EPIC la tecnologia usata per sfruttare l’ILP
combinando le caratteristiche dell’architettura hardware con la
compilazione dei programmi tipica dell’IA-64.
43
L’architettura IA-64: l’Itanium II
• 
L’archiettura IA-64, nell’implementazione dell’Itanium II ha le
seguenti caratteristiche:
– 
128 registri general-purpose a 64 bit lunghi ciascuno 65 bit (il bit
in più – poison bit – viene usato per gestire le eccezioni)
– 
128 registri floating point a 82 bit (è lo standard IEEE per il FP)
– 
64 registri predicativi da 1 bit ciascuno
– 
128 registri “speciali” usati per vari scopi (passaggio dei
parametri per le system call del SO, memory mapping, controllo
del sistema, registrazione delle performance della CPU, ecc.)
44
L’architettura IA-64: l’Itanium II
• 
dei 128 registri general purpose, i primi 32 sono sempre disponibili,
gli altri 32-128 sono usati come stack di registri : ad ogni procedura
chiamata viene assegnato un sottoinsieme di questi stack register.
• 
L’Itanium II ha 3 livelli di cache, e viene prodotto in diverse
configurazioni multi-core, con le seguenti caratteristiche:
– 
CPU Tukwilla (2010): tecnologia a 65 nm, clock, fino a
1.73GHz, cache L3 fino a 24MB, fino a 4 core, Hyper-threading,
circa 2 miliardi di transistors
– 
CPU Poulson (dal 2012): tecnologia a 32 nm, cache L3 fino a
32 MB, fino a 8 core, Hyper-threading, circa 3 miliardi di
transistors (fonte: AnandTech)
45
15
L’architettura IA-64: l’Itanium II
• 
L’architettura IA-64 prevede 5 tipi di unità funzionali per
l’esecuzione delle istruzioni (H-P3, Fig. 4.11):
Exec. unit Instr. description
type
I-unit
M-unit
F-unit
B-unit
L+X
example instr.
A
Integer ALU
add, sub, and, or, compare
I
non-ALU integer
int./ multimedia shift, bit test, moves
A
Integer ALU
add, sub, and, or, compare
M
Memory access
load / store for integer and FP registers
F
Floating Point
floating point Intructions
B
Branches
cond. branches, call, loop branches
L+X Extended
extended immediate, stop, no-ops
46
L’architettura IA-64: l’Itanium II
• 
L’architettura IA-64 sfrutta l’approccio VLIW aggiungendo però
una certa flessibilità nella formattazione delle istruzioni negli issuepackets.
• 
Il compilatore di una architettura IA-64 inserisce le istruzioni in
instruction groups: una sequenza di istruzioni indipendenti fra loro
che:
– 
non confliggono nell’uso delle unità funzionali
– 
non confliggono nell’uso dei registri
– 
non hanno dipendenze di tipo RAW e WAW
– 
hanno un numero limitato di dipendenze di tipo WAR
47
L’architettura IA-64: l’Itanium II
• 
La CPU è libera di schedulare le istruzioni all’interno di un group
come preferisce, e quindi, per quanto possibile, di eseguirle in
parallelo.
• 
Instruction group consecutivi vengono invece eseguiti in maniera
sequenziale, sebbene la CPU possa decidere di inziare l’esecuzione
di un gruppo prima che tutte le istruzioni del precedente siano
terminate, se la cosa non crea conflitti.
• 
Ogni gruppo contiene un numero arbitrario di istruzioni, ma il
compilatore deve indicare esplicitamente il limite fra un gruppo e il
successivo, usando una istruzione speciale chiamata stop.
48
16
L’architettura IA-64: l’Itanium II
• 
Le istruzioni dell-IA-64 Itanium II sono organizzate in bundle
lunghi 128 bit. Ogni bundle contiene 3 istruzioni da 41 bit e un
campo template di 5 bit (Tanenbaum, Fig. 5.50).
49
L’architettura IA-64: l’Itanium II
• 
• 
I 5 bit del template di un bundle servono per specificare:
– 
quali unità saranno usate dalle istruzioni contenute nel bundle
– 
l’eventuale presenza di uno stop in un qualche punto del bundle
Ad esempio, se il template di un bundle vale 10, indica che il bundle
contiene: M – stop – M – I . Ossia:
– 
la prima istruzione usa un’unità M
– 
finisce un instruction group e ne incomincia un altro (notate
quindi che un bundle può stare a cavallo di due group)
– 
La seconda istruzione usa di nuovo una unità M
– 
la terza istruzione usa un’unità I
50
L’architettura IA-64: l’Itanium II
51
17
L’architettura IA-64: l’Itanium II
• 
Nell’architettura IA-64 sono definiti più di 100 tipi di istruzioni.
Ognuna è lunga 41 bit, così suddivisi:
• 
Operation group (4 bit): specifica il tipo di istruzione
• 
Operation type (10 bit): specifica l’operazione richiesta
• 
Registers (3 x 7 bit): specifica i 3 registri usati
• 
Predicate register (6 bit) specifica il predicate register a cui è
associata l’istruzione per gestire la predicazione
• 
I registri predicativi vengono settati usando istruzioni di
comparazione. Ad esempio, CMPEQ R1,R2,P4 setta P4 a true e P5
a false se R1=R2 (e viceversa se R1 <> R2)
52
L’architettura IA-64: l’Itanium II
• 
Oltre alla full predication, l’Itanium II supporta una forma limitata
di speculazione attraverso le load speculative: le advanced load.
• 
Come noto, una load può produrre un lungo stall della pipeline se il
dato indirizzano non è presente in cache. Le istruzioni che usano
quel dato devono attendere il suo arrivo prima di poter passare alla
fase EX.
• 
Il compilatore è allora libero di spostare “indietro” la load, in modo
che venga eseguita prima di quando il dato prelevato dalla load
stessa dovrà essere usato da un’altra istruzione.
• 
L’idea è di dare alla load il tempo necessario a prelevare il dato –
anche se questo si trova in RAM – di modo che questo sia
sicuramente presente nel registro di destinazione della load quando
53
dovrà essere usato da altre istruzioni.
L’architettura IA-64: l’Itanium II
• 
Supponiamo dunque che la load venga spostata indietro di un certo
numero di istruzioni. Tra queste istruzioni “saltate” potrebbe
trovarsi una store, che nella versione originale del programma
sarebbe stata eseguita prima della load. Tuttavia, dopo lo
spostamento operato dal compilatore questa store verrà eseguita
dopo la load. E se vi fosse una dipendenza tra le due istruzioni?
• 
Una advanced load (LDA) è una load che è stata
speculativamente spostata prima di una store da cui potrebbe
potenzialmente dipendere.
• 
A run time, quando viene eseguita una LDA viene creata una nuova
entry in una tavola speciale detta ALAT. La entry creata contiene:
• 
il numero del registro di destinazione della load
• 
l’indirizzo della locazione di memoria usata dalla load (che,
54
appunto, in generale è noto solo a run time)
18
L’architettura IA-64: l’Itanium II
• 
Quando viene eseguita una STORE viene fatto anche un controllo
associativo (tutte le entry vengono controllate in parallelo)
sull’ALAT.
• 
Se una entry ha lo stesso indirizzo di memoria usato dalla STORE,
quella entry è marcata come invalida.
• 
Prima che una qualsiasi istruzione usi il registro caricato da una
LDA, l’entry della ALAT contenente quel registro viene controllata.
• 
Se la entry è valida, la speculazione sulla load ha avuto successo, e
l’entry dell’ALAT viene azzerato.
• 
Se la entry non è valida, la LOAD viene rieseguita.
55
L’architettura IA-64: l’Itanium II
• 
Come esempio, consideriamo la seguente situazione, in cui il
compilatore decide di spostare indietro la LD, di modo che quando
la MUL verrà eseguita, il contenuto della cella di RAM di indirizzo
0 (R1) sia già disponibile in R2.
• 
Nel caso peggiore, 0 (R1) dovrà essere letto
dalla RAM: il compilatore sa che sono
necessari N cicli di clock per una lettura in
RAM, e sposta all’indietro la LD di tante
istruzioni quante ne sono necessarie a far
passare Almeno N cicli di clock
• 
Supponiamo che, in questo spostamento, la
LD venga spostata prima di una SD
...
ADD
MUL
ADD
SD
...
...
LD
MUL
...
R6, R20, R30
R11, R6, R4
R10, R15, R25
R11, 8 (R10)
...
...
R2, 0 (R1)
R3, R2, R4
56
L’architettura IA-64: l’Itanium II
• 
Il compilatore non può sapere se vi è una relazione tra la SD e la
LD: le due istruzioni sono legate se fanno riferimento alla stessa
cella di RAM, ossia se 8 (R10) = 0 (R1) ma, in generale, questo si
può sapere solo a run time.
• 
se 8 (R10) = 0 (R1), questo vuol dire che,
nel programma, la MUL deve usare per
uno dei suoi argomenti il valore calcolato
dalla “MUL R11, R6, R4”, immagazzinato
temporaneamente all’indirizzo 8 (R10).
• 
Ma con lo spostamento della LD, la MUL
userebbe invece il valore contenuto in
0 (R1) prima che in quella cella sia stato
scritto il risultato della “MUL R11, R6,
R4”
...
ADD
MUL
ADD
SD
...
...
LD
MUL
...
R6, R20, R30
R11, R6, R4
R10, R15, R25
R11, 8 (R10)
...
...
R2, 0 (R1)
R3, R2, R4
57
19
L’architettura IA-64: l’Itanium II
• 
Il compilatore allora, esegue lo spostamento della LD, ma la
trasforma in una advanced load (LDA).
• 
Quando la LDA viene eseguita, nella ALAT
vengono scritti il nome del registro, R2, e il
valore dell’indirizzo della load, 0 (R1).
• 
Quando viene eseguita la SD, viene
confrontato l’indirizzo che usa con tutti gli
indirizzi nella ALAT. Se c’è un match,
l’entry della ALAT viene invalidata.
• 
All’issue della MUL, poiché R2 occorre
nella ALAT, se l’entry di R2 è invalida la
“LD R2, 0 (R1)” viene rieseguita prima di
eseguire la MUL. In ogni caso, l’entry della
ALAT viene cancellata.
...
ADD
MUL
LDA
ADD
SD
...
...
MUL
...
R6, R20, R30
R11, R6, R4
R2, 0 (R1)
R10, R15, R25
R11, 8 (R10)
...
...
R3, R2, R4
ALAT
R2
0 (R1)
i/v
58
L’architettura IA-64: l’Itanium II
• 
L’Itanium II ha una pipeline di 8 stage (contro le 10 dell’Itanium) e
11 unità funzionali pipelined che gli permettono di avere
contemporaneamente in esecuzione fino a 13 istruzioni.
• 
Può avviare fino a 6 istruzioni per ciclo di clock, che diventeranno
12 nella versione Poulson.
• 
Implementa una esecuzione in-order delle istruzioni, ma
implementa alcune caratteristiche tipiche dell’ILP dinamico:
• 
branch prediction
• 
speculazione
59
L’architettura IA-64: l’Itanium II
• 
Itanium è certamente un progetto controverso, già nel 2005 si
parlava del suo abbandono, a causa dei costi elevati del processore,
e della sua diffusione limitata solo per applicazioni di fascia alta.
• 
Le prestazioni dell’Itanium poi sono sempre più avvicinate dai
sistemi multi-core basati su ISA Intel 64, e che costano meno
potendo contare su una economia di scala più marcata.
60
20
L’architettura Trimedia TM32
•  Abbiamo detto all’inizio di questo capitolo che l’ILP statico è
particolarmente adatto per le applicazioni embedded, dove non ci si
può permettere un hardware troppo complesso / costoso / ad elevato
consumo di energia
•  Un classico esempio di processore VLIW è il TriMedia TM32,
progettato dalla Philips e usato per applicazioni multimediali in lettori
e registatori CD, DVD, MP3 players, videocamere digitali, televisori.
•  E’ quindi un processore dedicato per applicazioni molto specifiche, al
contrario di un processore come l’Itanium II.
61
L’architettura Trimedia TM32
•  Il TM32 ha un clock compreso tra 266 e 300 MHZ, e esegue istruzioni
VLIW ciascuna delle quali può specificare fino a 5 operazioni distinte
che possono essere avviate ad ogni colpo di clock. Alcuni degli slot
possono contenere delle no-op (Tanenbaum, Fig. 8.3).
62
L’architettura Trimedia TM32
•  il TM3260 possiede 10 tipi di UF pipelined, più l’unità FP sqrt/div.
non pipelined (Tanenbaum, Fig. 8.4):
63
21
L’architettura Trimedia TM32
•  Il TM3260 ha 128 registri general-purpose a 32 bit, + 4 registri
speciali (PC, PSW, 2 registri per gestire gli interrupt)
•  Supporta la predicazione di tutte le istruzioni, associandole ad un
registro che, se vale 0 ne annulla l’esecuzione.
•  Non esegue nessun controllo a run-time per verificare se le operazioni
inserite in una istruzione, e le operazioni di istruzioni eseguite
consecutivamente sono compatibili: semplicemente le esegue.
•  E’ infatti responsabilità del compilatore schedulare le operazioni in
ogni istruzione, e le diverse istruzioni in modo da limitare al massimo
gli stall delle pipeline e massimizzare l’uso delle diverse U.F.
64
L’architettura Trimedia TM32
•  In questo modo, si può limitare la complessità dell’hardware, e usare
compilatori per generare codice estremamente ottimizzato per
quell’hardware (del resto, il compilatore ha tutto il tempo che vuole...)
•  l’unico vero difetto di questo approccio è che il codice generato
occupa comunque molto più spazio di un codice equivalente per un
generico processore RISC
•  Per questa ragione, il codice che deve girare su questi processori
(tipicamente memorizzato in ROM) è compresso: solo quando
vengono prelevate dalla cache per essere eseguite le istruzioni
vengono decompresse.
•  Anche così, il codice compresso occupa circa il doppio dello spazio
che occuperebbe un codice identico per un generico processore RISC
65
(prossimo lucido: H-P3, Fig. 3.23)
approcci usati in CPU multiple-issue
name
issue
structure
hazard
detection
scheduling
chracteristic
examples
Superscalar
(static)
dynamic
hardware
static
in-order
execution
Sun
UltraSPARC
II/III
Superscalar
(dynamic)
dynamic
hardware
dynamic
some out-oforder
execution
IBM Power2
Superscalar
(speculative)
dynamic
hardware
dynamic with
speculation
out-of-order
execution with
speculation
Intel CPUs,
MIPS R10K,
Alpha 21264,
HP PA 8500,
IBM RS64III
VLIW/LIW
static
software
static
no hazards
between issue
packets
Trimedia, i860
EPIC
mostly static
mostly
software
mostly static
explicit
dependencies
marked by
compiler
Itanium,
Itanium II
66
22