Lezione 8 - dei.unipd.itpel/MicroC_e_DSP/Materiale_da_scaricare/Lezioni... · 3 Simone Buso -...

1

Simone Buso - Microcontrollori e DSP - Lezione 8 1

Lezione 8Sommario• Architetture con pipeline• Accelerazione• Gestione dei conflitti• Architetture superscalari


Lezione 8Materiale di riferimento1. D. A. Patterson, J. L. Hennessy, “Computer

Organization and Design”, Morgan Kaufmann, cap. 6 pagg. 436-528.

2. A. Clements, "The principles of computer hardware", Oxford, 2000, cap. 7, pagg. 360-369.

3. G. Bucci, "Architetture degli elaboratori elettronici", McGraw-Hill, 2001, cap. 6, pp. 209–278.

4. P. Lapsley, J. Bier, A. Shoham, E.A. Lee, "DSP Processor Fundamentals - Architectures and Features", IEEE Press, New York, 1997, cap. 9.

2


PipelineLa pipeline (letteralmente: catena di montaggio) è una particolare organizzazionedella CPU, che consiste nella sua suddivisione in una catena di stadi, che effettuano in successione temporale le diverse azioni necessarie alla esecuzione delle istruzioni.Sotto opportune ipotesi, l’adozione di questa organizzazione permette un considerevole aumento della velocità del processore.


PipelineIl concetto di pipeline e i suoi vantaggi potenziali sono noti fin dagli albori dell’era dei microprocessori; negli attuali processori per uso generico (PC) questa organizzazione è presente immancabilmente.Attualmente, viene utilizzata anche in tutti i microcontrollori di tipo RISC e nei DSP, anche se con livelli di complessità minori rispetto a quelli propri dei processori per PC.Vedremo infatti che l’organizzazione a pipeline, pur aumentando le prestazioni, rende la programmazione più difficile.

3


PipelineAbbiamo visto come l’esecuzione di una istruzione richieda diverse operazioni. Consideriamo ad esempio una istruzione tipoAdd R1, num;

ovvero [R1] = [R1] + M[num].Questa richiederà le seguenti operazioni:

Fetch DecodificaLetturaoperandi Esecuzione

Scritturarisultati

Ciascuna di queste fasi viene eseguita in un certo tempo, dipendente dalla velocità di risposta delle unità funzionali coinvolte.


PipelineSupponiamo, per esempio, di disporre di un processore che abbia unità funzionali separate per lo svolgimento di ciascuna faseossia:a.prelievo istruzione (F): 5 nsb.decodifica istruzione (D): 3 nsc. lettura/scrittura operandi/risultati

(R/W): 5 nsd.esecuzione (E): 2 ns

Consideriamo le due realizzazioni classiche: a singolo ciclo e multiciclo.

4


WERDF

PipelineTroveremo allora le seguenti situazioni:

5 3 5 2 5

20 ns

WERDF5 5 5 5 5

25 ns

Ciclo singolo

Multiciclo

Add R1, num i+1i-1

F

F

W

W

……

… …


PipelineIn una realizzazione a ciclo singolo, il periodo di clock del processore dovrà essere abbastanza lungo da permettere lo svolgimento di tutte le fasi, quindi 20 ns nel nostro caso.In una realizzazione multiciclo, a ciascuna fase corrisponde almeno un periodo di clockdel processore. La nostra istruzione richiederà allora, nel caso più semplice, 5periodi di clock, che dovranno avere durata pari a 5 ns. Il tempo di esecuzione sarà allora di 25 ns.

5


In entrambi i casi, nell’esecuzione della nostra istruzione, le diverse unità del processore lavorano solo per una frazione del tempo totale di esecuzione, il che è altamente inefficiente.L’organizzazione a pipeline interviene proprio su questa inefficienza. Le diverse unità funzionali vengono fatte lavorare simultaneamente, ma su segmenti di istruzioni diverse, come in una catena di montaggio industriale.Si tratta quindi di una struttura a stadi.

Pipeline


PipelineWERDF

WERDF

WERDF

i-1

Add R1, num

i+1

In un dato intervallo di tempo, diverse fasi dell’esecuzione di diverse istruzioni vengono svolte simultaneamente.Tutti gli stadi (F,D,R,E,W) della pipeline operano in parallelo, aumentando l’efficienza del processore.

6


Pipeline

In una organizzazione a pipeline il tempo di ciclo è fissato dalla più lenta delle unità funzionali (che ora costituisce uno stadiodella pipeline), come in una organizzazione multiciclo, e, se non insorgono conflitti, ad ogni ciclo di clock corrisponde il completamento di una istruzione, come in una soluzione a ciclo singolo.In condizioni ideali, una pipeline a n stadipermette quindi una accelerazione della velocità del processore fino ad un fattore n.


Accelerazione

Più esattamente, l’accelerazione garantita da una organizzazione a pipeline è data dal rapporto tra il numero di istruzioni da essa eseguite nell’unità di tempo e lo stesso numero valutato in una organizzazione multiciclo, in cui le unità funzionali (che si suppone siano le stesse) operino in seriesenza sovrapposizioni (i.e. ogni unità lavora solo su una istruzione fino al completamentodella sua esecuzione).

7


AccelerazioneIl valore dell’accelerazione è al più pari al numero n degli stadi della pipeline.In realtà, una serie di ragioni pratiche limitano questo valore al di sotto di n.In primo luogo, la pipeline comincia a completare le istruzioni solo dopo un certo tempo, detto tempo di riempimento, che è pari a n·Tclk.Inoltre, è possibile che il funzionamento della pipeline venga ostacolatodall’insorgenza di differenti tipi di conflitti.


AccelerazioneA causa del transitorio di riempimento il tempo richiesto per il completamento di N istruzioni è quindi sempre maggiore di N·Tclk. In effetti esso è pari a (n+N-1)·Tclk. Ne consegue che il numero medio di istruzioni completate nell’unità di tempo vale:

NMIpipeline =(n+N-1 )·Tclk

N

e quindi tende a 1/Tclk solo per N molto grande rispetto a n.

8


AccelerazioneUna conseguenza del fatto che il tempo medio richiesto da una istruzione dipenda dal numero di istruzioni, è che non è facile valutare sulla carta il tempo richiesto da un programma eseguito da un processore che abbia una organizzazione a pipeline, specialmente se il numero n di stadi è alto.Nei mC e DSP il numero di stadi è di solito tre (fetch, decodifica, esecuzione). Esistono comunque esempi di DSP con pipeline fino a cinque stadi (TMS320C54x).


ConflittiE’ possibile che la combinazione delle istruzioni di un dato programma richieda l’utilizzo dello stesso stadio della pipeline da parte di due diverse istruzioni nello stesso ciclo di clock.Questa situazione configura un conflitto strutturale nella pipeline.L’unica soluzione per rimuovere i conflitti strutturali è una modifica dell’organizzazionehardware del processore, che introduca una duplicazione delle risorse (e.g. memorie separate per dati e istruzioni).

9


ConflittiOltre un certo livello di duplicazione, il costodel processore diventa eccessivo.Si arriva sempre ad una soluzione di compromesso tra costo e penalità derivante dall’insorgenza di conflitti strutturali, che quindi si possono sempre verificare.

WERDF

EDF i+1

i

L’istruzione i+1 (senza operandi) entra in conflitto con l’istruzione i per l’uso della ALU.


Gestione dei conflitti strutturaliIl modo più semplice di gestire i conflitti strutturali consiste nell’introdurre dei meccanismi di ritardo nella pipeline.

Questo riduce la velocità del processore.

F F

D

WERDF

DF i+1

i

i+2D R

E

E

F i+3NOP

10


Gestione dei conflitti strutturaliL’introduzione di ritardi o stalli (tecnica detta di “interlocking”) rallenta l’esecuzione delle istruzioni, ma rappresenta l’unicasoluzione in presenza di un conflitto strutturale. Esistono però altri tipi di conflitti:• conflitti sui dati: si hanno quando una istruzione usa i risultati di una istruzione precedente che non si è ancora conclusa.

• conflitti di controllo: si hanno quando il programma prevede dei salti (istruzioni di jump) o delle diramazioni (branch).


Conflitti sui datiI conflitti sui dati tra una istruzione i e una successiva istruzione j in un sistema a pipeline possono essere di tre tipi:• j tenta di leggere un dato prodotto da i prima che i sia stata completata.

• j tenta di sovrascrivere un dato letto da i prima che i lo abbia effettivamente letto.

• j tenta di scrivere un risultato, che è anche risultato di i, prima che i sia conclusa.

Non tutti si verificano in ogni sistema a pipeline.

11


Conflitti sui datiI conflitti sui dati sono potenzialmente molto pericolosi, in quanto possono generare risultati non previsti in una elaborazione, senza che si attivi alcuna condizione di errore.Il problema del sistema di controllo della pipeline è in primo luogo quello di riconoscereil conflitto sui dati e poi di risolverlo.Sono possibili diverse soluzioni per i conflitti sui dati, che tentano di minimizzare il ricorso all’interlocking.


Conflitti sui datiConsideriamo le seguenti istruzioni:

add R1,num; i.e. [R1] = [R1] + M[num]add R2, R1; i.e. [R2] = [R2] + [R1]

WERDF

WERDF

add R1,num

add R2, R1

La seconda istruzione legge il registro R1 prima che questo sia stato aggiornato. Quindi la somma di R2 e R1 risulterà errata.

12


Conflitti sui datiPer riconoscere un simile conflitto sui dati è necessario che il controllore della CPU, ogni volta che attiva l’unità di lettura operandi,controlli se ci sono istruzioni a monte (quindi nelle fasi E o W) che stanno per scrivere su quell’operando (prenotazione).Questo richiede una opportuna, e abbastanza complessa, organizzazione del controllore.La risoluzione del conflitto può avvenire semplicemente ritardando la lettura dell’operando, cioè ancora con l’interlockingdella pipeline.


Gestione dei conflitti sui datiIn alternativa, il conflitto sui dati può essere gestito tramite:• bypass: il dato richiesto dall’istruzione j viene prelevato appena disponibile, anche prima della sua scrittura a destinazione.

• sovrapposizione: le fasi di lettura e scrittura di un operando possono avvenire nello stesso ciclo di clock che viene diviso a metà (prima scrittura, poi lettura).

• riordinamento: la sequenza delle operazioni viene alterata (dal compilatore) in modo da prevenire il conflitto (per programmi HLL).

13


R

W

Esempio di bypass

EDF

EDF

add R1,num

add R2, R3

EDF add R1, R3

R

R

W

W

L’operando richiesto dalla terza istruzione viene fornito in anticipo dalla stessa pipeline, senza attendere la sua effettiva scrittura.Si parla anche di internal forwarding.

Gestione dei conflitti sui dati


R

W

WEDF

EDF

add R1,num

add R2, R3

EDF add R1, R3

L’operando richiesto dalla terza istruzione viene letto nella seconda metà del ciclo di clock, dopo che era stato scritto, nella prima metà del ciclo, dalla prima istruzione.

Esempio di sovrapposizione

R

W

W

W

W

R

R

R

R

Gestione dei conflitti sui dati

14


Esempi di conflitti sui datiload R1, M[R2];add R3, R4;sub R5, R6;

Nessun conflitto

load R1, M[R2];add R3, R4;sub R1, R6;

Conflitto risolvibile per sovrapposizione.

load R1, M[R2];add R3, R4;sub R1, R3;

Conflitto risolvibile per bypass di entrambi gli operandi.

load R1, M[R2];add R1, R4;

Conflitto risolvibile solo con interlocking.


Conflitti di controlloQuando nella pipeline giunge alla fase di esecuzione una istruzione di salto o diramazione, le istruzioni successive devono essere scartate.Questo genera una bolla nella pipeline, che ne perturba il funzionamento.

WEDF

NOPF

FNOP

R

DNOP

jump next

F D RNOP

NOP

bolla

15


Gestione dei conflitti di controlloIn alternativa, alcuni processori operano il salto ritardato (delayed jump) che consiste nel completare comunque le istruzioni successive a quella di salto, in modo da non generare bolle.Ciò significa che il programmatore deve scrivere le istruzioni del suo programma in un ordine opportuno, tenendo conto di questa modalità di funzionamento del processore.Ciò rende la programmazione in assembly estremamente impegnativa e porta verso l’uso di liguaggio ad alto livello (HLL).


Gestione dei conflitti di controllo

load R1, M[R2];add R3, R4;sub R5, R6;jump Altrove;

load R1, M[R2];jump Altrove;add R3, R4;sub R5, R6;

Se il programma prevede questa sequenza di istruzioni …

Esempio di salto ritardato (di 2 istruzioni)

… il programmatore deveinvece scriverle in questo ordine. Le due istruzioni successive al jump saranno comunque eseguite.

16


Conflitti di controlloNei mC e nei DSP più semplici, la gestione dei salti avviene sempre per interlocking.Ne consegue che l’esecuzione di un salto richiede in realtà diversi cicli di clock.Alcuni DSP (e.g. AD 210xx) implementano invece solo salti ritardati. Questo richiede estrema attenzione nella programmazione in assembly o l’uso sistematico di istruzioni NOP.Infine, alcuni DSP (e.g. TMS320C3x) permettono di usare sia salti ritardati checon interlocking.


Conflitti di controlloUn caso particolare di conflitto di controllo si ha in relazione alle interruzioni. Il passaggio dal programma principale alla routine di servizio di una interruzione produce effetti sulla pipeline del tutto simili a quelli prodotti da un salto.Il tempo di ripristino della pipeline introduce un ritardo nell’inizio della routine di servizio, che accresce il cosiddetto tempo di latenzadell’interruzione.Esistono diverse possibilità di gestione della pipeline per minimizzare questo effetto.

17


Conflitti di controlloUn tipo diverso di conflitto di controllo è quello legato ai salti condizionati, necessari a controllare il flusso del programma in modo dinamico.In questo caso, l’introduzione immediata della bolla (interlocking) è sconsigliabile, in quanto può sempre accadere che la condizione di salto si riveli falsa.E’ quindi conveniente continuare nel prelievo delle istruzioni successive al salto condizionato e attendere la valutazione della condizione di salto.


Qualora la condizione di salto si riveli vera,le istruzioni già caricate andranno eliminatedalla pipeline, con conseguente generazione di una bolla.Alcuni processori evoluti fanno uso di meccanismi di gestione dei salti condizionati che ne minimizzano l’impatto sulla pipeline, tentando di predire l’esito della condizione di salto.Si tratta predizioni, basate su modelli statistici abbastanza rudimentali, messe in atto da una opportuna unità della CPU.

Conflitti di controllo

18


Confronto pipeline/multicicloConsideriamo un processore che abbia i seguenti tempi di risposta:

memoria: 2 nsALU: 2 nsregistri: 1 ns

Consideriamo inoltre un programma tipico che sia composto da istruzioni di vario tipo:

letture da memoria (load): 24%scritture in memoria (store): 12%operazioni (ALU su registri): 44%salti (tipo branch): 20%


Confronto pipeline/multicicloSupponiamo che l’organizzazione con pipeline consenta di:• gestire senza interlocking la metà delle operazioni di load, con una penalità di 1 ciclo di clock l’altra metà.

• eseguire, senza generare bolle, la metàdei salti e, per l’altra metà introdurre una penalità di 2 cicli di clock.

Ne consegue che il numero di cicli di clock richiesto dalle istruzioni tipo load è in mediapari a 1.5, mentre è pari a 0.5·1+0.5·(1+2) = 2 per le istruzioni di salto.

19


Confronto pipeline/multicicloIl programma tipico presenterà allora un NC medio pari a:

1.5·0.24 + 1·(0.12 + 0.44) + 2·0.2 = 1.32

Ricordiamo che nella realizzazione multiciclo, a 4 segmenti ma senza pipeline, il numero mediodi cicli di clock per istruzione, NC, risultava pari a 3.16.L’uso di una pipeline a 4 stadi consente quindi di ridurre di quasi il 60% il tempo di esecuzione del programma. Il fattore di accelerazione è quindi pari a 2.4.


Confronto pipeline/multiciclo

Numero di stadi della pipelinen

Acc

eler

azione

1 2 4 8 16

1.01.52.02.53.0

Diagramma che correla l’incremento di prestazioni al numero di stadi n (profondità) di una pipeline.

20


Confronto pipeline/multicicloI fattori che limitano l’incremento di prestazioni offerto da una pipeline sono:• conflitti sui dati: maggiore è il numero di stadi maggiore è la penalità rappresentata da uno stallo;

• rallentamento nell’esecuzione dei salti: è tanto maggiore quanto maggiore è il numero di stadi;

• complicazione della CPU che costringe a ridurre la frequenza di clock: è dovuta alle strutture di supporto e controllo della pipeline (registri, logica, …).


Architetture superscalariNei DSP di ultima generazione vengono sempre più spesso introdotte soluzioni architetturali prese dal mondo dei processori per uso generico (GPPs).Tra queste, risulta piuttosto interessante, il ricorso ad architetture dette superscalari.Queste consistono nella replicazione delle unità funzionali presenti all’interno della CPU, in modo da permettere l’esecuzione di molte istruzioni in parallelo.E’ tipico un fattore di replicazione compreso tra 2 e 4.

21


Architetture superscalariIn questo tipo di processori, vengono di solito adottate strategie di controllo molto avanzate:• predizione delle condizioni di branch; • gestione avanzata della memoria (RAM dinamiche, cache multilivello etc.);

• pipeline dinamica.Il repertorio delle istruzioni è di solito di tipo RISC, ma sono possibili architetture SIMD per aumentare ulteriormente il grado di parallelismo.


Architetture superscalariUna pipeline dinamica è in grado di gestire l’esecuzione delle istruzioni in modo non ordinato, in questo modo eliminando le penalità dovute all’insorgenza di bolle.La tipica struttura di una pipeline dinamicaprevede tre unità principali:• unità di fetch e decode (FDU);• unità di esecuzione (EXU);• unità di write-back (WBU).

La prima e l’ultima unità operano secondo l’ordine delle istruzioni, la seconda no.

22


Architetture superscalari

FDU

registri registri registri registri

WBU

ALU ALU ALU ALU

…

…

EXU

Prelievo e decodifica: in ordine, anche su molte istruzioni simultaneamente.

Esecuzione in parallelo. La FDU assegna a ciascuna unità funzionale della EXU una istruzione da eseguire, usando anche tecniche di predizione per i salti condizionati.

Scrittura dei risultati: la WBU gestisce i conflittisui dati e scrive solo i risultati sicuri.


Architetture superscalariL’uso di tecniche così sofisticate (parallelismo delle unità funzionali, pipeline dinamica, predizione delle condizioni di salto) comporta costi di realizzazione molto elevati.I DSP che ne fanno uso sono quindi destinati ad applicazioni particolari, su piccola scala, dove le prestazioni in termini di potenza di calcolo siano determinanti.Questi dispositivi sono inoltre caratterizzati da un consumo di potenza piuttosto elevato e risultano quindi inadatti a molte applicazioni come embedded controllers.

23


Architetture superscalariI DSP con architettura superscalare sono inoltre in diretta competizione con i processori per uso generico (GPP), che spesso offrono prestazioni confrontabili o addirittura superiori nel signal processing (in particolare audio e video).I DSP vengono ancora preferiti per ragioni di costo e di minore consumo di potenza.Inoltre, essendo lievemente meno sofisticati, risulta di norma più facile prevedere il tempo di esecuzione di un programma (fondamentale per applicazioni real-time).


Architetture superscalari/VLIWAlcuni DSP fanno uso della strategia VLIW(Very Long Instruction Word) per aumentare il livello di parallelismo interno. Questa tecnica combina un numero anche grande di istruzioni semplici (e.g. 8) in una sola istruzione in memoria, che viene prelevata in un solo ciclo di fetch.La decodifica scompone poi l’istruzione nelle sue componenti e, sfruttando un certo grado di parallelismo hardware, assegna, se possibile, ciascuna componente ad una unità di esecuzione.

24


Architetture superscalari/VLIWL’approccio VLIW non è però equivalente a quello superscalare perché:• solo alcune particolari sequenze di istruzioni semplici possono essere combinate in una istruzione lunga che sfrutti completamente la CPU (ad es. una cella di un filtro FIR);

• il livello di parallelismo hardware è di solito ridotto (massimo due unità di esecuzione);

• la pipeline è statica;• il bus istruzioni ha molti bit (e.g. 256).

Lezione 8 - dei.unipd.itpel/MicroC_e_DSP/Materiale_da_scaricare/Lezioni... · 3 Simone Buso -...

Documents

Transcript of Lezione 8 - dei.unipd.itpel/MicroC_e_DSP/Materiale_da_scaricare/Lezioni... · 3 Simone Buso -...