Coerenza e sincronizzazione della cache

In questo capitolo, discuteremo i protocolli di coerenza della cache per far fronte ai problemi di incoerenza multicache.

Il problema della coerenza della cache

In un sistema multiprocessore, può verificarsi incoerenza dei dati tra livelli adiacenti o all'interno dello stesso livello della gerarchia di memoria. Ad esempio, la cache e la memoria principale potrebbero avere copie incoerenti dello stesso oggetto.

Poiché più processori operano in parallelo e in modo indipendente più cache possono possedere copie diverse dello stesso blocco di memoria, ciò crea cache coherence problem. Cache coherence schemes aiuta a evitare questo problema mantenendo uno stato uniforme per ogni blocco di dati memorizzato nella cache.

Sia X un elemento di dati condivisi a cui fanno riferimento due processori, P1 e P2. All'inizio, tre copie di X sono coerenti. Se il processore P1 scrive un nuovo dato X1 nella cache, utilizzandowrite-through policy, la stessa copia verrà scritta immediatamente nella memoria condivisa. In questo caso, si verifica un'incoerenza tra la memoria cache e la memoria principale. Quando unwrite-back policy viene utilizzato, la memoria principale verrà aggiornata quando i dati modificati nella cache vengono sostituiti o invalidati.

In generale, ci sono tre fonti di problemi di incoerenza:

  • Condivisione di dati scrivibili
  • Migrazione dei processi
  • Attività di I / O

Protocolli Snoopy Bus

I protocolli Snoopy raggiungono la coerenza dei dati tra la memoria cache e la memoria condivisa attraverso un sistema di memoria basato su bus. Write-invalidate e write-update i criteri vengono utilizzati per mantenere la coerenza della cache.

In questo caso, abbiamo tre processori P1, P2 e P3 che hanno una copia coerente dell'elemento di dati "X" nella loro memoria cache locale e nella memoria condivisa (Figura-a). Il processore P1 scrive X1 nella sua memoria cache usandowrite-invalidate protocol. Quindi, tutte le altre copie vengono invalidate tramite il bus. È indicato con "I" (Figura-b). I blocchi non convalidati sono noti anche comedirty, cioè non dovrebbero essere usati. Ilwrite-update protocolaggiorna tutte le copie della cache tramite il bus. Usandowrite back cache, viene aggiornata anche la copia in memoria (Figura-c).

Eventi e azioni nella cache

I seguenti eventi e azioni si verificano sull'esecuzione di comandi di accesso alla memoria e di invalidamento:

  • Read-miss- Quando un processore vuole leggere un blocco e non è nella cache, si verifica un errore di lettura. Questo avvia unbus-readoperazione. Se non esiste alcuna copia sporca, la memoria principale che dispone di una copia coerente fornisce una copia alla memoria cache richiedente. Se una copia sporca esiste in una memoria cache remota, tale cache limiterà la memoria principale e invierà una copia alla memoria cache richiedente. In entrambi i casi, la copia cache entrerà nello stato valido dopo una lettura mancata.

  • Write-hit - Se la copia è sporca o reservedstato, la scrittura viene eseguita localmente e il nuovo stato è sporco. Se il nuovo stato è valido, il comando write-invalidate viene trasmesso a tutte le cache, invalidandone le copie. Quando la memoria condivisa viene scritta, lo stato risultante viene riservato dopo questa prima scrittura.

  • Write-miss- Se un processore non riesce a scrivere nella memoria cache locale, la copia deve provenire dalla memoria principale o da una memoria cache remota con un blocco sporco. Questo viene fatto inviando unread-invalidatecomando, che invaliderà tutte le copie della cache. Quindi la copia locale viene aggiornata con uno stato sporco.

  • Read-hit - Il read-hit viene sempre eseguito nella memoria cache locale senza causare una transizione di stato o utilizzare il bus snoopy per l'invalidazione.

  • Block replacement- Quando una copia è sporca, deve essere riscritta nella memoria principale con il metodo di sostituzione dei blocchi. Tuttavia, quando la copia è in uno stato valido, riservato o non valido, non avrà luogo alcuna sostituzione.

Protocolli basati su directory

Utilizzando una rete multistadio per costruire un multiprocessore di grandi dimensioni con centinaia di processori, i protocolli di cache snoopy devono essere modificati per adattarsi alle capacità di rete. Essendo la trasmissione molto costosa da eseguire in una rete multistadio, i comandi di coerenza vengono inviati solo a quelle cache che conservano una copia del blocco. Questo è il motivo per lo sviluppo di protocolli basati su directory per multiprocessori connessi alla rete.

In un sistema di protocolli basato su directory, i dati da condividere vengono inseriti in una directory comune che mantiene la coerenza tra le cache. Qui, la directory funge da filtro in cui i processori chiedono il permesso di caricare una voce dalla memoria primaria alla sua memoria cache. Se una voce viene modificata, la directory la aggiorna o invalida le altre cache con quella voce.

Meccanismi di sincronizzazione hardware

La sincronizzazione è una forma speciale di comunicazione in cui invece del controllo dei dati, le informazioni vengono scambiate tra processi di comunicazione che risiedono nello stesso o in diversi processori.

I sistemi multiprocessore utilizzano meccanismi hardware per implementare operazioni di sincronizzazione di basso livello. La maggior parte dei multiprocessori ha meccanismi hardware per imporre operazioni atomiche come operazioni di lettura, scrittura o lettura-modifica-scrittura della memoria per implementare alcune primitive di sincronizzazione. Oltre alle operazioni di memoria atomica, alcuni interrupt tra processori vengono utilizzati anche per scopi di sincronizzazione.

Coerenza della cache nelle macchine con memoria condivisa

Il mantenimento della coerenza della cache è un problema nel sistema multiprocessore quando i processori contengono memoria cache locale. L'incongruenza dei dati tra le diverse cache si verifica facilmente in questo sistema.

Le principali aree di preoccupazione sono:

  • Condivisione di dati scrivibili
  • Migrazione dei processi
  • Attività di I / O

Condivisione di dati scrivibili

Quando due processori (P1 e P2) hanno lo stesso elemento dati (X) nelle loro cache locali e un processo (P1) scrive nell'elemento dati (X), poiché le cache sono cache locale di scrittura di P1, la memoria principale è anche aggiornato. Ora, quando P2 prova a leggere l'elemento dati (X), non trova X perché l'elemento dati nella cache di P2 è diventato obsoleto.

Migrazione dei processi

Nella prima fase, la cache di P1 ha l'elemento dati X, mentre P2 non ha nulla. Un processo su P2 scrive prima su X e poi migra a P1. Ora, il processo inizia a leggere l'elemento di dati X, ma poiché il processore P1 ha dati obsoleti, il processo non può leggerli. Quindi, un processo su P1 scrive nell'elemento dati X e quindi migra su P2. Dopo la migrazione, un processo su P2 inizia a leggere l'elemento di dati X ma trova una versione obsoleta di X nella memoria principale.

Attività di I / O

Come illustrato nella figura, un dispositivo I / O viene aggiunto al bus in un'architettura multiprocessore a due processori. All'inizio, entrambe le cache contengono l'elemento dati X. Quando il dispositivo I / O riceve un nuovo elemento X, memorizza il nuovo elemento direttamente nella memoria principale. Ora, quando P1 o P2 (supponiamo P1) tentano di leggere l'elemento X, ottiene una copia obsoleta. Quindi, P1 scrive sull'elemento X. Ora, se il dispositivo I / O tenta di trasmettere X, ottiene una copia obsoleta.

Accesso alla memoria uniforme (UMA)

L'architettura Uniform Memory Access (UMA) significa che la memoria condivisa è la stessa per tutti i processori nel sistema. Classi popolari di macchine UMA, comunemente utilizzate per (file) server, sono i cosiddetti Symmetric Multiprocessors (SMP). In un SMP, tutte le risorse di sistema come memoria, dischi, altri dispositivi I / O, ecc. Sono accessibili dai processori in modo uniforme.

Accesso alla memoria non uniforme (NUMA)

Nell'architettura NUMA, ci sono più cluster SMP con una rete interna indiretta / condivisa, che sono collegati in una rete di passaggio di messaggi scalabile. Quindi, l'architettura NUMA è un'architettura di memoria distribuita fisicamente condivisa logicamente.

In una macchina NUMA, il controller della cache di un processore determina se un riferimento alla memoria è locale alla memoria di SMP o è remoto. Per ridurre il numero di accessi alla memoria remota, le architetture NUMA di solito applicano processori di memorizzazione nella cache che possono memorizzare nella cache i dati remoti. Ma quando sono coinvolte le cache, è necessario mantenere la coerenza della cache. Quindi questi sistemi sono noti anche come CC-NUMA (Cache Coherent NUMA).

Cache Only Memory Architecture (COMA)

Le macchine COMA sono simili alle macchine NUMA, con l'unica differenza che le memorie principali delle macchine COMA agiscono come cache a mappatura diretta o set-associative. I blocchi di dati vengono sottoposti ad hashing in una posizione nella cache DRAM in base ai loro indirizzi. I dati che vengono recuperati in remoto vengono effettivamente archiviati nella memoria principale locale. Inoltre, i blocchi di dati non hanno una posizione di casa fissa, possono muoversi liberamente in tutto il sistema.

Le architetture COMA hanno principalmente una rete di passaggio di messaggi gerarchica. Uno switch in un tale albero contiene una directory con elementi di dati come sottoalbero. Poiché i dati non hanno una posizione home, devono essere cercati esplicitamente. Ciò significa che un accesso remoto richiede un attraversamento lungo gli switch nell'albero per cercare i dati richiesti nelle loro directory. Quindi, se uno switch nella rete riceve più richieste dalla sua sottostruttura per gli stessi dati, le combina in una singola richiesta che viene inviata al genitore dello switch. Quando i dati richiesti vengono restituiti, lo switch ne invia più copie nella sua sottostruttura.

COMA contro CC-NUMA

Di seguito sono riportate le differenze tra COMA e CC-NUMA.

  • COMA tende ad essere più flessibile di CC-NUMA perché COMA supporta in modo trasparente la migrazione e la replica dei dati senza la necessità del sistema operativo.

  • Le macchine COMA sono costose e complesse da costruire perché richiedono hardware di gestione della memoria non standard e il protocollo di coerenza è più difficile da implementare.

  • Gli accessi remoti in COMA sono spesso più lenti di quelli in CC-NUMA poiché la rete ad albero deve essere attraversata per trovare i dati.