La pipeline

LuigiPalopoli

Ripartiamo da questo….

• Abbiamo visto comerealizzare unsempliceprocessore che esegue leistruzioni inunciclo

• Questo nonsi fapiù perché:§ Adettare il clocksono leistruzioni più lente(accessoalla memoria)

§ Sesi mettono istruzioni più complessediquelleche abbiamo visto,lecose peggiorano ancora dipiu’(esempio istruzioni floatingpoint)

§ Nonsi riesce afareottimizzazioni aggressivesullecose fatte più difrequente.

Che fare allora?

• Ilcosa farece loinsegnò HenryFordconlacatenadimontaggio (assemblyline):

“Ifeveryone ismovingforwardtogether, then

successtakescareofitself.”

“Comingtogether isabeginning.Keepingtogetherisprogress.Workingtogether

issuccess.”

Un esempio

• Supponiamodidoverfareil bucatoeche questoconsista nelle seguenti attività:

1. Mettere labiancheria nella lavatrice2. Terminato il lavaggio mettere i panni nell’asciugatrice3. Terminata l’asciugatura mettere Ipanni sull’asse da stiro

e procedere alla stiratura4. Finita lastiratura chiedere alproprio co-inquilino di riporre I

panni

• Abbiamoungrande vantaggio sementre lalavatrice lava unbucato,l’asciugatrice neasciugaunaltro eio nestiro unaltro ancora

Una rappresentazionegrafica

Supponendo che ciascunafase duri 30minuti,ll ciclodi lavaggio dura dueore(tra le18e el20peril

primo).Conil secondo metodo fino

alle 21.30nefaccio 4.

Notare che il tempoperfareunbucato (tempodi

risposta)rimane invariato(dueore).Ilthroughput

passa da 1/4a4/7(miglioramento di 2.3).Segli diamo temposi arriva

aunfattore 4

Andiamo su un esempiopiu’ serio

• Tornando alMIPS,lefasi di esecuzione diun’istruzione sono leseguenti:

1. Prelievo dell’istruzione dalla memoria2. Lettura dei registri e decodifica dell’istruzione

(possibile peril formato regolare delle istruzioniMIPS)

3. Esecuzione di un’operazione (tipo R)o calcolo di unindirizzo4. Accesso aun’operando nella memoria dati5. Scrittura delrisultato inunregistro

• Conseguentementeuseremo una pipelineacinque stadi

Un esempio

• Limitiamoci peril momento auna pipelinechesia ingrado di effettuare leseguentioperazioni:§ LOAD(lw),STORE(sw)§ AND(and),OR(or)§ Setlessthan(slt)§ Branchonequal(beq)

Tempi

• Itempirichiesti perlevarie fasi sono I seguenti:

• L’istruzione piu’lenta e’lalw.Quindi ci si deveadeguare adessa perlascelta delclock

Varie implementazioni

• Diagramma temporale perseguenza istruzioni:

Implementazione asingolo ciclo

Implementazione apipeline

Tempotra fineprimaafinequartaquarta istruzioni passa da2400(3*800)a1400ps.

Confronto di prestazioni

• Unconfronto diprestazioni può essere fattaconlaseguente formula(valida selapipelineoperaincondizioni ideali)

Tempo tra due istruzioni con pipeline =

Tempo tra due istruzioni senza pipeline

Numero di stadi della pipeline

• Laformulasuggerisce che concinquestadidovremmo arrivare auntempotra dueistruzioni (inverso delthroughput)chedovrebbe essere 1/5.

Osservazioni

• Nell’esempioprecedente siamo passati da 2400a1400(miglioramento1.7)comemai non5?• Primaosservazione:perottenereuna prestazionedi1/5dovremmoportare il clocka160ps (nonpossibile)perche’ci sono alcune fasi che durano 200ps (alpiu’4volte)• Seconda osservazione:ovviamenteil problemae’cheabbiamo consideratopoche istruzioni e nonabbiamofatto intempoariempire lapipeline.

Comportamento al limite

• Seconsideriamomolte piu’istruzioni (adesempio 1000000)peruntotale di 1000003 sipassa da untempodi esecuzione di1000003*800psauntempodi esecuzione di1400+1000000*200ps.

• Sefacciamo il rapporto vediamo chel’incremento prestazionale interminidithroughput isavvicina al400%

Vantaggi del RISCVantaggi delle architetture RISC(alaMIPSperil pipelining)• Primovantaggio:tutte leistruzioni hanno lastessa lunghezza.

Questo facilita di molto il prelievo (sempre una word)

• Secondo vantaggio:I codici degli operandisono inposizionefissa.Questo permette di accedervi leggendo il registerfileinparallelo conladecodifica dell’istruzione

• Terzo vantaggio:gli operandiresidenti inmemoria sono possibilisoloperlw e sw.Cio’permette di usare laALUperil calcolo diindirizzi (cosa che nonsarebbe possibile sedovessimo usare leALUinduefasi della stessa istruzione)

• Quartovantaggio:l’uso diaccessi allineati fa sì che gli accessi inmemoria avvengano sempre inunciclo ditrasferimento(impegnando unsolostadio della pipeline)

Hazard

• Incondizioni normali lapipelinepermette dieseguire una istruzione perciclo di clock.

• Alle voltequesto nonè possibile perilverificarsi dicondizioni critiche (detti hazard).

• Passiamo inrassegna alcuni tipologie dihazard.

Hazard Strutturali

• Unacondizione dihazardstrutturale è una perlaqualel’architettura dell’elaboratore rendeimpossibile l’esecuzione dialcune sequenze diistruzioni inpipeline.

• Adesempio,seio disponessi di un’unicamemoria,nonpotrei nello stesso ciclo,caricare istruzioni e memorizzare (o prelevare)operandidalla memoria.

Hazard sui dati• Questo tipo di hazardsi verifica quando lapipelinedeve essere messa installoperottenere delleinformazioni dagli stadi precedenti

• Nell’esempio della stiratura,semiaccorgo chemancauncalzino,devointerrompere lastiraturadell’altroeandarlo acercare (bloccando anche lefasi precedenti).

• Nel caso delMIPS,consideriamo laseguente sequenza

add $s0, $t0, $t1sub $t2, $s0, $t3

• Ilproblema è che s0 vienememorizzato nella quintafase,mentre lasubdopo nehabisogno nella secondafase….quindi e’costrettaadaspettare

Come risolverlo?

• L’hazard precedente blocca il completamentodella secondistruzione pertre cicli di clock

• Incerti casi possiamo cavarcela alivello dicompilazione invertendo alcune istruzioni

• Tuttavia il compilatore può risolvere ilproblema soloinalcuni casi

• Ingenerale,è utileosservare che nonoccorreaspettare dimemorizzare il risultato

Torniamo all’esempio• Unarappresentazione grafica perl’operazione dellapipelinesu una delle istruzioni è laseguente:

Instructionfetch

(qudratinomemoria istr.)

Instructiondecode

(qudaratinospezzato

registerfile)

InstructionExecute

Accesso allamemoria

Writeback(scritturarisulato nelregisterfile)

Ombra =unità usata peristruzione

Operand forwarding• L’operand forwarding(o propagazione)o anchebypassviene usato perrendere il risultatodisponibile bypassando l’operazione di storage

Appena il risultato èdisponibile viene

passato avanti all’unitache lodeve usare

Hazard sul controllo

• Ilterzo tipo di hazardriguarda il controllo(sostanzialmentei salti condizionati)

• Torniamo all’esempio delbucato§ Supponiamo che,aseconda dellivello di sporco sivoglia decidere perunlavaggio aggressivo

§ Quello che dovrei fareè verificare lacondizione deipanniall’uscita dell’asciugatrice esu questa basecambiare leimpostazioni

§ manel farquesto si blocca lapipeline (fino ache nonhofinito l’asciugatura nonposso procedere allavaggio della prossima mandata)

Salto condizionato

• Ilcaso simileaquello delbucato si presentaconi salti condizionati

• Supponiamo diavere uncircuitomotosofisticato che cipermetta dicalcolarel’indirizzo disalto già alsecondostadio

• Comunque,dobbiamo bloccare lapipelineperuno o duecicli

Esempio

Alla finedelprelievo capisco cheè unbeq easpetto peruncicloprimadifareil prelievo diquella

successiva

Predizione del salto

• Selapipelineè più lunga generare questostallo è uncosto troppo lungo

• Quello che si faè avere dei circuiti cheprevedano i salti

• Adesempio,nel caso precedente si puòassumere che il salto nonvenga preso e poicorregersi incaso contrario

Esempio precedente

Siassumeche nonvengapreso

Circuiteria di branch prediction

• L’esempio che abbiamo visto primononèparticolarmente sofisticato (finisce conilfunzionare benesoloseil branchnonvienepreso)

• Esistono circuiterie più sofisticate chepermettono dimemorizzare l’esisto delbranchprecedente eassumere che il comportamentosi mantenga coerente.