Associative simulazione della cache - Trattare con uno schema difettosa

Question

Mentre si lavora su simulazione di una cache completamente associativa (in MIPS montaggio), un paio di domande è venuto in mente sulla base di alcune informazioni leggere on-line;

Secondo alcune note della University of Maryland

  

Trovare uno slot: Al massimo, uno slot deve corrispondere. Se   v'è più di uno slot che   le partite, allora avete un guasto   schema di cache completamente associativa. voi   non dovrebbe mai avere più di una copia   della linea di cache in qualsiasi slot di un   Cache completamente associativa. È difficile   mantenere più copie, e non lo fa   ha senso. Gli slot possono essere usati   per le altre linee di cache.

Questo significa che dovrei controllare tutto il tempo la lista completa di tag al fine di verificare la presenza di una seconda partita? Dopo tutto, se non lo faccio, non sarò mai "realizzare" circa il guasto con la cache, tuttavia, controllando ogni singola volta sembra abbastanza inefficiente.

Nel caso che faccio di controllo, e in qualche modo riesco a trovare una seconda partita, il che significa schema di cache difettoso, che cosa devo fare allora? Anche se la risposta migliore sarebbe quella di fissare la mia realizzazione, ma Sono interessato su come gestire la cosa durante l'esecuzione se questa situazione dovrebbe sorgere.

Answer 1

Se più di uno slot valido corrisponde a un indirizzo, allora che significa che quando è stata eseguita una ricerca precedente per lo stesso indirizzo, uno slot valida che avrebbe dovuto abbinato l'indirizzo non è stato utilizzato (forse perché non è stata verificata nel primo luogo) o più di uno slot valido è stato utilizzato per memorizzare la linea che non era nella cache affatto.

Senza dubbio, questo dovrebbe essere considerato un bug.

Ma se abbiamo appena deciso di non risolvere il bug (forse preferiamo non commettere più di tanto hardware per una migliore attuazione) l'opzione più ovvia è quello di scegliere uno degli slot di invalidare. Sarà quindi disponibile per le altre linee di cache.

Per quanto riguarda come scegliere quali uno di invalidare, se una delle linee duplicate è pulito, invalidate che uno a preferenza di una linea di cache sporca. Se più di linea di cache è sporco e non sono d'accordo si dispone di un ancora più grande bug fix, ma in ogni caso la cache non è sincronizzata e probabilmente non importa quale si sceglie.

Edit: ecco come potrei implementare hardware per fare questo:

Prima di tutto, non fa un sacco di senso per Avvia con l'assunzione di duplicati, piuttosto lavoreremo in giro che al momento opportuno in seguito. Ci sono poche possibilità di ciò che deve accadere quando la memorizzazione nella cache di una nuova linea.

• La linea è già nella cache, non è necessaria alcuna azione
• La linea non è nella cache, ma ci sono slot disponibili non validi: Posizionare la nuova linea in uno degli slot disponibili
• La linea non è nella cache, ma non ci sono slot disponibili non validi. Un'altra linea valida deve essere sfrattato e la nuova linea prende il suo posto.
  
  • Scegliere un candidato sfratto ha conseguenze prestazioni. linee di cache pulita può essere sfrattati per libero, ma se scelto male, può causare un altro cache miss in un prossimo futuro. Considerate se tutti tranne uno linea di cache è sporco. Se solo la linea di cache pulita viene sfrattato, allora molti letture sequenziali alternanza tra due indirizzi causerà un cache miss su ogni lettura. invalidazione della cache è tra i due dure problemi Comp Sci (l'altro è 'nominare le cose') e fuori dalla portata di questa domanda esatta.

I probabilmente implementare una ricerca che verifica la presenza di slot corretto di agire su per ciascuno di essi. Poi un altro blocco avrebbe scelto la prima da quella lista e agire su di esso.

Ora, tornando alla domanda. Quali sono le condizioni in cui i duplicati potrebbe eventualmente entrare nella cache. Se gli accessi di memoria sono rigorosamente ordinati, e l'implementazione (come sopra) è corretto, non credo che i duplicati sono possibili a tutti. E così non c'è bisogno di controllare per loro.

Ora lascia prendere in considerazione un caso più plausibile in cui un singolo cache è condiviso tra due core della CPU. Stiamo andando a fare proprio la cosa più semplice che potrebbe funzionare e duplicato tutto tranne la stessa memoria cache per ogni core. Così lo slot ricerca hardware è non condiviso. A sostegno di questa, un po 'in più per ogni slot è usato come un mutex. ricerca hardware non può utilizzare uno slot che è bloccata dal altro core. in particolare,

• Se l'indirizzo è nella cache, cercare di bloccare la fessura e restituire quello slot. Se lo slot è già bloccato, stallo fino a quando non è libero.
• Se l'indirizzo non è nella cache, trovare una sbloccato di slot che non è valido o valido, ma evictable.

in questo caso si può effettivamente finire in una posizione in cui due slot condividono lo stesso indirizzo. Se entrambi i core tentano di scrivere in un indirizzo che non è nella cache, finiranno per ottenere slot diversi, e si verificherà una linea duplicata. Prima lascia pensare a quello che potrebbe accadere:

• Entrambe le linee sono stati legge dalla memoria principale. Saranno lo stesso valore e saranno entrambi essere pulito. È giusto sfrattare sia.
• Entrambe le linee erano scrive. Entrambi saranno sporca, ma probabilmentenon essere uguali. Si tratta di una condizione di competizione che avrebbe dovuto essere risolto con l'applicazione mediante l'emissione di recinzioni di memoria o altre istruzioni di ordinazione di memoria. Non possiamo indovinare quale dovrebbe essere utilizzato, se non ci fosse la cache la condizione di competizione si manterrà nella RAM. È giusto sfrattare sia.
• Una linea era una lettura e uno era una scrittura. La scrittura è sporco, ma la lettura è pulito. Ancora una volta, questa condizione di gara sarebbe persistito nella RAM se non ci fosse la cache intervenire, ma il lettore potrebbe aver visto un valore diverso. sfrattando la linea pulita è giusto per la RAM, e ha anche l'effetto collaterale di favorire sempre leggere ordinazione poi scrivere.

Così ora sappiamo che cosa fare al riguardo, ma da dove viene questa logica appartengono. In primo luogo permette di pensare a cosa potrebbe accadere se non facciamo nulla. Un successivo accesso cache per lo stesso indirizzo su entrambi i campioni possano ritornare entrambe le linee. Anche se né nucleo emette scrive, legge potrebbe tenere venire differente, alternando tra i due valori. Questo rompe ogni idea immaginabile su ordinazione di memoria.

una soluzione potrebbe essere semplicemente dire che le linee sporchi appartengono ad un nucleo solo, la linea non è sporco, ma sporco e proprietà di un altro nucleo.

• Nel caso di due letture simultanee, entrambe le linee sono identiche, sbloccato e intercambiabili. Non importa quale linea un'anima ottiene per le operazioni successive.
• nel caso di scritture contemporanee, entrambe le linee non sono sincronizzati, ma reciprocamente invisibile. Anche se la condizione di competizione che si crea è un peccato, è ancora porta ad un ordinamento di memoria ragionevole, come se tutte le operazioni che avvengono sulla linea scartata successo prima una delle operazioni sulla linea pulita.
• Se una lettura e una scrittura avvengono in concomitanza, la linea sporca è invisibile al nucleo lettura. Tuttavia, la linea pulita è visibile ad entrambi i core e causerebbe memoria ordinamento abbattere per lo scrittore. scrive futuri potrebbero anche causare a bloccare entrambi (perché entrambi sarebbe sporco).

Questo ultimo caso praticamente milita che le linee sporchi essere preferiti a quelli puliti. Questo forze almeno alcuni hardware aggiuntivo per cercare linee sporchi prime e le linee pulite solo se non sono stati trovati linee sporchi. Così ora abbiamo una nuova implementazione della cache concorrente:

• Se l'indirizzo è nella cache e sporco e di proprietà del nucleo richiedente, usare quello slot
• se l'indirizzo è nella cache ma pulito
  • per legge, basta usare quello slot
  • in scrittura, contrassegnare lo slot come sporco e utilizzare lo slot
• Se l'indirizzo non è nella cache e ci sono gli slot non validi, utilizzare uno slot non valida
• se non ci sono slot non validi, sfrattare una linea e l'uso che di slot.

Ci stiamo avvicinando, c'è ancora un buco nella sua attuazione. Che cosa succede se entrambi i core accedono allo stesso indirizzo, ma non contemporaneamente . La cosa più semplice è probabilmente da dire solo che le linee sono davvero sporchi invisibile agli altri nuclei. Nella cache ma sporco è lo stesso che non essendo nella cache affatto.

Ora tutto quello che dobbiamo pensare è che effettivamente fornisce lo strumento per le applicazioni da sincronizzare. Probabilmente farei uno strumento che svuota solo in modo esplicito una linea se è sporco. Questo sarebbe solo richiamare lo stesso hardware che viene utilizzato durante sfratto, ma segna la linea pulita invece di valido.

Per fare una lunga breve post, l'idea è di trattare con i duplicati non rimuovendoli, ma facendo in modo che non possono portare a ulteriori problemi di ordinazione di memoria, e lasciando il lavoro di deduplicazione per l'applicazione o eventuale sfratto.