Progetto di una memoria cache per il processore DLX

Andrea GrandiFilippo Malaguti

Massimiliano MattettiGabriele MorliniThomas Ricci

Progetto di Calcolatori Elettronici M

Obiettivi del progetto

1. Progettazione e implementazione di una memoria cache

2. Integrazione nel processore DLX

3. Realizzazione dei testbench

4. Studio della Block RAM

Caratteristiche della cache

• Cache di tipo Set-Associative– Realizzazione di un componente VHDL indipendente – Dimensione e numero di vie parametrizzabili

• Comportamento in caso di write miss: write-allocate

• Coerenza garantita dal protocollo MESI

Cache

Tag Dati

Algoritmo di rimpiazzamento

• Politica LRU (Least Recently Used)

• Un contatore associato ad ogni linea della cache– Meccanismo di aggiornamento dei contatori

• HIT:– Resetto contatore della via in cui c’è stato l’HIT– Incremento i contatori di valore più basso

• INV– Contatore della via invalidata portato al massimo– Decremento i contatori con valore più elevato

• MISS– Si scarta la via con contatore più elevato

cache_hit_oncache_hit_on

cache_inv_oncache_inv_on

cache_replacecache_replace

Strutture dati VHDL: Cache_lib.vhdlCONSTANT OFFSET_BIT : natural := 5;

CONSTANT INDEX_BIT : natural := 2;

CONSTANT TAG_BIT : natural := PARALLELISM − INDEX_BIT − OFFSET_BIT;

CONSTANT NWAY : natural := 2;

TYPE data_line IS ARRAY (0 to 2 OFFSET_BIT − 1) of ∗∗STD_LOGIC_VECTOR (7 downto 0);

TYPE cache_line IS

RECORD

data : data_line;

status : natural;

tag : STD_LOGIC_VECTOR (TAGBIT−1 downto 0);

lrucounter : natural;

END RECORD;

TYPE set_ways IS ARRAY (0 to NWAY− 1) of cache_line;

TYPE cache_type IS ARRAY (0 to 2 INDEX_BIT − 1) of set_ways ;∗∗

Schema delle strutture dati

Cache con 4 vieCache con 4 vieNumero di set_ways

dipende dal numero di bit di index

Numero di set_ways dipende dal numero di

bit di index

cache_type

Interfacciamento del componente

Controllo stato interno della cache

Controllo stato interno della cache

Scambio di dati con la RAM

Scambio di dati con la RAM

Scambio di dati con il DLX

Scambio di dati con il DLX

Modifica dello stato delle linee

Modifica dello stato delle linee

Interfacciamento con RAM

• Inizialmente si utilizza il componente Ram_cmp• La RAM è realizzata come un array di data_line

• Successivamente sarà sostituita dalla Block RAM.

Interfacciamento con controllore

• Operazioni supportate:• Snoop dei dati presenti in cache• Invalidazione di una linea• Caricamento linea in stato E o S

Implementazione

La cache è internamente suddivisa in quattro processi principali che interagiscono tra loro.

cache_dlxcache_dlx cache_replacecache_replace

cache_snoopcache_snoop cache_ramcache_ram RAMRAMControllore di memoriaControllore di memoria

DLXDLX

Cache

Processo cache_dlx

I compiti di questo processo riguardano i seguenti aspetti: • gestione della lettura di dati dalla cache;• gestione della scrittura dei dati provenienti dal DLX nella

cache;• attivazione del meccanismo di rimpiazzamento di una linea;• generazione del segnale di ready per il DLX;

Riceve dal DLX i segnali: • ch_memrd: segnale per una richiesta di letture;• ch_memwr: segnale per una richiesta di scrittura;

Processo cache_ram

Questo processo si occupa dell’intefacciamento con la RAM. 

Viene attivato dagli altri processi interni alla cache, tramite l'attivazione dei segnali:• write_line: per iniziare una scrittura sulla memoria RAM• read_line: per iniziare una lettura sulla memoria RAM

 

Segnala al processo chiamante il termine dell'operazione richiesta tramite il segnale rdwr_done.

Processo cache_replace

Si occupa di gestire i meccasmi per il rimpiazzamento delle linee.  In particolare questoprocesso implementa la politica di rimpiazzamentobasata sui contatori. 

Processo cache_snoop

Il processo cache snoop è attivato dal segnale esterno ch_eads, proveniente dal controllore di memoria e consente a quest’ultimo di operare sullo stato delle linee.

In seguito all’attivazione di ch_eads, il processo ha il seguente comportamento: • ch_hit viene portato al valore ‘1’ se la linea oggetto dello snoop è presente

in cache con stato diverso da MESI_I;

• ch_hitm viene portato al valore ‘1’ se la linea è presente in stato MESI_M; in questo caso viene anche forzata la scrittura della linea in RAM;

• se il segnale ch_inv è al valore '0' la linea viene portato allo stato MESI_S; se è al valore ‘1’ allo stato MESI_I.

I quattro processi si scambiano segnali che consentono la sincronizzazione delle operazioni da svolgere.

 

Ogni processo notifica il completamento dell’operazione richiesta attivando un opportuno segnale di ready.

Comunicazione tra processi

Attiva il rimpiazzamento di Attiva il rimpiazzamento di una linea, in seguito ad un una linea, in seguito ad un miss.miss.

Attiva il rimpiazzamento di Attiva il rimpiazzamento di una linea, in seguito ad un una linea, in seguito ad un miss.miss.

Attiva la scrittura in Attiva la scrittura in RAM di una linea in RAM di una linea in stato MESI_M, prima stato MESI_M, prima che sia rimpiazzata.che sia rimpiazzata.

Attiva la scrittura in Attiva la scrittura in RAM di una linea in RAM di una linea in stato MESI_M, prima stato MESI_M, prima che sia rimpiazzata.che sia rimpiazzata.

Attiva la propagazione della Attiva la propagazione della modifica di una linea in stato modifica di una linea in stato MESI_S in memoria RAM;MESI_S in memoria RAM;

Attiva la propagazione della Attiva la propagazione della modifica di una linea in stato modifica di una linea in stato MESI_S in memoria RAM;MESI_S in memoria RAM;

Attiva la scrittura di una Attiva la scrittura di una linea in stato MESI_M in linea in stato MESI_M in memoria RAM in seguito ad memoria RAM in seguito ad uno snoop.uno snoop.

Attiva la scrittura di una Attiva la scrittura di una linea in stato MESI_M in linea in stato MESI_M in memoria RAM in seguito ad memoria RAM in seguito ad uno snoop.uno snoop.

Richiede la lettura di Richiede la lettura di una nuova linea dalla una nuova linea dalla RAM.RAM.

Richiede la lettura di Richiede la lettura di una nuova linea dalla una nuova linea dalla RAM.RAM.

Modifica al DLX

IFIF IDID EXEX MEMMEM WBWB

RAMRAM

CacheCache

DLX

Cache_cmp

Ram_cmp

Integrazione della cache nel DLXModifica dello stadio di MEMORY:

• doppio bus dati per input ed output dalla cache • bus indirizzi verso la cache• segnali di controllo verso la cache (memwr/memrd)• segnale di sincronizzazione con la cache (ready)

Modifiche al codice dello stadio di MEM

Operazione di Load:

case a_opcode_high is

when I_LW | IF_LF =>

memory_address_register <= alu_exit_buffer;

memrd <= '1';

wait until ready = '1' and ready'event;

memrd <= '0' after TIME_UNIT/3;

dest_register <= a_rd_i;

dest_register_data <= load_memory_data_register;data_out <= load_memory_data_register;

Modifiche al codice dello stadio di MEM

Operazione di Store:

when I_SW | IF_SF =>

dest_register <= (others => '0');

dest_register_data <= (others => '0');

data_out <= alu_exit_buffer;

store_memory_data_register <= memory_data_register_buffer;

memory_address_register <= alu_exit_buffer;

memwr <= '1';

wait until ready = '1' and ready'event;

memwr <= '0' after TIME_UNIT/3;

Stadio di Memory

Testbench

Testbench del componente:

1. Cache_test_ReadAndReplacement.vhd2. Cache_test_ReadAndWrite.vhd3. Cache_test_Snoop.vhd

Testbench integrazione con processore DLX:

1. ProvaReplacement123: verifica comunicazione tra cache e DLX e del meccanismo di rimpiazzamento

Cache_test_ReadAndReplacement.vhd

Tag Index Replacement

Linea invalidata (MESI_I)

Replacement

• Fase 1: inizializzazione• Fase 2: invalidazione di una linea• Fase 3: verifica funzionamento meccanismo

Replacement, mediante contatori

Cache_test_ReadAndWrite.vhd

• Fase 1: inizializzazione: una linea in MESI_S

• Fase 2: scritture

MESI_S MESI_E

MESI_I MESI_M

MESI_E MESI_M

Cache_test_Snoop.vhd

Dopo aver inizializzato la cache…

ProvaReplacement123

Obiettivo:Testare la corretta comunicazione tra lo stadio di MEM e la CACHE e il meccanismo di rimpiazzamento, Codice Assembler:X"20010000", --l1: addi r1,r0,0 ; X"20020001", --l2: addi r2,r0,1 ; X"AC220000", --l3: sw 0(r1),r2 ; X"20420001", --l4: addi r2,r2,1 ; X"AC220100", --l5: sw 16#100(r1),r2 ; X"20420001", --l6: addi r2,r2,1 ; X"AC220080", --l7: sw 16#80(r1),r2 ; X"8C220000", --l8: lw r2,0(r1) ; X"20210004", --l9: addi r1,r1,4 ; X"0BFFFFE0", --l10: j l3 ;X"FFFFFFFF", --NOP

l3: 0+0= 00 0000 0000

l5: 100+0= 01 0000 0000

l7: 80+0= 00 1000 0000

l8: 0+0= 00 0000 0000

ProvaReplacement123

l3: 0+0= 00 0000 0000

l5: 100+0= 01 0000 0000

l7: 80+0= 00 1000 0000

l8: 0+0= 00 0000 0000

Block RAM

• Una scheda FPGA Spartan-3 Xilix offre una serie di Block Ram interne al chip di FPGA, il cui numero dipende dalle caratteristiche tecniche dell’FPGA utilizzata.

• Caratteristiche implementative: Capacità di memorizzazione: 18,432 celle di memoria SRAM

2 porte d’accesso configurabili:

16 Kbits di dato18 Kbits +

2 Kbits per bit di parità

Single-PortDual-Port

Block RAM

• Caratteristiche implementative: Configurazioni interne dei dati:

512x36: accesso a dati a 36 bit di cui 32 di dato e 4 bit di parità.Ram Depth = 512

…

2Kx9: accesso a dati a 9 bit di cui 8 di dato e 1 bit di parità. Ram Depth = 2K

…

16Kx1: accesso a dati di 1 solo bit alla volta.Ram Depth = 16K

Realizzazione di un progetto d’esempio

Scopi:

1. Come utilizzare la Block Ram in un progetto VHDL

2. Configurazione ed inizializzazione Block RAM

3. Verificarne il funzionamento

Realizzazione di un progetto d’esempio

Scopi:

1. Come utilizzare la Block Ram in un progetto VHDL

2. Configurazione ed inizializzazione Block RAM

3. Verificarne il funzionamento

BlockRam_cmp: progetto d’esempioBlockRam_cmp: Ram integrabile con Cache_cmp col compito di scambiare con

essa delle data_line. Block RAM in Single-Port con organizzazione 2Kx9. Tempi d’accesso non nulli!

• Come si utilizza la Block Ram in un progetto VHDL?1. Xilix Core Generator

2. Utilizzo di componenti Block Ram della libreria UNISIM packageVcoponets sulla base dell’organizzazione interna voluta.

BlockRam_cmp: Implementazione

Riceve le richieste di lettura e scrittura di una linea di memoria

da e verso la Block Ram

Riceve le richieste di lettura e scrittura di una linea di memoria

da e verso la Block Ram

Gestione dell’accesso sequenziale alla Block Ram tramite una serie di letture o

scritture di singoli byte

Gestione dell’accesso sequenziale alla Block Ram tramite una serie di letture o

scritture di singoli byte

Completamento del trasferimento in Block Ram e asserzione del

segnale di ready

Completamento del trasferimento in Block Ram e asserzione del

segnale di ready

Configurazione RAMB16_S9

• Attributi di configurazione nella sezione generic di un component VHDL: WRITE_MODE INIT SRVAL

INIT_xx

• Inizializzazione del contenuto:

Testbench: WRITE_FIRST

• Scopo: Verificare il corretto funzionamento

del componente. Verificare le diverse WRITE_MODE

in scrittura. WRITE_MODE = WRITE_FIRST

Testbench: READ_FIRST WRITE_MODE = READ_FIRST

Politica Read-before-Write : la scrittura su Block Ram comporta prima la lettura del dato presente in memoria che andrà sovrascritto dalla scrittura corrente

Testbench: NO_CHANGE WRITE_MODE = NO_CHANGE

La scrittura non comporta alcun cambiamento dell’uscita.

Il valore nullo che si legge dopo la scrittura sul bdata_out è il valore inizializzato sul registro d’uscita con l’attributo INIT .

Il valore nullo che si legge dopo la scrittura sul bdata_out è il valore inizializzato sul registro d’uscita con l’attributo INIT .

Sviluppi Futuri

• Integrazione del componente BlockRam_cmp nel progetto Cache_cmp + DLX

Necessità di introdurre un contatore per gli stati di wait e che deve inviare il ready al DLX al termine di un accesso in memoria

Modifica interna al DLX per stallare la pipeline in caso di assenza del ready