Tecniche di parallelismo, processori RISCunina.stidue.net/CalcolatoriElettronici2_DMCA... ·...
Transcript of Tecniche di parallelismo, processori RISCunina.stidue.net/CalcolatoriElettronici2_DMCA... ·...
-
09.a
Tecniche di parallelismo, processori RISCTecniche di parallelismo, processori RISC
Pipelining Pipelining Altre tecniche di parallelismoAltre tecniche di parallelismo
Processori superscalariProcessori superscalariCaratteristiche dei processori RISCCaratteristiche dei processori RISC
Esempi di processori RISCEsempi di processori RISC
Testo di riferimento: [Congiu] – 9.1-9.3 (pg. 253–264)
1
Architettura degli Elaboratori © 2009
32
Fasi per elaborazione di un istruzioneFasi per elaborazione di un istruzioneIF (Instruction Fetch)● Lettura dell'istruzione da memoria, incremento PC
ID (Instruction Decode)● Decodifica istruzione e prelievo operandi da registri
EX (Execution)● Esecuzione dell'istruzione
MEM (Memory)● Accesso in memoria (scrittura o lettura, solo per certe
istruzioniWB (Write Buffer)● Scrittura del risultato nel registro opportuno (register file)
-
2
Architettura degli Elaboratori © 2009
32
PipeliningPipelining
Se le fasi sono eseguite da sezioni indipendenti di hardware, possono essere tutte contemporaneamente attive (su istruzioni diverse)
Dopo il transitorio: istruzione completata ad ogni stadiotransitorio
3
Architettura degli Elaboratori © 2009
32
Hardware in piHardware in piùù
Nuovi registri fra ogni stadio del pipeline per memorizzare i risultati parziali di ogni ciclo.
-
4
Architettura degli Elaboratori © 2009
32
EvoluzioneEvoluzione
5
Architettura degli Elaboratori © 2009
32
Se le 4 fasi sono eseguite da 4 sezioni indipendenti di hardware, possono essere tutte 4 contemporaneamente attive (su istruzioni diverse):
Pipelining: esempio numericoPipelining: esempio numerico
Da T3 in poi viene completata una istruzione ogni 20 ns.
-
6
Architettura degli Elaboratori © 2009
32
Il tempo richiesto per l’esecuzione di un programma di N istruzioni con la tecnica del pipelining descritta nella figura precedente èpari a:
TE = 80 + 20 × (N - 1) ns
Senza pipeline il tempo necessario sarebbe:TE = 80 × N ns
Per N abbastanza grande, il pipeline riduce il tempo di esecuzione di un fattore 4.
Pipelining: vantaggiPipelining: vantaggi
7
Architettura degli Elaboratori © 2009
32
Pipelining: fattore di Pipelining: fattore di speedspeed--upupFattore di speedup SK: indica quanto più veloce l’uso di un pipeline rende l’esecuzione di un programma (ovvero di quanto viene ridotto il tempo di esecuzione), rispetto al caso in cui il pipeline sia assente:● TK = tempo di esecuz. di N istruzioni con pipeline di k fasi,● T1 = tempo di esecuz. di N istruzioni senza pipeline;
fattore di speedup SK:SK = T1/TK = (NkT ) / [kT + (N-1)T ] = Nk / (k+N-1 )● k = numero di fasi del pipeline,● T = tempo di esecuzione di una fase.● Per N grande, SK tende ad essere uguale a k.
quando k è grande (> 8) il processore si dice superpipelined.
-
8
Architettura degli Elaboratori © 2009
32
SuperPipelineSuperPipeline
Incremento della lunghezza del pipeline per aumentare la velocità di esecuzione del singolo stadio (riduzione tk)Se lo stadio ALU ha una durata superiore rispetto agli altri moduli, considero stadi ALU separati per ridurre il tempo sprecato dagli stadi più breviÈ necessaria una unità di controllo più complicata per gestire il pipeline e gli “inceppamenti”
Intel Pentium 4 - superpipeline con 20 stadi
9
Architettura degli Elaboratori © 2009
32
Il fattore di speedup Sk è un valore teorico raggiunto solo se il pipeline opera, a regime, avviando sempre, ad ogni periodo del clock, una nuova istruzione (e completandone una):in realtà il pipeline può incepparsi (subire un pipeline stall ) per problemi dovuti a:●accessi alla memoria (cache miss),●conflitti dei dati (data hazard),●conflitti di salto (branch hazard);
in conseguenza a questi stall, il fattore di speedup si riduce.
Inceppamento del pipelineInceppamento del pipeline
-
10
Architettura degli Elaboratori © 2009
32
Le fasi di fetch e di accesso a operandi/risultati hanno una durata pari alle altre fasi (un periodo di clock), solo se gliaccessi alla memoria si risolvono nella cache (cache hit).In caso di cache miss, l’operazione può richiedere 2 o 3 periodi di clock; di conseguenza il pipeline si inceppa (subisce uno stall ) e l’esecuzione delle istruzioni viene ritardata, come indicato nel seguente diagramma temporale:
Cache missCache miss
11
Architettura degli Elaboratori © 2009
32
Data hazard (conflitto dei dati): si verifica quando gli operandi di una istruzione sono i risultati dell’istruzione precedente;in tal caso l’esecuzione dell’istruzione non può procedere e l’esecuzione subisce un ritardo (pipeline stall) (di 2 periodi di clock nell’esempio di figura):
Data Data hazardhazard
-
12
Architettura degli Elaboratori © 2009
32
I data hazard possono essere evitati dal compilatore, con un riordino delle istruzioni (per eseguire altre istruzioni prima di quella cui servono i dati);le conseguenze negative di un data hazard possono essere ridotte dal processore, con la tecnica del by-pass (detta anche data-forwarding): i risultati prodotti dall’ALU vengono inoltrati allo stadio successivo del pipeline, in contemporanea alla (e senza attendere la) loro memorizzazione:
Rimedi contro i data Rimedi contro i data hazardhazard
13
Architettura degli Elaboratori © 2009
32
Branch hazard (conflitto dei salti): si verifica nelle istruzioni di salto condizionato, quando (prima di conoscere se il salto verrà effettuato) il pipeline viene alimentato con le istruzioni della diramazione che non sarà intrapresa;in tal caso è necessario: ●svuotare il pipeline, ●annullare gli effetti delle istruzioni che ne
hanno percorso indebitamente alcune fasi,●ri-alimentare il pipeline con le istruzioni
dell’altra diramazione.
Branch Branch hazardhazard
-
14
Architettura degli Elaboratori © 2009
32
Per gestire correttamente un branch hazard si può:●ritardare il pipeline (stall): il pipeline non
viene alimentato fino a che, valutati gli effetti dell’istruzione precedente, (dai quali spesso dipende la condizione di salto), la diramazione da intraprendere risulta nota; così l’esecuzione subisce sempre un ritardo;
●cercare di evitare questo ritardo usando tecniche di:▪ delayed branch (salto ritardato),▪ branch prediction (predizione del salto).
Gestione dei branch Gestione dei branch hazardhazard
15
Architettura degli Elaboratori © 2009
32
DelayedDelayed branchbranch
La tecnica prevede che il processore esegua comunque una ulteriore istruzione (successiva a quella di salto) prima di intraprendere il salto; ●il compilatore può allora riordinare le istruzioni in modo da collocarne una (da eseguire comunque) dopo ogni istruzione di salto;
●se non riesce a trovare una istruzione di questo tipo, il compilatore inserisce, dopo l’istruzione di salto, una NOP (comporta un ritardo, ma evita di avviare l’esecuzione di istruzioni che non devono essere eseguite).
-
16
Architettura degli Elaboratori © 2009
32
Branch Branch predictionpredictionLa predizione dei salti (branch prediction) può essere:● statica: stabilita dal compilatore: ad es. i salti
all’indietro nelle iterazioni vengono (quasi) sempre intrapresi;
● dinamica: stabilita dal processore sulla base della storia precedente (stimando che la prossima volta venga intrapresa la diramazione presa più volte in passato);
il processore utilizza a questo scopo una cache veloce contenente (su CAM) gli indirizzi delle istruzioni di salto● il PC viene confrontato con gli indirizzi nella CAM; ● è comunemente usata una di queste due organizzazioni:
▪ BHT (Branch History Table), in cui ciascun elemento indica solo se il salto va intrapreso oppure no;
▪ BTB (Branch Target Buffer), che contiene anche, per ciascun elemento, direttamente l’indirizzo a cui saltare.
17
Architettura degli Elaboratori © 2009
32
Altre tecniche di parallelismoAltre tecniche di parallelismo
• Superscalarità• Speculative execution• Out of order execution• VLIW (Very Long Instruction Word)• Register renaming• SIMD (Single Instruction Multiple Data)
-
18
Architettura degli Elaboratori © 2009
32
SuperscalaritSuperscalaritàà
Le tecniche superscalari, che negli anni ‘60 erano usate solo nei supercomputer (> 1M$) sono ora impiegate anche nei desktop, grazie al numero elevato di transistor/chip reso possibile dalla tecnologia di integrazione.Il termine “superscalare” vuole indicare che questa tecnica consente di andar oltre l’aumento di velocità reso possibile dalla riduzione di scala (delle dimensioni dei componenti) nella tecnologia di integrazione dei microprocessori.
19
Architettura degli Elaboratori © 2009
32
Processori superscalariProcessori superscalari
Un processore superscalare usa più di un pipeline, in modo da poter avviare l’esecuzione di più istruzioni in parallelo, quando le circostanze lo consentono.Un processore superscalare con N pipeline èpotenzialmente N volte più veloce del suo equivalente con pipeline singola.La potenzialità di una CPU superscalare è sfruttata appieno solo se il codice che viene eseguito ècaratterizzato da un alto grado di parallelismo a livello di istruzioni (Instruction Level Parallelism - ILP); altrimenti le prestazioni non differiscono molto da quelle di una CPU tradizionale.
-
20
Architettura degli Elaboratori © 2009
32
In funzione delle caratteristiche del codice che viene eseguito e del numero di pipeline, l’incremento di velocità ottenuto con la superscalarità, rispetto ad una CPU con pipelinesingolo, ha valori comunemente compresi tra il 50% e il 500%;per ottenere buone prestazioni è molto importante individuare le possibilità di ILP nel codice che deve essere eseguito;nei processori superscalari attuali, una porzione significativa dell’hardware (area di silicio) viene usata a questo scopo.
Prestazioni dei processori superscalariPrestazioni dei processori superscalari
21
Architettura degli Elaboratori © 2009
32Intel Pentium-I: 2-way superscalar (1993).
Sun SuperSPARC/Viking: 3-way superscalar (1993).
Intel Pentium-II/III: 5-way superscalar (1996-1999).
AMD Athlon/K7: 9-way superscalar (1999).
Esempi storici di processori superscalariEsempi storici di processori superscalari
-
22
Architettura degli Elaboratori © 2009
32
Speculative Speculative executionexecution
• Il termine esecuzione speculativa (speculative execution) è talvolta usato per indicare il fatto che il processore esegue contemporaneamente, su 2 pipeline, entrambi i flussi di istruzioni delle due diramazioni di un salto condizionato, scartandone uno quando il valore della condizione di salto è divenuto noto;
• l’esecuzione speculativa comporta un notevole impiego di risorse hardware, dal momento che vengono eseguiti due flussi di istruzioni per raccogliere i risultati di uno solo;
• l’Intel Pentium Pro/II/III è un esempio storico di processore con speculative execution.
23
Architettura degli Elaboratori © 2009
32
Out of Out of orderorder executionexecution
• Per le istruzioni tra le quali non vi sono dipendenze, non è necessario che l’esecuzione avvenga nello stesso ordine con cui esse si trovano in memoria;
• può essere conveniente alterare questo ordine (out of order execution) in modo da inserire l’esecuzione di queste istruzioni, prive di dipendenze, tra quelle che presentano dipendenze, al fine di evitare inceppamenti (stall ) dei pipeline;
• l’esecuzione fuori ordine consente di sfruttare maggiormente i pipeline di un processore superscalare;
• per evitare incongruenze, i risultati prodotti dalle istruzioni sono solitamente scritti (in memoria o nei registri) secondo l’ordine originario delle istruzioni.
-
24
Architettura degli Elaboratori © 2009
32
VeryVery Long Long InstructionInstruction Word (VLIW)Word (VLIW)
• La tecnologia VLIW, utilizzata in alcuni processori superscalari, prevede che istruzioni (indipendenti) la cui esecuzione può essere avviata contemporaneamentevengano raggruppate in una unica istruzione;
• ciascuna istruzione VLIW specifica pertanto più operazioni da eseguire su distinti operandi da parte di più pipeline;
• è responsabilità del compilatore individuare le possibilità di ILP (parallelismo a livello di istruzioni) e raggruppare in un’unica VLIW le istruzioni indipendenti;
• rispetto ai processori superscalari privi di VLIW, nei quali la individuazione e lo sfruttamento dell’ILP è compito dell’HW, quelli con VLIW hanno un hardware più semplice;
• le prestazioni di un processore VLIW dipendono fortemente dalla qualità del compilatore.
25
Architettura degli Elaboratori © 2009
32
CPU tradizionale vs. VLIWCPU tradizionale vs. VLIW
-
26
Architettura degli Elaboratori © 2009
32
• La tecnologia VLIW viene anche usata per emulare con processori RISC le istruzioni di “vecchi” processori CISCo RISC (backward compatibility);
• per ottenere ciò si usano metodi di “traduzione dinamica”, con i quali le istruzioni CISC o RISC vengono tradotte in una singola istruzione VLIW, via software, durante l’esecuzione;
• per velocizzare la traduzione, i processori VLIW mantengono in una cache veloce le traduzioni da CISC/RISC a VLIW;
• ovviamente la hit rate di questa translation cache è molto importante;
• l’IA-64 “Itanium” dell’Intel e il Crusoe della Transmetasono due esempi di processori con tecnologia VLIW; (chiamata EPIC - Explicit Parallel Instruction Computing da Intel e “code morphing” da Transmeta).
Emulazione di CISC con VLIWEmulazione di CISC con VLIW
27
Architettura degli Elaboratori © 2009
32
RegisterRegister renamingrenaming
●Nell’esecuzione fuori ordine delle istruzioni, può accadere che istruzioni indipendenti non possano essere eseguite in parallelo perchéusano o modificano lo stesso registro.
●Per sfruttare la possibilità di parallelismo anche in questi casi, il processore può essere dotato di una gran quantità di registri cui vengono assegnati i nomi dinamicamente, per cui a due istruzioni che usano lo stesso registro il processore può assegnare due registri fisici diversi (sistemando le cose alla fine).
-
28
Architettura degli Elaboratori © 2009
32
Single Single InstructionInstruction Multiple Data (SIMD)Multiple Data (SIMD)
Una istruzione opera le medesime elaborazioni, simultaneamente, su un insieme di dati.Questa possibilità è utile negli algoritmi di elaborazione di immagini (le stesse trasformazioni operate su tutti i pixel), nell’elaborazione dei segnali e, in generale, nelle applicazioni multimediali.
Esempio:istruzioni MMX (Multi Media Extension) e SSE (Streaming SIMD Extension) nelle CPU x86.
29
Architettura degli Elaboratori © 2009
32
CISC vs. RISCCISC vs. RISCCISC: Complex Instruction Set Computer RISC: Reduced Instruction Set Computer
Per un programma di NI istruzioni, eseguito da un processore che impiega in media CI periodi di clock (TC) per eseguire una istruzione, il tempo di esecuzione TE è:
TE = NI × CI × TC
Entrambe le architetture CISC e RISC perseguono l’obiettivo di ridurre i tempi di esecuzione dei programmi:● CISC cercando di ridurre NI (poche istruzioni
potenti, la cui esecuzione può richiedere molti periodi di clock CI);
● RISC cercando di ridurre CI (molte istruzioni semplici, eseguite velocemente, in pochi periodi di clock CI).
-
30
Architettura degli Elaboratori © 2009
32
CISCCISC
● La facilità con cui in un processore microprogrammatosi possono definire nuove istruzioni, ha portato a processori dotati di istruzioni complesse, tali da eseguire, con un’unica istruzione, più operazioni che altrimenti richiederebbero più istruzioni di macchina (allo scopo di ridurre NI);
● il risparmio di tempo ottenuto evitando le operazioni di fetch di queste ultime può essere decisamente piùconsistente del tempo richiesto per gli accessi, ancorché numerosi, alla memoria di controllo;
● quest’ultima affermazione era vera fintanto che i tempi di accesso alla RAM erano molto più lunghi di quelli per l’accesso alla memoria di controllo.
31
Architettura degli Elaboratori © 2009
32
RISCRISC
• Istruzioni con struttura il più possibile uniforme, tale da garantire che il loro prelievo e la loro esecuzione avvengano in un numero costante e piccolo di periodi di clock (lo scopo è di ridurre CI );
• istruzioni progettate per sfruttare bene i pipeline;• niente microcodice (responsabile della varietà nel
numero di cicli di clock necessari per eseguire istruzioni diverse);
• il 20% delle istruzioni CISC svolge l’80% del lavoro (regola dell’80/20): l’obiettivo dei RISC è di essere capaci di eseguire solo questo 20% ma velocemente(le operazioni eseguite dal rimanente 80% vengono realizzate tramite combinazioni delle prime)
-
32
Architettura degli Elaboratori © 2009
32
Caratteristiche dei processori RISCCaratteristiche dei processori RISC• Pochissime forme di indirizzamento utilizzate (spesso solo
quella “diretta di registro” e “auto-relativa”): le forme di indirizzamento sofisticate richiedono word di estensione, comportano istruzioni di diversa lunghezza e un numero variabile di cicli di clock per la loro esecuzione;
• accessi in memoria consentiti solo a pochissime istruzioni (load e store);
• un numero di registri elevato (per diminuire la necessità di accedere alla memoria);
• le istruzioni che accedono alla memoria richiedono un periodo di clock e una fase di pipeline in più: i rallentamenti che ne derivano sono drasticamente ridotti dalla presenza di memoria cache veloce ed efficiente;
• anche l’ordinamento delle istruzioni (prodotto dai compilatori) è tale da evitare fenomeni di data hazard.
33
Architettura degli Elaboratori © 2009
32
Confronto RISC vs/ CISCConfronto RISC vs/ CISC
-
34
Architettura degli Elaboratori © 2009
32
Vantaggi dellVantaggi dell’’impostazione RISCimpostazione RISC
• Il progresso tecnologico nella velocità delle RAM e nelle memorie cache ha ridotto i tempi di accesso allamemoria centrale e ha reso meno significativoil vantaggio della microprogrammazione;
• il progresso nelle tecniche di parallelismo dell’hardwareha portato ad usare meccanismi (pipeline, etc) che producono risultati migliori se le istruzioni hanno tutte la stessa lunghezza e vengono eseguite nello stesso numero di periodi di clock;
• il progresso nelle tecniche di ottimizzazione dei compilatori ha portato a produrre codice che sfrutta bene le risorse del processore che consentono il parallelismo (registri, cache, pipeline, …).
35
Architettura degli Elaboratori © 2009
32
CISC vs. RISCCISC vs. RISC
•Nonostante tutti i vantaggi dei RISC, il numero di processori CISC esistenti al mondo è almeno 1000 volte maggiore di quello dei processori RISC;
•gli embedded computer (negli elettrodomestici, nelle automobili, nelle fotocopiatrici, etc.) hanno quasi sempre un chip CISC al loro interno: la potenza e le prestazioni dei processori RISC semplicemente non servono in quelle applicazioni;
•anche tra i calcolatori il numero di macchine con istruzioni CISC è almeno 20 volte superiore a quello delle macchine con istruzioni RISC.
-
36
Architettura degli Elaboratori © 2009
32•L’architettura x86 è di tipo CISC, ma all’interno dei moderni processori x86 le unità di calcolo eseguono istruzioni RISC (che consentono di sfruttare le possibilità di parallelismo presenti nell’hardware);
•le istruzioni di macchina CISC del programma da eseguire vengono convertite dall’hardware in sequenze di istruzioni RISC (chiamate μopsdall’Intel e R-ops dall’AMD); sono queste ultime ad essere effettivamente inviate ai pipeline.
x86: CISC o RISC?x86: CISC o RISC?
37
Architettura degli Elaboratori © 2009
32
Esempi di processori CISCEsempi di processori CISC
CISC: ▪Digital: VAX, PDP-11, ▪ Intel: x86 (fino al Pentium), ▪Motorola: 68000.
CISC con conversione interna a RISC:▪ Intel: Pentium II/III/4, Core 2, Atom, Core i7 ▪AMD: Athlon, K6, K8.
-
38
Architettura degli Elaboratori © 2009
32
Esempi di processori RISCEsempi di processori RISC
RISC:● desktop e server:
▪ Silicon Graphics: MIPS, ▪ Sun Microsystems: SPARC, ▪ Digital: Alpha, ▪ Hewlett Packard: PA-RISC, ▪ IBM e Motorola: PowerPC, ▪ Intel: i860, i960.
● embedded:▪ Advanced RISC Machines: ARM, ▪ Hitachi: SuperH,▪ Mitsubishi: M32R,▪ Silicon Graphics: MIPS16.
09.a
FineFine
Le architetture RISC