Progetto Processore MIPS con pipeline a 5 stadi - … Processore MIPS... · 6. Programmi di test:...

. . . . . .. . . .

. . . . . . . . .

UUUnnniiivvveeerrrsssiii tttààà dddeeeggglll iii ssstttuuudddiii dddiii PPPaaavvviiiaaa

CALCOLATORI ELETTRONICI II

PPRROOGGEETTTTOO VVHHDDLL::

PPRROOCCEESSSSOORREE MMIIPPSS CCOONN PPIIPPEELLIINNEE AA 55 SSTTAADDII PPEERR IINNTTEERRII

a cura di

Andrea Brandoli Alessandro Garberi Paolo Milanesi

A.A. 2003/2004

Calcolatori Elettronici II Processore MIPS con pipeline a 5 stadi per interi

1

INDICE INDICE............................................................................................................ 1

INTRODUZIONE............................................................................................. 4

Descrizione del progetto...................................................................................................4

Descrizione del gruppo di lavoro ......................................................................................4

PARSER ......................................................................................................... 5

Uso dell'interfaccia grafica ...............................................................................................5

Sintassi riconosciuta dal parser........................................................................................7

Sorgente di MIPS2BIN .....................................................................................................8

ISA: INSTRUCTION SET ARCHITECTURE .................................................. 9

Istruzioni di Tipo-R ...........................................................................................................9

Istruzioni di Tipo-I ...........................................................................................................11

Istruzioni di Tipo-J ..........................................................................................................12

DESCRIZIONE FUNZIONALE DELLE DESIGN ENTITIES......................... 13

1. MI: MEMORIA ISTRUZIONI ...................................................................................14

1.1. ARCHITETTURA .............................................................................................14

1.1.1. CARICAMENTO DELLE ISTRUZIONI IN MEMORIA ...............................14

1.1.2. LETTURA DELLE ISTRUZIONI DALLA MEMORIA .................................15

1.2. DATAFLOW.....................................................................................................15

2. MD: MEMORIA DATI..............................................................................................16

2.1. ARCHITETTURA .............................................................................................16

2.1.1. LETTURA E SCRITTURA DEI DATI IN MEMORIA..................................17

2.2. DATAFLOW.....................................................................................................17

3. Reg: BANCO REGISTRI ........................................................................................18

3.1. ARCHITETTURA .............................................................................................19

3.1.1. SCRITTURA/LETTURA REGISTRI ..........................................................19

3.1.2. SELEZIONE DEI DATI LETTI...................................................................20

3.2. DATAFLOW.....................................................................................................20

4. ALU: UNITA’ LOGICO-ARITMETICA ....................................................................22

4.1. ARCHITETTURA .............................................................................................22

4.1.1. ESECUZIONE DEI COMANDI ALU..........................................................22

4.2. DATAFLOW.....................................................................................................23


2

5. FASE IF: INSTRUCTION FETCH...........................................................................24

5.1. ARCHITETTURA .............................................................................................24

5.1.1. AGGIORNAMENTO SINCRONO DEL PROGRAM COUNTER ...............24

5.1.2. AGGIORNAMENTO COMBINATORIO DEL PROGRAM COUNTER.......25

5.2. DATAFLOW.....................................................................................................25

6. FASE ID: INSTRUCTION DECODE .......................................................................27

6.1. ARCHITETTURA .............................................................................................27

6.1.1. REGISTRI DI PIPELINE IF/ID ..................................................................28

6.1.2. UNITÀ PER IL RILEVAMENTO E PER LA GESTIONE DELLE CRITICITÀ

DI CONTROLLO .....................................................................................................28

6.1.2.1. Criticità “load”.......................................................................................29

6.1.2.2. Criticità “load-store”..............................................................................29

6.1.2.3. Criticità “branch”...................................................................................29

6.1.2.4. Criticità “jalr”.........................................................................................30

6.1.2.5. Criticità “jmp”........................................................................................31

6.1.3. UNITÀ PER LA GESTIONE DELLE ECCEZIONI .....................................31

6.1.4. UNITÀ DI CONTROLLO ...........................................................................32

6.1.5. CALCOLO DEL PROSSIMO PROGRAM COUNTER ..............................33

6.1.6. AZZERAMENTO DEI BIT DI CONTROLLO .............................................34

6.1.7. ALTRI PROCESSI ....................................................................................35

6.1.7.1. Jalr Mux: selezione dato letto 1............................................................35

6.1.7.2. Jalr Mux: selezione registro destinazione ............................................35

6.1.7.3. Jalr Mux: selezione dell’indirizzo di salto..............................................36

6.1.7.4. Beq: controllo uguaglianza dati letti .....................................................36

6.2. DATAFLOW.....................................................................................................36

7. FASE EX: EXECUTE..............................................................................................38

7.1. ARCHITETTURA .............................................................................................38

7.1.1. REGISTRI DI PIPELINE ID/EX.................................................................39

7.1.2. FORWARDING.........................................................................................39

7.1.3. MUX: SELEZIONE OPERATORE 1 .........................................................41

7.1.4. MUX: SELEZIONE DATO DA SCRIVERE NELLA MEMORIA DATI ........41

7.1.5. MUX: SELEZIONE OPERATORE 2 .........................................................42

7.1.6. MUX: SELEZIONE REGISTRO DESTINAZIONE.....................................42

7.1.7. ECCEZIONE: SCRITTURA REGISTRI EPC E CAUSA............................42


3

7.1.8. AZZERAMENTO DEI BIT DI CONTROLLO .............................................43

7.1.9. UNITÀ DI CONTROLLO DELLA ALU.......................................................44

7.1.10. GENERAZIONE DEL BIT DI ECCEZIONE...............................................44

7.2. DATAFLOW.....................................................................................................44

8. FASE DM: DATA MEMORY...................................................................................46

8.1. ARCHITETTURA .............................................................................................46

8.1.1. REGISTRI DI PIPELINE EX/DM...............................................................47

8.1.2. LETTURA E SCRITTURA E SELEZIONE DATO DA SCRIVERE IN

CACHE DATI ..........................................................................................................47

8.2. DATAFLOW.....................................................................................................48

9. FASE WB: WRITE BACK ......................................................................................49

9.1. ARCHITETTURA .............................................................................................49

9.1.1. REGISTRI DI PIPELINE DM/WB..............................................................50

9.1.2. SELEZIONE DATO DA SCRIVERE SU BANCO REGISTRI ....................50

9.2. DATAFLOW.....................................................................................................51

10. CONCLUSIONI: Schema finale .........................................................................52

11. CONCLUSIONI: Dataflow finale ........................................................................53

TESTBENCH ................................................................................................ 54

1. Forwarding ..............................................................................................................54

2. Criticità load & load-store ........................................................................................55

3. Branch dipendente ..................................................................................................56

4. Eccezione: Owerflow...............................................................................................57

5. Eccezione: divisione per zero .................................................................................58

6. Programmi di test: ‘fattoriale.asm’ ...........................................................................59

7. Programmi di test: ‘numeri_primi.asm’ ....................................................................61

8. Programmi di test: ‘matrice.asm’ .............................................................................63

ESEMPIO DI SIMULAZIONE ....................................................................... 65

1. Fase IF: Instruction Fetch .......................................................................................66

2. Fase ID: Instruction Decode (rilevazione stallo) ......................................................67

3. Fase ID: Instruction Decode (decodifica istruzione) ................................................68

4. Fase EX: Execute ...................................................................................................69

5. Fase DM: Data Memory ..........................................................................................70

6. Fase WB: Write Back ..............................................................................................71

INDICE DELLE FIGURE, TABELLE ED EQUAZIONI ................................. 72


4

INTRODUZIONE

Descrizione del progetto

Questo è il progetto in VHDL di un semplice processore MIPS. Le sue caratteristiche sono:

- processore a 32 bit con architettura RISC in pipeline a 5 stadi

- cache dati e cache istruzioni separate

- 32 registri general pourpose

- ALU per numeri interi

Descrizione del gruppo di lavoro

Il lavoro è stato effettuato da:

- Brandoli Andrea [email protected]

- Garberi Alessandro [email protected]

- Milanesi Paolo [email protected]

Le varie parti del progetto sono state suddivise nella maniera qui sotto riportata:

- Garberi Alessandro si è curato della pianificazione e della programmazione del

parser che ha permesso di codificare le istruzioni da Assembler MIPS a codice

binario eseguibile. Inoltre si è occupato di progettare la memoria dati del

processore.

- Gli altri componenti del gruppo hanno curato lo sviluppo del progetto di tutte le

restanti entità e più precisamente: Brandoli Andrea si è occupato interamente della

progettazione delle fasi di data memory, di write back e della ALU, mentre Milanesi

Paolo ha progettato la memoria istruzioni e la fase di fetch. Le fasi di decode,

execute e il banco registri – per via della loro complessità e dipendenza – sono

state progettate da entrambi.

Non va dimenticato comunque che una considerevole parte del lavoro è stata realizzata

da tutti i componenti del gruppo, che si sono trovati assiduamente in Università, al fine di

assemblare le varie entità e testare il corretto funzionamento del progetto.


5

PARSER Il programma MIPS2BIN converte il set di istruzioni del nostro processore (un piccolo

MIPS) in binario leggibile dal processore. L'output di questo programma può essere usato

direttamente come sorgente per la memoria istruzioni nel simulatore VHDL.

Figura 1 – Interfaccia parser di base

Uso dell'interfaccia grafica

Il programma è composto principalmente da 2 finestre di testo: quella di sinistra per il

sorgente in assembly-code, quella di destra per l'output in binary-code.

Il pulsante Convert avvia la traduzione.

Durante la traduzione vengono evidenziati gli eventuali errori riscontrati, dando il

riferimento alla riga e al tipo di errore. In caso di errori non gravi viene comunque

generato un codice binario, anche se con alcuni bit indicati come “-” nel caso di registro

non valido o “~” nel caso di overflow; una riga di 32 “*” indica invece un'istruzione non

riconosciuta.


6

Figura 2 – Interfaccia parser: riconoscimento errore

Una volta effettuata la traduzione è possibile spostarsi con il mouse sopra le varie linee del

sorgente o del binario per visualizzare la traduzione della singola istruzione nelle varie

parti di cui è composta o l'indirizzo delle etichette. Se si modifica il testo compare un “*”

sulla parte superiore della finestra che è stata modificata, così da ricordare che la

traduzione non è stata aggiornata; mentre “*” è attivo non è possibile vedere la traduzione

delle singole linee di codice al passaggio del mouse (in quanto non sarebbero

coerenti). Cliccando su Convert di nuovo, gli “*” spariranno.

I pulsanti Copy, presenti da entrambe le parti, copiano il contenuto della finestra in

memoria (negli appunti), così da poterli incollare dove serve.

Il pulsante New svuota il contenuto della finestra del sorgente, così da poter inserire un

nuovo programma.

Il pulsante Paste sostituisce il contenuto della finestra del sorgente con il testo presente in

memoria (negli appunti), così da poter inserire un programma copiato da altre parti.

I rettangoli identificati da Line: indicano il numero di riga corrente nel testo; cliccando sul

numero si apre una finestra nella quale è possibile specificare direttamente il numero della

riga a cui saltare.


7

Nella casella di testo identificata da Base address: è possibile settare l'indirizzo di partenza

della prima istruzione. Questa impostazione influisce sugli indirizzi delle etichette e sulle

JUMP (le BRANCH sono insensibili a tale modifica in quanto l'offset di salto è relativo

all'istruzione).

Cliccando sul pulsante Exit il programma termina. Per spostarsi nei vari campi con la

tastiera usare il tasto Tab; per inserire un carattere tabulatore nel testo premere Ctrl+Tab;

per andare ad una riga specificandone il numero senza usare il mouse, premere, da una

delle finestre di testo, Ctrl+G.

Figura 3 – Interfaccia parser: dettaglio

Sintassi riconosciuta dal parser

Il parser riconosce la normale sintassi dei sorgenti MIPS ristretta al set di istruzioni del

processore progettato.

In particolare riconosce:

- registri in formato $0 ~ $31 - registri indicati con i nomi simbolici (es.: $zero, $ra, ecc.)


8

- etichette (la riga dell'etichetta deve contenere solo l'etichetta più un eventuale

commento)

- commenti a linea intera o accanto ad ogni istruzione (i commenti iniziano con

“#” o con “;” e terminano con la riga)

- in tutte le istruzioni di Tipo-I il valore immediato può essere sostituito con

un'etichetta

Sorgente di MIPS2BIN

Il programma è scritto in VisualBasic. La traduzione vera e propria è svolta dalla

funzione ConvertASM2BIN(). Il testo viene diviso in linee separate da NextLine(), poi

ogni linea viene separata in tokens dalla funzione NextToken(). Per semplificare

l'analisi, la funzione Tabs2Spaces() converte eventuali Tabs in Spazi. Il sorgente viene

analizzato 2 volte. Prima vengono analizzate le etichette: viene calcolato e memorizzato

l'indirizzo di ognuna in un vettore. Successivamente vengono tradotte le istruzioni.

Le istruzioni sono state divise in 4 gruppi principali (Tipo-R, Tipo-I, Tipo-J e Tipo-

B, inserito per gestire la BREAK). Ogni gruppo è stato suddiviso in vari sottogruppi

in base ai parametri che devono essere riconosciuti (numero di parametri e ordine),

così da risparmiare codice per le istruzioni simili sotto qualche aspetto. I 3 Select Case

servono proprio per selezionare il tipo di traduzione da eseguire: il primo riconosce

l'istruzione dal nome ed identifica il gruppo, il secondo cerca i parametri in base

alla prima selezione infine il terzo assembla le varie parti dell'istruzione nell'ordine

corretto.

Le principali funzioni di supporto alla traduzione e per la gestione di errori sono:

- Int2Bin(): traduce un intero in binario

- Reg2Bit(): traduce il nome di un registro nella sua codifica binaria

- Label2Address(): scandisce il vettore delle etichette e restituisce l'indirizzo di quella

richiesta

- CheckSep(): controlla i dei vari campi separatori (virgole e parentesi)

- CheckMemBlock(): controlla che le JUMP siano indirizzabili (quindi che siano nello

stesso blocco da 256 MB)

- ErrorMsg(): informa l'utente dell'errore trovato

Tutte le altre funzioni gestiscono l'interfaccia grafica e l'interazione con l'utente.


9

ISA: INSTRUCTION SET ARCHITECTURE Le istruzioni sono tutte a lunghezza fissa (come vuole l'architettura RISC) di 32 bit.

Ci sono 3 tipi di istruzioni:

- Registro-Registro (Tipo-R)

- Immediate (Tipo-I)

- Jump (Tipo-J)

Tutte le istruzioni hanno un campo iniziale di 6 bit (opcode) che indica la famiglia di

istruzioni di appartenenza:

- Un opcode = 0 indica istruzioni di tipo R. - L'opcode = 2 è usato dall'unica istruzione di tipo J.

- Altri opcode indicano istruzioni di tipo I.

Istruzioni di Tipo-R Tabella 1 – Struttura generale istruzione di Tipo-R

Le istruzioni di tipo R possono specificare 1 o 2 registri sorgente (rs e rt) ed 1 registro

destinazione (rd). Ogni registro è indicato da un campo a 5 bit. Nelle istruzioni di shift

(SLL, SRA) il campo shamt (shift amount) è usato per indicare l'entità dello shift, nelle altre

istruzioni questo campo è inutilizzato. Il secondo registro sorgente (rt) non è utilizzato nelle

istruzioni NOT, MOVE, SLL, SRA e JALR. Le istruzioni NOP e BREAK sono 2 casi

particolari di tipo R: la prima ha tutti i 32 bit a 0, la seconda usa congiuntamente i 20 bit

dati da rs, rt, rd e shamt per memorizzare il codice di break da eseguire. Il campo funct (6

bit) indica l'operazione da eseguire sui dati. Tutte le istruzioni di tipo R sono quindi

riconosciute tramite la coppia opcode-funct con opcode = 0.

Si noti che l'istruzione SLL con rd, rs uguali a $0 e shamt = 0 corrisponde ad una NOP,

ma questo non è un problema in quanto è uno shift di nessuna posizione ed il

risultato viene scritto su $0 che non è modificabile, quindi è un'istruzione che non fa

nulla.


10

Tabella 2 – Lista istruzioni di Tipo-R


11

Istruzioni di Tipo-I Tabella 3 – Struttura generale istruzione di Tipo-I

Le istruzioni di tipo I hanno un campo da 16 bit (immediate) con cui caricare direttamente

un valore. Il valore caricato verrà poi esteso a 32 bit mantenendone il segno. Il registro rs

viene solo letto, mentre il registro rt viene scritto o letto in base all'istruzione. Ogni

registro è indicato da un campo a 5 bit. L'istruzione da eseguire viene indicata

dall'opcode. Tabella 4 – Lista istruzioni di Tipo-I


12

Istruzioni di Tipo-J Tabella 5 – Struttura generale istruzione di Tipo-J

Esiste una sola istruzione di tipo J, la J (Jump). Questa particolare istruzione ha un

campo da 26 bit (address) con cui è possibile cambiare il valore del program counter. Il

valore indicato da address viene shiftato a sinistra di 2 posizioni (moltiplicato per 4) in

quanto i 2 bit meno significativi indicano un byte all'interno di una istruzione e quindi sono

inutili. Il valore così ottenuto (28 bit) viene concatenato ai 4 bit più significativi del program

counter. Come conseguenza, la memoria si trova “divisa” in blocchi da 256 MB e ogni

istruzione di jump può indirizzare solo istruzioni appartenenti allo stesso blocco.

L'istruzione è identificata dall' opcode = 0x2.

Tabella 6 – Lista istruzioni di Tipo-J


13

DESCRIZIONE FUNZIONALE DELLE DESIGN ENTITIES Nella realizzazione della pipeline sono state utilizzate le seguenti design-entities:

1. MI: Memoria delle istruzioni

Memoriadelle

istruzioni

Indirizzo

Datoletto

2. MD: Memoria dati

MemoriaDati

Indirizzo

DatolettoDato

scritto

3. Reg: Banco registri

Registri

Registroletto 1Registroletto 2

Datoletto 1

Datoletto 2

Registroscritto

Datoscritto

4. ALU: Unità logico-aritmetica

ALU

Op1

Op2

5. IF Instruction

Fetch

6. ID Instruction

Decode

7. EX Execute

8. DM Data Memory

9. WB Write Back

ALUIM Reg DM Reg


14

1. MI: MEMORIA ISTRUZIONI La memoria istruzioni contiene il sottospazio di indirizzi occupati dal programma. Di

seguito è riportata l’interfaccia1:

Figura 4 – Interfaccia della memoria istruzioni

1.1. ARCHITETTURA L’entità è caratterizzata dai seguenti segnali:

- mem_enable: bit di abilitazione della memoria (‘0’ accesa, ‘1’ spenta)

- addr: indirizzo di memoria di 32 bit che contiene l’istruzione

- data_out: istruzione di 32 bit prelevata dalla memoria

La memoria istruzioni è descritta in maniera comportamentale da due processi che

comunicano grazie al segnale memory, l’array di memoria.

1.1.1. Caricamento delle istruzioni in memoria Il processo “load_mem” carica le istruzioni del programma in memoria leggendo il codice

binario eseguibile da un file di testo

Figura 5 – Il processo che carica le istruzioni in memoria

1 In tutte le interfacce sono riportati, rispettivamente, in alto il nome dell’entità, a sinistra gli ingressi “in”, a destra le uscite “out” e in

basso i bus “inout”.


15

1.1.2. Lettura delle istruzioni dalla memoria Il processo “read_mem” legge l’istruzione contenuta in cache indirizzata da addr ed

effettua un controllo sull’indirizzamento bloccando l’esecuzione del programma se si

verifica errore.

Figura 6 – Il processo che legge le istruzioni dalla

1.2. DATAFLOW Il seguente schema mostra (a livello di flusso dei dati) come è stata progettato la memoria

istruzioni e come sono collegati tra loro i due processi descritti in precedenza.

Figura 7 – I processi della memoria istruzioni


16

2. MD: MEMORIA DATI La memoria dati simula la cache dati presente all’interno del processore.

Di seguito è riportata l’interfaccia:

Figura 8 – Interfaccia della memoria dati

2.1. ARCHITETTURA L’entità è caratterizzata dai seguenti segnali:

- mem_enable: bit di abilitazione della memoria (‘0’ accesa, ‘1’ spenta)

- rw_type: 2 bit che selezionano il tipo di lettura/scrittura

“01” byte (8 bit)

“10” half-word (16 bit)

“11” word (32 bit)

- mem_read: bit di richiesta lettura (se ‘1’ la memoria è attivata in lettura)

- mem_write: bit di richiesta scrittura (se ‘1’ la memoria è attiva in scrittura)

- addr: indirizzo di memoria a 32 bit che contiene il dato da leggere/scrivere

- data_in: dato di 32 bit da scrivere nella locazione di memoria indirizzata

- data_out: dato di 32 bit letto dalla locazione di memoria indirizzata

La memoria dati è descritta in maniera comportamentale da un processo, risvegliato da

tutti i segnali in ingresso all’entità.


17

2.1.1. Lettura e scrittura dei dati in memoria Il processo “rw_data_mem” effettua la lettura o la scrittura in memoria dati. A partire dai

due bit mem_read e mem_write viene controllato il tipo di operazione da eseguire.

L’allocazione in memoria è di tipo multi-byte little endian (le locazioni di memoria sono

occupate a partire dal byte meno significativo del dato a 32 bit). Le scritture di byte e half-

word vengono effettuate in modalità read-modify-store (i byte non specificati rimangono

inalterati). Inoltre effettua un controllo sull’indirizzamento bloccando l’esecuzione del

programma se si verifica errore.

Figura 9 – Il processo della memoria dati

2.2. DATAFLOW Il seguente schema mostra (a livello di flusso dei dati) come è stata progettata la memoria

dati e come sono collegati tra loro i processi descritti in precedenza.

Figura 10 – I processi della memoria dati


18

3. Reg: BANCO REGISTRI L’architettura del processore prevede 32 registri a 32 bit. L’elenco ufficiale di tutti i registri,

separati secondo il loro utilizzo previsto, è il seguente:

Tabella 7 – Tabella delle convenzioni adottate per i registri

Nome Numero Uso

$zero $0 il valore costante 0

$v0-$v1 $2-$3 valori per risultati di espressioni

$a0-$a3 $4-$7 argomenti

$t0-$t7 $8-$15 temporanei

$s0-$s7 $16-$23 salvati

$t8-$t9 $24-$25 altri temporanei

$gp $28 global pointer

$sp $29 stack pointer

$fp $30 frame pointer

$ra $31 return address

$at $1 riservato

$k0 $26 riservato

$k1 $27 riservato

Di seguito è riportata l’interfaccia dell’entità:

Figura 11 – Interfaccia banco registri


19

3.1. ARCHITETTURA L’architettura del banco registri è di tipo comportamentale e consiste di due processi,

descritti di seguito.

3.1.1. Scrittura/lettura registri Nella pipeline le istruzioni leggono e scrivono sui registri in due fasi differenti, nel

medesimo colpo di clock. L’istruzione in decode legge i registri reg_read_1, reg_read_2

(registri da leggere), viceversa quella in write back scrive il dato data_write (dato da

scrivere) nel registro reg_write (registro da scrivere).

La scrittura avviene in maniera sincrona, sul fronte di discesa del clock, al contrario la

lettura (asincrona) è effettuata nel momento in cui sono propagati i dati da leggere

dall’istruzione in decode.

Per questa ragione il processo “wr_register” è attivabile dal clock, dai registri di lettura e

dal segnale di abilitazione:

Figura 12 – Il processo che legge e scrive i registri

Il banco registri è scritto solo quando il bit di controllo reg_write_bit è posto ad ‘1’

(abilitazione scrittura). Come già detto in precedenza2 il registro zero contiene soltanto zeri

e non può essere scritto. Per questa ragione tutte le verifiche per la rilevazione delle

dipendenze nella pipeline, prevedono di escludere il controllo se il registro destinazione è

$zero.

2 Vedi tabella 1


20

La lettura asincrona viene memorizzata in due segnali temporanei (data_1, data_2), che

verranno ‘sostituiti’ con il dato da scrivere nel momento in cui il registro di lettura e di

scrittura coincidano3.

3.1.2. Selezione dei dati letti Il processo “select_data” permette di selezionare i dati letti. E’ possibile che uno, od

entrambi i registri da leggere coincidano con quello da scrivere. In tal caso il dato o i dati

da trasferire in uscita non sono quelli precedentemente memorizzati, ma coincideranno

con il dato proveniente dalla fase di write back (segnale data_write).

La corretta selezione è effettuata da due mux che, oltre a verificare l’uguaglianza tra

registri, controllano l’abilitazione a scrivere dell’istruzione in write back per evitare di

anticipare il dato non esatto.

Nel caso in cui il registro da scrivere sia $zero, il passaggio diretto tra dato scritto e letto

non è eseguito, poiché un’istruzione annullata (bit di controllo a ‘0’) potrebbe tentare di

scrivere qualunque valore su $zero, dando origine ad un anticipo sbagliato.

Figura 13 – Il processo che seleziona i dati letti

MUX

MUX

Partecombinatoria

REG_READ_1

REG_READ_2

DATA_1

DATA_2

DATA_READ_1

DATA_READ_2

REG_WRITE

DATA_WRITE

CLK REG_WRITE_BIT

BANCO REGISTRI

Figura 14 – Schema della selezione dei dati letti

3.2. DATAFLOW Il seguente schema mostra (a livello di flusso dei dati) come è stata progettato il banco

registri e come sono collegati tra loro i due processi descritti in precedenza.

3 Vedi paragrafo 3.1.2


21

Figura 15 – I processi del banco registri


22

4. ALU: UNITA’ LOGICO-ARITMETICA L’unità logico-aritmetica è quella parte del processore che permette di eseguire tutte le

operazioni logiche e aritmetiche previste dall’ISA. Di seguito è riportata l’interfaccia

dell’entità:

Figura 16 – Interfaccia della alu

4.1. ARCHITETTURA L’architettura della ALU è di tipo comportamentale e consiste di un unico processo,

descritto di seguito.

4.1.1. Esecuzione dei comandi ALU L’unità logico-aritmetica di questo processore esegue operazioni su operandi a 32 bit. Il

risultato restituito è anch’esso a 32 bit, inoltre viene generato un flag di controllo (di 2 bit)

che segnala alla fase di execute se è stato prodotto un overflow da somma o sottrazione

(primo bit) oppure se è stata eseguita una divisione per zero (secondo bit). Il bit md_flag,

invece, è utilizzato in ingresso alla ALU per segnalare il tipo di divisione e/o

moltiplicazione. Più in dettaglio si ha:

- Se md_flag = ‘0’ viene eseguita la MULTL oppure la DIVR

- Se md_flag = ‘1’ viene eseguita la MULTH oppure la DIVQ

Le operazioni aritmetiche implementate dall’entità sono state rese possibili grazie

all’utilizzo delle librerie per la gestione del tipo ‘std_logic’: ieee.numeric_std e

ieee.std_logic_signed.


23

I comandi della ALU (specificati dal tipo enumerato com) sono descritti nella seguente

tabella:

Tabella 8 – Elenco comandi ALU

Nome Descrizione DISABILITA Disabilita la ALU

SOMMA Esegue la somma dei due operandi

SOTTRAZIONE Esegue la sottrazione dei due operandi

MOLTIPLICAZIONE Esegue MULTL oppure MULTH sui due operandi

DIVISIONE Esegue DIVR (resto) oppure DIVQ (quoziente) sui due operandi

SHIFT_LOGICO_SX Esegue lo scalamento logico a sinistra del primo operando

SHIFT_ARIT_DX Esegue lo scalamento aritmetico a destra del primo operando

NOT_A Esegue la NOT del primo operando

AND_A_B Esegue la AND dei due operandi

NOR_A_B Esegue la NOR dei due operandi

XOR_A_B Esegue la XOR dei due operandi

MINORE Verifica se il primo operando è minore del secondo4

PASS_A Fa passare il primo operando

PASS_HIGH_B Fa passare la parte alta del secondo operando5

4.2. DATAFLOW Il seguente schema mostra (a livello di flusso dei dati) come è stata progettata la alu.

Figura 17 – I processi della ALU

4 Restituisce 1 nel caso la disuguaglianza sia verificata, 0 altrimenti 5 Op2[31-16]


24

5. FASE IF: INSTRUCTION FETCH

La fase di fetch permette il prelevamento delle istruzioni dalla sua componente interna, la

memoria istruzioni6. Inoltre è in questa fase che viene aggiornato il registro PC (program

counter o registro contatore istruzioni).

L’interfaccia dell’entità in esame è riportata di seguito:

Figura 18 – L’intefaccia della fetch

5.1. ARCHITETTURA L’architettura dell’entità è stata studiata per soddisfare le richieste di progetto e per

risolvere i problemi sorti durante la sua realizzazione. Dal punto di vista software, si è

deciso di adottare un’architettura di tipo comportamentale, che ci permettesse di rispettare

i vincoli rtl.

Essa è realizzata servendosi di una componente implementata altrove (memoria

istruzioni), e impiegando 2 processi concorrenti, il cui funzionamento è descritto nelle righe

che seguono.

5.1.1. Aggiornamento sincrono del program counter Il processo “agg_pc_sync” è risvegliato dai segnali di clk e di reset (asincrono). Il registro

contatore istruzioni è resettato all’indirizzo base del programma quando prevale il segnale

di reset (reset = ‘1’) sul clk.

6 Vedi paragrafo 1.


25

L’aggiornamento è effettuato, secondo la logica edge-triggered, sul fronte di salita del

segnale di clk attraverso le operazioni di una piccola ALU che somma 47 al pc corrente per

generare l’indirizzo della istruzione successiva che verrà caricata dalla memoria.

Figura 19 – Il processo di aggiornamento sincrono del program counter

5.1.2. Aggiornamento combinatorio del program counter La parte combinatoria della fetch è affidata al processo “agg_comb_pc”: attivato da tutti i

segnali della sua sensitivity list, realizza i due operatori logici (and e or) e il multiplexer che

consentono di selezionare il prossimo program counter a seconda del flusso di esecuzione

del programma. Più in dettaglio il multiplexer permette di selezionare:

- il segnale pc + 4 propagato dal processo sequenziale

- il segnale id_pc_salto proveniente dalla decode e contenente l’indirizzo di un salto

- l’indirizzo dove si trova la routine per la gestione delle eccezioni

Figura 20 – Il processo di aggiornamento combinatorio del program counter

5.2. DATAFLOW Il seguente schema mostra (a livello di flusso dei dati) come è stata progettata la fase di

decode e come sono collegati tra loro i vari processi descritti in precedenza.

7 Viene effettuta la somma di 4 perché l’indirizzo è di 4 byte = 32 bit


26

Figura 21 – I processi della fetch


27

6. FASE ID: INSTRUCTION DECODE La fase di decode permette il riconoscimento dell’istruzione, nonché il controllo e la

gestione delle criticità non risolvibili mediante la tecnica dell’anticipo (forwarding8).

L’interfaccia dell’entità in esame è riportata di seguito:

Figura 22 – L'interfaccia della decode




i vincoli rtl.

Essa è realizzata servendosi di una componente implementata altrove (banco registri9), e

impiegando diversi processi concorrenti, il cui funzionamento è descritto nelle righe che

seguono.

8 Vedi paragrafo 7.1.2 9 Vedi paragrafo 3.


28

6.1.1. Registri di pipeline IF/ID Per risolvere il problema della sincronizzazione e della propagazione dei segnali

provenienti dalla fase precedente, è stato realizzato un processo sincrono denominato

“propaga_reg_pipeline_IF_ID”. Esso è attivato dal clock oppure da un segnale di reset

(asincrono), utile per azzerare i registri di pipeline if/id, letti o scritti proprio all’interno di

questo processo.

Sul fronte di salita del clock, i segnali10 provenienti dalla fetch vengono memorizzati ed

immediatamente propagati all’interno della decode, dove possono essere utilizzati.

Questi segnali serviranno, poi, ad attivare altri processi combinatori, che riconosceranno

l’istruzione (unità di controllo), oppure rileveranno e risolveranno, dove possibile, eventuali

criticità (unità per le criticità) od eccezioni (unità per le eccezioni).

Figura 23 – Il processo che propaga i registri di pipeline IF/ID

Dimensione totale registri pipeline IF/ID = 64 bit

6.1.2. Unità per il rilevamento e per la gestione delle criticità di controllo L’esecuzione sequenziale e continua delle istruzioni potrebbe essere impedita, laddove si

dovessero riscontrare delle criticità di controllo.

Esistono delle istruzioni di salto, condizionato o meno, che permettono al program counter

di riferirsi ad una locazione qualsiasi della memoria istruzioni, costringendo la pipeline ad

interrompere il normale flusso d’esecuzione.

Esistono, poi, istruzioni che, a causa delle dipendenze dati devono fermarsi nella fase di

decode, in attesa che i dati siano pronti, o che possano essere anticipati mediante la

tecnica del forwarding.

Il processo che si occupa di rilevare tali criticità è denominata “hazard_unit”; esso si avvale

di segnali provenienti dalle altre fasi11, e mediante opportuni confronti riesce a rilevare le

criticità: Load, Load – Store, Branch, Jalr, Jmp.

10 Istruzione codificata, program counter aggiornato (pc + 4)


29

Figura 24 – Il processo che implementa l’unità di rilevamento delle criticità

6.1.2.1. Criticità “load” Se in execute si trova un’istruzione di tipo load (ex_mem_read = ‘1’) ed il registro

destinazione (ex_rd) coincide con almeno uno dei due registri sorgenti dell’istruzione in

decode (rs_decode, rt_decode), è necessario implementare uno stallo, che permetterà alla

load di preparare il dato da anticipare nella fase successiva (EX).

6.1.2.2. Criticità “load-store” Supponiamo che in execute si trovi una load (ex_mem_read = ‘1’), e che, in decode esista

una store (id_mem_write = ‘1’). Se quest’ultima dipende dalla load in funzione del solo

registro rs, è possibile evitare lo stallo, implementando un’anticipo in data memory. In tal

caso, quando la store dovrà scrivere in memoria, riceverà il dato ormai pronto,

direttamente dalla write back (wb_data_write). Il bit di controllo che gestisce tale anticipo è

denominato hazard_load_store.

6.1.2.3. Criticità “branch” Se in decode viene rilevata una branch, si possono riscontrare diversi casi critici:

1. Branch con condizione non verificata

2. Branch con condizione verificata

3. Branch dipendente dall’istruzione in execute

4. Branch dipendente dall’istruzione in data memory

Tutte queste combinazioni sono previste e risolte dal processo di gestione delle criticità.

11 Bit di controllo, oppure bit che identificano il registro destinazione delle istruzioni precedenti quella in esame


30

Il primo caso non comporta nessun problema, dato che l’architettura presuppone di non

effettuare mai il salto12.

Il secondo caso comporta la cancellazione dell’istruzione precedentemente caricata nella

fetch, ma questo non ha richiesto particolare difficoltà di gestione.

Per gli altri casi, invece, gli autori sono stati costretti a modificare in alcuni punti lo schema

di progetto, implementando due stalli oppure uno, a seconda della situazione.

La logica su cui si basa la risoluzione delle criticità dei punti 3 e 4 è la seguente:

“Qualora la branch dipenda dalle istruzioni precedenti, risulterebbe scorretto valutare

subito la condizione di salto, quindi si è deciso di fermare la branch per uno o due colpi di

clock13, e solo nel momento in cui la dipendenza scompaia, ponendo il segnale id_valuta

uguale ad ‘1’, la pipeline accrediterà il risultato del processo che appurerà l’eventuale

necessità di saltare14; l’unico inconveniente si ha qualora l’offset della branch abbia i

cinque bit più significativi, coincidenti con almeno uno dei due registri sorgenti. Infatti pur

azzerando i bit di controllo, la branch ‘modificata’ e propagata dipenderebbe da quella

rimasta ferma in decode (5 bit dell’offset uguali ad almeno un registro sorgente); per

evitare ciò, in presenza di uno stallo (segnale hazard = ‘1’), un mux provvederà ad

azzerare sempre tale registro. In tutti i nostri controlli, infatti, il registro zero non può e non

deve essere considerato per la rilevazione delle dipendenze, dato che esso è riservato e

non scrivibile!”15.

6.1.2.4. Criticità “jalr” A differenza della branch, l’istruzione jalr effettua sempre il salto, ma il registro in cui si

trova l’indirizzo del prossimo program counter, potrebbe non essere ancora pronto. Anche

in questo caso risulterebbe inesatto, accettare tale indirizzo, e per evitare di cambiare il

corretto flusso d’esecuzione del programma, l’istruzione jalr è trattata esattamente come la

branch dipendente16, fatto salvo di considerare il bit id_jalr_bit al posto di id_salta nella

rilevazione delle criticità dati (dipendenze).

12 Esistono strumenti migliori per gestire le branch, basti pensare al delay slot, oppure al branch prediction. 13 1 colpo di clock (stallo singolo) qualora la branch dipenda dall’istruzione in data memory, 2 nel caso dipenda dall’istruzione in

execute. 14 Il processo è denominato “ctrl_equal” e pone ad uno il segnale id_rs_eq_rt. 15 Vedi codice vhdl in appendice per ulteriori ragguagli 16 Vedi criticità branch (3° e 4° caso)


31

6.1.2.5. Criticità “jmp” L’istruzione jmp non comporta difficoltà particolari, anche se come tutte queste criticità

implica un’inevitabile diminuzione del throughtput17. L’unico accorgimento necessario è la

cancellazione dell’istruzione in fetch.

Oss. 1: Lo stallo è implementato ponendo a zero i seguenti bit:

- id_pc_write (per evitare la scrittura del program counter, che rimarrà inalterato18)

- id_if_write (per evitare la scrittura dei registri di pipeline if/id)

- Bit di controllo (in decode)

Oss. 2: Tutte le criticità diventano inutili qualora si presenti un’eccezione, essendo questa

ultima prioritaria.

6.1.3. Unità per la gestione delle eccezioni Le eccezioni rilevabili e gestibili dalla architettura di questa pipeline sono:

- Overflow

- Divisione per zero

- Istruzione ‘break’

Il processo, denominato “exception_unit”, ha proprio il compito di coordinare la pipeline in

presenza di una di queste eccezioni.

Nel caso di overflow o divisione per zero, un segnale (ex_flag_ecc) proveniente dalla fase

successiva (execute), impone la cancellazione delle istruzioni presenti nella pipeline, ad

eccezione di quelle residenti in data memory e write back, che invece saranno completate.

Qualora si rilevasse una ‘break’ (id_break_ctrl_signal = ‘1’), sarà sufficiente cancellare19

l’istruzione residente nella fase precedente (fetch).

In tutti e tre i casi, comunque, il program counter punterà ad un indirizzo20 specifico,

laddove sono memorizzate le routine che permetteranno di gestire l’eccezione in corso21.

17 Numero istruzioni eseguite nell’unità di tempo 18 Vedi paragrafo 5.1.1 19 Le istruzioni non saranno cancellate realmente, ma saranno rese ’ innocue’ azzerando i bit di controllo 20 1020 in decimale in questa architettura, ma è solo una convenzione 21 Per identificare l’eccezione si leggeranno i registri CAUSA ed EPC


32

Oss. 1: La cancellazione delle istruzione si implementa ponendo a ‘1’ i seguenti segnali:

- id_scarta (azzera i bit di controllo dell’istruzione in decode)

- id_scarta_ex (azzera i bit di controllo dell’istruzine in exe)

- id_scarta_if (trasforma l’istruzione in fetch in una nop)

Figura 25 – Unità per la gestione delle eccezioni

6.1.4. Unità di Controllo Leggendo i campi del codice operativo22 e delle funzionalità alu23, il processo denominato

“ctrl_unit” riesce ad identificare l’istruzione, se esistente nell’ ISA, e a generare gli

appropriati bit di controllo, necessari per gestire l’intera pipeline.

Figura 26 – Unità di controllo

22 Istruzione[31-26] 23 Istruzione[5-0]


33

6.1.5. Calcolo del prossimo program counter Durante il normale flusso d’esecuzione del programma, il program counter futuro è

semplicemente il program counter dell’istruzione precedente più la dimensione

dell’istruzione stessa24. Come già detto, però, il normale flusso può essere alterato da

alcune istruzioni, oppure dal verificarsi di alcune criticità di controllo25. In tali casi il

program counter futuro, assumerà valori dipendenti dal tipo di istruzione.

Nell’ architettura esiste un processo combinatorio, denominato “next_pc”, che ha il compito

di calcolare il prossimo program counter in caso di salto. Per fare questo è stato introdotto

un segnale (id_pc_salto) che sarà sempre scritto, indipendentemente dal fatto che il salto

venga eseguito o meno. All’interno del processo sarà generato anche l’offset, in seguito

propagato alla fase successiva; esso corrisponde ai sedici bit meno significativi

dell’istruzione, estesi26 a trentadue (default), oppure ai ventisei bit meno significativi (jalr,

jmp, break), ancora una volta estesi a trentadue.

id_pc_salto assumerà sempre il seguente valore27:

id_pc_salto = (pc+4) + ((id_offset esteso) sll28 2)

Tale espressione non sarà valida per le successive istruzioni:

1. Jalr (id_jalr_bit_signal = ‘1’, id_salta_inc = ‘1’)

2. Jmp (id_salta_inc = ‘1’)

In questi casi si avrà:

1. id_pc_salto = [rs] , ovvero il contenuto del primo registro sorgente

2. id_pc_salto = (pc + 4)[31-28] &29 ((id_offset esteso) sll 2)

Se l’istruzione comporta criticità di controllo, il prossimo program counter sarà proprio il

valore di id_pc_salto; viceversa il program counter futuro sarà semplicemente pc + 4. In

caso d’eccezione, poi, l’indirizzo di riferimento diverrà quello in cui sono memorizzate le

routine per gestire tale evento critico.

24 In questo caso 4 byte, ovvero 32 bit 25 Vedi 6.1.2 26 Considerando il segno (bit più significativo rappresenta il bit di segno) 27 Default 28 Shift logic left (vedi implementazione nel package del progetto) 29 Operatore di concatenamento


34

Figura 27 – Il processo per il calcolo del prossimo pc

Oss. 1: Nel processo “next_pc” è presente una piccola ALU in grado di compiere le

operazioni di somma (+) e di concatenamento (&). Se il bit di ctrl id_salta_inc vale ‘1’,

allora ci sarà una concatenazione, viceversa si effettuerà sempre una somma.

Oss. 2: Ancora una volta viene data la priorità all’eccezione nel caso in cui si verifichi la

stessa e una criticità del controllo.

6.1.6. Azzeramento dei bit di controllo E’ stato creato un processo, denominato “mux_bit_ctrl”, che si occupa dell’azzeramento

dei bit di controllo che vengono propagati alla fase successiva. Questi bit saranno annullati

se e solo se i segnali ‘id_scarta_signal’ oppure ‘hazard’ sono al valore ‘1’.

Figura 28 – Il processo che permette l’azzeramento dei bit di controllo


35

6.1.7. Altri Processi Questo paragrafo è stato scritto per descrivere i processi rimanenti, utili per gestire

correttamente istruzioni di tipo jalr e beq. In particolare per l’istruzione jalr è stato

necessario introdurre diversi multiplexer aggiuntivi rispetto allo schema di progetto30.

6.1.7.1. Jalr Mux: selezione dato letto 1 L’istruzione jalr prevede di memorizzare il contenuto del program counter aggiornato nel

registro destinazione, oppure se omesso, nel registro 31 (riservato al return address).

Per fare questo il pc deve essere propagato alla fase di write back, dove avverrà la

scrittura effettiva nel banco registri se il bit di abilitazione (wb_reg_write_bit) sia ad ‘1’.

La propagazione voluta si ottiene posizionando un mux all’uscita del banco registri: in caso

di jalr il primo dato letto sarà sostituito proprio dal pc.

Figura 29 – Il processo che seleziona il primo dato letto

Oss. 1: La scelta di utilizzare il primo dato letto per scrivere il pc sta nel fatto che la alu

nell’execute prevede il comando per bypassare il primo operando e non il secondo.

6.1.7.2. Jalr Mux: selezione registro destinazione Come già accennato in precedenza il registro destinazione potrà essere rd31, oppure il

registro 31. Una volta rilevata l’istruzione jalr (id_jalr_bit_signal = ‘1’) un mux selezionerà

come registro destinazione l’uno o l’altro. Occorre ricordare che esiste un mux esterno32

che azzererà tale registro in caso di stallo (hazard = ‘1’)

Il processo combinatorio che si occupa di selezionare il registro destinazione è

denominato “registro_destinazione_sel”.

30 Vedi figura 6.65 del libro “Struttura, organizzazione e progetto dei calcolatori” 31 Istruzione[15-11] 32 Vedi paragrafo 6.1.6


36

Figura 30 – Il processo che seleziona il registro destinazione

6.1.7.3. Jalr Mux: selezione dell’indirizzo di salto Come già accennato, nel caso dell’istruzione JALR il prossimo program counter

corrisponde al contenuto del registro rs; viceversa l’indirizzo da propagare alla fetch

risulterà essere il risultato della piccola alu presente in decode.

Il mux è implementato attraverso un processo combinatorio, denominato “jalr_pc”.

Figura 31 – Il processo che seleziona l’indirizzo di salto

6.1.7.4. Beq: controllo uguaglianza dati letti Il processo “ctrl_equal” pone a ‘1’ il segnale id_rs_eq_rt se i dati letti dal banco registri

sono uguali, altrimenti il segnale viene posto a ‘0’.

Figura 32 – Il processo che controlla l’uguaglianza dei dati letti




37

Figura 33 – I processi della decode


38

7. FASE EX: EXECUTE La fase di execute permette l’esecuzione delle istruzioni decodificate grazie all’utilizzo di

una sua componente interna, l’unità logico-aritmetica (ALU). L’interfaccia dell’entità in

esame è riportata di seguito:

Figura 34 – L’interfaccia della execute

7.1. Architettura L’architettura dell’entità è stata studiata per soddisfare le richieste di progetto e per



i vincoli rtl. Essa è realizzata usando diversi processi concorrenti, il cui funzionamento è

descritto nelle righe che seguono.


39

7.1.1. Registri di pipeline ID/EX I vari campi dell’istruzione, i bit di controllo ed i dati letti sono scritti sui registri di pipeline

ID/EX sul fronte di salita del clock. Una volta memorizzati possono essere propagati

all’interno dello stadio d’esecuzione, dove saranno utilizzati.

Come si evince dall’immagine sottostante il processo (propaga_reg_pipeline_ID_EX) è

attivabile dai segnali di clock e di reset (asincrono): il primo permette di eseguire la

scrittura e la propagazione sincrona, mentre il secondo è utilizzato per azzerare i registri di

pipeline.

Figura 35 – Il processo che propaga i registri di pipeline ID/EX

Dimensione Totale registri pipeline ID/EX = 160 bit

7.1.2. Forwarding

L’esecuzione in parallelo delle istruzioni comporta, da una parte un grande vantaggio in

termine di throughput, dall’altra l’insorgere di conflitti dovuti sia alla presenza di flussi

d’istruzioni non sempre sequenziali33 sia alla forte dipendenza tra istruzioni ‘vicine’.34

33 I programmi reali presentano un gran numero (variabile secondo il tipo di programma) di criticità di controllo (salti condizionati o

incondizionati)


40

Le criticità di controllo sono risolte nella fase di decode35, mentre le dipendenze dati sono

eliminate in gran parte nel terzo stadio della pipeline. Eccetto qualche raro caso (load,

branch, jmp, jalr, break) infatti, le istruzioni dell’ architettura utilizzano e generano i dati

durante o al termine della fase d’esecuzione (risp.). Qualora vi siano delle dipendenze è

sufficiente, quindi, passare all’execute i dati corretti dalle fasi di data memory o write back.

Il transito dei dati avviene sempre, anche quando le istruzioni sono indipendenti. Il

funzionamento corretto dell’anticipo è garantito da alcuni multiplexer comandati da

un’apposita unità (forward_unit) e dai bit di controllo denominati dm_reg_write_bit,

wb_reg_write_bit36.

Il processo combinatorio che porta avanti il controllo delle dipendenze di tipo RAW37 è

denominato “forward_unit”.

Figura 36 – Il processo che gestisce il forwarding

Il funzionamento del processo è molto semplice: In base al controllo dell’uguaglianza tra i

registri sorgenti dell’istruzione in execute (ex_rs_signal, ex_rt) e i registri destinazione

delle istruzioni in data memory (dm_rd) e write back(wb_rd), l’unità di propagazione

attribuirà, sempre, i valori più appropriati ai segnali che comandano i mux (sel_mux_1,

sel_mux_2) e che gestiscono il forwarding. Nel caso di dipendenze i mux selezioneranno i

dati anticipati, viceversa sceglieranno i dati propagati dallo stadio precedente (dati letti o

offset in base al tipo d’istruzione).

34 Esiste anche un terzo conflitto, di tipo hardware non preso in considerazione data la natura del nostro processore. L’unica risorsa

condivisa potenziale è la memoria, ma nella progettazione gli autori hanno separato le due cache (istruzioni e dati) evitando di incorrere

nel problema di accedere contemporaneamente ad un’unica risorsa comune (fetch e data memory). 35 Vedi paragrafo 6.1.4 36 Bit di abilitazione scrittura del registro destinazione in dm e wb rispettivamente 37 Read After Write: sono le uniche dipendenze dati rilevate e risolte da questa pipeline


41

Oss. 1: La dipendenza sarà rilevata qualora esiste uguaglianza tra almeno un registro

sorgente ed un registro destinazione e nel caso in cui il bit di abilitazione alla scrittura in

write back del registro destinazione sia attivo.

Oss. 2: Se il registro destinazione è il registro zero, le dipendenze non sono considerate

tali.

Oss. 3: Se un istruzione dipende sullo stesso registro sia dall’istruzione in WB, sia in DM,

allora il dato da anticipare sarà quello relativo all’istruzione più recente (quello in DM).

Oss. 4: Le istruzioni che non generano (load) o che non utilizzano il dato nello stadio

d’execute (beq, jalr, jmp) sono gestite nella fase di decode38.

7.1.3. Mux: Selezione operatore 1

Il multiplexer che seleziona il primo operatore dell’alu è gestito da uno dei due segnali in

uscita dall’unità di forwarding (sel_mux_1). Il processo che lo implementa è denominato

“mux_1”:

Figura 37 – Il processo che seleziona il primo operatore della ALU

7.1.4. Mux: Selezione dato da scrivere nella memoria dati

In base al tipo d’istruzione residente in questo stadio, il dato selezionato dal mux in

oggetto può corrispondere al secondo operatore dell’alu, oppure al dato da scrivere nella

memoria dati (store).

Il multiplexer è gestito dal secondo segnale in uscita dall’unità di forwarding (sel_mux_2).

Il processo che lo implementa è denominato “mux_2”:

Figura 38 – Il processo che seleziona il dato da scrivere in memoria

38 Vedi paragrafo 6.1.2


42

7.1.5. Mux: Selezione operatore 2

Il secondo operatore dell’alu sarà il dato scelto dal mux_2 oppure l’offset. In base al tipo

d’istruzione e al conseguente bit di controllo ex_alu_sources, il mux selezionerà il dato

corretto da propagare alla unità aritmetico logica. Il processo che implementa il multiplexer

è denominato “mux_2_1”:

Figura 39 – Il processo che seleziona il secondo operatore della ALU

7.1.6. Mux: Selezione registro destinazione

Il mux che seleziona il registro destinazione è gestito dal bit di controllo ex_reg_dest.

Occorre notare che nel momento in cui i bit di controllo dovessero essere azzerati per una

criticità od un eccezione, o semplicemente perché l’istruzione non debba scrivere nel

banco registri, il bit di abilitazione reg_write_bit sarà sempre posto uguale a zero,

escludendo la memorizzazione del dato nel registro destinazione propagato fino all’ultimo

stadio della pipeline. Il processo che implementa il multiplexer in questione è denominato

“mux_reg_dest”:

Figura 40 – Il processo che seleziona il registro di destinazione

7.1.7. Eccezione: Scrittura registri EPC e CAUSA

In caso di eccezione questo processo effettua la scrittura dei registri EPC39 e Causa40. Nel

primo registro viene salvato l’indirizzo + 4 dell’istruzione che ha causato l’eccezione, il

secondo registro mantiene traccia del motivo per cui tale eccezione si è verificata. Come

tutti i processi di scrittura sui registri, anche questo processo viene attivato dal segnale di

clock e scrive sui registri sul fronte di discesa di tale segnale.

39 Il registro EPC (Exception Program Counter) è di 32 bit 40 Il registro Causa è di 20 bit


43

Le possibile cause di eccezione sono le seguenti:

Figura 41 – Tabella eccezioni

Numero Nome Descrizione

4 CAUSA_OW Eccezione dovuta a overflow aritmetico

2 CAUSA_DIV Eccezione dovuta a divisione per zero

Qualsiasi altro numero41 Codice_break Eccezione identificata dal campo codice dell’istruzione break

Il processo che implementa la scrittura dei registri “EPC” e “Causa” è denominato

“write_causa_epc”:

Figura 42 – Il processo che scrive i registri EPC e Causa

7.1.8. Azzeramento dei bit di controllo

In caso di eccezione, l’unità di controllo alza a ‘1’ il segnale “id_scarta_ex” che azzera i bit

di controllo presenti nei registri di pipeline EX/MEM e MEM/WB. I processi che gestiscono

l’azzeramento sono rispettivamente:

Figura 43 – Il processo che azzera EX/DM

Figura 44 – Il processo che azzera DM/WB

41 Si ricorda che l’eccezione 1 è riservata al debugger


44

7.1.9. Unità di controllo della ALU All’interno dello stadio di Execute è instanziata la componente ALU42. Il processo

“alu_ctrl_unit” realizza l’unità di controllo di questa componente: in base al codice

operativo e al campo func dell’istruzione, seleziona l’operazione che dovrà essere

eseguita dall’unità logico-aritmetica.

Figura 45 – Il processo che controlla la ALU

7.1.10. Generazione del bit di eccezione Il bit di eccezione (ex_ecc_out) che deve essere inviato all’unità di controllo è il risultato

delle operazioni logiche effettuate sui segnali ex_ow_ctrl_signal, flag_ow e flag_div

mostrate in figura:

id_ow_ctrl_signal flag_ow

flag_div

ex_ecc_out

Figura 46 – Schema logico bit di eccezione

Figura 47 – Il processo che genera il bit di

eccezione


execute e come sono collegati tra loro i vari processi descritti in precedenza.

42 Vedi paragrafo 4.


45

Figura 48 – I processi della execute


46

8. FASE DM: DATA MEMORY La fase di data memory permette l’accesso in memoria (cache dati) che è gestito dai bit di

controllo dell’istruzione. L’interfaccia dell’entità in esame è riportata di seguito:

Figura 49 – L’interfaccia della data memory




i vincoli rtl.

Essa è realizzata servendosi di una componente implementata altrove (memoria dati43), e

impiegando due processi concorrenti, il cui funzionamento è descritto nelle righe che

seguono.

43 Vedi paragrafo 1.


47

8.1.1. Registri di pipeline EX/DM L’indirizzo, il dato da scrivere, il registro destinazione e i bit di controllo sono scritti sui

registri di pipeline EX/DM sul fronte di salita del clock. Una volta memorizzati possono

essere propagati all’interno dello stadio di data memory, dove saranno utilizzati.

Il processo sincrono (propaga_reg_pipeline_EX_DM) in grado di scrivere e propagare i

segnali in oggetto è attivato dai segnali di clock e di reset (asincrono).

Figura 50 – Il processo che propaga i registri di pipeline EX/DM

Dimensione totale registri pipeline IF/ID = 76 bit

8.1.2. Lettura e scrittura e selezione dato da scrivere in cache dati All’interno dello stadio di Data Memory è istanziata la componente memoria dati, che

costituisce la cache dati del processore. La memoria sarà letta o scritta in maniera

asincrona.

L’architettura progettata prevede tre bit di controllo per gestire l’accesso in cache:

- dm_mem_read (bit che indica la lettura, corrispondente all’istruzione load)

- dm_mem_write (bit che indica la scrittura, corrispondente all’istruzione store)

- dm_rw_type (2 bit che identificano la dimensione del dato da leggere o scrivere)

Nell’ISA del processore le uniche istruzioni reputate ad accedere alla memoria, e quindi

con i bit di controllo precedentemente descritti diversi da zero, sono:

- LOAD word (32 bit)


48

- LOAD half-word (16 bit)

- LOAD byte (8 bit)

- STORE word (32 bit)

- STORE half-word (16 bit)

- STORE byte (8 bit)

L’architettura prevede di eliminare lo stallo in caso di load e store dipendenti sul solo

registro sorgente rs. In questa situazione il dato da scrivere è quello propagato dallo stadio

successivo di write back. Il bit di controllo che comanda il mux di selezione è denominato

“dm_load_store_signal”.

Figura 51 – Il processo che seleziona il dato da scrivere nella cache dati


data memory e come sono collegati tra loro i vari processi descritti in precedenza.

Figura 52 – I processi della data memory


49

9. FASE WB: WRITE BACK La fase di write back permette la scrittura sul banco registri del registro destinazione.

Di seguito è riportata l’interfaccia dell’entità in esame:

Figura 53 – L’interfaccia della write back

9.1. Architettura L’architettura dell’entità è stata studiata per soddisfare le richieste di progetto e per



i vincoli rtl.

Essa è realizzata servendosi di due processi (uno combinatorio e uno sequenziale) il cui

funzionamento è descritto nelle righe che seguono.


50

9.1.1. Registri di pipeline DM/WB Il dato da scrivere, il risultato della alu, il registro destinazione e i bit di controllo sono scritti

sui registri di pipeline DM/WB sul fronte di salita del clock. Una volta memorizzati possono

essere propagati all’interno dello stadio di write back, dove saranno utilizzati.

Lo schema del processo sincrono (propaga_reg_pipeline_dm_wb) in grado di scrivere e

propagare i segnali in oggetto è il seguente:

Figura 54 – Il processo che propaga i registri di pipeline DM/WB

Dimensione totale registri pipeline DM/WB = 71 bit

9.1.2. Selezione dato da scrivere su banco registri Il bit di controllo wb_mem_to_reg seleziona il dato da scrivere nel banco registri tra il dato

letto dalla data memory e il risultato della alu.

Figura 55 – Il processo che seleziona il dato da scrivere sul banco registri


51



Figura 56 – I processi della write back


52

10. CONCLUSIONI: Schema finale

Figura 57 – Schema finale44 della pipeline semplice a 5 stadi progettata

44 Le parti in rosso corrispondono alle zone aggiunte o modificate rispetto allo schema della fig. 6.65 del libro

PC

+

4

4000

0040

Este

nsi

one

del

segn

o

=

Shi

ft a

sini

stra

di 2

+

Uni

tà d

iril

evam

ento

del

lecr

itici

tà

Reg

istr

i

Regi

stro

lett

o 1

Regi

stro

lett

o 2

Dato

lett

o 1

Dato

lett

o 2

Regi

stro

scri

tto

Dato

scri

tto

Unità

di

cont

rollo

EXMWB

M U X

0

M U X

Mem

oria

delle

istr

uzio

ni

Indi

rizz

o Dato

lett

o

IF.S

cart

a

Salta IF

/ID

Istr

uzio

ne [2

5-21

]

Istr

uzio

ne [2

0-16

]

Istr

uzio

ne [1

5-11

]

ID.S

cart

a

Cau

sa

EPC

M U X M U X M U X

M U X

Uni

tà d

ipr

opag

azio

ne

DM

WB

Uni

tà d

ico

ntro

llode

llaAL

U

ALU

Op

ALU

Src

Reg

Dst

M U X

M U X0

0

EX.S

cart

a

ID/E

X

EX/M

EM

Mem

oria

Dat

i

Indi

rizz

o Dato

lett

oDa

tosc

ritt

o

WB

MemWrite

Mem

Rea

d

M U XMemtoReg

Reg

Writ

e

MEM

/WB

ALU

Op1

Op2

16 26

32

Haz

ard

0R

_31

Haz

ard

M U X

M U X

M U X

Jalr

Jalr

Flag

_ow

Flag

_div

Ow

_ctr

l

Flag

_ecc

Salta

_inc

Salta

M U XLoad/Store

PcWrite


53

11. CONCLUSIONI: Dataflow finale

Figura 58 – Il dataflow finale della pipeline mostra come sono collegate fra loro le diverse fasi


54

TESTBENCH Per collaudare il processore, durante le varie fasi di progetto, sono stati utilizzati diversi

programmi di test, ognuno dei quali mirato a verificare il perfetto funzionamento di ogni

istruzione e di ogni situazione critica risolvibile. Di seguito sono riportati i più significativi.

1. Forwarding

Tabella 9 – Programma che verifica il forwarding

MIPS Assembly Code Machine Binary Code (32 bit) # forwarding addi $8, $0, 5 addi $9, $0, 10 sub $2, $9, $8 add $2, $8, $9 slt $3, $8, $2

00100000000010000000000000000101 00100000000010010000000000001010 00000001001010000001000000100010 00000001000010010001000000100000 00000001000000100001100000101010

Il programma presenta 4 dipendenze dati, ciascuna evidenziata con un colore diverso. Al

termine dell’esecuzione si ha rispettivamente: [$2] = 15 e [$3] = 1. Questo mostra che i

forwarding sono stati effettuati nella maniera corretta, come evidenziato dai seguenti

messaggi di assert prodotti durante l’esecuzione del programma:

# ** Note: FORWARD_UNIT: Conflitto raw exe-dm [rs] risolto... # Time: 450 ns Iteration: 1 Instance: /tb_pipeline/e_x # ** Note: FORWARD_UNIT: conflitto raw exe-wb [rt] risolto... # Time: 450 ns Iteration: 1 Instance: /tb_pipeline/e_x # ** Note: FORWARD_UNIT: conflitto raw exe-wb [rt] risolto... # Time: 550 ns Iteration: 1 Instance: /tb_pipeline/e_x # ** Note: FORWARD_UNIT: conflitto raw exe-dm [rt] risolto... # Time: 650 ns Iteration: 1 Instance: /tb_pipeline/e_x


55

2. Criticità load & load-store

Tabella 10 – Programma che verifica lo stallo e l’anticipo tra write back e data memory (load-store)

MIPS Assembly Code Machine Binary Code (32 bit) # stallo load addi $1, $0, 4 addi $2, $0, 8 sw $0, 0($0) sw $1, 0($1) sw $2, 0($2) lw $3, 0($0) lw $4, 4($3) # 1° stallo lw $5, 4($4) # 2° stallo sw $5, 12($3)# forward DM - WB

00100000000000010000000000000100 00100000000000100000000000001000 10101100000000000000000000000000 10101100001000010000000000000000 10101100010000100000000000000000 10001100000000110000000000000000 10001100011001000000000000000100 10001100100001010000000000000100 10101100101001010000000000000100

Il programma presenta 3 dipendenze dati, ciascuna evidenziata con un colore diverso.

Questa volta l’anticipo in execute non è sufficiente per risolvere le criticità in $3 e $4, in

quanto l’istruzione LOAD rende disponibile il dato solo dopo la lettura in memoria; nel caso

in cui la LOAD sia seguita da una STORE dipendente sul primo registro sorgente, la

nostra architettura prevede un passaggio all’indietro tra il dato letto in cache e quello da

scrivere ($5), evitando lo stallo.

Durante la simulazione sono state generate le seguenti importanti note: Note: HAZARD UNIT: Criticita' load --> stallo... # Time: 750 ns Iteration: 2 Instance: /tb_pipeline/uut2 Note: Attenzione: conflitto raw exe-dm [rs] risolto... # Time: 850 ns Iteration: 1 Instance: /tb_pipeline/uut3 Note: HAZARD UNIT: Criticita' load --> stallo... # Time: 950 ns Iteration: 2 Instance: /tb_pipeline/uut2 Note: Attenzione: conflitto raw exe-dm [rs] risolto... # Time: 1050 ns Iteration: 1 Instance: /tb_pipeline/uut3 Note: HAZARD UNIT: Criticita' load store risolvibile senza stallo... Lo stallo è stato reso necessario per trasferire, alle LOAD dipendenti, i dati corretti nel

momento del loro utilizzo (terzo stadio della pipeline).

Poiché la STORE si serve del primo registro sorgente in data memory, con l’anticipo

previsto è possibile evitare lo stallo.

Al termine dell’esecuzione nelle prime 4 locazioni di memoria sono stati scritti i valori

corretti 0, 4, 8, 8. Il contenuto dei registri è rispettivamente: [$3] = 0, [$4] = 4 e [$5] = 8.


56

3. Branch dipendente

Tabella 11 – Programma per verificare il funzionamento della BRANCH dipendente

MIPS Assembly Code Machine Binary Code (32 bit) # salto condizionato con dipendenza addi $1, $0, -1 eti: addi $1, $1, 1 beq $1, $0, eti sw $1, 0($0)

00100000000000011111111111111111

00100000001000010000000000000001 00010000001000001111111111111110 10101100000000010000000000000000

Il programma presenta 2 dipendenze dati di tipo read afer write ($1). La prima criticità è

risolvibile con il forwarding, mentre la seconda (BRANCH) con un doppio stallo.

Dopo il doppio stop, la BRANCH potrà essere valutata correttamente. Il salto all’etichetta

“eti:” dovrà essere eseguito solo la prima volta.

Le note rilevanti generate durante l’esecuzione sono state: Note: BRANCH_EQUAL detect... # Time: 350 ns Iteration: 1 Instance: /tb_pipeline/uut2 Note: Attenzione: conflitto raw exe-dm [rs] risolto... # Time: 350 ns Iteration: 1 Instance: /tb_pipeline/uut3 # ** Note: Attenzione: conflitto raw exe-dm [rt] risolto... # Time: 350 ns Iteration: 1 Instance: /tb_pipeline/uut3 Note: HAZARD UNIT: Criticita' branch o jalr --> doppio stallo... # Time: 350 ns Iteration: 2 Instance: /tb_pipeline/uut2 Note: HAZARD UNIT: Criticita' branch o Jalr --> singolo stallo... # Time: 450 ns Iteration: 2 Instance: /tb_pipeline/uut2 Note: HAZARD UNIT: Branch o Jalr senza stallo... # Time: 550 ns Iteration: 1 Instance: /tb_pipeline/uut2 Note: BRANCH_EQUAL detect... ** Note: CONTROL UNIT: Salto da eseguire (BRANCH,JMP O JALR) --> cancellazione dell'istruzione in fetch... # Time: 550 ns Iteration: 4 Instance: /tb_pipeline/uut2 # Time: 850 ns Iteration: 1 Instance: /tb_pipeline/uut2 Note: HAZARD UNIT: Criticita' branch o jalr --> doppio stallo... # Time: 850 ns Iteration: 2 Instance: /tb_pipeline/uut2 Note: HAZARD UNIT: Criticita' branch o Jalr --> singolo stallo... # Time: 950 ns Iteration: 2 Instance: /tb_pipeline/uut2 Note: HAZARD UNIT: Branch o Jalr senza stallo... # Time: 1050 ns Iteration: 1 Instance: /tb_pipeline/uut2 Note: CONTROL UNIT: Nessuna eccezione rilevata... # Time: 1050 ns Iteration: 4 Instance: /tb_pipeline/uut2

Come previsto la condizione della BRANCH è verificata solo una volta; la STORE scriverà

‘1’ nella prima locazione di memoria a 1350 nano secondi.


57

4. Eccezione: Owerflow

Tabella 12 – Programma che verifica la gestione dell’overflow (codice eccezione: 4)

MIPS Assembly Code Machine Binary Code (32 bit) # overflow eti: lui $1, 32000 lui $2, 32000 add $3, $1, $2 beq $1, $2, eti break 57

00111100000000010111110100000000 00111100000000100111110100000000 00000000001000100001100000100000 00010000001000101111111111111100 00000000000000000000111001001101

Il programma genera un’eccezione durante l’esecuzione dell’istruzione ADD. Le istruzioni

in IF, ID, EX saranno cancellate (BREAK, BRANCH, ADD). Il program counter punterà alla

locazione di memoria in cui si trovano le routine per la gestione delle eccezioni.

Durante l’esecuzione del programma sono state generate le seguenti note: Note: BRANCH_EQUAL detect... # Time: 450 ns Iteration: 1 Instance: /tb_pipeline/uut2 Note: HAZARD UNIT: Criticita' branch o Jalr --> singolo stallo... # Time: 450 ns Iteration: 2 Instance: /tb_pipeline/uut2 Note: CONTROL UNIT: cancellazione delle istruzioni in IF, ID, EX... # Time: 450 ns Iteration: 6 Instance: /tb_pipeline/uut2 Failure: Instruction_memory: Errore di indirizzamento # Time: 550 ns Iteration: 1 Process: /tb_pipeline/uut1/uut/leggi_mem File Note: SHIFT O NOP detect... # Time: 550 ns Iteration: 1 Instance: /tb_pipeline/uut2

Come si può notare dagli assert prodotti, durante l’esecuzione dell’istruzione ADD si è

verificato un overflow; poco prima l’unità di rilevamento delle criticità aveva rilevato una

BRANCH dipendente (singolo stallo), ma nel momento in cui l’unità di controllo s’accorge

dell’eccezione, cancella immediatamente le istruzione in IF, ID, EX. Il program counter ha

tentato di accedere all’indirizzo in cui si trovano le routine di gestione delle eccezioni; tale

indirizzo è fuori dallo spazio d’indirizzamento del programma, per tale motivo viene rilevato

un errore nella fase di fetch.

Nel frattempo la BREAK si è trasformata in una NOP (550 nano secondi). Inoltre il registro

$3 non è stato scritto dall’istruzione che ha provocato l’eccezione, mentre $1 e $2

contengono i valori corretti.

Per la gestione dell’eccezione sono stati scritti i registri “EPC” E “CAUSA”: il primo

contiene il valore dell’ADD + 4, il secondo il codice dell’eccezione (4).


58

5. Eccezione: divisione per zero

Tabella 13 – Programma che verifica la gestione della divisione per zero (codice eccezione: 2)

MIPS Assembly Code Machine Binary Code (32 bit) # divisione per 0 eti: addi $8, $0, 10 addi $9, $0, 0 divq $2, $8, $9 j eti add $3, $8, $9

00100000000010000000000000001010 00100000000010010000000000000000 00000001000010010001000000011010 00001000000000000000000000000000 00000001000010010001100000100000

Il programma prevede una divisione per zero; l’eccezione provocherà la cancellazione

delle istruzioni in IF, ID, EX. Il program counter punterà alla locazione di memoria in cui si

trovano le routine per la gestione delle eccezioni.

L’esecuzione del programma ha generato i seguenti assert:

Note: JMP detect... # Time: 450 ns Iteration: 1 Instance: /tb_pipeline/uut2 Note: CONTROL UNIT: Salto da eseguire (BRANCH,JMP O JALR) cancellazione dell'istruzione in fetch...

# Time: 450 ns Iteration: 2 Instance: /tb_pipeline/uut2 Error: Alu: DIVISIONE PER 0... # Time: 450 ns Iteration: 4 Instance: /tb_pipeline/uut3/alu Note: CONTROL UNIT: cancellazione delle istruzioni in IF, ID, EX... # Time: 450 ns Iteration: 6 Instance: /tb_pipeline/uut2 * Failure: Instruction_memory: Errore di indirizzamento # Time: 550 ns Iteration: 1 Process: /tb_pipeline/uut1/uut/leggi_mem Note: SHIFT O NOP detect... # Time: 550 ns Iteration: 1 Instance: /tb_pipeline/uut2

Come si evince dalle note sovrastanti, quando la JMP è in ID, l’istruzione DIVQ genera

l’eccezione divisione per 0 (codice 2). Quando la JMP è pronta a saltare, il rilevamento

dell’eccezione comporta la cancellazione delle istruzioni in IF, ID, EX. Il salto all’indirizzo

dell’istruzione JMP non viene effettuato, mentre il program counter punterà all’indirizzo di

gestione delle eccezioni (fuori dalla mappatura del programma). L’istruzione ADD viene

‘trasformata’ in una NOP. Inoltre sono stati scritti i registri “EPC” E “CAUSA”: il primo

contiene il valore della DIVQ + 4, il secondo il codice dell’eccezione (2).


59

6. Programmi di test: ‘fattoriale.asm’

Tabella 14 – Programma che calcola il fattoriale di un numero

MIPS Assembly Code Machine Binary Code (32 bit)

# fattoriale.asm main: addi $4, $0, 12 addi $24, $0, fatt addi $29, $0, 1020 jalr $24 move $3, $2 lui $2, 10 sra $2, $2, 16 break 0 fatt: beq $4, $0, esci addi $29, $29, -8 sw $31, 4($29) sw $4, 8($29) addi $4, $4, -1 jalr $24 lw $4, 8($29) lw $31, 4($29) multl $2, $4, $2 addi $29, $29, 8 jalr $31, $30 esci: lui $2, 1 sra $2, $2, 16 jalr $31, $30

00100000000001000000000000001100 00100000000110000000000000100000 00100000000111010000001111111100 00000011000000001111100000001001 00000000010000000001100000010000 00111100000000100000000000001010 00000000010000000001010000000011 00000000000000000000000000001101

00010000100000000000000000001010 00100011101111011111111111111000 10101111101111110000000000000100 10101111101001000000000000001000 00100000100001001111111111111111 00000011000000001111100000001001 10001111101001000000000000001000 10001111101111110000000000000100 00000000100000100001000000011000 00100011101111010000000000001000 00000011111000001111000000001001

00111100000000100000000000000001 00000000010000000001010000000011 00000011111000001111000000001001

Il programma calcola il fattoriale del numero contenuto in $4 (12). Il funzionamento è il

seguente:

1. E’ stato supposto che lo SP (stack pointer) punti all’indirizzo 1020 (cache dati).

2. E’ stato riempito lo stack con i valori da moltiplicare

3. Si è effettuata la moltiplicazione degli elementi contenuti nella pila

4. Si è memorizzato in $2 e poi in $3 il risultato del fattoriale

Di seguito è riportato un’istantanea di alcuni registri e di un sottoinsieme di locazioni della

memoria dati nella fase conclusiva dell’esecuzione del programma.


60

Figura 59 – Contenuto della memoria dati e dei registri nelle fasi finali dell’esecuzione del programma

Il calcolo del fattoriale di 12 è memorizzato nel $2 dopo 16900 nano secondi. Il valore

riportato è corretto (479001600), dimostrando la giustezza dell’esecuzione del programma.

Ancora una volta la pipeline è stata in grado di risolvere le criticità presenti.

Si può notare (parte sottostante dell’immagine) che la memoria dati contiene i valori 12,

11, 10, 9, …0 che sono i fattori della moltiplicazione.


61

7. Programmi di test: ‘numeri_primi.asm’45 Tabella 15 – Programma che calcola i numeri primi compresi tra 0 e 100 (vedi 2° istruzione)

MIPS Assembly Code Machine Binary Code (32 bit) # numeri_primi.asm main: addi $25, $0, 10 # Place N in $4 addi $4, $0, 100 addi $5, $0, -32768 addi $16, $0, 1 addi $18, $0, 0 seek: addi $16, $16, 1 # Find first prime sll $12, $16, 2 lw $8, 0($12) # Erase all garbage sw $0, 0($12) end_prog2: beq $16, $4, end_prog # (Can be replaced by beq ... ,end_prog2) beq $8, $5, not_prime # s0 is a prime number sll $12, $18, 2 sw $16, 0($12) addi $18, $18, 1 not_prime: # Save s0 value addi $17, $16, 0 mark_loop: add $17, $17, $16 # Branch If Greater Than sub $8, $4, $17 and $8, $8, $5 beq $8, $5, seek sll $12, $17, 2 sw $5, 0($12) beq $0, $0, mark_loop end_prog: break 0

00100000000110010000000000001010

00100000000001000000000001100100 00100000000001011000000000000000 00100000000100000000000000000001 00100000000100100000000000000000

00100010000100000000000000000001

00000010000000000110000010000000 10001101100010000000000000000000

10101101100000000000000000000000

00010010000001000000000000001100

00010001000001010000000000000011

00000010010000000110000010000000 10101101100100000000000000000000 00100010010100100000000000000001

00100010000100010000000000000000

00000010001100001000100000100000

00000000100100010100000000100010 00000001000001010100000000100100 00010001000001011111111111110010 00000010001000000110000010000000 10101101100001010000000000000000 00010000000000001111111111111001

00000000000000000000000000001101

Il programma utilizza buona parte del set d’istruzioni del processore. Sono implementati

cicli e sono risolte diverse criticità dati eliminabili con l’anticipo. L’esecuzione del

programma è terminato dall’istruzione BREAK che genera un eccezione il cui codice è ‘0’.

A titolo puramente esemplificativo sono riportate gli ultimi assert generati durante la

simulazione dell’esecuzione:

45 Il programma è stato scritto da Alok Menghrajani (fonte: internet)


62

Note: BREAK detect... # Time: 436250 ns Iteration: 1 Instance: /tb_pipeline/uut4/uut # ** Note: CONTROL UNIT: cancellazione delle istruzioni in IF ... # Time: 436250 ns Iteration: 2 Instance: /tb_pipeline/uut4/uut # ** Failure: Instruction_memory: Errore di indirizzamento # Time: 436350 ns Iteration: 1 Process: /tb_pipeline/uut1/uut/leggi_mem

Come si può notare l’istruzione BREAK genera un’eccezione già in fase di ID, a differenza

dell’overflow e della divisione per 0, quindi è sufficiente cancellare l’istruzione in IF. Il

program counter punta all’indirizzo in cui sono memorizzate le routine di gestione delle

eccezioni.

DI seguito è riportata un’istantanea della memoria:

Figura 60 – Contenuto della memoria dati nelle fasi finali dell’esecuzione del programma

Come si può notare nelle prime venticinque locazioni di memoria (cache dati) sono stati

memorizzati i numeri primi calcolati. L’ultima scrittura avviene a circa 432 micro secondi.


63

8. Programmi di test: ‘matrice.asm’

Tabella 16 – Programma che inizializza una matrice 10 x 10

MIPS Assembly Code Machine Binary Code (32 bit)

# matrice.asm main: lui $8, 0 # i lui $9, 0 # j lui $10, 0 # k lw $11, 0($0) addi $11, $11, 10 # nrig = 10 lui $12, 10 sra $12, $12, 16 # ncol = 10 ciclo: add $13, $8, $9 sw $13, 0($10) addi $10, $10, 4 addi $9, $9, 1 slt $24, $9, $12 addi $25, $0, 1 beq $24, $25, ciclo lui $9, 0 addi $8, $8, 1 slt $24, $8, $11 addi $25, $0, 1 beq $24, $25, ciclo lui $2, 10 sra $2, $2, 16 end: break 0

00111100000010000000000000000000 00111100000010010000000000000000 00111100000010100000000000000000 10001100000010110000000000000000 00100001011010110000000000001010 00111100000011000000000000001010 00000001100000000110010000000011 00000001000010010110100000100000 10101101010011010000000000000000 00100001010010100000000000000100 00100001001010010000000000000001 00000001001011001100000000101010 00100000000110010000000000000001 00010011000110011111111111111001 00111100000010010000000000000000 00100001000010000000000000000001 00000001000010111100000000101010 00100000000110010000000000000001 00010011000110011111111111110100 00111100000000100000000000001010 00000000010000000001010000000011 00000000000000000000000000001101

Il programma genera una matrice 10 x 10, la cui struttura è riportata di seguito:

0 1 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 9 102 3 4 5 6 7 8 9 10 113 4 5 6 7 8 9 10 11 124 5 6 7 8 9 10 11 12 135 6 7 8 9 10 11 12 13 146 7 8 9 10 11 12 13 14 157 8 9 10 11 12 13 14 15 168 9 10 11 12 13 14 15 16 179 10 11 12 13 14 15 16 17 18

⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦

Equazione 1 – Matrice 10x10 generata dal programma ‘matrice.asm’


64

Dal programma “matrice.asm” è stata selezionata l’istruzione46 da portare avanti nella

simulazione dettagliata riportata47. Come si può notare dal listato, nell’inizializzazione della matrice viene fatto variare prima

l’indice j (indice colonna), in modo da memorizzare la matrice stessa per righe. Verranno

allocate le prime 100 locazioni di memoria (cache dati) con la logica seguente: “Le prime

10 locazioni conterranno la prima riga, le 10 successive la seconda, ecc…”

Di seguito è riportato un’istantanea della porzione di memoria che contiene le ultime righe:

Figura 61 – Istantanea della memoria dati (contiene le ultime 2 righe della matrice) e di alcuni registri

Come si può notare l’ultimo elemento della matrice è scritto a 106,5 micro secondi (vedi

cursore giallo). Nella parte alta dell’immagine è possibile osservare il contenuto di alcuni

registri. Tra di esse si verifica facilmente che gli indici di riga e di colonna ($8, $9) sono

entrambi a 9, quindi la matrice è stata scandita completamente. I registri $11 e $12

contengono il valore del numero di righe e di colonne rispettivamente. Dai risultati si

deduce che la pipeline ha risolto le varie criticità presenti.

46 In particolare l’istruzione selezionata è l’ADDI che si trova nella 5° riga del programma 47 Vedi capitolo “Esempio di simulazione”


65

ESEMPIO DI SIMULAZIONE E’ stata fatta una simulazione dettagliata dell’istruzione evidenziata alla sesta riga del

seguente programma48:

Tabella 17 – Programma di esempio

MIPS Assembly Code Machine Binary Code (32 bit) main: lui $8, 0 # i lui $9, 0 # j lui $10, 0 # k lw $11, 0($0) addi $11, $11, 10 # nrig = 10 lui $12, 10 sra $12, $12, 16 # ncol = 10 ciclo: add $13, $8, $9 sw $13, 0($10) addi $10, $10, 4 addi $9, $9, 1 slt $24, $9, $12 addi $25, $0, 1 beq $24, $25, ciclo lui $9, 0 addi $8, $8, 1 slt $24, $8, $11 addi $25, $0, 1 beq $24, $25, ciclo lui $2, 10 sra $2, $2, 16 end: break 0

00111100000010000000000000000000 00111100000010010000000000000000 00111100000010100000000000000000 10001100000010110000000000000000 00100001011010110000000000001010 00111100000011000000000000001010 00000001100000000110010000000011 00000001000010010110100000100000 10101101010011010000000000000000 00100001010010100000000000000100 00100001001010010000000000000001 00000001001011001100000000101010 00100000000110010000000000000001 00010011000110011111111111111001 00111100000010010000000000000000 00100001000010000000000000000001 00000001000010111100000000101010 00100000000110010000000000000001 00010011000110011111111111110100 00111100000000100000000000001010 00000000010000000001010000000011 00000000000000000000000000001101

L’istruzione in esame: addi $11, $11, 10

presenta una situazione di conflitto, sul registro evidenziato, gestita con uno stallo (poiché

dipende da una load e quindi lo stallo è inevitabile) e risolta con un anticipo. In totale,

quindi, verrà generata una sola “bolla” nella pipeline.

Nei paragrafi seguenti sono riportati i risultati della simulazione del programma nella

pipeline con un periodo di clock di 100 ns e indirizzo base 48.

48 E’ il programma ‘matrice.asm’ già esaminato in precedenza


66

1. Fase IF: Instruction Fetch

Figura 62 – Simulazione istruzione in fetch e contenuto della memoria istruzioni

Commenti sulla simulazione: - L’istruzione ADDI entra nella fase di fetch al 5° colpo di clock (450 ns)

- Dai segnali di controllo id_salta, id_salta_inc e id_sel_pc_ecc si può notare che non

c’è nessun salto da effettuare e non si è verificata alcuna eccezione

- Il program counter corrente (if_pc_signal) viene aggiornato (al valore 64) poiché il bit

id_pc_write è posto a ‘1’

- L’istruzione prelevata dalla memoria è “00100001011010110000000000001010”

(segnale if_instr) e corrisponde all’istruzione ADDI esaminata

- I segnali che contengono il program counter futuro (if_pc_4 e if_pc_next_signal) sono

anch’essi aggiornati correttamente (al valore 68 = 64 + 4)


67

2. Fase ID: Instruction Decode (rilevazione stallo)

Figura 63 – Simulazione istruzione in decode (rilevazione stallo) e contenuto banco registri

Commenti sulla simulazione: - L’istruzione ADDI entra nella fase di decode al 6° colpo di clock (550 ns)

# ** Note: CONTROL UNIT: ADD_IMMEDIATE detected... # Time: 550 ns Iteration: 1 Instance: /tb_pipeline/i_d

- L’istruzione propagata dal registro di pipeline IF/ID corrisponde alla ADDI in esame

- Il registro da leggere (reg_read_1) è 11, ma il dato letto (id_data_read_1) non è

ancora pronto

- Il bit ex_mem_read = ‘1’ rileva che in EX c’è una istruzione LOAD, inoltre si ha che il

registro rs della decode (id_rs = 11) è uguale al registro rt della execute (ex_rt = 11)

- Viene quindi rilevato lo stallo e il segnale hazard viene posto a ‘1’ # ** Note: HAZARD UNIT: Criticita' load --> stallo... # Time: 550 ns Iteration: 2 Instance: /tb_pipeline/i_d

- Il segnale id_pc_write viene posto a ‘0’ così che il program counter rimanga

‘congelato’ per il prossimo colpo di clock (if_pc_write = ‘0’)


68

3. Fase ID: Instruction Decode (decodifica istruzione)

Figura 64 – Simulazione istruzione in decode (decodifica istruzione) e contenuto banco registri

Commenti sulla simulazione: - L’istruzione ADDI rimane nella fase di decode al 7° colpo di clock (650 ns)

- L’istruzione propagata dal registro di pipeline IF/ID corrisponde alla ADDI in esame

- Il registro da leggere (reg_read_1) è 11, ma il dato letto (id_data_read_1) non è

ancora pronto

- Il bit ex_mem_read = ‘0’ rileva che in EX non c’è più l’istruzione di LOAD (infatti è

stata introdotta una bolla nella pipeline)

- Non si ha più criticità e il segnal hazard viene posto a ‘0’ # ** Note: HAZARD UNIT: Nessuna criticita' rilevata... # Time: 650 ns Iteration: 2 Instance: /tb_pipeline/i_d

- Il segnale id_pc_write ritorna a ‘1’ così che il program counter possa venire

aggiornato per il prossimo colpo di clock (if_pc_write = ‘1’)

- Il segnale id_reg_write_bit viene posto a ‘1’ poiché l’istruzione deve scrivere su un

registro e viene propagato alle fasi successive


69

4. Fase EX: Execute

Figura 65 – Simulazione istruzione in execute e segnali dell’unità logico-aritmetica

Commenti sulla simulazione: - L’istruzione ADDI entra nella fase di execute all’ 8° colpo di clock (750 ns)

- I segnali wb_reg_write_bit = ‘1’ e wb_rd = ex_rs_signal = 11 segnalano alla unità di

forwarding che è presente un conflitto RAW tra EX e WB

- L’unità di forwarding effettua l’anticipo dei dati dalla fase WB alla fase EX # ** Note: FORWARD_UNIT: conflitto raw exe-wb [rs] risolto... # Time: 750 ns Iteration: 1 Instance: /tb_pipeline/e_x

- Il multiplexer sel_mux_1 = “10” seleziona il dato anticipato proveniente dalla WB

- L’insieme dei multiplexer sel_mux_2 e sel_mux_2_1 fanno passare l’offset

- L’operazione che deve eseguire la ALU è una somma

- Gli operandi della ALU sono i dati corretti da sommare 0 (op_1) e 10 (op_2)

- Il risultato della ALU (ex_res_alu) è la somma dei due operandi, cioè 10


70

5. Fase DM: Data Memory

Figura 66 – Simulazione istruzione in data memory e contenuto della memoria dati

Commenti sulla simulazione: - L’istruzione ADDI entra nella fase di data memory al 9° colpo di clock (850 ns)

- L’indirizzo di accesso in memoria corrisponde al risultato della ALU precedentemente

calcolato

- I bit che regolano l’accesso in memoria (dm_mem_read_signal e

dm_mem_write_signal) sono entrambi a ‘0’ e quindi non vi è alcun accesso: ** Note: DATA MEMORY: Nessun accesso alla memoria # Time: 850 ns Iteration: 1 Instance: /tb_pipeline/d_m/mem_dati


71

6. Fase WB: Write Back

Figura 67 – Simulazione istruzione in write back e contenuto memoria dati

Commenti sulla simulazione: - L’istruzione ADDI entra nella fase di write back al 10° colpo di clock (950 ns)

- Il bit wb_mem_to_reg_signal posto a ‘0’ permette al mux in write back di selezionare

il risultato della alu come dato da scrivere

- Il bit wb_reg_write_bit propagato dalle fasi precedenti vale ‘1’ e quindi viene abilitata

la scrittura sul banco dei registri

- Il segnale wb_data_write contiene il dato da scrivere nel banco registri (cioè 10)

- Il banco registri viene aggiornato sul fronte di discesa del segnale di clock (1000 ns)

quando avviene la scrittura del risultato dell’ istruzione (cioè 10) nel registro $11


72

INDICE DELLE FIGURE, TABELLE ED EQUAZIONI INDICE DELLE FIGURE Figura 1 – Interfaccia parser di base................................................................................................................................... 5

Figura 2 – Interfaccia parser: riconoscimento errore........................................................................................................... 6

Figura 3 – Interfaccia parser: dettaglio................................................................................................................................ 7

Figura 4 – Interfaccia della memoria istruzioni .................................................................................................................. 14

Figura 5 – Il processo che carica le istruzioni in memoria................................................................................................. 14

Figura 6 – Il processo che legge le istruzioni dalla............................................................................................................ 15

Figura 7 – I processi della memoria istruzioni ................................................................................................................... 15

Figura 8 – Interfaccia della memoria dati .......................................................................................................................... 16

Figura 9 – Il processo della memoria dati.......................................................................................................................... 17

Figura 10 – I processi della memoria dati.......................................................................................................................... 17

Figura 11 – Interfaccia banco registri ................................................................................................................................ 18

Figura 12 – Il processo che legge e scrive i registri .......................................................................................................... 19

Figura 13 – Il processo che seleziona i dati letti................................................................................................................ 20

Figura 14 – Schema della selezione dei dati letti .............................................................................................................. 20

Figura 15 – I processi del banco registri ........................................................................................................................... 21

Figura 16 – Interfaccia della alu ........................................................................................................................................ 22

Figura 17 – I processi della ALU ....................................................................................................................................... 23

Figura 18 – L’intefaccia della fetch.................................................................................................................................... 24

Figura 19 – Il processo di aggiornamento sincrono del program counter.......................................................................... 25

Figura 20 – Il processo di aggiornamento combinatorio del program counter................................................................... 25

Figura 21 – I processi della fetch ...................................................................................................................................... 26

Figura 22 – L'interfaccia della decode............................................................................................................................... 27

Figura 23 – Il processo che propaga i registri di pipeline IF/ID.......................................................................................... 28

Figura 24 – Il processo che implementa l’unità di rilevamento delle criticità ..................................................................... 29

Figura 25 – Unità per la gestione delle eccezioni.............................................................................................................. 32

Figura 26 – Unità di controllo ............................................................................................................................................ 32

Figura 27 – Il processo per il calcolo del prossimo pc....................................................................................................... 34

Figura 28 – Il processo che permette l’azzeramento dei bit di controllo............................................................................ 34

Figura 29 – Il processo che seleziona il primo dato letto................................................................................................... 35

Figura 30 – Il processo che seleziona il registro destinazione .......................................................................................... 36

Figura 31 – Il processo che seleziona l’indirizzo di salto................................................................................................... 36

Figura 32 – Il processo che controlla l’uguaglianza dei dati letti........................................................................................ 36

Figura 33 – I processi della decode .................................................................................................................................. 37

Figura 34 – L’interfaccia della execute.............................................................................................................................. 38

Figura 35 – Il processo che propaga i registri di pipeline ID/EX........................................................................................ 39

Figura 36 – Il processo che gestisce il forwarding............................................................................................................. 40

Figura 37 – Il processo che seleziona il primo operatore della ALU.................................................................................. 41

Figura 38 – Il processo che seleziona il dato da scrivere in memoria ............................................................................... 41

Figura 39 – Il processo che seleziona il secondo operatore della ALU ............................................................................. 42

Figura 40 – Il processo che seleziona il registro di destinazione....................................................................................... 42

Figura 41 – Tabella eccezioni ........................................................................................................................................... 43

Figura 42 – Il processo che scrive i registri EPC e Causa ................................................................................................ 43


73

Figura 43 – Il processo che azzera EX/DM....................................................................................................................... 43

Figura 44 – Il processo che azzera DM/WB...................................................................................................................... 43

Figura 45 – Il processo che controlla la ALU..................................................................................................................... 44

Figura 46 – Schema logico bit di eccezione...................................................................................................................... 44

Figura 47 – Il processo che genera il bit di eccezione....................................................................................................... 44

Figura 48 – I processi della execute.................................................................................................................................. 45

Figura 49 – L’interfaccia della data memory...................................................................................................................... 46

Figura 50 – Il processo che propaga i registri di pipeline EX/DM...................................................................................... 47

Figura 51 – Il processo che seleziona il dato da scrivere nella cache dati ........................................................................ 48

Figura 52 – I processi della data memory ......................................................................................................................... 48

Figura 53 – L’interfaccia della write back .......................................................................................................................... 49

Figura 54 – Il processo che propaga i registri di pipeline DM/WB..................................................................................... 50

Figura 55 – Il processo che seleziona il dato da scrivere sul banco registri ...................................................................... 50

Figura 56 – I processi della write back .............................................................................................................................. 51

Figura 57 – Schema finale della pipeline semplice a 5 stdi progettata.............................................................................. 52

Figura 58 – Il dataflow finale della pipeline mostra come sono collegate fra loro le diverse fasi ....................................... 53

Figura 59 – Contenuto della memoria dati e dei registri nelle fasi finali dell’esecuzione del programma.......................... 60

Figura 60 – Contenuto della memoria dati nelle fasi finali dell’esecuzione del programma .............................................. 62

Figura 61 – Istantanea della memoria dati (contiene le ultime 2 righe della matrice) e di alcuni registri ........................... 64

Figura 62 – Simulazione istruzione in fetch e contenuto della memoria istruzioni............................................................. 66

Figura 63 – Simulazione istruzione in decode (rilevazione stallo) e contenuto banco registri ........................................... 67

Figura 64 – Simulazione istruzione in decode (decodifica istruzione) e contenuto banco registri ..................................... 68

Figura 65 – Simulazione istruzione in execute e segnali dell’unità logico-aritmetica......................................................... 69

Figura 66 – Simulazione istruzione in data memory e contenuto della memoria dati........................................................ 70

Figura 67 – Simulazione istruzione in write back e contenuto memoria dati ..................................................................... 71

INDICE DELLE TABELLE ED EQUAZIONI Tabella 1 – Struttura generale istruzione di Tipo-R ............................................................................................................. 9

Tabella 2 – Lista istruzioni di Tipo-R ................................................................................................................................. 10

Tabella 3 – Struttura generale istruzione di Tipo-I............................................................................................................. 11

Tabella 4 – Lista istruzioni di Tipo-I ................................................................................................................................... 11

Tabella 5 – Struttura generale istruzione di Tipo-J............................................................................................................ 12

Tabella 6 – Lista istruzioni di Tipo-J .................................................................................................................................. 12

Tabella 7 – Tabella delle convenzioni adottate per i registri.............................................................................................. 18

Tabella 8 – Elenco comandi ALU ...................................................................................................................................... 23

Tabella 9 – Programma che verifica il forwarding ............................................................................................................. 54

Tabella 10 – Programma che verifica lo stallo e l’anticipo tra write back e data memory (load-store) .............................. 55

Tabella 11 – Programma per verificare il funzionamento della BRANCH dipendente....................................................... 56

Tabella 12 – Programma che verifica la gestione dell’overflow (codice eccezione: 4) ...................................................... 57

Tabella 13 – Programma che verifica la gestione della divisione per zero (codice eccezione: 2) ..................................... 58

Tabella 14 – Programma che calcola il fattoriale di un numero......................................................................................... 59

Tabella 15 – Programma che calcola i numeri primi compresi tra 0 e 100 (vedi 2° istruzione) ......................................... 61

Tabella 16 – Programma che inizializza una matrice 10 x 10 ........................................................................................... 63

Tabella 17 – Programma di esempio ................................................................................................................................ 65 Equazione 1 – Matrice 10x10 generata dal programma ‘matrice.asm’.............................................................................. 63

Progetto Processore MIPS con pipeline a 5 stadi - … Processore MIPS... · 6. Programmi di test:...

Documents

Transcript of Progetto Processore MIPS con pipeline a 5 stadi - … Processore MIPS... · 6. Programmi di test:...