ALUctrRegDstALUSrcExtOpMemToRegMemWrEqualImm16RdRtRsnPC_selInstructionMemoryDataPathControl UnitOpFunRegWrInstruction[31:0][21:25][16:20][11:15][0:15][26:31][0:5]OpFunRsRtRdImm7

(1)

Università degli Studi dell’Insubria Dipartimento di Scienze Teoriche e Applicate

Architettura degli elaboratori

CPU multiciclo

Marco Tarini

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

Esempio di CPU monociclo Quadro complessivo

- 2 -

ALUctr

RegDst ExtOpALUSrc MemWr MemToReg

Equal Imm16

Rd Rt Rs

nPC_sel Instruction

Memory

DataPath Control Unit

Op Fun

RegWr

Instruction[31:0]

[21:25] [16:20] [11:15] [0:15]

[26:31] [0:5]

Op Fun

Rs Rt Rd Imm

7

(2)

Il datapath: quadro complessivo

- 3 -

32 ALUctr

Clk busW

RegWr

32 32

busA

32 busB

5 5 5

Rw Ra Rb 32x32 Registers

Rs

Rd Rt

RegDst

Extender

16 32 imm16

ALUSrc ExtOp

Clk

Adr Data Memory

32 MemToReg 7

WrEn MemWr

Mux

In Out

*

nPC_sel 30

ALU

= alla CU

Clk PC

CInSUM 1

30 30 00

30 30

instruction 32

32 Instrucntion

Memory Adr

Out

Cosa non va in un processore con CPI=1?

Il tempo di ciclo è lungo

Tutte le istruzioni impiegano lo stesso tempo della più lenta La memoria reale non si comporta come quella ipotizzata

Non riesce a completare letture o scritture in un solo ciclo ragionevolmente breve

CPU multiciclo

Architettura degli elaboratori - 4 -

Arithmetic & Logical

Load

Store

Branch

Critical Path

PC Inst Memory Reg File mux ALU mux setup

PC Inst Memory Reg File mux ALU Data Mem mux setup

PC Inst Memory Reg File mux ALU Data Mem

PC Inst Memory Reg File cmp mux

(3)

Riduzione del tempo di ciclo

Si spezza la rete combinatoria in due parti (con registri in mezzo) Il lavoro che si faceva in un ciclo lento viene fatto in due cicli, più veloci

CPU multiciclo

storage element

Combinational Logic

storage element

storage element storage element

Combinational Logic (A)

storage element Combinational

Logic (B)

Esempio di CPU monociclo Quadro complessivo

- 6 -

ALUctr

RegDst ExtOpALUSrc MemWr MemToReg

Equal Imm16

Rd Rt Rs

nPC_sel Instruction

Memory

DataPath Control Unit

Op Fun

RegWr

Instruction[31:0]

[21:25] [16:20] [11:15] [0:15]

[26:31] [0:5]

Op Fun

Rs Rt Rd Imm

7

(4)

Partizionamento del Datapath

CPU multiciclo

PC

Next PC Operand Fetch Exec Reg. File

Mem Access Data Mem

Instruction Fetch Result Store

ALUctr RegDst

ALUSrc

ExtOp MemWr

nPC_sel RegWr

MemWrMemRd

Control Unit

Qui memorizziamo i dati intermedi (in appositi registri)

Datapath Multiciclo

CPU multiciclo

PC

Next PC Operand Fetch Ext ALU Reg. File

Mem Access Data Mem

Instruction Fetch Result Store

ALUctr RegDst

ALUSrc

ExtOp

nPC_sel RegWr

MemWrMemRd

IR

A B

R

M Reg

File

MemToReg Equal

ALU exec Mem access

(5)

CPU multiciclo: vantaggio ulteriore

Nella CPU a 1 ciclo, abbiamo dovuto replicare delle parti del datapath:

memoria:

per LW, in uno stesso ciclo devo

sia leggere una istruzione sia leggere un dato dalla RAM:

Soluzioni (poco realistiche):

o separazione di RAM istruzioni dalla RAM dati:-(

o memoria a doppio bus di uscita (caro!) :-(

ALU:

per BEQ, in uno stesso ciclo devo sia computare la condizione (zero),

sia eseguire una somma calcolare il valore del nuovo PC soluzione:

un addizionatore ulteriore fuori dalla ALU solo per il computo del PC:-(

Nella CPU multiciclo, le stessa memoria e la stessa ALU possono assolvere funzioni diverse in passi diversi! :-)

CPU multiciclo

Esempio: istruzione R-type (add, sub, . . .)

CPU multiciclo

PC

Next PC Exec Reg. File

Mem Access Data Mem

IR

A B

S

M Reg

File

Equal

Istruz. Trasferimento logico tra Registri ADDU R[rd]  R[rs] + R[rt];

PC  PC + 4

Istruz. Trasferimento fisico tra Registri (fetch) IR  MEM[PC]

ADDU

A  R[rs]; B  R[rt]

S  A + B

R[rd]  S; PC  PC + 4

(6)

Esempio: istruzione I-type

(qui: un’operazione logica con valore immediato)

Istruz. Trasferimento logico tra Registri

ORi R[rt]  R[rs] OR zx(Im16);

PC  PC + 4

Istruz. Trasferimento fisico tra Registri

(fetch) IR  MEM[PC]

ORi

S  A or ZeroExt(Im16) R[rt]  S; PC  PC + 4

CPU multiciclo

PC

Mem Access Data Mem

IR

A B

S

M Reg

File

Equal

Esempio: istruzione I-type

Istruz. Trasferimento logico tra Registri

LW R[rt]  MEM[R[rs] + sx(Im16)]

Istruz. Trasferimento fisico tra Registri

(fetch) IR  MEM[PC]

LW

S  A+SignExt(Im16) M  Mem[S]

R[rt]  M; PC  PC + 4

CPU multiciclo

PC

Mem Access Data Mem

IR

A B

S

M Reg

File

Equal

(7)

Esempio: istruzione Store

Istruz. Trasferimento logico tra Registri SW MEM[ R[rs] + sx(Im16) ]  R[rt];

Istruz. Trasferimento fisico tra Registri IR  MEM[PC]

SW

S  A+SignExt(Im16) Mem[S]  B; PC  PC + 4

CPU multiciclo

PC

Mem Access Data Mem

IR

A B

S

M Reg

File

Equal

Esempio: Instruzione Branch

Istruz. Trasferimento logico tra Registri BEQ if R[rs] == R[rt]

then PC  PC+4+ sx(Im16) || 00 else PC  PC+4

Istruz. Trasfer. fisico tra Registri IR  MEM[PC]

BEQ|Eq PC  PC + sx(Im16) || 00 BEQ|/Eq PC  PC + 4

CPU multiciclo

PC

Mem Access Data Mem

IR

A B

S

M Reg

File

Equal

Si ipotizza che il banco dei registri sia capace di valutare

l’uguaglianza di Rs e Rt

(8)

Università degli Studi dell’Insubria Dipartimento di Scienze Teoriche e Applicate

CPU multiciclo a bus interno

Un altro modo di progettare una CPU

Ricorda: la CPU si connette alla memoria centrale attraverso un Bus (esterno)

Architettura degli elaboratori

Memory ^B_U

S

CPU

(9)

Datapath a singolo bus (interno) CPU

CPU multiciclo

ALU PC MAR

MDR

Memory IR

ordini . . .

Temp Addr

Data

V

Z 4

select

ALU Op

BUS

Control Unit

CPU BUS

ImmExt Realistica

(possibile gerarchia)

R₃₁ R₀ R₁

…

CPU a Singolo Bus: note 1/2

Idea:

usare un Bus interno alla CPU per connettere tutti i suoi componenti i Registri utente R0…R31

altri Registri di uso interno (PC e IR incluso) la ALU

la Control Unit

Ciascuno dei passi in cui è scomposta ogni istruzione dell’

Instruction Set viene formulato come una sequenza di trasferimenti di valore fra i registri (utente, o di uso interno)

(compreso quello che avviene attraverso la ALU)

dei three-state-buffers connettono registri da/al BUS interno, controllano quale registro viene riversato sul / lett dal bus sono pilotati da appositi ordini provenienti dalla CU (qui: in blu) L’interazione con la memoria centrale avviene attraverso degli appositi registri (dato e address: MDR MAR), cablati sul BUS esterno

CPU multiciclo

(10)

CPU a Singolo Bus: note 2/2

Esempio: per il registo interno PC:

ordine PC_out: se = 1, si riversa il contenuto di PC sul bus ordine PC_in: se = 1 , il PC viene impresso col contenuto del bus nota: alcuni registri sono cablati solo in lettura o solo in scrittura sul bus (vedi direzione delle freccie nello schema=

Ad ogni ciclo, solo UN registro può essere immesso sul BUS interno perché abbiamo un unico bus interno (CPU BUS)

per il registro scelto, R_outvale 1

per tutti gli altri registri, l’ordine R_outvale 0

Il valore del registro scelto verrà trasferito su tutti i reg in cui R_in= 1 Nota: tutti i registri sono sincronizzati in scrittura con il clock.

CPU multiciclo

Controllo del bus interno

CPU multiciclo

R_i V

Z

CPU BUS

Riin

Ri_out Vin

Zin

Z_out

IR_in IR

PC ^PCin

MAR MAR_in

alla ALU dalla ALU

alla CU

MDR ^MDRⁱⁿ

MDRout

PC_out

da Imm_out IR

Immediate value

…

(11)

BUS

CPU

Uso del bus CPU-RAM

CPU BUS

MAR ^MARin

MDR ^MDRⁱⁿ

MDRout

Memory addr

data

Control Unit

RD WR

2

CPU

Uso del bus CPU-RAM

CPU BUS

MAR ^MARin

MDR ^MDRⁱⁿ

MDRout

Memory addr

data

Control Unit

RD WR

2

B U S

2

32

(12)

Bus che connette la CPU alla RAM:

note

Consiste di 3 fasci di connessioni:

Address(qui 32 bits – se 32 è lunghezza della parola) Connette l’apposito registro MAR

alla porta ADDR del banco di memoria

Data(32 bits – se 32 è lunghezza della parola)

Connette il campo Data della memoria a MDR, e viceversa.

Percorso in un verso o l’altro (o nessuno dei due)

a seconda di appositi tri-state buffers controllati dal banco di memoria (detti Output Enable e Chip Select, come sappiamo)

Controllo(qui 2 bits)

i segnali read e write dalla CU,

si immettono negli input RD e WR della memoria

inoltre, vedremo dopo, il segnale MFC verso la CU (un terzo bit)

E’ questa la composizione di tutti i tipici bus

CPU multiciclo

CPU multiciclo con bus interno

Ogni registro ha (sottointeso, non disegnato nello schema)

la sincronizzazione col clock (al fronte di discesa, ogni registro può memorizzare il contenuto del bus interno)

il comando di caricamento (L, per Load) pilotato dallo stesso ordine di ingresso

es: per il registro PC, PC_incontrolla sia il three state buffer che L

CPU multiciclo

CPU BUS

PC

PC_in

PC_out

L

32

clock

possibile variante:

PC_incontrolla solo L ma PC_outdeve controlalre un Three State buffer!

(13)

Registri utente

CPU multiciclo

ALU PC MAR

MDR

Memory

IR ordini

. . .

Temp Addr

Data

V

Z

A B

R 4

select

Controllo ALU

BUS

Control Unit

MUX

CPU BUS

ImmExt

R₃₁ R₀ R₁

…

CPU

Registri utente: note

Sono gli unici “visibili” al programmatore.

Cioè quelli che compaiono nelle istruzioni dell’Instruction Set.

attraverso le istruzioni, il programmatore ne controlla il contenuto.

(o, più spesso, il compilatore,

quando il programmatore scrive codice ad alto livello) Sono quei 32 registri R0…R31 previsti dal MIPS

Nel nostro schema precedente, erano contenuti nel Register File In questo schema, è più comodo gestirli come 32 registri separati Dall’esterno vengono spesso chiamati semplicemente «i registri»

(nei contesti in cui CPU la usiamo, piuttosto che chiederci come sia fatta)

Gli altri registri dello schema sono di uso interno alla CPU:

servono all’esecuzione delle istruzioni

I registri utente non devono essere “sporcati” nell’esecuzione.

CPU multiciclo

(14)

Registri di uso interno

CPU multiciclo

ALU PC MAR

MDR

Memory

IR ordini

. . .

Temp Addr

Data

V

Z

A B

R 4

select

Controllo ALU

BUS

Control Unit

MUX

CPU BUS

Imm16ext

R₃₁ R₀ R₁

…

CPU

Registri di uso interno (non utente): note

Hanno ruoli specifici:

PC (Program Counter):

contiene l’indirizzo della prossima istruzione IR (Instruction Register):

contiene l’istruzione corrente MAR (Memory Address Register):

contiene l’indirizzo di memoria centrale a cui compiere l’accesso (in lettura o scrittura)

MDR (Memory Data Register):

contiene la parola letta dalla memoria o da scrivere in memoria VeZ:

il (potenziale) primo parametro della ALU, e il suo risultato Temp:

registro temporaneo generico

Alcuni solo scritti dal BUS, altri sia scritti che letti

(e sono cablati di conseguenza sui Bus, interni ed esterni)

CPU multiciclo

(quali? Vedi lo schema)

(15)

Unità di controllo

CPU multiciclo

ALU PC MAR

MDR

Memory

IR ordini

. . .

Temp Addr

Data

V

Z

A B

R 4

select

Controllo ALU

BUS

Control Unit

MUX

CPU BUS

Imm16ext

R₃₁ R₀ R₁

…

CPU

Unità di controllo

CPU multiciclo

clock

IR

next step WMFC

Step No

read write alla memoria

Logica di controllo (combinatorio)

alla ALU

op

…

al datapath

3

3 Op

code

(16)

Logica (combinatoria!) dell’unità di controllo

Prende in input:

Istruzione corrente In particolare, OpCode Numero del passo corrente

Ogni istruz = tanti passi

CPU multiciclo

Produce in output ordini/segnali:

Read / Write per la memoria RAM indirzzati alla RAM

(passeranno attraverso il BUS esterno) La Op della ALU

Quale op deve calcolare la ALU…

I mutex del datapath ALU Bit di controllo del BUS interno

Tutti i valori dei three state buffer Determinano quale registro viene copiato in quale/i registro/i Quale sia il prossimo passo

(per ora…)

CPU multiciclo

ALU PC MAR

MDR

IR ordini

. . .

TEMP Addr

Data

V

Z

A B

R 4

select4

ALUcrt

Control Unit

MUX

CPU BUS

ImmOut

R₃₁ R₀

…

to m e m

Vin PCout MARin MARout

PCin

MDRin MDRout

Zin

Zout

IRin

R0in R0out

R31in R31out TEMPin TEMPout

…

esiti

(17)

Semantica delle istruzioni

espressa con «RTL» (Register Transfer Logic)

Istruzione Effetto su registri e memoria Effetto su PC

addu R[rd]  R[rs] + R[rt] PC  PC + 4

subu R[rd]  R[rs] – R[rt] PC  PC + 4

ori R[rt]



R[rs] OR zero_ext(imm16)

PC  PC + 4

lw R[rt]



MEM[R[rs] + sign_ext(imm16)]

PC  PC + 4

sw MEM[R[rs] + sign_ext(imm16)]

 R[rt]

PC  PC + 4

beq if(R[rs]==R[rt])

then PC  PC + 4 +

sign_ext(imm16)||00 else PC  PC + 4

- 36 -

Esecuzione dell’instruction fetch

CPU multiciclo

L’instruction fetche la prima parte del ciclo fetch-and-execute Ad livello più alto, consiste in due sotto-operazioni:

IR ← MEM[ PC ]; // caricamento dell’istruzione in IR PC ← PC + 4 ; // passaggio all’istruzione successiva Come implementare questo con la nostra achietettura?

METODO:

guardare lo schema

scegliere una sequenza di trasferimenti

(rispettando i vincoli: le connessione cablate, il bus può trasportare una sola parola alla volta, etc)

riportare, per ogni passo dell’esecuzione,

quali ordini devono essere emanati dalla Control UNIT

(18)

Esecuzione dell’instruction fetch

Vogliamo ottenere:

IR ← MEM[ PC ];

PC ← PC + 4 ;

Esempio di implementazione:

dal passo 5 in poi, eseguiremo l’istruzione caricata in IR

CPU multiciclo

Passo (ciclo di clock)

Comandi Passo

Succ.

Effetti:

0 PCout, MARin, 1 MAR ← PC;

1 Read 2 MDR←MEM[MAR];

2 MDRout, IRin 3 IR ← MDR;

3 PCout, select 4, add, Zin 4 Z ← PC+4;

4 Zout, PCin 5 PC←Z;

Esecuzione dell’instruction fetch

Nell’implementazione vista sopra,

utilizziamo 5 passi (5 cicli di clock) per eseguire un instruction fetch

Possiamo fare meglio? Sì!

alcuni passi possono essere eseguiti in parallelo Il passo 0 e il passo 3 per esempio:

solo il 3 ha bisogno della ALU

entrambi riversano il contenuto del registro PC sul bus Il passo 0 e il passo 1

Nello stesso passo in cui riemipamo MAR,

possiamo chiedere alla memoria di leggere a quella locazione (il risultato arriverà in MDR)

Una versione ottimizzata quindi usa quindi solo 3 passi

CPU multiciclo

(19)

Esecuzione dell’instruction fetch (ottimizzata)

Vogliamo ottenere:

IR ← MEM[ PC ];

PC ← PC + 4 ;

Impementazione ottimizzata:

Dal passo 3 in poi, eseguiremo l’istruzione (ora nell’IR)

CPU multiciclo

Comandi Passo

Succ.

Effetti:

0 PCout, MARin,

select 4, add, Zin, read

1 MAR ← PC;

Z ← PC+4;

1 Zout, PCin, 2 PC←Z;

MDR←MEM[MAR];

Come implementare l’attesa variabile della memoria

L’accesso in memoria centrale può richiedere un numero variabile di cicli, durante i quali la CU deve rimanere in attesa / in pausa

Il numero esatto dipende da quale caso si verifica -- per es : cache hitin L1: nessun ciclo di attesa

cache miss in L1, cache hit in L2: 3 cicli di attesa cache miss in L1, cache miss in L2: 10 cicli di attesa

Nel nostro caso, alla fine del passo 1 potrebbe essere necessario aspettare che la memoria ottemeperi alla richesta

la CPU deve attendere!

idea: congeliamo il contatore di passi cioè gli impediamo, temporaneamente, di assumere il valore del prossimo passo

...fino a che la memoria non ha completato la richiesta Come implementare questo comportamento?

CPU multiciclo

(20)

Come implementare l’attesa variabile della memoria

CPU multiciclo

Comandi Passo

Succ.

Effetti:

0 PCout, MARin,

select 4, add, Zin

1 MAR ← PC;

Z ← PC+4;

1 Zout, PCin,

read

2 PC←Z;

MDR←MEM[MAR];

ATTESA DI UN CERTO NUMERO DI CICLI DI CLOCK (quanti ce ne vogliono perché la memoria finisca)

Come implementare l’attesa variabile della memoria

Come implementare questo comportamento?

Nella memoria: viene implementato un segnale «ho finito»

chiamato MFC: Memory Function Complete

viene settato ad 1 (dalla memoria) quando l’op richiesta è conclusa raggiungerà la Control Unit attraverso il bus esterno

MFC fa parte dei segnali di controllo di cui è composto quel bus Nella CU, introduciamo il bit di «GO»: (implementazione: un RS-latch!)

1: aggiorna il passo con il prossimo valore (quando il clock scatta) 0: (freeze) non aggiornarlo  tutto rimane fermo allo stato attuale Quando la CU si appresta a utilizzare la memoria, un manda WMFC

WMFC: Wait for MFC

resetta il bit di «GO»  la CU si mette in pausa (asinconamente!) Il MFC lanciato dalla memoria setta il bit di «GO» nuovamente a 1!

(asinconamente!)

Qualsiasi numero di cicli di clock può essere passato nel frattempo

CPU multiciclo

(21)

Unità di controllo (updated)

CPU multiciclo

clock

IR

next step WMFC

dalla memoria MFC

Step No go

bit

S R

Q

read write alla memoria

Logica di controllo (combinatorio)

alla ALU

op

…

al datapath

L

3

3 Op

code

Logica (combinatoria!) dell’unità di controllo

Prende in input:

Istruzione corrente In particolare, OpCode Numero del passo corrente

Ogni istruz = tanti passi

CPU multiciclo

Produce in output ordini/segnali…:

Read / Write per la memoria RAM indirzzati alla RAM

(passeranno attraverso il BUS esterno) La Op della ALU

Quale op deve calcolare la ALU…

I mutex del datapath ALU Bit di controllo del BUS interno

Tutti i valori dei three state buffer Determinano quale registro viene copiato in quale/i registro/i Quale sia il prossimo passo Il comando WMFC

«Wait (for) MFC»

Se 1: resetta il bit “Go”, mettendo in pausa la CU fino a quando la RAM non la risveglia mandando MFC

«Memory Function Completed»

(22)

Temporizzazione: lettura da memoria

CPU multiciclo

Clock

1° ciclo 2° ciclo 3° ciclo

MAR_in Indir.

read R/W MDR_inE

4° ciclo 5° ciclo

dato

MFC MDR_out

attesa della lettua !

Nuova versione dell’ instruction fetch:

Dal passo 3 in poi, eseguo l’execute dell’istruzione nell’IR

Come implementare l’attesa variabile della memoria

CPU multiciclo

Comandi Passo

Succ.

Effetti:

0 PCout, MARin, read, select 4, add, Zin

1 MAR ← PC;

Z ← PC+4;

1 Zout, PCin

WMFC

2 PC←Z;

MDR←MEM[ MAR ];

(23)

Simulazione passo 0

PCout, MARin, read, select 4, add, Zin

CPU multiciclo

ALU PC MAR

Memory MDR IR

RD

ordini . . .

R₁ Addr

Data

V

Z

A B

R 4

Select 4

ADD

BUS

Control Unit

MUX

R₂

R₃

CPU BUS

Read

Legge la parola all’indirizzo 1000, dove c’è l’istruzione

add R3 R2 R1

1000

1004

Simulazione passo 1 (inizio) Zout, PCin

CPU multiciclo

ALU PC MAR

MDR

Memory

IR ordini

. . .

R₁ Addr

Data

V

Z

A B

R 4

select

Controllo ALU

BUS

Control Unit

MUX

R₂

R₃

CPU BUS

1004

(24)

Simulazione passo 1 (conclusione) Zout, PCin, Vin

CPU multiciclo

ALU PC MAR

MDR

Memory

IR ordini

. . .

R₁ Addr

Data

V

Z

A B

R 4

select

Controllo ALU

BUS

Control Unit

MUX

R₂

R₃

CPU BUS

Istruzione add R3 R2 R1

MFC Inviato quando la

lettura è completata

Simulazione passo 2 MDRout, IRin

CPU multiciclo

ALU PC MAR MDR

Memory

IR ordini

. . .

R₁ Addr

Data

V

Z

A B

R 4

select

Controllo ALU

BUS

Control Unit

MUX

R₂

R₃

CPU BUS

Istruzione

add R3 R2 R1 Istruzione

add R3 R2 R1