1 1

Calcolatori Elettronici T ISA DLX: Implementazione

Tramite Struttura Sequenziale

2 2

E disponibile un interprete e simulatore (EasyDLX) per un insieme semplificato dellISA DLX realizzato da Daniele Biagi nellambito di un progetto del corso di Linguaggi e Modelli computazionali (prof. Denti). Il simulatore in grado di eseguire salti, evidenziando step by step la prossima istruzione che sar eseguita. Supporta tutte operazioni logiche e aritmetiche con operandi interi. Home page (Google code): http://code.google.com/p/easydlx/ Pagina web sul sito di Linguaggi e Modelli computazionali: http://edenti.deis.unibo.it/Ling/2010-2011/BestProjects/Biagi/index.html

3 3

Riassunto delle principali caratteristiche dellISA del DLX

32 registri da 32 bit di uso generale (R0..R31, con R0=0) 32 registri floating point da 32 bit (utilizzati esclusivamente dalle unit funzionali in

virgola mobile) Istruzioni di lunghezza costante 32 bit allineate Campi di dimensioni fisse nellambito di istruzioni diverse 3 formati di istruzione: I, R, J Non ci sono istruzioni specifiche per la gestione dello stack Nelle istruzioni di tipo JL lindirizzo di ritorno e salvato in R31 Non c un registro di FLAG settato dalle istruzioni ALU; le condizioni vengono settate

esplicitamente nei registri con il gruppo di istruzioni SET condition IN REGISTER (SCN): SetCoNdition Rd, Rs1, Rs2/Immediato (ex. Cond: EQ (if Rs1=Rs2 then Rd

4 4

Il set di istruzioni del DLX Le principali istruzioni aritmetiche e logiche

Istruzioni logiche anche con op. immediato: AND, ANDI, OR, ORI, XOR, XORI Istruzioni aritmetiche: ADD, ADDI, SUB, SUBI, MULT, DIV Istruzioni di traslazione logica (a destra anche aritmetica): SLL(I)1, SRL(I), SRA(I)2

Istruzioni di SET CONDITION: Scn, ScnI(mmediate), con cn = EQ, NE, LT, GT, LE, GE Le principali istruzioni di trasferimento dati

Load byte (signed/unsigned), Load Halfword (signed/unsigend), Load Word (LB, LBU, LH, LHU, LW)

Store byte, Store Halfword, Store Word (SB, SH, SW) Load/Store Floating Point in singola o doppia precisione (LF/SF e LD/SD) Copia un dato da un GPR a un FPR e viceversa (MOVI2FP e MOVFP2I)

Le principali istruzioni di trasferimento del controllo Istruzioni di salto condizionato (PC+4 relative): BNEZ, BEQZ Istruzioni di salto incondizionato diretto e indiretto(PC+4 relative): J, JR Istruzioni di chiamata a procedura (Jump and Link, lindirizzo di ritorno viene

automaticamente salvato in R31): JAL, JALR Istruzione di ritorno dalla procedura di servizio delle interruzioni: RFE

1) Shift logico a sinistra e shift aritmetico a sinistra coincidono (entrano 0 nei bit meno significativi). Per questa ragione NON esiste SLA. Fare attenzione con shift a sinistra, non preserva il segno e pu generare overflow. 2) NB. Trascinando a destra di una posizione un registro e inserendo a sinistra sempre il bit del segno si mantiene il segno del dato mentre lo si divide successivamente per 2

5 5

DLX: formato delle istruzioni

Load, Store, Branch condizionale, JR e JALR (trasf. controllo via registro), SetCond e ALU con op. imm.

Nelle operazioni di LD e ALU RS2=Rdest, nelle ST RS2=sorg. -- RS1 per indirizzo o sorgente (con imm.)

I Codice operativo RS2/Rd RS1 Operando immediato di 16 bit

J Codice operativo Offset di 26 bit (PC relative)

Trasferimento del controllo diretto e incondizionato (J e JAL)

R Codice operativo RS2 RS1 Rd Estensione al Cod. op (11 bit)

Istruzioni aritmetiche e logiche del tipo Rd Rs1 op Rs2 oppure SetCond fra registri

6 bit 5 bit 5 bit 5 bit 11 bit

0 31

Numerazione dei bits

Attenzione: in alcune istruzioni I (LOAD e ALU) RS2 rappresenta il registro destinazione

6 6

Istruzioni Aritmetico Logiche (ALU)

Istruzioni a 3 operandi 2 operandi sorgente 1 operando destinazione.

destinazione: registro

sorgente : registro, registro / operando immediato (16 bit)

Esempi: ADD R1, R2, R3 R1 R2+R3

ADDI R1, R2, 3 R1 R2+3

ADDI R1, R0, 5 R1 0+5 (cio : ) formato I R1 5

ADD R1, R5, R0 R1 R5+R0 (cio : ) formato R R1 R5

formato R

formato I R1 in posizione Rd, R2 e R0 in posizione RS1 nel formato della istruzione

R1 in posizione Rd nel formato della istruzione

7

Istruzioni di Set Condition

Queste istruzioni confrontano i due operandi sorgente e mettono a 1 oppure a 0 loperando destinazione in funzione del risultato del confronto

SLT R1,R2,R3 if (R2

8

Istruzioni per il trasferimento dati (formato I, unica modalit di indirizzamento)

Sono istruzioni che accedono alla memoria (load e store) Lindirizzo delloperando in memoria la somma del contenuto di

un registro con un offset di 16 bit Listruzione codificata secondo il formato I Esempi:

LW R1, 40(R3) R1 32 M[40+R3]

LB R1, 40(R3) R1 M[40+R3] ## (M[40+R3]7)24

Sign Extension

LBU R1,40(R3) R1 M[40+R3] ## (0)24

SW R7,10(R5) 32 R7 M[10+R5]

LH R1, 40(R3) R1 M[41+R3] ## (M[41+R3]7)16 M[40+R3] ##

9 9

Istruzioni per il trasferimento del controllo: salti incondizionati (con e senza ritorno)

JUMP: Trasferimento del controllo (o salto) incondizionato JUMP AND LINK: Trasferimento di controllo con salvataggio

dellindirizzo di ritorno (chiamata a procedura) BRANCH: Trasferimento di controllo condizionato (salto condizionato)

(PC relative, OFFSET di 26 bit) J alfa PC (PC +4) + OFFSET(alfa) Formato Istruz. di tipo J

JALR R3 R31 PC+4 ; PC R3 JAL alfa R31 PC+4 ; PC (PC +4) + OFFSET(alfa)

JUMP

J R3 PC R3 Formato Istruz. di tipo I

JUMP AND LINK (salto a procedura e ritorno)

J R31 PC R31 Questa listruzione di ritorno da procedura (senza stack possibile un solo livello di nesting !!)

10 10

BRANCH BRANCH EQUAL ZERO BRANCH NOT EQUAL ZERO

BEQZ R4, alfa

( sono entrambe istruzioni PC relative, con OFFSET di 16 bit)

if (R4=0): PC (PC +4)+OFFSET(alfa)

BNEZ R4, alfa if (R4=0): PC (PC +4)+OFFSET(alfa)

BEQZ e BNEZ sono istruzioni di formato I

Con una istruzione di tipo set condition seguita da unistruzione di salto condizionato si realizza la funzione di Compare and Branch (confronto e salto condizionato dal risultato del confronto) senza bisogno di flag dedicati

N.B. il registro da cui dipende il salto indicato nel formato della istruzione nella posizione RS1

Istruzioni per il trasferimento del controllo: salti condizionati (Branch)

11 11

Esempio di codice assembler DLX

Si scriva il codice assembler per il calcolo della somma degli elementi di un vettore di indirizzo iniziale A (= 2^15 ?

12 12

Datapath e Unit di Controllo La struttura di una CPU, come tutte le reti logiche sincrone che elaborano dati, pu essere

strutturata in due blocchi Unit di Controllo e Datapath. La CPU, per funzionare, ha bisogno della memoria esterna su cui risiedono il programma

e i dati.

reset

interrupt ready

CPU

istruzioni

Dati (in)

indirizzi

Dati (out)

U.d.C.

Data Path

clock memoria

Rete logica processore

13 13

Datapath: contiene tutte le unit di elaborazione ed i registri necessari per lesecuzione delle istruzioni della CPU. Ogni istruzione appartenente allInstruction Set eseguita mediante una successione di operazioni elementari, dette micro-operazioni.

Micro-operazione: operazione eseguita allinterno del DATAPATH in un ciclo di clock (esempi: trasferimento di un dato da un registro ad un altro registro, elaborazione ALU)

Unit di Controllo: una RSS che in ogni ciclo di clock invia un ben preciso insieme di segnali di controllo al DATAPATH al fine di specificare lesecuzione di una determinata micro-operazione.

Datapath e Unit di Controllo

14 14

Register file C A

B

Struttura del DLX (esecuzione sequenziale)

TEMP

IAR

PC

S1 S2 dest

alu

CPU

Memoria

dati in scrittura

dati/istruzioni in lettura Indirizzi

Instruction register

C O

N T

R O

L

U

N I

T

fetch

MDR

MAR

execute

Parallelismo dellarchitettura: 32 bit

(bus, alu e registri hanno parallelismo 32) I segnali di controllo non sono riportati !

15

I registri del DLX (tutti a 32 bit)

15

Register file: 32 Registri General Purpose Registers R0.R31 con R0=0

IAR: Interrupt Address Register Deposito dellindirizzo di ritorno in caso di interruzione

PC: Program Counter MAR: Memory Address Register Contiene lindirizzo del dato da

scrivere o leggere in memoria IR: Instruction Register Contiene listruzione attualmente in

esecuzione TEMP: Temporary Register Registro di deposito temporaneo di

risultati MDR: Memory Data Register Registro di transito temporaneo dei

dati da e per la memoria A e B: Registri di uscita dal Register File

A parte il Register File questi registri NON sono accessibili al programmatore !!! In alcuni casi istruzioni speciali per accedere ad alcuni (e.g., IAR)

16 16

Funzioni della ALU Dest (uscite) 4 bit di comando S1 + S2 S1 S2 S1 and S2 S1 or S2 S1 exor S2 Shift S1 a sinistra di S2 posizioni Shift S1 a destra di S2 posizioni Shfit S1 aritmetico a destra di S2 posizioni S1 S2 0 1

Flag di uscita Zero Segno negativo Carry

La ALU una rete PURAMENTE combinatoria

17 17

Trasferimento dati sul datapath I bus S1 ed S2 sono multiplexati (tri-state) con parallelismo 32 bit. I registri campionano sul fronte positivo del clock, hanno due porte di

uscita O1 e O2 per i due bus (o i registri A e B) e dispongono di tre ingressi di controllo:

un ingresso di Write Enable (WE*) ed uno di Output Enable per ogni porta di uscita, una per ogni bus S1 e S2 (OE1* e OE2*).

Al fine di valutare la massima frequenza a cui possibile far funzionare il datapath importante conoscere le seguenti temporizzazioni:

TC (max) : ritardo max tra il fronte positivo del clock e listante in cui i segnali di controllo generati dallunit di controllo sono validi;

TOE (max): ritardo max tra larrivo del segnale OE e listante in cui i dati del registro sono disponibili sul bus;

TALU (max): ritardo massimo introdotto dalla ALU; TSU (min) : tempo di set-up minimo dei registri (requisito minimo per il

corretto campionamento da parte dei registri). La massima frequenza di funzionamento del data path si calcola come

segue:

fCK(max) = 1/TCK

TCK > TC (max) + TOE (max) + TALU (max) + TSU (min)

18 18

Esempio : esecuzione della microistruzione Rin Rout

S2

alu

WE* OE1*

OE2* WE* OE1*

OE2*

S1

Rout Rin

dest

clock

O2 O1 O2 O1

I I i1 i2 u = i2

WERin*

OE2Rout*

I segnali in blu (segnali di controllo) provengono dallUnit di Controllo

I segnali di controllo in grassetto sono attivi nel ciclo di clock in cui il micro-step Rin Rout viene eseguito

(e.g. TEMP) (e.g. MAR)

Clock sempre collegato: write enable !

19 19

Il set di istruzioni non floating-point del DLX Data Transfer LW Ra, offset(Rb) LB Ra, offset(Rb) LBU Ra, offset(Rb) LH Ra, offset(Rb) LHU Ra, offset(Rb) SW Ra, offset(Rb) SH Ra, offset(Rb) SB Ra, offset(Rb) LHI Ra, value *MOVS2I Ra, Rs *MOVI2S Rs, Ra * Special register Rs (IAR)

Aritmetiche/logiche ADD Ra,Rb,Rc ADDI Ra,Rb,value ADDU Ra,Rb,Rc ADDUI Ra,Rb, value SUB Ra,Rb,Rc SUBI Ra,Rb,value SUBU Ra,Rb,Rc SUBUI Ra,Rb, value DIV Ra,Rb,Rc DIVI Ra,Rb,value MULU Ra,Rb,Rc MULI Ra,Rb, value SLL Ra ,Rb,Rc SLLI Ra,Rb;value SHR Ra,Rb.Rc SHRI Ra,Rb,value SLA Ra,Rb,Rc SLAI Ra,Rb,value OR Ra,Rb,Rc ORI Ra,Rb,value XOR Ra,Rb,Rc XORI Ra,Rb,value AND Ra,Rb,Rc ANDI Ra,Rb,value

Controllo SETx Ra,Rb,Rc SETIx Ra,Rb,value BEQZ Ra, offset BNEQZ Ra, offset J offset JR Ra JL offset JLR Ra N.B. x pu essere LT, GT, LE, GE, EQ, NE Esiste anche listruzione TRAP che esegue una chiamata a interrupt software vettorizzata

20 20

Il progetto dellUnit di Controllo Una volta definito il Set di Istruzioni e progettato il DATAPATH, il passo

successivo del progetto di una CPU il progetto dellUnit di Controllo (CONTROLLER).

Il CONTROLLER una RSS: il suo funzionamento pu essere specificato tramite un diagramma degli stati.

Il CONTROLLER (come tutte le RSS) permane in un determinato stato per un ciclo di clock e transita (pu transitare) da uno stato allaltro in corrispondenza degli istanti di sincronismo (fronti del clock).

Ad ogni stato corrisponde quindi un ciclo di clock. Le micro-operazioni che devono essere eseguite in quel ciclo di clock sono specificate (in linguaggio RTL) nel diagramma degli stati che descrive il funzionamento del CONTROLLER allinterno degli stati.

A partire dalla descrizione RTL si sintetizzano poi i segnali di controllo che devono essere inviati al DATAPATH per eseguire le operazioni elementari

associate ad ogni stato.

21 21

Il diagramma degli

stati del controller

Data transfer

ALU

Set

Jump

Branch

Ready ? IR

Estrazione automatica dei registri durante la fase di decode di una istruzione (qualsiasi)

I Codice operativo RS2/Rd RS1 Operando immediato di 16 bit

J Codice operativo Offset di 26 bit (PC relative)

R Codice operativo RS2 RS1 Rd Estensione al Cod. op (11 bit)

0 31

<

A B

Questi 5 + 5 bit sono utilizzati per estrarre, preventivamente e ancora prima di conoscere che tipo di istruzione che stata letta dalla memoria, dal Register File due registri in A e B. Nel caso di istruzione J non ci sono registri coinvolti e quindi saranno estratti bit corrispondenti alloffset. Nel caso di istruzione I, in B potrebbe finire il valore del registro destinazione (e.g. in una LD o operazione ALU (tipo I)). Infine: i 5 + 5 bit rappresentano gli indici (o presunti tali) ma non il valore dei due registri che contenuto nel Register File.

23 23

Gli stati della fase di fetch In questa fase si deve verificare se presente un interrupt (evento esterno

asincrono che la CPU deve servire con apposito software); se linterrupt presente e pu essere servito (IEN = true) si esegue

implicitamente listruzione di chiamata a procedura allindirizzo 0, e si salva lindirizzo di ritorno nellapposito registro IAR;

se linterrupt non presente o le interruzioni non sono abilitate, si va a leggere in memoria la prossima istruzione da eseguire (il cui indirizzo in PC)

MAR PC

Dallultimo stato dellistruzione

precedente IAR: Interrupt Address Register IAR PC

PC 0

IEN 0

IEN: Interrupt

Enable Flag

(int and IEN) = 1 (int and IEN) = 0

IR M(MAR)

Alla fase di decodifica

Ready = 1

Ready = 0

24 24

Si modifica il DATAPATH in

maniera da poter indirizzare

la memoria dal PC. Meno stati ma

maggiore complessit

Data transfer

ALU

Set

Jump

Branch

Ready ? INSTRUCTION FETCH

INSTRUCTION DECODE*

Tutte le istruzioni impiegano un clock in meno per essere

eseguite ! Ma

potenzialmente aggiore lentezza

-> minore freq. clock

Il diagramma degli

stati del controller

PC

25 25

Ready ?

IR

26 26

Estensione del segno (IR15)16 ## IR15..0

0

15

31

IR

31 3017 16

BUS S1 o S0

Da UdC

15-0

27 27

MDR

Memoria logica

Memoria fisica

BUS 3

8

7

6

5

4

3

2

1

0 a

b

c

d

e

f

g

h

i

a

e

i

b

f

l

0 7 8 15

c

g

d

h

16 23 24 bit 31

8

7

6

5

4

2

1

0

BUS 2 BUS 1 BUS 0

29 29

Trasferimenti BYTE, HW I trasferimenti di bytes sono SEMPRE considerati allineati I trasferimenti di HW debbono avvenire a indirizzi multipli di 2 I trasferimenti di Word debbono sempre avvenire a indirizzi multipli di 4 In caso di disallineamento: fault Nel caso di store di dati di dimensione inferiore alla word NON si ha estensione del segno La lettura/scrittura di bytes e HW (a causa del reciproco disallineamento fra i registri e la memoria) implica che fra i registri e la memoria siano interposti dei mux/demux (realizzati con tristate)

Registro MDR

Memoria

Come sono attivati i WE delle memorie ?

Progettare la rete

30 30

Trasferimenti BYTE, HW MDR

Memoria

31 0

Mux Demux

I MUX 23-16 e 31-24 hanno come ingresso anche il bit 7 del byte 7-0 della memoria (LB) e il bit 15 del byte 15-8 della memoria (LH) Ad esempio in una LB il MUX 7-0 si collega direttamente alla memoria mentre i MUX 15-8, 23-16 e 31-24 si collegano al bit 7 del MUX 7-0 proveniente dalla memoria. In una SH a indirizzo multiplo di 2 e non di 4 il DEMUX 7-0 dal MDR si collega alla memoria 23-16 e il DEMUX 15-8 alla memoria 31-24. Gli altri due bytes della memoria rimangono invariati

Mux Demux

0

Bit pi signif. byte precedenti

Solo in lettura

Trasferimento unsigned

24 23 16

31 31

C

32 32 RD

33 33 INIT

C

34 34

INIT

A = 0

BRANCH

YES YES NO NO

BEQZ BNEZ Controllo per le istruzioni di BRANCH A! = 0

PC

35 35

Numero di clock necessari per eseguire le istruzioni

Istruzione Cicli Wait Totale

Load 6 2 8 Store 5 2 7 ALU 5 1 6 Set 6 1 7 Jump 3 1 4 Jump and link 5 1 6 Branch (taken) 4 1 5 Branch (not taken) 3 1 4

CPI CPIN

numero totale di istruzioni ii

n

=i = 1 ( * )

Esempio su DLX LOAD: 21%, STORE: 12%, ALU: 37%, SET: 6%, JUMP: 2% BRANCH (taken): 12%, BRANCH (not-taken): 11%

CPI = 6.3

36 36

Controllo cablato (hardwired) Segnali di controllo

INSTRUCTION REGISTER (IR)

40

Opcode + OpCode Extension

6

Datapath

Stato presente

Rete combinatoria che genera uscite e stato futuro

Int e ready 2 6+11 3

Stato futuro

228 righe

Rs1, Rs2, Rd

- Indici di Rs1, Rs2 e Rd provengono da IR

- IR25..0 sono portati ai bus S1 ed S2 del data path attraverso due buffer tristate

IR25..0

U.d.C.

32 bit dalla memoria

- U.d.C. genera anche i segnali di comando per la memoria (MEMRD e MEMWR)

Flag

37 37

I passi dellesecuzione delle istruzioni Nel DLX lesecuzione di tutte le istruzioni pu essere scomposta in 5 passi, ciascuno eseguito in uno o pi cicli di clock. Tali passi sono detti: 1) FETCH: listruzione viene prelevata dalla memoria e posta in IR. 2) DECODE: listruzione in IR viene decodificata e vengono prelevati gli

operandi sorgente dal Register File. 3) EXECUTE: elaborazione aritmetica o logica mediante la ALU. 4) MEMORY: accesso alla memoria e, nel caso di BRANCH aggiornamento

del PC (branch completion). 5) WRITE-BACK: scrittura sul Register File.

38 38

Le micro-operazioni eseguite in ciascun passo

1) FETCH MAR PC ;

M[MAR];

2) DECODE

A RS1, B RS2, PC PC+4

IR

39 39

Le micro-operazioni eseguite in ciascun passo

MEMORIA:

MDR B;

ALU:

BRANCH:

3) EXECUTE

MAR A + (IR15)16 ## IR15..0 ;

C

40 40

Le micro-operazioni eseguite in ciascun passo

4) MEMORY

MDR M[MAR]; (LOAD)

MDR; (STORE)

BRANCH:

M[MAR]

If (Cond) PC Temp;

Memoria:

[A] il registro che condiziona il salto (Cond) ;

JAL e JALR: C PC;

41 41

5) WRITE-BACK

RD C ;

C MDR; (se una LOAD due micropassi))

Le micro-operazioni eseguite in ciascun passo

PC Temp;

istruzioni J, JR, JAL, JALR

istruzioni diverse da J, JR, JAL, JALR

RD C ;