Il Processore: Datapath e Controllo

(1)

Il Processore: Datapath e

Controllo

Prof. Massimo De Santo

Nota: Questi lucidi sono un adattamento del materiale didattico relativo al Capitolo 4 del testo di Patterson & Hennessy “Struttura e progetto dei calcolatori”. Parte dei lucidi derivano dal lavoro del Dr. Sumanta Guha dell’Asian Istitute of Technology.

(2)

Realizziamo il MIPS

o

 

Implementazione dell’instruction set del MIPS

o

 

Semplificato per contenere solo

n  Istruzioni aritmetico-logiche: add, sub, and, or, slt

n  Istruzioni che riferiscono alla memoria: lw, sw

n  Istruzioni di controllo del flusso: beq, j

op rs rt offset

6 bits 5 bits 5 bits 16 bits

op rs rt rd shamt funct

6 bits 5 bits 5 bits 5 bits 5 bits 6 bits

R-Format

I-Format

op address

6 bits 26 bits

(3)

Il Ciclo Fetch/Execute

o  Vista ad alto livello della realizzazione fetch/execute

n  usa PC per leggere l’indirizzo dell’istruzione

n  fetch dell’istruzione dalla memoria e incremento PC

n  usa campi istruzione per selezionare i registri da leggere n  execute dipendente dall’istruzione

n  ripeti… Registers Register # Data Register # Data memory Address Data Register # PC Instruction ALU Instruction memory Address

(4)

Implementazione Processore

o  Single Cycle

n  Ogni istruzione eseguita in 1 ciclo di clock

n  Il ciclo di clock dimensionato sull’istruzione più lenta; quindi, n  svantaggio: velocità dimensionata sull’istruzione più lenta

o  Multi-Cycle

n  Dividere il ciclo fetch/execute in passi multipli n  Esecuzione di 1 passo ad ogni ciclo del clock

n  Vantaggio: ogni istruzione usa solo i cicli necessari

o  Pipelined

n  Esecuzione di ogni istruzione in passi multipli

n  Esecuzione di 1 step per istruzione in ogni ciclo di clock n  Elaborazione di più istruzioni in parallelo – assembly line

(5)

Elementi Funzionali

o  Due tipi di elementi funzionali nell’ hardware:

n  Elementi che operano sui dati (elementi combinatori)

(6)

Elementi Combinatori

o  Lavorano come funzioni input ⇒ output, ad es., ALU

o  La Logica combinatoria legge gli input da un registro e scrive gli

output in un altro registro o nello stesso registro di partenza.

o  Le operazioni di read/write avvengono in un singolo ciclo – gli

elementi combinatori non possono memorizzare i dati da un ciclo al prossimo State element 1 Combinational logic State element

(7)

Elementi di Stato

o  Gli elementi di stato contengono i dati, ad es., registri e

memoria

o  L’insieme degli elementi di stato definisce lo stato della

macchina

n  Che significa? Che succede se “spengo” e “riaccendo”…

o  I Flipflop e i latch sono elementi di stato 1-bit, cioè, sono

memorie 1-bit

o  Gli outputdi un flipflop o latch dependono sempre dal valore

del bit immagazzinato, cioè, dal loro stato, e possono essere chiamati 1/0 o high/low o true/false

o  L’input di un flipflop o latch può cambiare il suo stato in

(8)

Elementi di Stato del Datapath: Register File

o  I Registri sono realizzati con array di D-flipflop

Register file (banco dei registri)

Read register number 1 Read data 1 Read data 2 Read register number 2 Register file Write register Write data Write Clock 5 bits 5 bits 5 bits 32 bits 32 bits 32 bits Control signal

(9)

Elementi di Stato del Datapath: Register File (2)

o  Realizzazione delle Porte di Read:

Le porte di read sono implementate con una coppia di multiplexer: 5 bit per 32 registri

M u x Register 0 Register 1 Register n – 1 Register n M u x Read data 1 Read data 2 Read register number 1 Read register number 2 Clock

(10)

Elementi di Stato del Datapath: Register File (3)

o  Realizzazione delle Porte di Write:

La porta di write è implementata usando un decoder 5-to-32 per 32 registri.

Il clock è rilevante per il write: lo stato del registro può cambiare solo sul fronte del clock

n-to-1 decoder Register 0 Register 1 Register n – 1 C C D D Register n C C D D Register number Write Register data 0 1 n – 1 n Clock

(11)

Implementazione del MIPS Single-cycle

o  La nostra prima implementazione del MIPS userà un

singolo lungo ciclo di clock per ciascuna istruzione

o  Ogni istruzione inizia sul fronte di salita (o, discesa) del

clock e termina sul successivo fronte

o  Questo approaccio non è efficiente perchè è molto più

lento di quello multicycle dove differenti classi di istruzioni

possono avere differenti numberi di cicli

n  in una realizzazione single-cycle ogni istruzione prende lo

stesso tempo dell’istruzione più lenta

n  in una realizzazione multicycle questo problema è risolto

consentendo a istruzioni più veloci di usare meno cicli

o  Anche se il single-cycle non è efficiente, è semplice da

capire

(12)

Datapath: Fetch Istruzione & Incremento del PC

PC Instruction memory Instruction address Instruction

a. Instruction memory b. Program counter

Add Sum c. Adder PC Instruction memory Read address Instruction 4 Add

Tre elementi usati per

memorizzare e prelevare le istruzioni e

incrementare il PC

(13)

Datapath: funzionamento

Instruction <- MEM[PC] PC <- PC + 4 RD Memory ADDR PC Instruction 4 ADD

(14)

Datapath: Istruzioni R-Type

ALU control RegWrite Registers Write register Read data 1 Read data 2 Read register 1 Read register 2 Write data ALU result ALU Data Data Register numbers a. Registers b. ALU Zero 5 5 5 3 Instruction Registers Write register Read data 1 Read data 2 Read register 1 Read register 2 Write data ALU result ALU Zero RegWrite ALU operation 3

Due elementi usati per implementare le istruzioni R-type

(15)

Datapath: funzionamento

add rd, rs, rt

R[rd] <- R[rs] + R[rt]; 5 5 5 RD1 RD2 RN1 RN2 WN WD RegWrite Register File op rs rt rd shamt funct Operation ALU Zero Instruction 3

(16)

Datapath: Istruzioni Load/Store

16 32 Sign extend b. Sign-extension unit MemRead MemWrite Data memory Write data Read data

a. Data memory unit Address Instruction 16 32 Registers Write register Read data 1 Read data 2 Read register 1 Read register 2 Data memory Write data Read data Write data Sign extend ALU result Zero ALU Address MemRead MemWrite RegWrite ALU operation 3

Due elementi addizionali per

(17)

Datapath: funzionamento

op rs rt offset/immediate 5 5 16 RD1 RD2 RN1 RN2 WN WD RegWrite Register File Operation ALU 3 E X T N D 16 32 Zero RD WD MemRead Memory ADDR MemWrite 5

lw rt, offset(rs)

R[rt] <- MEM[R[rs] + s_extend(offset)];

(18)

op rs rt offset/immediate 5 5 16 RD1 RD2 RN1 RN2 WN WD RegWrite Register File Operation ALU 3 E X T N D 16 32 Zero RD WD MemRead Memory ADDR MemWrite 5

sw rt, offset(rs)

MEM[R[rs] + sign_extend(offset)] <- R[rt]

Datapath: funzionamento

(19)

Datapath: Istruzioni di Branch

16 32 Sign extend Zero ALU Sum Shift left 2 To branch control logic Branch target PC + 4 from instruction datapath

Instruction Add Registers Write register Read data 1 Read data 2 Read register 1 Read register 2 Write data RegWrite ALU operation 3 Datapath

Non serve hardware per lo shift: Basta connettere i fili da

input all’output, ognuno spostato a sinistra di 2 bits

(20)

beq rs, rt, offset

op rs rt offset/immediate 5 5 16 RD1 RD2 RN1 RN2 WN WD RegWrite Register File Operation ALU E X T N D 16 32 Zero ADD <<2 PC +4 from instruction datapath if (R[rs] == R[rt]) then   PC <- PC+4 + s_extend(offset<<2)

Datapath: funzionamento

(21)

MIPS Datapath I: Single-Cycle

L’Input è un registro (R-type) o la metà inferiore dell’istruzione estesa in segno (load/store)

Combiniamo i datapath delle istruzioni R-type e load/store usando due multiplexer

Il Dato proviene da ALU (R-type) o dalla memoria (load)

(22)

Datapath: funzionamento

Istruzioni R-type

add rd,rs,rt

5 5 16 RD1 RD2 RN1 RN2 WN WD RegWrite Register File Operation ALU 3 E X T N D 16 32 Zero RD WD MemRead Data Memory ADDR MemWrite 5 Instruction 32 M U X M U X ALUSrc MemtoReg

(23)

Datapath: funzionamento

Istruzioni Load

lw rt,offset(rs)

(24)

Datapath: funzionamento

Istruzioni Store

sw rt,offset(rs)

(25)

MIPS Datapath II: Single-Cycle

PC Instruction memory Read address Instruction 16 32 Registers Write register Write data Read data 1 Read data 2 Read register 1 Read register 2 Sign extend ALU result Zero Data memory Address Write data Read data _M u x 4 Add M u x ALU RegWrite ALU operation 3 MemRead MemWrite ALUSrc MemtoReg

Aggiungiamo il fetch dell’istruzione

instruction memory separata perché la lettura dell’istruzione dei dati può avvenire nello stesso ciclo

Adder separato perché le operazioni ALU e l’incremento del PC avvengono nello stesso ciclo

(26)

MIPS Datapath III: Single-Cycle

PC Instruction memory Read address Instruction 16 32

Add ALU _result

M u x Registers Write register Write data Read data 1 Read data 2 Read register 1 Read register 2 Shift left 2 4 M u x ALU operation 3 RegWrite MemRead MemWrite PCSrc ALUSrc MemtoReg ALU result Zero ALU Data memory Address Write data Read data _M u x Sign extend Add

Aggiungiamo il branch e un altro multiplexer

l’indirizzo della istruzione è PC+4 o l’indirizzo destinazione del branch

Adder Extra perchè ambedue operano in ogni ciclo

Nuovo multiplexer

Nota Importante : in una realizzazione single-cycle i dati non possono essere immagazzinati durante una istruzione – possono solo spostarsi nella logica combinatoria

(27)

Esecuzione della add

add rd, rs, rt

5 5 16 RD1 RD2 RN1 RN2 WN WD RegWrite Register File Operation ALU 3 E X T N D 16 32 Zero RD WD MemRead Data Memory ADDR MemWrite 5 Instruction 32 M U X ALUSrc MemtoReg ADD <<2 RD Instruction Memory ADDR PC 4 ADD ADD M U X M U X PCSrc

(28)

Esecuzione della lw

lw rt,offset(rs)

(29)

Esecuzione della sw

sw rt,offset(rs)

(30)

Esecuzione della beq

beq r1,r2,offset

(31)

Controllo

o  La Control Unit riceve gli input dai

n  bit dell’ opcode della istruzione

o  La Control Unit genera

n  gli input di controllo della ALU

n  i segnali di write enable (eventualmente, anche read enable) di

ogni elemento di memoria

(32)

Controllo della ALU

o  Il controllo principale invia un campo a 2-bit ALUOp al controllo ALU.

Usando ALUOp e il campo funct della istruzione il controllo ALU genera il campo di controllo a 3-bit della ALU

ALU control Func- field tion 000 and 001 or 010 add 110 sub 111 slt

o  La ALU deve eseguire

n  add per load/store (ALUOp 00) n  sub per branch (ALUOp 01)

n  Una tra and, or, add, sub, slt per le istruzioni R-type, in funzione del

campo a 6-bit funct (ALUOp 10)

Main

Control ALU Control 2 ALUOp 6 Instruction funct field 3 ALU control input To ALU ALUOp generation by main control Ricordiamo

(33)

Bit di controllo della ALU

*

C’è un errore nella fig del libro se X ->

conflitto tra la riga 2 e le 3-7!

(34)

Progetto del Controllo principale

o  Osservazioni sul formato istruzioni MIPS

n  L’opcode è sempre nei bit 31-26

n  i due registri da leggere sono sempre rs (bit 25-21) e rt (bit 20-16) n  il registro base per i load/store è sempre rs (bits 25-21)

n  l’offset a 16-bit per il branch equal e load/store è sempre nei bit 15-0 n  il registro destinazione per i loads è nei bit 20-16 (rt) mentre per le

istruzioni R-type è nei bit 15-11 (rd) (ci vorrà un multiplexer)

31-26 25-21 20-16 15-11 10-6 5-0 31-26 25-21 20-16 15-0 opcode opcode rs rs rt rt _address rd shamt funct R-type Load/store or branch

(35)

Unità di Controllo Datapath 1

MemtoReg MemRead MemWrite ALUOp ALUSrc RegDst PC Instruction memory Read address Instruction [31– 0] Instruction [20– 16] Instruction [25– 21] Add Instruction [5– 0] RegWrite 4 16 32 Instruction [15– 0] 0 Registers Write register Write data Write data Read data 1 Read data 2 Read register 1 Read register 2 Sign extend ALU result Zero Data memory Address Read data _M u x 1 0 M u x 1 0 M u x 1 0 M u x 1 Instruction [15– 11] ALU control Shift left 2 PCSrc ALU

Add _resultALU

Datapath del MIPS con i segnali di controllo e un multiplexer per selezionare il registro destinazione: a cosa servono i 9 segnali di controllo?

(36)

(37)

Unità di Controllo Datapath 2

PC Instruction memory Read address Instruction [31– 0] Instruction [20 16] Instruction [25 21] Add Instruction [5 0] MemtoReg ALUOp MemWrite RegWrite MemRead Branch RegDst ALUSrc Instruction [31 26] 4 16 32 Instruction [15 0] 0 0 M u x 0 1 Control

Add ALU _result

M u x 0 1 Registers Write register Write data Read data 1 Read data 2 Read register 1 Read register 2 Sign extend M u x 1 ALU result Zero PCSrc Data memory Write data Read data M u x 1 Instruction [15 11] ALU control Shift left 2 ALU Address

il datapath MIPS con la control unit: l’input di controllo è il campo opcode da 6-bit, l’output sono sette segnali da 1-bit e il segnale ALUOp da 2-bit

37 Per PCSrc è necessario il risultato dello zero test

(38)

I segnali di controllo

Instruction RegDst ALUSrc

Memto-Reg Reg Write Mem Read Mem

Write Branch ALUOp1 ALUp0

R-format 1 0 0 1 0 0 0 1 0

lw 0 1 1 1 1 0 0 0 0

sw X 1 X 0 0 1 0 0 0

beq X 0 X 0 0 0 1 0 1

Ricaviamo i segnali di controllo per il datapath MIPS a partire dal campo opcode dell’ istruzione

(39)

Segnali di Controllo: R-Type

Control signals shown in blue 1 0 0 0 1

??? Value depends on _funct

0 0 5 5 16 RD1 RD2 RN1 RN2 WN WD RegWrite Register File Operation ALU 3 E X T N D 16 32 Zero RD WD MemRead Data Memory ADDR MemWrite 5 Instruction I32 M U X ALUSrc MemtoReg ADD <<2 RD Instruction Memory ADDR PC 4 ADD ADD M U X M U X PCSrc MUX _RegDst 5 rd I[15:11] rt I[20:16] rs I[25:21] immediate/ offset I[15:0] 0 1 0 1 1 0 1 0 i segnali di controllo sono mostrati in blu

(40)

Segnali di Controllo:lw

0 Control signals shown in blue 0 010 1 1 1 0 1 5 5 16 RD1 RD2 RN1 RN2 WN WD RegWrite Register File Operation ALU 3 E X T N D 16 32 Zero RD WD MemRead Data Memory ADDR MemWrite 5 Instruction I32 M U X ALUSrc MemtoReg ADD <<2 RD Instruction Memory ADDR PC 4 ADD ADD M U X M U X PCSrc MUX _RegDst 5 rd I[15:11] rt I[20:16] rs I[25:21] immediate/ offset I[15:0] 0 1 0 1 1 0 1 0 i segnali di controllo sono mostrati in blu

(41)

Segnali di Controllo: sw

0 Control signals shown in blue X 010 1 X 0 1 0 5 5 16 RD1 RD2 RN1 RN2 WN WD RegWrite Register File Operation ALU 3 E X T N D 16 32 Zero RD WD MemRead Data Memory ADDR MemWrite 5 Instruction I32 M U X ALUSrc MemtoReg ADD <<2 RD Instruction Memory ADDR PC 4 ADD ADD M U X M U X PCSrc MUX _RegDst 5 rd I[15:11] rt I[20:16] rs I[25:21] immediate/ offset I[15:0] 0 1 0 1 1 0 1 0 i segnali di controllo sono mostrati in blu

(42)

Segnali di Controllo: beq

Control signals shown in blue X 110 0 X 0 0 0 1 if Zero=1 5 5 16 RD1 RD2 RN1 RN2 WN WD RegWrite Register File Operation ALU 3 E X T N D 16 32 Zero RD WD MemRead Data Memory ADDR MemWrite 5 Instruction I32 M U X ALUSrc MemtoReg ADD <<2 RD Instruction Memory ADDR PC 4 ADD ADD M U X M U X PCSrc MUX _RegDst 5 rd I[15:11] rt I[20:16] rs I[25:21] immediate/ offset I[15:0] 0 1 0 1 1 0 1 0 i segnali di controllo sono mostrati in blu

(43)

E il

_jump

?

o

 

Ricordiamo la struttura dell’istruzione:

o

 

il problema è la costruzione del target

address a 32 bit a partire dai 26 disponibili

o

 

Soluzione:

n 

spiazzamento relativo al PC

n 

allineamento della parola

31-26 25-0 opcode address Jump

(44)

Datapath esteso per il

_jump

Shift left 2 PC Instruction memory Read address Instruction [31– 0] Data memory Read data Write data Registers Write register Write data Read data 1 Read data 2 Read register 1 Read register 2 Instruction [15– 11] Instruction [20– 16] Instruction [25– 21] Add ALU result Zero MemtoReg ALUOp MemWrite RegWrite MemRead Branch Jump RegDst ALUSrc Instruction [31– 26] 4 M u x Instruction [25– 0] Jump address [31– 0]

PC+4 [31– 28] Sign extend 16 32 Instruction [15– 0] 1 M u x 1 0 M u x 0 1 M u x 0 1 ALU control Control

Add ALU _result

M u x 0 1 0 ALU Shift left 2 26 28 Address la Control Unit

genera un nuovo bit di controllo per il

Nuovo multiplexer con control bit Jump Costruzione del jump

(45)

Datapath: Esecuzione del jump

5 5 16 RD1 RD2 RN1 RN2 WN WD RegWrite Register File Operation ALU 3 E X T N D 16 32 Zero RD WD MemRead Data Memory ADDR MemWrite 5 Instruction I 32 M U X ALUSrc MemtoReg ADD <<2 RD Instruction Memory ADDR PC 4 ADD ADD M U X M U X PCSrc MUX _RegDst 5 0 1 0 1 1 0 1 0 ALU Control Control Unit 6 6 op I[31:

op I[31:26] funct I[5:0]

ALUOp 2 Branch M U X 0 1 Jump <<2 26 CONCAT 28 jmpaddr I[25:0] PC+4[31-28] 32

(46)

Analisi del single-cycle

o

 

l’esecuzione di ogni tipo di istruzione può essere

descritta attraverso varie “fasi” (step)

o

 

Le fasi non sono realmente distinte dal momento che

ogni istruzione viene completamente eseguita in un

singolo ciclo di clock – le fasi indicano semplicemente

il flusso dei dati nel datapath

o

 

il funzionamento del datapath durante un singolo ciclo

è puramente combinatorio – niente viene memorizzato

durante un ciclo di clock

o

 

Quindi, la macchina è stabile in un dato stato all’inizio

del ciclo e raggiunge un nuovo stato stabile alla fine

dello stesso ciclo

(47)

Istruzioni R-type: Fasi

add $t1, $t2, $t3

1.  Fetch dell’istruzione e incremento del PC

2.  Leggi i due registri sorgente dal register file:

rispettivamente ($t2) dai bit 20-16 e ($t3) dai bit 15-11dell’istruzione

3.  La ALU effettua la somma dei valori letti dal register file

4.  Il risultato viene scritto nel register file: il registro

destinazione ($t1) è individuato dai bit 25-21 dell’istruzione

(48)

Istruzioni Load/Store: Fasi

2.  Leggi il registro base dal register file: il registro base

($t2) è dato dai bit 25-21 dell’istruzione

3.  La ALU calcola la somma del valore letto dal the register

file e dell’offset esteso in segno contenuto nei 16 bit meno significativi dell’istruzione

4.  La somma è utilizza come indrizzo di accesso alla

memoria dati

5.  I dati letti in memoria vengono scritti nel register file: il

registro destinazione ($t1) è individuato dai 20-16 dell’istruzione

(49)

Istruzioni Branch: Fasi

2.  Leggi due registri ($t1 e $t2) dal register file

3.  La ALU calcola la differenza dei valori letti dal the

register file; il valore di PC+4 viene addionato all’offset esteso in segno fatto scorrere a sinistra di due per

calcolare l’indirizzo destinazione del branch

4.  Il risultato Zero dalla ALU è usato per decidere quale

delle due somme precedenti (dagli step 1 o 3) va memorizzato nel PC

(50)

_{Single-Cycle: Problemi}

o  Assumendo che il periodo del clock sia fisso e che per ogni

istruzione il datapath usa un singolo ciclo di clock, abbiamo:

n  CPI = 1

n  la durata del ciclo è determinata dall’istruzione con il percorso più

lungo (load)

o  molte istruzioni potrebbero esser eseguite con un ciclo più breve:

spreco di tempo

o  che succederà se introduco istruzioni più complesse come quelle in

virgola mobile?

n  tutte le risorse usate più di una volta nello stesso ciclo di clock

devono essere duplicate

(51)

Clock fisso vs. clock variabile

o  Consideriamo una macchina con una unità floating point.

Assumiamo i seguenti ritardi delle unità funzionali:

n  memoria: 2 ns., ALU e addizionatori: 2 ns., FPU add: 8 ns., FPU mul: 16 ns., accesso register file (read or write): 1 ns.

n  multiplexer, control unit, accessi al PC, sign extension, connessioni: no delay

o  Assumiamo il seguente mix di istruzioni

n  tutti i load durano lo stesso tempo e ammontano al 31% n  tutti gli store durano lo stesso tempo e ammontano al 21% n  le istruzioni R ammontano al 27%

n  i branch ammontano al 5%

n  gli jump ammontano al2%

n  FP add e sub durano lo stesso tempo e ammontano al 7%

(52)

Clock fisso vs. clock variabile (2)

o

 

Proviamo a comparare le prestazioni di

n

 

una realizzazione single-cycle che utilizza un clock

di periodo fisso

n

 

una realizzazione single-cycle che usa un clock di

periodo variabile

o  clock variabile significa che ogni istruzione viene eseguita

in un singolo periodo di clock che dura solo lo stretto necessario per quel tipo di istruzione (non si può fare in pratica ma supponiamo che lo sia!)

(53)

Soluzione

o  Periodo del clock nel caso clock fisso =

T istruzione più lunga = 20 ns.

o  Periodo medio del clock nel caso clock variabile =

8 × 31% + 7 × 21% + 6 × 27% + 5 × 5% + 2 × 2% +

20 × 7% + 12 × 7% = 7.0 ns.

o  Quindi, performance_var-period/performance_fixed-period= 20/7 = 2.9

Instruction Instr. Register ALU Data Register FPU FPU Total class mem. read oper. mem. write add/ mul/ time sub div ns. Load word 2 1 2 2 1 8 Store word 2 1 2 2 7 R-format 2 1 2 0 1 6 Branch 2 1 2 5 Jump 2 2 FP mul/div 2 1 1 16 20 FP add/sub 2 1 1 8 12

(54)

Considerazioni

o

 

una soluzione: un clock di periodo variabile con

differenti tempi di ciclo per ogni classe di istruzioni

n  infattibile, realizzare un clock a velocità variabile è un

incubo progettuale

o

 

un’altra possibile soluzione:

n  usare un periodo di clock piccolo…

n  … facendo si che le diverse istruzioni vengano eseguite

con un numero di cicli di clock diverso

dividendo le istruzioni in fasi e eseguendo ogni fase in un singolo ciclo

(55)

Approccio Multicycle

o  suddividere le istruzioni in passi

n  ogni passo dura un ciclo di clock

n  bilanciare l’ammontare di lavoro in modo che ogni passo sia

all’incirca uguale all’altro

n  fare in modo che in ogni ciclo si utilizzi una sola unità funzionale

così da non doverle duplicare

n  le unità funzionali posso essere condivise tra i diversi cicli di una

istruzione

o  tra i passi

n  alla fine d un ciclo i dati devono essere memorizzati per poter

essere utilizzati in cicli successivi della stessa istruzione

o  è necessario inserire registri intermedi interni (cioè invisibili al

programmatore)

n  I dati che dovranno essere usati in istruzioni successive sono

memorizzati negli elementi di stato visibili: il register file, il PC, la memoria

(56)

Datapath Multicycle

n  singola memoria per dati e istruzioni

n  singola ALU, non sono necessari adder extra

n  registri extra per memorizzare i dati tra i cicli di clock

PC Memory Address Instruction or data Data Instruction register Registers Register # Data Register # Register # ALU Memory data register A B ALUOut 56

(57)

Datapath Multicycle (2)

Shift left 2 PC Memory MemData Write data M u x 0 1 Registers Write register Write data Read data 1 Read data 2 Read register 1 Read register 2 M u x 0 1 M u x 0 1 4 Instruction [15– 0] Sign extend 32 16 Instruction [25– 21] Instruction [20– 16] Instruction [15– 0] Instruction register 1 M u x 0 3 2 M u x ALU result ALU Zero Memory data register Instruction [15– 11] A B ALUOut 0 1 Address

(58)

Suddividere le istruzioni in passi

o  Ogni passo richiede un ciclo di clock

1.  IF: Instruction fetch e incremento PC

2.  ID: Instruction decode e prelievo dei registri

3.  EX: Esecuzione, calcolo indirizzo memoria o complet. branch

4.  MEM: Accesso in memoria o completamento istruzioni R-type

5.  WB: completamento lettura memoria

(59)

Passo 1:

IF

o  Uso del PC per prelevare l’istruzione e inserirla nell’apposito

instruction register

Incremento del PC di 4 e memorizzazione del risultato nel PC

o  ogni passo è composto di “micro-passi” che possono essere

descritti in RTL (Register-Transfer Language):

IR = Memory[PC]; PC = PC + 4;

(60)

Passo 2: (

ID

)

o  Leggi i registri rs e rt se l’istruzione lo richiede

Calcola l’indirizzo di salto se l’istruzione è un branch

o  RTL:

A = Reg[IR[25-21]]; B = Reg[IR[20-16]];

(61)

Passo 3:

EX

o

 

la ALU esegue una tra quattro funzioni in

dipendenza del tipo di istruzione

n  riferimento di memoria:

ALUOut = A + sign-extend(IR[15-0]);

n  R-type:

ALUOut = A op B;

n  branch (l’istruzione termina):

if (A==B) PC = ALUOut;

n  jump (l’istruzione termina):

PC = PC[31-28] || (IR(25-0) << 2)

(62)

Passo 4:

MEM

o  Sempre in dipendenza dal tipo di istruzione:

o  i Load e Store accedono alla memoria

n  load

MDR = Memory[ALUOut];

n  store (l’istruzione termina)

Memory[ALUOut] = B;

o  R-type (l’istruzione termina)

(63)

Passo 5:

WB

o  Sempre in dipendenza dal tipo di istruzione:

o  i Load scrive nei registri (writes back) (l’istruzione termina)

Reg[IR[20-16]]= MDR;

Nota Importante:

Non ci sono motivi dal punto di vista del datapath (o del controllo) perché il Passo 5 non possa essere eliminato eseguendo

Reg[IR[20-16]]= Memory[ALUOut];

per le istruzioni load nel Passo. In questo modo scomparirebbe il registro MDR

Il motivo per non farlo risiede nel fatto che per mantenere i singoli Passi bilanciati in lunghezza, occorre far si che ogni Passo contenga al più una operazione ALU o un accesso ai registri o un accesso alla memoria

(64)

Vista d’insieme

Step name

Action for R-type instructions

Action for memory-reference instructions

Action for branches

Action for jumps IF: Instruction fetch IR = Memory[PC]

PC = PC + 4

ID: Instruction A = Reg [IR[25-21]]

decode/register fetch B = Reg [IR[20-16]]

ALUOut = PC + (sign-extend (IR[15-0]) << 2)

EX: Execution, address ALUOut = A op B ALUOut = A + sign-extend if (A ==B) then PC = PC [31-28] II

computation, branch/ (IR[15-0]) PC = ALUOut (IR[25-0]<<2)

jump completion

MEM: Memory access or R-type Reg [IR[15-11]] = Load: MDR = Memory[ALUOut]

completion ALUOut or

Store: Memory [ALUOut] = B

(65)

Multicycle Passo1: IF

IR = Memory[PC]; PC = PC + 4; 4 PC + 4 5 5 RD1 RD2 RN1 RN2 WN WD RegWrite Registers Operation ALU 3 Zero RD WD MemRead Memory ADDR MemWrite 5 Instruction I PC I R M D R A B ALU OUT

(66)

Multicycle Passo 2: ID

A = Reg[IR[25-21]]; (A = Reg[rs]) B = Reg[IR[20-15]]; (B = Reg[rt]) ALUOut = (PC + sign-extend(IR[15-0]) << 2) Branch Target Address Reg[rs] Reg[rt] PC + 4 5 5 RD1 RD2 RN1 RN2 WN WD RegWrite Registers Operation ALU 3 Zero RD WD MemRead Memory ADDR MemWrite 5 Instruction I PC I R M D R A B ALU OUT

(67)

Multicycle Passo 3: EX (est. segno)

ALUOut = A + sign-extend(IR[15-0]); Mem. Address Reg[rs] Reg[rt] PC + 4 5 5 RD1 RD2 RN1 RN2 WN WD RegWrite Registers Operation ALU 3 Zero RD WD MemRead Memory ADDR MemWrite 5 Instruction I PC I R M D R A B ALU OUT

(68)

Multicycle Passo 3: EX (R-Type)

ALUOut = A op B R-Type Result Reg[rs] Reg[rt] PC + 4 5 5 RD1 RD2 RN1 RN2 WN WD RegWrite Registers Operation ALU 3 Zero RD WD MemRead Memory ADDR MemWrite 5 Instruction I PC I R M D R A B ALU OUT

(69)

Multicycle Passo 3: EX (Branch)

if (A == B) PC = ALUOut; Branch Target Address Reg[rs] Reg[rt] Branch Target Address 5 5 RD1 RD2 RN1 RN2 WN WD RegWrite Registers Operation ALU 3 Zero RD WD MemRead Memory ADDR MemWrite 5 Instruction I PC I R M D R A B ALU OUT

(70)

Multicycle Passo 3: EX (Jump)

PC = PC[31-28] concat (IR[25-0] << 2) Jump Address Reg[rs] Reg[rt] Branch Target Address 5 5 RD1 RD2 RN1 RN2 WN WD RegWrite Registers Operation ALU 3 Zero RD WD MemRead Memory ADDR MemWrite 5 Instruction I PC I R M D R A B ALU OUT

(71)

Multicycle Passo 4: MEM (Read lw)

MDR = Memory[ALUOut]; Mem. Data PC + 4 Reg[rs] Reg[rt] Mem. Address 5 5 RD1 RD2 RN1 RN2 WN WD RegWrite Registers Operation ALU 3 Zero RD WD MemRead Memory ADDR MemWrite 5 Instruction I PC I R M D R A B ALU OUT

(72)

Multicycle Passo 4: MEM (Write sw)

Memory[ALUOut] = B; PC + 4 Reg[rs] Reg[rt] 5 5 RD1 RD2 RN1 RN2 WN WD RegWrite Registers Operation ALU 3 Zero RD WD MemRead Memory ADDR MemWrite 5 Instruction I PC I R M D R A B ALU OUT

(73)

Multicycle Passo 4: MEM (R-Type)

Reg[IR[15:11]] = ALUOUT R-Type Result Reg[rs] Reg[rt] PC + 4 5 5 RD1 RD2 RN1 RN2 WN WD RegWrite Registers Operation ALU 3 Zero RD WD MemRead Memory ADDR MemWrite 5 Instruction I PC I R M D R A B ALU OUT

(74)

Multicycle Passo 5: WB (lw)

Reg[IR[20-16]] = MDR

;

PC + 4 Reg[rs] Reg[rt] Mem. Data Mem. Address 5 5 RD1 RD2 RN1 RN2 WN WD RegWrite Registers Operation ALU 3 Zero RD WD MemRead Memory ADDR MemWrite 5 Instruction I PC I R M D R A B ALU OUT

(75)

Multicycle: Controllo

Shift left 2

MemtoReg

IorD MemRead MemWrite

PC Memory MemData Write data M u x 0 1 Registers Write register Write data Read data 1 Read data 2 Read register 1 Read register 2 Instruction [15– 11] M u x 0 1 M u x 0 1 4 ALUOp ALUSrcB RegDst RegWrite Instruction [15– 0] Instruction [5– 0] Sign extend 32 16 Instruction [25– 21] Instruction [20– 16] Instruction [15– 0] Instruction register 1 M u x 0 3 2 ALU control M u x 0 1 ALU result ALU ALUSrcA Zero A B ALUOut IRWrite Address Memory data register

(76)

Multicycle: Controllo (2)

Shift left 2 PC M u x 0 1 Registers Write register Write data Read data 1 Read data 2 Read register 1 Read register 2 Instruction [15– 11] M u x 0 1 M u x 0 1 4 Instruction [15– 0] Sign extend 32 16 Instruction [25– 21] Instruction [20– 16] Instruction [15– 0] Instruction register ALU control ALU result ALU Zero Memory data register A B IorD MemRead MemWrite MemtoReg PCWriteCond PCWrite IRWrite ALUOp ALUSrcB ALUSrcA RegDst PCSource RegWrite Control Outputs Op [5– 0] Instruction [31-26] Instruction [5– 0] M u x 0 2 Jump address [31-0] Instruction [25– 0] 26 _Shift 28 left 2 PC [31-28] 1 1 M u x 0 3 2 M u x 0 1 ALUOut Memory MemData Write data Address Nuovo multiplexer

(77)

Sommario

o  Le tecniche descritte finora sono il cuore delle architetture

contemporanee

o  La soluzione Multicycle offre due grandi vantaggi

n  le unità funzionali possono essere riusate all’interno di una singola

istruzione – riduzione di costi e migliore uso spazi

n  le istruzioni con un percorso di esecuzione più breve possono

essere completate più velocemente utilizzando meno cicli di clock

o  I computer moderni spingono il paradigma multicycle ad un livello

più alto per ottenere un più alto throughput delle istruzione:

n  introdurremo il pipelining nel quale molte istruzioni possono esser

eseguite contemporaneamentee mediante la sovrapposizione delle diverse fasi di ciascuna

n  tutte le scelte architetturali del MIPS troveranno una spiegazione completa quando capiremo che sono state fatte in vista del pipeline