Difference between revisions of "Detailed studies"

Revision as of 15:15, 26 September 2017

This page contains all the experience from the user that have worked on nu+ architecture and want to share all the acquired experiences

Fused multiply-add inside the microarchitecture

Vincenzo

Replacement L2

Introduction

In questo Capitolo si intende mostrare come si svolge la Replacement Chain relativamente alla cache L2, osservando come il Directory Controller evolve per gestire l’occorrenza di tale casistica. Lo scopo principale è quello di testare tutti i casi in cui si verifica un replacement L2, come descritto in figura:

Memory in Directory Controller

Per poter comprendere al meglio come funziona il meccanismo di replacement è necessario in primis valutare come è strutturata la cache amministrata dal Directory Controller. La seguente descrizione rappresenta la configurazione utilizzata per tutti gli esperimenti. Come possiamo osservare dalla figura la cache è costituita da quattro way e 64 set, ogni way contiene al proprio interno un tag e un dato (64 bit).

Gli indirizzi gestiti sono di 32 bit e sono organizzati come descritto in figura:

Ogni directory controller può quindi gestire un numero limitato di indirizzi, ad esempio la Tile 0 può gestire gli indirizzi da 0x00000000 a 0x3fffffff, la Tile 1 da 0x4000000 a 0x7fffffff, e così via. Negli esperimenti trattati vengono utilizzate quattro Tile.

Replacement Chain

Per poter causare un replacement è necessario riempire tutte e quattro le way relative ad un determinato set: all’atto dell’inserimento di una nuova entry nello stesso set viene realizzato il replacement. Per una questione di semplicità è necessario scrivere il codice da eseguire direttamente in Assembly all’interno dei kernel utilizzati, per avere un maggiore controllo sulle operazioni effettuate e sugli indirizzi di memoria utilizzati. L’operazione di replacement è gestita in maniera tale da rimpiazzare direttamente la entry LRU senza invalidare la linea di cache su cui effettuare il replacement, demandando le operazioni di invalidazione (verso i cache controller) ad una successiva fase. Per poter stabilire che si sta verificando un replacement è necessario osservare il segnale do replacement. Tale segnale è alto solo se

do_replacement = dc2_message_valid && ((allocate_cache | | update_cache) && !deallocate_cache) && !is_replacement && !dc2_message_cache_hit && dc2_message_cache_valid;

quindi se il dc2 ha processato una richiesta diversa da un replacement e che non causi la deallocazione di una linea di cache, se non si è verificato un hit all’interno della cache allora sarà necessario eseguire un replacement. A seguito dell’asserzione del segnale do replacement si scatena l’enqueue della richiesta di replacement all’interno della relativa coda attraverso il segnale dc3 replacement enqueue, inserendo in tale coda anche il contenuto della linea di cache su cui effettuare il replacement:

dc3_replacement_enqueue                    	= dc2_message_valid && do_replacement;
assign dc3_replacement_request.source          = dc2_message_source,
dc3_replacement_request.memory_address.tag  	= dc2_message_cache_tag,
dc3_replacement_request.memory_address.index  	= dc2_message_address.index,
dc3_replacement_request.memory_address.offset 	= 0,
dc3_replacement_request.data                 	= dc2_message_cache_data,
dc3_replacement_request.state                 	= dc2_message_cache_state,
dc3_replacement_request.sharers_list          	= dc2_message_cache_sharers_list,
dc3_replacement_request.owner                 	= dc2_message_cache_owner;

Si tenga conto che dc2 message address.index contiene l’indice dell’LRU prelevato dallo stadio 2. Così come descritto all’interno della documentazione del Directory Controller, lo Stage 1 contiene uno scheduler a priorità fissa che comporta la processazione con massima priorità delle replacement request se la condizione can issue replacement request è verificata. Oltre ai soliti segnali lo Stage 1 trasmette allo Stage 2 i segnali:

dc1_replacement_state <= output_replacement_state;
dc1_replacement_sharers_list <= output_replacement_sharers_list;
dc1_replacement_owner <= output_replacement_owner;

Tali segnali vengono inoltrati dallo Stage 2 allo Stage 3. Nello Stato 3, in cui avviene l’effettiva processazione della richiesta, viene effettuato il replacement, così come definito all’interno della Protocol ROM a seconda dello stato in cui ci si trova.

Replacement di una linea nello Stato M

Per poter testare il replacement di un blocco nello stato M e valutare i segnali principali descritti nella relativa documentazione, per quanto rigurda il Directory Controller, è stato costruito il seguente kernel:

if(tile_id==0){	
 asm( 	
  "moveih s20, 0x0000"
  "moveil s20, 0x0000"
  "store32 s21, (s20)"
		
  "moveil s20, 0x1000"
  "store32 s21, (s20)"
  
  "moveil s20, 0x2000"
  "store32 s21, (s20)"	
 );
}else if(tile_id==1){
 asm( 	
  "moveih s20, 0x0000"
  "moveil s20, 0x4000"
  "store32 s21, (s20)"
  
  "moveil s20, 0x8000"
  "store32 s21, (s20)"
 );
}

In questo caso la Tile 0 esegue tre store e la Tile 1 ne esegue 2. Per poter distinguere le diverse richieste si osservi il segnale dc1 message valid in figura, tale segnale è asserito quando lo scheduler a priorità fissa preleva una delle richieste dalla rispettiva coda.

Come si può evincere dalla simulazione i messaggi vengono processati dal Directory Controller nel seguente ordine:

• 1. store della Tile 1 all’indirizzo 0x00004000
• 2. store della Tile 0 all’indirizzo 0x00000000
• 3. store della Tile 1 all’indirizzo 0x00008000
• 4. store della Tile 0 all’indirizzo 0x00001000
• 5. store della Tile 0 all’indirizzo 0x00002000

Le richieste sono state effettuate in modo tale da appartenere allo stesso set, così da scatenare il replacement.

Date le richieste, la cache è allocata nel seguente modo:

Per ottenere le precedenti informazioni è stato valutato il segnale dc3_update_cache_way, che abilita la scrittura della entry nella L2. Tale segnale dipende direttamente da selected_way, che in caso di hit contiene l’hit_index, in caso contrario l’lru_way (si faccia riferimento alla sezione relativa alla Pseudo LRU).

assign selected way = hit ? hit idx : lru_way;

In alternativa è possibile osservare come evolve il segnale dc1_message_cache_state. Osserviamo in dettaglio cosa succede nel caso di una semplice richiesta:

Il caricamento nella cache avviene per mezzo del segnale dc3_update_cache_state. Dalla seguente figura è possibile verificare come la entry venga allocata nella way 0, così come descritto in precedenza.

All’atto della quinta store si ha che la cache L2 si riempie e parte il meccanismo di replacement. Per comprenderne il funzionamento possiamo osservare quali sono i messaggi che dovrebbero essere scambiati in via teorica, per poi ottenere un riscontro pratico:

Dalla successiva figura è possibile osservare che la richiesta viene eseguita e la linea di cache viene inserita al posto della entry indicata dal segnale lru way; possiamo quindi rilevare il segnale do_replacement alto e di conseguenza anche il segnale do_replacement_enqueue), che comporta l’inserimento della richiesta all’interno della replacement queue.

A questo punto è interessante verificare come si svolge l’operazione di replace all’interno della pipe osservando l’evoluzione dei segnali negli Stage in ordine crescente, quindi:

• Stage 1: in figura possiamo osservare che la condizione can_issue_replacement_request è soddifatta, quindi viene prelevata la richiesta dalla relativa coda. Tale richiesta è di tipo ’c’, ovvero Replace.

• Stage 2: la richiesta viene inoltrata allo stage 3, è possibile verificare come la selected_way è proprio pari all’lru_way dato il miss, anche se non verrà utilizzata nello stage 3, perchè viene prelevata la way che accompagna la richiesta;
• Stage 3: il segnale is_replacement è alto, quindi si tratta effettivamente di un replacement.

I messaggi che vengono inviati a questo punto dipendono dalla Protocol ROM, così come si può osservare dal seguente estratto di codice:

{STATE_M, REPLACEMENT, 1'b?, 1'b?}   : begin // Replacement

 // Send BACKINV To Owner
	
 dpr_output.message_forwarded_send         = 1'b1;
	
 dpr_output.message_forwarded_type         = MESSAGE_BACKINV;
	
 dpr_output.message_forwarded_to_owner     = 1'b1;
	
	
 // Next State MN_A
	
 dpr_output.next_state                     = STATE_MN_A;
	
 dpr_output.next_state_is_stable           = 1'b0;

E` quindi necessario generare i messaggi di invalidation da inviare all’owner della linea di cache rimossa (si osservi il messaggio BACK_INV in figura).

Un altro modo per valutare i segnali consiste nel porsi ad un più alto livello di dettaglio, analizzando le transazioni attarverso lo scambio di messaggi, raccolti all’interno del log (rappresentato dal file display_coherence.txt).

=======================
Directory Controller - [Time 12810] [TILE 0] - Message Sent
Forwarded Destinations: 0010
Source:       0
Address:      00004000
Requestor:    DCACHE
Packet Type:  BACK_INV
Uncoherent:   0
=======================
Cache Controller - [Time 12890] [TILE 1] [Core 0]
Source:       0
Address:      00004000
Requestor:    DCACHE
Packet Type:  BACK_INV
Uncoherent:   0

Una volta processata tale richiesta viene aggiunta una entry nel TSHR (vedi figura seguente), indicando che il blocco di cache rimosso si trova nello stato 5 (MN^A), ovvero in attesa degli INV_ACK.

Così come ci si aspetta dall’evoluzione del protocollo negli altri controllori, prima o poi ritroveremo in ingresso allo Stage 1 messaggi di response del tipo ’b’, Last INV ACK (dato che si tratta dell’unico owner). Il messaggio Last INV ACK corrisponde al WB inviato al Directory Controller, così come visto nella rappresentazione teorica dello scambio messaggi. Una volta ricevuto l’ACK il bit della validità della relativa entry TSHR si abbassa.

Replacement di una linea nello Stato S

Caso 1: Singolo Sharer

Caso 2: Multiple Sharers

Replacement di una linea nello Stato I

Replacement negli stati instabili