Difference between revisions of "L2 and Directory cache controller"

Revision as of 20:15, 20 September 2017

Il Directory Controller è quel componente che si occupa della gestione della cache L2 (o LLC), in maniera tale da realizzare i meccanismi di coerenza e, sfruttando l'inclusività della L2, è possibile gestire contemporanemante anche la cache della Directory. Infatti se una linea di cache non è presente nella L2 non sarà presente in nessuna delle cache L1 e quindi risulta inutile avere la corrispettiva linea di cache della directory. Pertanto le informazioni della Cache Directory sono associate a quelle della cache L2.

Così come si può dedurre dal codice, il Directory Controller può essere suddiviso in tre stage, che vedremo nel dettaglio in seguito.

Nel Directory Controller è presente anche un ulteriore componente trasversale, il TSHR, (transaction status handling registers) che si occupa della gestione delle richieste in sospeso. Un'assunzione fondamentale relativa al Directory Controller è che in ogni momento può essere processata una sola richiesta per volta all'interno della pipe. La fisolofia alla base della gestione delle richieste è che se una linea i trova in uno stato stabile, allora è memorizzata in cache, altrimenti nel TSHR. Il Directory Controller si interfaccia con la Network Interface per la ricezione e l'invio di richieste e risposte.

Stage1

Lo stage 1 ha lo scopo principale di dover eseguire l'issue di una richiesta in ingresso al controllore. Tali richieste provengono dalla Network Interface (forwarded request e response) più una richiesta di replacement generata internamente dal controllore (verrà spiegato nel dettaglio nello stage 3). Per poter eseguire una richiesta, bisogna interrogare;

• il TSHR, se c'è una richiesta già pendente o se è pieno;
• la protocol ROM, se la richiesta deve essere bloccata;
• la Network Interface, se la rete non è disponibile ad inviare un possibile pacchetto;
• gli stage successivi, per vedere se ci sono o meno richieste ancora nella pipe.

Di seguito è riportato il codice equivalente:

can_issue_replacement_request = !rp_empty && !tshr_full && !replacement_request_tshr_hit &&
   ! (( dc2_pending ) ||( dc3_pending )
   ) && ni_forwarded_request_network_available && ni_response_network_available;

Mentre la condizione relativa all'invio di una response risulta essere particolarmente semplice, quella relativa alla request è molto simile a quella descritta per la replacement request, ma complicata nella valutazione della entry prensente nel TSHR, così da non violare le condizioni imposte dal protocollo, ovvero: che non ci sia stato un hit, oppure se c'è stato un hit e la richiesta non è valida, oppure, se c'è stato un hit e la richiesta è valida, il protocollo non stalla tale richiesta. Tale complicazione è dovuta al fatto che bisogna eseguire richieste relative a richieste precedentemente pendenti.

assign can_issue_request = ni_request_valid && !tshr_full && ( !request_tshr_hit || ( request_tshr_hit  && !request_tshr_entry_info.valid) ||
   ( request_tshr_hit && request_tshr_entry_info.valid  && !stall_request ) ) &&
   ! (( dc2_pending ) || ( dc3_pending )
   ) && ni_forwarded_request_network_available && ni_response_network_available;
assign can_issue_response = ni_response_valid;

Come detto, tale stage scambia informazioni con il TSHR. Più precisamente invia allo stesso i tag e i set relativi ad una richiesta, risposta o replacement request, ottenendo come risposta un segnale di hit per ogni diversa tipologia; solo se il segnale di hit è alto le relative informazioni (index e entry_info) possono essere interpretate. Di seguito è riportato come esempio il codice relativo alle Request:

assign dc1_tshr_lookup_tag[REQUEST_TSHR_LOOKUP_PORT] = ni_request.memory_address[`L2_CACHE_TAG_SUBFIELD];
assign dc1_tshr_lookup_set[REQUEST_TSHR_LOOKUP_PORT] = ni_request.memory_address[`L2_CACHE_SET_SUBFIELD];

assign request_tshr_hit  = tshr_lookup_hit[REQUEST_TSHR_LOOKUP_PORT];
assign request_tshr_index  = tshr_lookup_index[REQUEST_TSHR_LOOKUP_PORT];
assign request_tshr_entry_info  =  tshr_lookup_entry_info[REQUEST_TSHR_LOOKUP_PORT];

L'interazione con la Protocol ROM in questo stage ha come obiettivo principale quello di determinare se una richiesta deve essere o meno "stallata", così come previsto dal protocollo di coerenza. Il tutto viene realizzato attraverso la comunicazione da parte dello Stage 1 alla sezione apposita della Protocol ROM del tipo di messaggio, dello stato e dell'owner della relativa risorsa.

assign dpr_state = tshr_lookup_entry_info[REQUEST_TSHR_LOOKUP_PORT].state;
assign dpr_message_type = ni_request.packet_type;
assign dpr_from_owner = ni_request.source == request_tshr_entry_info.owner;

assign stall_request = dpr_output_request.stall;

Determinate le condizioni per poter eseguire l'issue di una richiesta, uno scheduler fixed-priority esegue lo scheduling delle richieste nel seguent ordine: replacement request, response, forwarded request. In particolare, nel caso in cui sia presente almeno una richiesta all'interno della Replacement Queue, essa sarà sempre prelevata ed eseguita con massima priorità al fine di preservare l'ordine di esecuzione delle istruzioni, che equivale a preservare la coerenza.

In conclusione della descrizione dello Stage 1, possiamo notare la presenza della tag&state cache L2, che conserva i tag della cache L2 e lo stato della Directory. In questo caso possiamo verificare come i segnali di scrittura e aggiornamento delle voci presenti all'interno della cache L2 siano retroazionate dallo Stage 3 (ciò rappresenta uno dei motivi principali per cui può essere processata una singola richiesta alla volta).

TSHR

Il TSHR ha lo stesso identico funzionamento dell'MSHR. Si rimanda al paragrafo nel Cache Controller per la dinamica del funzionamento interno.

Stage 2

Per quanto riguarda lo Stage 2 possiamo notare che riceve in ingresso l'output dello Stage 1 e la retroazione proveniente dallo Stage 3, in output segnali diretti allo Stage 3, in parte costituiti da semplici inoltri degli input provenienti dallo Stage 1.

All'interno dello Stage 2 possiamo notare la presenza della cache di livello L2 contenente i dati, per cui ritroviamo la logica di hit/miss plru. Di seguito è riportato come viene eseguito il controllo di hit:

generate
genvar way_idx;
   for ( way_idx = 0; way_idx < `L2_CACHE_WAY; way_idx++ ) begin
      assign hit_oh[way_idx] = dc1_message_cache_valid[way_idx] && ( dc1_message_cache_tag[way_idx] == dc1_message_address.tag );
   end
endgenerate

Il codice riportato mostra l'assegnazione della way selezionata, che in caso di hit è assegnata al relativo indirizzo, altrimenti alla lru_way, che rappresenta l'output della pseudo-lru, ovvero la linea di cache meno utilizzata.

assign selected_way = hit ? hit_idx : lru_way;

All'interno del Memory Bank possiamo osservare come la lettura venga effettuata utilizzando l'index proveniente dallo Stage 1 e la way ottenuta come descritto, mentre la scrittura è sotto il diretto controllo dello Stage 3. I dati contenuti all'interno della cache sono i dati contenuti nella cache L2 e i dati della Cache Directory, cioè l'owner della linea e la lista degli sharer .

Stage 3

Il compito fondamentale dello Stage 3 è quello di eseguire effettivamente la richiesta in ingresso attraverso i segnali provenienti dalla Protocol ROM. Prima di poter determinare i segnali di controllo in uscita bisogna selezionare opportunamente lo stato in ingresso. Ciò dipende da vari fattori:

• se c'è stato un cache hit, allora lo stato da processare viene prelevato dalla cache;
• se c'è stato un TSHR hit, allora c'è una richesta pendente e bisogna prelevare lo stato dal TSHR;
• se c'è un replacement, allora bisogna prelevare lo stato dal messaggio stesso;
• se non si è verificato nessuno dei precedenti casi, allora lo stato è N, non presente in cache.

La selezione viene realizzata attraverso un scheduler a priorità fissa e l'uscita comprende informazioni relative alla coerenza (stato, sharerer list e owner) con in relativo indirizzo. Le uscite della Protocol ROM sono molteplici e determinano tutte le principali azioni che svolge lo Stage 3: TSHR update, Cache update, PseudoLRU update e generazione dei messaggi.

TSHR update

Per TSHR update si intende allocare, deallocare o aggiornare una entry del TSHR. La filosofia alla base della Directory è avere linee di cache valide quando lo stato è stabile, mentre avere la linea di cache allocata nel TSHR quando lo stato è instabile. Per allocare una linea nel TSHR, lo stato corrente deve essere stabile e il successivo no; condizione opposta per la deallocazione di una entry. L'aggiornamento, invece, avviene solo se stato corrente e successivo sono entrambi instabili e bisogna aggiornare una delle informazioni contenute al suo interno. Il segnale che valida un'operazione su TSHR è asserito ogni qual volta viene eseguita una qualsiasi operazione su TSHR.

assign coherence_update_info_en  =
  ( current_state != dpr_output.next_state ) | // cambiamento nello stato
  dpr_output.owner_clear | dpr_output.owner_set_requestor | dpr_output.sharers_add_owner | // cambiamento nell'owner
  dpr_output.sharers_add_requestor | dpr_output.sharers_clear | dpr_output.sharers_remove_requestor; // cambianento nella sharer list

assign tshr_allocate = current_state_is_stable && !next_state_is_stable,

  tshr_update  = !current_state_is_stable & !next_state_is_stable & coherence_update_info_en, 
  tshr_deallocate = !current_state_is_stable && next_state_is_stable; 

assign dc3_update_tshr_entry_info.valid =( tshr_allocate | tshr_update ) & ~tshr_deallocate; 
assign dc3_update_tshr_enable  = dc2_message_valid && ( tshr_allocate || tshr_deallocate || tshr_update ) ;

Cache update

Per quanto riguarda la fase di Cache update è necessario definire attentamente quando allocare, deallocare o aggiornare una linea di cache. Ricordando che una linea si trova in cache se lo stato associato è stabile e si trova nel TSHR se lo stato è instabile, l'allocazione di una linea di cache avviene se si passa ad uno stato stabile che non sia N (ovvero la nuova linea di cache non sia invalida), mentre l'update avviene quando una linea era già presente nella cache e bisogna aggiornarne le informazioni (senza però passare ad uno stato instabile).

Le condizioni per la deallocazione di una linea di cache sono legate anche alla gestione del replacement. Essa avviene quando una linea passa dalla cache al TSHR o eliminata (stato N).

assign update_cache     = dc2_message_cache_hit & current_state_is_stable & next_state_is_stable & ( coherence_update_info_en | dpr_output.store_data );
assign deallocate_cache = ( tshr_allocate & dc2_message_cache_hit) ;
assign allocate_cache    = next_state_is_stable & ( coherence_update_info_en | dpr_output.store_data ) & ~(tshr_deallocate & dpr_output.invalidate_cache_way);

assign dc3_update_cache_enable  = dc2_message_valid && !is_replacement && ( allocate_cache || update_cache || deallocate_cache ),
  dc3_update_cache_validity_bit   = ~dpr_output.invalidate_cache_way,

Ora si consideri questa osservazione: il passaggio allo stato N avviene solo quando è stato eseguito un replacement (tale condizione è generica e non dipendente dal protocollo). Per rendere più efficiente la gestione del replacement, si evita di deallocare la linea di cache ad ogni replacement, sostituendola subito con la nuova entry (quindi già valida) e quella uscente verrà subito inserita nella Replacement Queue. Questa è la parte più delicata dell'aggiornamento della cache, perchè potenzialmente si legge contemporaneamente un dato dalla memoria (che va nella replacement queue), si invia un messaggio sulal rete e si alloca una linea nel TSHR.

Protocol ROM

Il modulo directory\_protocol\_rom implementa il protocollo MSI dal punto di vista del Directory Controller, così come descritto in figura.

\begin{figure}[h] \centering \includegraphics[width=1.05\linewidth]{Images/MSI_DC} \caption{Descrizione dettagliata del protocollo} \label{fig:msidc} \end{figure}

Così come visto per il Cache Controller, anche in questo caso è stato utilizzato MSI, apportando però alcune modifiche: l'inserimento dello stato N rappresenta una condizione nella quale il dato che si intende ottenere è presente solo in memoria centrale, mentre lo stato I lo stato in cui il dato è nel Directory Controller, ma in nessuna cache. Ciò è stato necessario al fine di preservare l'inclusività. Ne derivano altri due stati transienti $ MN^{A} $ e $ NS^{D} $: il primo è dovuto ad una operazione di replacement, mentre il secondo deriva dall'ottenimento del dato dalla memoria centrale a seguito della richiesta da parte di un Cache Controller.

Così come si può evincere nel codice del protocollo adottato, negli eventi di replacement le linee di cache non vengono invalidate: questo perchè, come detto precedentemente, l'operazione di replacement sostituisce subito la vecchia linea di cache con la nuova, evitando di passare attraverso la procedura di invalidazione della entry sovrascritta (quindi un'evenutale invalidazione invaliderebbe erroneamente la linea di cache già entrata).

assign do_replacement = dc2_message_valid && update_cache && !dc2_message_cache_hit && dc2_message_cache_valid;
assign dc3_replacement_enqueue   = dc2_message_valid && do_replacement;

Generazione dei messaggi di uscita

I messaggi che possono essere generati possono essere di forward request o di response: quando e come generare tali messaggi è definito dal protocollo di coerenza.