Architettura degli elaboratori

(1)

Università degli Studi dell’Insubria

Dipartimento di Scienze Teoriche e Applicate

Architettura degli elaboratori

Pipelining

Marco Tarini

Dipartimento di Scienze Teoriche e Applicate [email protected]

Il pipelining è conveninete in generale (e spesso naturale)

Esempio della lavanderia

Anna, Bernardo, Caterina e Davide hanno ciascuno dei panni da lavare, asciugare e piegare

Il lavaggio impiega 30 minuti

L’asciugamento impiega 40 minuti

Per la piegatura ci vogliono altri 20 minuti

A B C D

(2)

Lavaderia sequenziale

6 ore per 4 processi completi 4*(30+40+20)

Pipelining

Architettura degli elaboratori - 3 -

A

B C D

30 40 20 30 40 20 30 40 20 30 40 20

6 7 8 9 10 11 Mezzanotte

Tempo

Lavanderia con pipelining

3 ore e mezza per 4 processi completi 30+4*40+20

Pipelining

A

B C D

6 7 8 9 10 11 Mezzanotte

Tempo

30 40 40 40 40 20

(3)

Pipelining: caratteristiche

Il singolo task non viene velocizzato.

L’intero processo è velocizzato Il tempo totale dipende dalla fase più lenta

Più task che usano risorse diverse sono attivi in parallelo Più sono le fasi e migliore è l’efficienza complessiva potenziale

Fasi di lunghezza diversa riducono il miglioramento Ci possono essere stalli su dipendenze da risorse

Pipelining

A

B C D

30 40 40 40 40 20

6 7 8 9

Tempo 9:30

Partizionamento del datapath per pipelining

Si suddivide il datapath in più parti, separate da registri Il lavoro che prima si faceva in un ciclo si può fare in più fasi

PC

Next PC Operand Fetch Exec Reg. File

Mem Access Data Mem

Instruction Fetch Result Store^A^LU

ctr RegDst

ALUSrcExtOp MemWr

nPC_sel

RegWr

MemWr

MemRd

Control

Qui vanno i registri

(4)

Datapath

Pipelining

PC

Next PC Exec

Reg. File Mem AccessData Mem

Instruction Fetch ALUctr RegDst

ALUSrcExtOp

nPC_sel RegWr

MemWr

MemRd

IR

A B Reg

File R

M

MemToReg Equal

Esecuzione con pipelining

Pipelining

IFetch Dcd Exec Mem WB

IFetch Dcd Exec Mem WB IFetch Dcd Exec Mem WB

IFetch Dcd Exec Mem WB

Program Flow

Time

(5)

Giustificazione del Pipelining

Date 100 istruzioni da eseguire Macchina multiciclo

T_exec= 10 ns/cycle x 6 CPI x 100 inst = 6000 ns Macchina con pipeline ideale

T_exec= 10 ns/cycle x (1 CPI x 100 inst + 4 cycle drain) =

= 1040 ns

Pipelining

Pipeline con le risorse esistenti

Time (clock cycles)

Inst 0

Inst 1

Inst 2

Inst 4 Inst 3

ALU

Im Reg Dm Reg

ALU

Im Reg Dm Reg

ALU

Im Reg Dm Reg

ALU

Im Reg Dm Reg

ALU

Im Reg Dm Reg

(6)

Quali problemi si possono verificare?

Structural hazards:

tentativo di usare una stessa risorsa in due modi diversi nello stesso momento

es: una istruzione usa la memoria dati, si prolunga (cache miss), ma anche quella successiva ha bisogno di accedere alla memoria Data hazards:

tentativo di usare un dato prima che sia pronto

es: un’istruzione lavora su valori che dipendono dal risultato dell’esecuzione dell’istruzione precedente

Control hazards:

tentativo di eseguire un’istruzione prima che si sia determinato quale essa debba essere

es: con istruzioni di salto (specie quello condizionato) Hazard: qualsiasi condizione che impedisce di eseguire le due istruzioni indipendentemente una dall’altra

Pipelining

Alcuni cenni su

come si affrontano gli hazard

Si può risolvere l’hazard…

…aspettando

si mette lo stage opportuno dell’istruzione dipendente dalla precedente in pausa il controllo della pipeline deve individuare il problema prima che avvenga!

…scartando

si butta via l’attuale lavoro della pipeline e si ricomincia (“flushing” della pipeline) è sufficiente individuare il problema DOPO che è avvenuto

Es: l’istruzione dietro (successiva) ha usato in lettura un registro che è stato appena modificato dall’istruzione davanti (precedente)? Flush.

Oppure: l’istruzione davanti (precedente) ha effettuato un salto e quindi quella dietro (successiva) sta lavorando con un PC e IR sbagliato? Flush.

…prevenendo

Il compilatore, come ottimizzazione, può riordinare le operazioni in modo che il risultato sia lo stesso ma ci siano meno hazard

…prevedendo

attraverso alcuni meccanismi preposti, l’architettura stessa tenta di predirre su base statistica i risultati rilevanti dell’istruzione in corso (es il PC – “branch prediction”, o il valori prodotti – “value prediction”).

Se la predizione si rivela giusta: tutto ok. Se si rivela sbagliata: flush.

Pipelining

(7)

Control Hazards

I control hazards sono fra i più difficili da gestire, e i più dannosi per le performance del pipeline.

specie quelli dovuti a salti condizionati (es «branch on equal») l’istruzione determina il PC solo nella fase dopo la ALU!

l‘istruzione successiva non può neanche procedere con il fetch Sfortunatamente, i branch sono indispensabili alla programmazione e statisticamente sono operazioni estremamente frequenti

Soluzione parziale 1 (da parte dell’archiettura):

Branch prediction

La CPU stessa implementa a circuito un meccanismo che tenta di indovinare (su base statistica, guardando gli ultimi casi avvenuti) la direzione del branch e prevedere in anticipo il prossimo PC.

Se la previsione si rivela sbagliata: flush

Pipelining

Control Hazards

Soluzione parziale 2 (da parte di chi scrive i programmi, esseri umani o più spesso compilatori):

Evitare i branch, quando possibile.

Per es ricorrendo a espressioni condizionali…

… o espressioni booleane, etc

if (a==b) z = 10;

else z = (x+15);

z = (a==b)? 10 : (x+15) ;

invece di espressione condizionale.

Un operatore fra tre termini (A?B:C). Non è un salto!

boolean a = …;

if (b) a = true;

boolean a = …;

a = a OR b; invece di

(8)

Operatore condizionale (operatore ternario)

In molti linguaggi ad alto livello (es C, Java, C++…), sintassi:

(non è solo questione di efficienza: a volte può essere utile per scrivere codice elegante e coinciso)

Come blocco funzionale combinatorio (ad es in una ALU a tre operatori)

Pipelining

(a) ? b : c

un’espressione che vale:

b se a è vero (o non zero), c se a è falso (o zero)

a b c

n n n

?

n

a b c

n n n

a?b:c MUX

1 0

n OR a n vie

Operatore condizionale

(operatore ternario): esempio pratico di uso

Esempio di uso:

determinare il massimo e il minimo fra due numeri float a e b (cioè ordinarli)

Pipelining

float max, min;

if (a>b) { max = a;

min = b;

}

else { max = b;

min = a;

}

float max = (a>b)?a:b ; float min = (a>b)?b:a ; in virgola mobile

…oppure…