Architettura degli elaboratori

(1)

Università degli Studi dell’Insubria

Dipartimento di Scienze Teoriche e Applicate

Architettura degli elaboratori

Pipelining e multi-core (cenni)

Marco Tarini

Dipartimento di Scienze Teoriche e Applicate marco.tarini@uninsubria.it

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

Pipelining

Architettura degli elaboratori - 2 -

A B C D

(2)

Lavanderia sequenziale

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

Pipelining

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

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

Pipelining

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

Gli stage di un pipeline

Instruction Fetch :

la prossima istruzione viene letta IR  MEM[ PC ] Decode:

la Control Unit prende in input l’istruzione, e produce tutti i comandi di controllo.

vengono letti i registri necessari Execute :

La ALU produce i risultati delle operazioni richieste

…oppure gli indirizzi degli accessi in memoria finali Memory :

Accesso alla memoria RAM Write Back :

Scrittura nei registri finali

(5)

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

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

(6)

Pipeline con le risorse esistenti

Pipelining

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

Quali problemi si possono verificare?

Hazard: qualsiasi condizione che impedisce di eseguire le due istruzioni indipendentemente una dall’altra.

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)

(7)

Control Hazard: esempio

add $4, $5, $6 R4  R5 + R6

beq $1, $2, 40 IF R1 == R2 JUMP 40

lw $3, 300($0) R3  MEM[ R0 + 300 ]

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

(8)

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 BEQ «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) ;

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;

diventa diventa

(9)

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…

(10)

Parallelismo

Pipeline:

instruction-level parallelism

sono le fasi delle istruzioni ad essere eseguite in parallelo Multicore:

thread-level parallelism

sono interi “task” ad essere eseguiti in parallelo

su processori separati

Sia le architetture multi-core che quelle a pipeline emergono dalla stessa considerazione tecnologica:

il progresso HW nn si può più tradurre semplicemente in un incremento della frequenza di clock (causa varie limitazioni fisiche) l’incremento delle prestazioni deve cambiare natura, passando da «più istruzioni eseguite in fila» (per secondo),

a «più istruzioni eseguite in contemporanea»

Pipelining

CPU 1 CPU 2 CPU 3

task 1 task 2 task 3

Multi-Core

(Thread-level parallelism)

Esempio di possibile architettura a quattro “core” (su un chip):

CPU 1

CACHE L1

CACHE L2

eRg ALU …

CPU 2

CACHE L1

eRg ALU …

CPU 3

CACHE L1

eRg ALU …

CPU 4

CACHE L1

eRg ALU …

BUS

RAM

(11)

Multi-core: note

Più processori (i «core») eseguono diversi task (i «thread») in parallelo Architettura:

memoria centrale condivisa e così (spesso) anche la cache L2

la cache L1 (spesso) è replicata per ogni processore Funzionamento

ogni core: ciclo fetch+execute di un proprio programma l’interazione con gli altri core, quando è richiesta, avviene

attraverso gli accessi alla memoria condivisa, oppure attraverso scambio di messaggi

nota: l’accesso alla memoria condivisa (soprattutto in scrittura!) richiede alcuni importanti accorgimenti, e appositi meccanismi HW Un’architettura di questo tipo è capace di multi-tasking HW («vero»)

contrasta con multi-tasking software: il Sistema Operativo alterna l’esecuzione di vari task su un solo processore

Pipelining

infatti ciascuno ha il suo PC

(ProgramCounter)

Thread-level parallelism: note

Le difficoltà maggiori sono sul lato Software:

come scrivere programmi che sfruttano questa capacità dell’Hardware?

ai programmatori umani viene più naturale scrivere programmisequenziali: una sola sequenza di istruzioni da eseguire in fila (sequenzialità = il contrario di parallelismo) molti algoritmisono inerentemente sequenziali,

pieni di passaggi richiedono prima il compimento dei precedenti alcuni (ma non tutti) i problemida risolvere computazionalmente si prestano male, inerentemente, a soluzioni (algoritmi) parallele cioè problemi,algoritmi, programmi(implementazioni)

hanno un livello variabile (alto o basso) di parallelismo implicito

= quanto possono essere eseguiti in parallelo in potenza per esplicitare il parallelismo implicito c’è bisogno di HW parallelo soluzione parziale: i compilatori pensati per un’architettura multi-core devono produrre programmi (in linguaggio macchina) multi-thread

esistono linguaggi ad alto livello (e varianti) per aiutarli in questo scopo

Pipelining