Difference between revisions of "L1 Cache Controller"

Revision as of 18:49, 20 September 2017

Il cache controller è composto da 4 stage, di cui 3 registrati. Prima di descrivere nel dettaglio i componenti, introduciamo la dinamica generale degli elementi.

• Stage 1. Lo scopo principale è quello di poter schedulare una tra le richieste provenienti dal core (es. cache miss) e dalla rete (es. frwd request). La scelta dell'arbitro è basata principalmente sulla presenza di un'altra richiesta nel controllore, sulla disponibilità della rete a trasmettere e sulla disponibilità del protocollo a processare il messaggio. Quest'ultimo implica la necessità di dover esaminare lo stato delle transazioni pendenti del controllore.
• Stage 2. Principalmente contiene il registro delle transazioni pendenti dal core (MSHR), il quale viene interrogato tramite una lookup table dall'arbitro nello stadio precedente altresì viene modificato dallo stadio successivo seguendo l'evoluzione del protocollo. Inoltre contiene una memoria per conservare lo stato di ogni singola linea di cache.
• Stage 3. E' sicuramente lo stadio più complesso perchè quì viene interrogato il protocollo, che sulla base della richiesta schedulata e dello stato corrente della richiesta, genera tutti i segnali per poter determinare lo stato successivo della richiesta (modificando l'MSHR), del dato in cache (modificando lo stato ed il dato nella cache L1 del datapath) e di eventuali messaggi da inviare sulla rete.
• Stage 4. E' lo stato più semplice perchè ha lo scopo di dover impacchettare eventuali messaggi da inviare sulla rete da parte del controllore. Tale stadio non è registrato e comunica direttamente con la network interface.

Come si può notare, il protocollo è interrogato sia nel primo stadio che nel terzo, quindi verrà considerato come un elemento trasversale e sarà descritto a parte.

Prima descrivere gli stage nel dettaglio, si riportano gli assunti basilari per comprendere ed introdurre le scelte architetturali:

• Il cache controller può evadere un'altra richiesta sullo stesso indirizzo solo se la precedente è uscita dal controllore

%\item When a request is issued (both from NI or CI), it can modify an MSHR entry after two clock cycles, hence the next request may read a non up to date entry. In order to avoid this, the \texttt{Fetch Unit} does not schedule two consecutive requests on the same address.

• Le transazioni coinvolgono sempre blocchi di memoria.
• Non è possibile gestire due richieste che operano sullo stesso set.

% perchè se generano più di un replacement, abbiamo più di una richiesta per core?

• Solo le richieste del core possono istanziare un valore nell'MSHR, di preciso le load, le store e le writeback.
• gli stati sono salvati in cache solo se stabili , altrimenti si trovano nell'MSHR

Stadio 1

Tale stadio deve poter schedulare una delle seguenti richieste: load miss, store miss, flush e writeback da parte del core; forwarded request e response da parte della rete per un totale di sei richieste da schedulare. Tali richieste vengono presentate al cache controller dalla core interface e dalla network interface, rispettivamente. Finchè non viene schedulata una richiesta, essa rimane sempre pendente all'ingresso dello stadio, quindi rimane bufferizzata in tali interfacce e rimossa dal buffer quando viene scelta. Si vuole ricordare che la richiesta di writeback include anche le richieste di eviction. Infatti le richieste di writeback sono inviate al memory controller per effettuare una scrittura di una linea di cache, quindi per la memoria hanno lo stesso effetto di una eviction. Per quasi tutte le richieste le condizioni che possono impedire la schedulazione di una richiesta da parte dell'arbitro sono le seguenti:

• un'altra richiesta di qualsiasi tipo per lo stesso indirizzo è attualmente servita nella pipe del controllore
• c'è una richiesta di qualsiasi tipo pendente nell'MSHR per quell'indirizzo
• la rete non è disponibile ad inviare un pacchetto di quel tipo
• il protocollo indica uno stallo della richiesta ( a parte la richiesta di response)

assign can_issue_load  = ci_load_request_valid && 
// 2a condizione
( !load_mshr_hit ||
// 4a condizione
( load_mshr_hit  && !load_mshr.valid) ||( load_mshr_hit && load_mshr.valid && !stall_load ) ) &&
!( // 1a condizione
   ( cc2_pending_valid && ( ci_load_request_address.index == cc2_pending_address.index ) ) || 
   ( cc3_pending_valid && ( ci_load_request_address.index == cc3_pending_address.index ) )
// 3a condizione
) & ni_request_network_available;

La seconda condizione implica un duplice controllo: che non sia eseguito un hit oppure che ci sia un hit, ma che il valore restituito non sia anche valido. Infatti una entry può scatenare una hit anche se non è valida e può essere valida anche senza eseguire hit. Si nota che non si esegue un controllo sull'issueing della richiesta sulla base degli slot liberi nell'MSHR. Infatti, ipotizzando che solo le richieste del core possono istanziare uno slot nell'MSHR e solo una richiesta per volta per ogni thread può essere eseguia, allora basta dimensionare le entry nell'MSHR pari al numero di thread affinchè tale controllo diventi superfluo. Le richieste di flush non istanziano un elemento nell'MSHR perchè non devono mai attendere risposte ai messaggi inviati in risposta alla loro esecuzione. Da notare che la richiesta di writeback può avanzare anche se c'è già una richiesta pendente nell'MSHR, ma è uno slot preallocato per eseguire un eviction di un blocco (vai alla sezione Caso d'uso eviction) al fine di essere sicuri di poterla sempre eseguire \textbf{prima di ogni altra richiesta su quell'indirizzo}.

// aggiunta della condizione nella writeback
( writeback_mshr_hit && writeback_mshr.waiting_for_eviction || 
!stall_writeback && writeback_mshr_hit)

Il protocollo prende la decisione di poter stallare una richiesta in ingresso sulla base dello stato delle richieste dello stesso indirizzo pendenti nell'MSHR, così come dichiarato nella seconda condizione. Questo implica, prima di tutto, che bisogna eseguire un controllo su tutti gli slot dell'MSHR, anche relativi a thread differenti, per tutte le sei richieste pendenti tramite sei differenti lookup table. Ciò significa che riceve in ingresso l'entry MSHR dallo stadio successivo per poter controllare lo stato corrente della transazione pendente, immettendo in uscita il tag ed il set di tutte le richieste in ingresso. Tutto avviene in maniera combinatoriale e la decisione viene presa nello stesso ciclo.

// esempio per la load
assign cc1_mshr_lookup_tag[MSHR_LOOKUP_PORT_LOAD ]  = ci_load_request_address.tag;
assign cc1_mshr_lookup_set[MSHR_LOOKUP_PORT_LOAD ]  = ci_load_request_address.index;
assign load_mshr = cc2_mshr_lookup_entry_info[MSHR_LOOKUP_PORT_LOAD];
stall_protocol_rom load_stall_protocol_rom (
   .current_request ( load            ),
   .current_state   ( load_mshr.state ),
   .pr_output_stall ( stall_load      )
);

Definite tutte le componenti in ingresso, adesso l'arbitro è capace di eseguire lo scheduling di una richiesta. Tale arbitro è di tipo fixed-priority e schedula le richieste con la seguente priorità decrescente: flush, writeback, store, response, forwarded request, load. Dalle considerazioni fatte precedentemente, è chiaro che la flush e la writeback hanno una priorità maggiore rispetto alle altre richieste al fine di poter dare alle richieste degli altri thread il dato che non sia vecchio.

L'uscita di tale stadio è registrata e porta allo stadio successivo la richiesta schedulata comprensiva della entry MSHR scelta.

Stadio 2

Il secondo stadio non ha una logica complessa, ma contiene elementi fondamentali del controllore: un blocco di hit/miss detection, l'MSHR, la memoria degli stati dei blocchi in cache L1 ed una pseudo LRU. Il flusso di esecuzione principale parte dalle uscite registrate dello stadio precedente (nel codice le si posson notare con segnali che iniziano con ``cc1_request ) che passano parallelamente al blocco di hit/miss detection, la memoria degli stati dei blocchi in cache L1 e la pseudo LRU. Il blocco di hit/miss detection riceve contemporaneamente il tag proveniente dalla richiesta schedulata dal controllore ed il tag proveniente dalla cache L1 - assieme ad i privilegi associati - al fine di poter eseguire nuovamente il check sull'hit/miss del blocco in cache. È nuovamente rieseguito perchè una richiesta inviata dal core può essere schedulata dopo altre richieste dal controllore che possono comportare una modifica della cache stessa. La memoria degli stati dei blocchi della L1 è acceduta dalle uscite dello stadio precedente solo in lettura al fine di poter prelevare gli stati di un determinato set. Non è ancora fatta la scelta della way da prelevare, ma è eseguita nello stadio successivo. La pseudo LRU riceve una richiesta di lettura della way meno utilizzata da parte delle uscite registrate del primo stadio. Inoltre riceve direttamente dalla load store unit l'ultima way utilizzata per un set al fine di poterla spostare come way più utilizzata.

Ci sono inoltre altri due flussi secondari, ma non meno importanti, che non utilizzano le uscite registrate. Il primo è l'accesso alla MSHR in lettura. Tale accesso avviene ricevendo combinatorialmente gli ingressi dallo stadio precedente di tutte le richieste pendenti in ingresso (segnali cc1_mshr_lookup_tag/_index) al fine di poter leggere - tramite una lookup table - le MSHR entry per ogni richiesta. Tali entry sono inviate combinatorialmente allo stadio precedente e vengono utilizzate per poter scegliere la richiesta da schedulare. Il secondo è l'accesso in scrittua per modificare l'MSHR (segnali cc3\_update\_mshr\_xxx) e gli stati della cache L1 (segnali cc3_update_coherence_state_xxx). Tali segnali provengono combinatorialmente dallo stadio successivo e determinati sulla base dell'evoluzione del protocollo di coerenza.

MSHR

Il Miss Status Handling Register contiene informazioni relative a tutte le richieste di miss sollevate dal core che non sono ancora state definitivamente evase. Così come detto precedentemente, tale MSHR ha un numero di entry pari al numero di thread in quanto solo una richiesta alla volta può essere eseguita per thread. L'MSHR deve poter fornire le informazioni in maniera combinatoriale a chi lo interroga e deve poter fornire anche un modo per poter modificare la struttura delle entry. Per questo motivo, la struttura dell'MSHR può essere suddivisa in una parte di lettura e in una di scrittura delle entry. La parte di lettura dell'MSHR deve poter fornire tali informazioni agli altri stadi in maniera combinatoriale. Quindi, anche se non è tipico di una MSHR standard, le informazioni lette sono prelevate tramite una lookup table. Una entry della MSHR contiene le segueni informazioni: \begin{table}[h] \centering \begin{tabular}{ | l | l | l | l | l | l | l | l |} \hline Valid & State & Address & Thread Id & Data & Ack Count & Waiting For Eviction & Wakeup Thread \\ \hline \end{tabular} \caption{Tabella MSHR} \label{tab:mshr} \end{table}

• Valid: indica se la entry è utilizzata o meno
• State: raccoglie lo stato attuale della richiesta relativo al protocollo di coerenza, usato sia per poter
• Address: indirizzo di memoria a cui si riferisce la richiesta
• Thread ID: id del thread che ha sollevato la richiesta
• Data: dati che accompagnano la richiesta
• Ack count: numero di ack che la richiesta deve ancora ricevere
• Waiting for eviction: asserito se sull'indirizzo della richiesta deve essere eseguita una eviction ed ha senso solo se è asserito anche il bit di valid.
• Wakeup Thread : determina se il thread dovrà essere risvegliato al termine della transazione

Di seguito è riportato il punto in cui viene eseguita la lettura della entry. Tale lettura viene ulteriormente replicata per ogni lookup port (nel nostro caso sei).

generate

for ( i = 0; i < `MSHR_SIZE; i++ ) begin : lookup_logic assign hit_map[i] = /*( mshr_entries[i].address.tag == tag ) &&*/ ( mshr_entries[i].address.index == index ) && mshr_entries[i].valid;

end
endgenerate
oh_to_idx #(

.NUM_SIGNALS( `MSHR_SIZE )) u_oh_to_idx ( .index ( selected_index ), .one_hot( hit_map )

);
assign mshr_entry = mshr_entries[selected_index];

Supponendo che l'MSHR sia di tipo read-first, per ogni entry viene effettuato il controllo sull'address: se c'è una richiesta già pendente valida, allora viene asserito il bit nella hit map, al quale invierà la corrispondente entry in uscita.

Per quanto riguarda la parte di scrittura, viene specifcato qual è l'id della entry da aggiornare con le informazioni da inserire. Supponendo sia read-first, le informazioni aggiornate saranno disponibili il colpo di clock successivo all'aggiornamento. Infine si vuol notare che nell'MSHR sono stati separati i dati della entry dalle altre informazioni per poter evitare di appesantire il processo di lookup dato che non servirebbero ai fini delle decisioni dello scheduling. Tali dati sono messi nel banco di memoria "mshr_data_sram".

Stadio 3

Il terzo stadio è sicuramente il più complesso perchè contiene il protocollo di coerenza e tutte le azioni che bisogna eseguire in seguito. Il cuore dello stadio è sicuramente il modulo ROM, il quale calcola le azioni da compiere sulla base dello stato corrente e della richiesta in ingresso schedulata. Le azioni e le uscite sono descritte dettagliatamente nella sottosezione apposita. Prima di tutto, bisogna inserire correttamente i dati di ingresso all'interno della ROM. Se la richiesta è stata già schedulata nel primo stadio, lo stato corrente deve essere ancora scelto. Infati, la scelta si basa su due situazioni, cioè se c'è una richiesta pendente nell'MSHR (cc2_request_mshr_hit) o se c'è un dato già presente in cache. Nel primo caso, lo stato da considerare è quello salvato nell'MSHR entry e precedentemente prelevato; nel secondo caso, bisogna invece considerare lo stato del dato in cache - salvato nell'apposito modulo di memoria dello stadio 2; nel caso in cui nessuno dei due casi si realizzasse, allora significa che tale blocco non è stato mai letto o modificato, quindi lo si pu considerare nello stato di partenza (Invalid nel nostro caso). Selezionato lo stato, si può procedere a prelevare le uscite della ROM, contenute nella struttura "pr_output". Sulla base delle uscite della ROM, è possibile identificare 4 diverse macro-uscite: valutazione di un replacement, aggiornamento dell'MSHR, aggiornamento della linea di cache (con il suo stato) e definizione del messaggio di uscita. Tali azioni sono descritte nelle apposite sottosezioni. Si vuole ricordare che le azioni di modifica ai dati salvati nel cache controller avvengono dopo due cicli dallo scheduling di una richiesta. Per evitare problemi di errato aggiornamento, si bloccano tutte le richieste verso indirizzi che sono ancora nella pipe del controllore.

Valutazione di un replacement

Il replacement è l'operazione che si scatena quando deve essere istanziato un nuovo dato in cache, ma non c'è più spazio in quel set. Questo implica salvare il nuovo dato nella cache ed inviare il vecchio dato in cache ai livelli superiori di memoria (solo se è stato modificato). I segnali calcolati in questo punto non vengono direttamente portati in uscita, ma sono utilizzate per poter determinare le altre macro-uscite corretamente. Bisogna quindi sofferamrsi su tali segnali:

replaced_way_valid = cc2_request_snoop_privileges[cc2_request_lru_way_idx].can_read |
 cc2_request_snoop_privileges[cc2_request_lru_way_idx].can_write;
do_replacement = pr_output.write_data_on_cache &&
 !cc2_request_snoop_hit && replaced_way_valid;

Dallo stadio 2 precedente riceviamo la way uscente (cc2_request_lru_way_idx) e vediamo se il blocco è ancora valido - cioè se è possibile almeno leggere o scrivere. In questo caso, allora bisogna vedere se il protocollo ha disposto una scrittura in cache. E' evidente che bisogna anche controllare se c'è stato un hit o meno in cache, altrimenti non bisogna eseguire un replace, bensì un update dei dati.

Aggiornamento MSHR entry

L'aggiornamento di una entry MSHR dipende sia dai segnali direttamente presi dalla ROM sia de un'eventuale replacement da effettuare. Nel caso in cui bisogna eseguire un replacement, bisogna prima ricordare cosa accade al datapath. Alla ricezione della richiesta di replacement, il datapath invierà una richiesta di eviction per quel dato.

da fare % Il problema può sorgere se un'altra richiesta dello stesso thread è sospesa su

Per questo motivo, viene preallocata la entry, ponendo tutte le informazioni ai fini del replace nella entry, e settando sia i bit di validità che di waiting_for_eviction. Nel caso in cui non bisogna eseguire il replacement, allora si aggiornerà l'entry MSHR nei seguenti modi e casi:

always_comb begin

cc3_update_mshr_en = 1'b0; cc3_update_mshr_entry_info.valid = ( pr_output.allocate_mshr_entry || pr_output.update_mshr_entry ) && !pr_output.deallocate_mshr_entry; cc3_update_mshr_entry_info.address = cc2_request_address; cc3_update_mshr_entry_info.state = pr_output.next_state; cc3_update_mshr_entry_info.thread_id = cc2_request_mshr_hit ? cc2_request_mshr_entry_info.thread_id  : cc2_request_thread_id; cc3_update_mshr_entry_info.ack_count = pr_output.decr_ack_count ? cc2_request_mshr_entry_info.ack_count - 1  : ( pr_output.req_has_ack_count ? cc2_request_sharers_count : cc2_request_mshr_entry_info.ack_count ); cc3_update_mshr_entry_info.waiting_for_eviction = 1'b0; cc3_update_mshr_entry_info.wakeup_thread = cc2_request_mshr_hit ? cc2_request_mshr_entry_info.wakeup_thread  : ( cc2_request == load || cc2_request == store ); cc3_update_mshr_index = cc2_request_mshr_hit ? cc2_request_mshr_index : cc2_request_mshr_empty_index; if ( cc2_request_valid ) cc3_update_mshr_en = ( pr_output.allocate_mshr_entry || pr_output.update_mshr_entry || pr_output.deallocate_mshr_entry );

end

Prima di tutto, si nota che viene scatenato un update nell'MSHR solo se il protocollo ha richiesto espicitamente una sua modifica. Si nota inoltre che una linea sarà invalida sicuramente se il protocollo ha disposto una sua deallocazione. Il calcolo del conteggio degli ack viene eseguito in questo modo: se è stato disposto un decremento, viene decrementato il suo precedente valore, altrimenti si controlla se la richiesta ha un nuovo conteggio da inserire, altrimenti rimane il conteggio inalterato. Una ulteriore nota di attenzione bisogna porla sull'index da calcolare. Infatti se l'entry è già presente nell'MSHR, la richiesta viene arrestata dallo scheduler, a parte per le richieste di writeback, in cui la richiesta avanza se c'è stata una preallocazione. In questo caso, non si può prelevare l'index libero dell'MSHR, ma bensì quello già preallocato e presente nella richiesta stessa(cc2_request_mshr_index).

Aggiornamento della linea di cache e del suo stato

Ogni qual volta viene eseguita una modifica di una linea di cache, che sia per un replacement o meno, bisogna aggiornare sia la linea di cache L1 sia il suo stato di coerenza nel controllore. Per aggiornamento si intende anche una scrittura di una nuova linea di cache. Per aggiornare le linee della L1 si utilizzeranno i segnali "cc3_update_ldst_xxx", mentre si useranno le linee "cc3_update_coherence_state_xxx" per aggiornare lo stato. Vengono analizzate insieme perchè sono logicamente connesse: ogni linea di cache nella L1 ha la propria variabile di stato nel controllore.

assign cc3_update_ldst_command  = do_replacement ? CC_REPLACEMENT :

( pr_output.write_data_on_cache ? CC_UPDATE_INFO_DATA : CC_UPDATE_INFO );

assign cc3_update_ldst_way      = cc2_request_snoop_hit ? cc2_request_snoop_way_idx 
   : cc2_request_lru_way_idx;
assign cc3_update_ldst_address      = cc2_request_address;
assign cc3_update_ldst_store_value = ( pr_output.ack_count_eqz && pr_output.req_has_data ) ?

cc2_request_data : cc2_request_mshr_entry_data;

assign cc3_update_ldst_privileges  = pr_output.next_privileges;
assign cc3_wakeup_thread_id         = cc2_request_mshr_hit ? cc2_request_mshr_entry_info.thread_id
   : cc2_request_thread_id;

assign cc3_update_coherence_state_index = cc2_request_address.index;
assign cc3_update_coherence_state_way   = cc2_request_snoop_hit ? cc2_request_snoop_way_idx 
  : cc2_request_lru_way_idx;
assign cc3_update_coherence_state_entry = pr_output.next_state;

always_comb begin

cc3_update_ldst_valid = 0; cc3_update_coherence_state_en = 0; if ( cc2_request_valid ) begin cc3_update_ldst_valid = ( pr_output.update_privileges && cc2_request_snoop_hit ) || pr_output.write_data_on_cache; cc3_update_coherence_state_en = ( pr_output.next_state_is_stable && cc2_request_snoop_hit ) || ( pr_output.next_state_is_stable && !cc2_request_snoop_hit && pr_output.write_data_on_cache ); end

end

L'aggiornamento della cache L1 viene validato (cc3_update_ldst_valid) ogni qual volta bisogna effettuare una scrittura comandata dalla ROM oppure quando bisogna solo aggiornare i privilegi per una linea già esistente. Si nota che l'aggiornamento è poco restrittivo, perchè viene eseguito ogni volta che bisogna scrivere dati in cache, senza controllare che vi sia un hit o meno, come avvine per il replacement. La differenza sta nel comando da inviare al datapath: nel caso in cui sia sta comandato un replacement(CC_REPLACEMENT), allora si invia un comando che forzerà il datapath ad effettuare la scrittura del dato ed a far uscire la linea sostituita tramite evict. Nel caso di scrittura diretta si invia un altro comando(CC_UPDATE_INFO_DATA), il quale è ulteriormente differente dal comando che consente di poter aggiornare solo i privilegi della linea di cache (CC_UPDATE_INFO). Il controllo bisogna eseguirlo sulla way da aggiornare: se c'è stato un hit nella cache L1, allora bisogna utilizzare la stessa way, altrimenti si può prelevare quella fornita dalla LRU. E' inoltre interessante notare il controllo eseguito sul dato da scrivere in memoria: se il protocollo determina che la richiesta ha un dato e con un numero di ack nullo, allora bisogna scrivere il dato della richiesta, altrimenti quello nella MSHR. Ciò accade, per esempio, quando si ottiene una risposta per una getM e l'ultima risposta è proprio il dato. L'aggiornamento dello stato della linea di cache (cc3_update_coherence_state_en) avviene in due casi: o se c'è stato un hit ed il prossimo stato è stabile, o se non c'è stato hit, ma il prossimo stato è stabile ed ha la necessità di scrivere in cache. E' importante sottolineare il fatto che c'è sempre la condizione di avere un prossimo stato stabile perchè implica il salvataggio dello stato solo se è stabile, altrimenti si troverà lo stato transiente nell'MSHR. La way viene è scelta con lo stesso criterio della linea di cache al fine di essere allineati.

Definizione del messaggio di uscita

Le uniche uscite registrate di tale stadio avvengono solo quando la richiesta in ingresso richiede l'invio di un messaggio da portare al prossimo stadio (e poi alla rete).

always_ff @( posedge clk ) begin

cc3_message_valid <= cc2_request_valid && ( pr_output.send_response || pr_output.send_request ); cc3_message_is_response <= pr_output.send_response; cc3_message_request_type <= pr_output.request; cc3_message_response_type <= pr_output.response; ... cc3_message_has_data <= pr_output.send_data_from_cache || pr_output.send_data_from_mshr || pr_output.send_data_from_request; cc3_message_data <= pr_output.send_data_from_mshr ? cc2_request_mshr_entry_data : cc2_request_data;

end

Modulo ROM protocollo di coerenza

Al fine di poter mantenere uno stato coerente per tutti i dati del sistema, tutti i controllori associati alle strutture di memoria devono eseguire una serie di azioni che prendono il nome di protocollo di coerenza. Ogni protocollo può essere visto come una macchina a stati contraddistinto da una serie di stati stabili e transienti le cui transizioni si innescano da una serie di richieste. Gli stati, le richieste e le azioni compiute dal protocollo di coerenza sono tutte prestabilite e decise a tavolino. Per questo motivo, può essere utile salvare tale protocollo all'interno di una memoria ROM, in modo da ottenere una facilità di progettazione e soprattutto una facile intercambiabilità: se in futuro si vorrà implementare un altro protocollo di coerenza, basterà cambiare i valori della ROM. Gli stati stabili che sono stati definiti sono tre: Modified, Shared e Invalid. Tale protocollo va sotto il nome di MSI ed è il più comune e conosciuto protocollo di coerenza utilizzato. Gli stati transienti servono per accoglier e gestire opportunamente eventuali richieste per la stessa linea di cache mentre si sta transitando da uno stato stabile ad un altro. Le richieste che possono essere fatte sono di tre tipi: Il modulo che contiene l'implementazione del protocollo è composto da un grande costrutto di selezione cobinatoriale, il quale riceve in ingresso lo stato corrente - selezionato opportunamente - e la richiesta schedulata. Le macroazioni da eseguire sono esplicate nella tabella sottostante.

\begin{figure}[t] \centering \includegraphics[scale=0.55]{Images/MSI_CC.pdf} \caption{Descrizione dettagliata del protocollo. } \label{fig:cc_protocol} \end{figure}

Ad ogni richiesta, si attende uno o più ack finchè non si va a zero e si può concludere la transazione (deallocando il valore nell'MSHR e salsando lo sato stabile in cache). Nelle parti in cui non c'è scritto niente, significa che il protocollo non avrà mai l'opportnità di capitare in tale combinazione stato/richiesta. In tale protocollo i comportamenti sono quasi tutti ben conosciuti in letteratura, ma si voglino notare comunque alcune cose:

• Il messaggio di recall viene inviato dal directory controller ed è inteso come un messaggio di back invalidation, cioè il directory controller (il quale è anche il gestore della cache livello 2) invalida una linea di cache del livello sottostante ogni qual volta una linea di cache del livello 2 viene eliminata; ciò viene fatto al fine di poter mantenere la proprietà di inclusività della gerarchia di cache
• il messaggio di writeback viene inviato in risposta ad un messaggio di recall al memory controller per poter effetture la scrittura della linea di cache in memoria centrale
• Tutto ciò implica che un cache controller invierà solo i messaggi di writeback e riceverà solo messaggi di recall (mai il viceversa)
• i messaggi di risposta alla flush sono diversi rispetto a quelli del replacement perchè i messaggi di flush inviano il dato in memoria con una WB e senza cambiare lo stato del dato in cache, mentre il replacement invia i dati alla directory in seguito ad una evict del dato in cache - se necessario - per poter diventare il nuovo owner
• i messaggi di risposta alla flush sono diversi rispetto a quelli del recall perchè, anche se inviano entrambi un messaggio di writeback alla memoria, la flush lo invia solo al memory controller e senza modificare lo stato della cache, mentre la recall invalida il dato in cache ed inoltre invia una WB anche al directory controller. L'invio del WB al directory controller è voluto per poter fornire un ack alla recall.
• i messaggi di WB in risposta alla recall non sono inviati se si trova nello stato S perchè non è l'owner del dato (se ne occuperà il director controller stesso)

Stadio 4

Il quarto stadio può essere considerato un'anticamera della network interface, ed in effetti le sue uscite non sono registrate, ma si immettono direttamente negli ingressi dellla network interface. Tale stadio funge da compositore di pacchetti, utilizzando le informazioni ottenute dallo stadio precedente per inviare correttamente una richiesta/risposta alla rete.