Coerenza e sincronizzazione della cache

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

Il problema della coerenza della cache

In un sistema multiprocessore, l’incoerenza dei dati può verificarsi tra livelli adiacenti o nello stesso livello della gerarchia di memoria. Per esempio, la cache e la memoria principale possono avere copie incoerenti dello stesso oggetto.

Quanto più processori operano in parallelo, e indipendentemente più cache possono possedere copie diverse dello stesso blocco di memoria, questo crea un problema di coerenza della cache. Gli schemi di coerenza della cache aiutano ad evitare questo problema mantenendo uno stato uniforme per ogni blocco di dati nella cache.

Lascia che X sia un elemento di dati condivisi a cui hanno fatto 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, utilizzando la politica write-through, la stessa copia sarà scritta immediatamente nella memoria condivisa. In questo caso, si verifica un’incoerenza tra la memoria cache e la memoria principale. Quando viene usata una politica di write-back, 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 dei dati scrivibili
• Migrazione dei processi
• Attività I/O

Protocolli Bus Snoopy

I protocolli Snoopy raggiungono la coerenza dei dati tra la memoria cache e la memoria condivisa attraverso un sistema di memoria basato sul bus. Le politiche di Write-invalidate e write-update sono usate per mantenere la coerenza della cache.

In questo caso, abbiamo tre processori P1, P2, e P3 che hanno una copia coerente dell’elemento dati ‘X’ nella loro memoria cache locale e nella memoria condivisa (Figura-a). Il processore P1 scrive X1 nella sua memoria cache usando il protocollo write-invalidate. Quindi, tutte le altre copie sono invalidate attraverso il bus. È indicato con ‘I’ (Figura-b). I blocchi invalidati sono anche conosciuti come sporchi, cioè non dovrebbero essere usati. Il protocollo write-update aggiorna tutte le copie della cache attraverso il bus. Usando la cache write back, viene aggiornata anche la copia di memoria (Figura-c).

Eventi e azioni della cache

Seguenti eventi e azioni si verificano durante l’esecuzione dei comandi di accesso alla memoria e di invalidazione –

• Read-miss – Quando un processore vuole leggere un blocco e questo non si trova nella cache, si verifica un read-miss. Questo avvia un’operazione di lettura sul bus. Se non esiste una copia sporca, allora la memoria principale che ha una copia coerente, fornisce una copia alla memoria cache richiedente. Se esiste una copia sporca in una memoria cache remota, questa memoria cache si trattiene dalla memoria principale e invia una copia alla memoria cache richiedente. In entrambi i casi, la copia nella cache entrerà nello stato valido dopo un read miss.

• Write-hit – Se la copia è in stato sporco o riservato, la scrittura viene fatta localmente e il nuovo stato è sporco. Se il nuovo stato è valido, il comando write-invalidate viene trasmesso a tutte le cache, invalidando le loro copie. Quando la memoria condivisa viene scritta attraverso, lo stato risultante è riservato dopo questa prima scrittura.

• Write-miss – Se un processore non riesce a scrivere nella memoria cache locale, la copia deve venire o dalla memoria principale o da una memoria cache remota con un blocco sporco. Questo viene fatto inviando un comando read-invalidate, che invaliderà tutte le copie della cache. Poi la copia locale viene aggiornata con lo stato sporco.

• Lettura-hit – La lettura-hit viene sempre eseguita nella memoria cache locale senza causare una transizione di stato o usare il bus snoopy per l’invalidazione.

• Sostituzione del blocco – Quando una copia è sporca, deve essere riscritta nella memoria principale con il metodo della sostituzione del blocco. Tuttavia, quando la copia è in stato valido o riservato o non valido, non avrà luogo alcuna sostituzione.

Protocolli basati su directory

Utilizzando una rete multistadio per costruire un grande multiprocessore con centinaia di processori, i protocolli della cache snoopy devono essere modificati per adattarsi alle capacità della rete. Essendo il broadcasting molto costoso da eseguire in una rete multistadio, i comandi di coerenza vengono inviati solo a quelle cache che conservano una copia del blocco. Questa è la ragione per lo sviluppo di protocolli basati su directory per multiprocessori collegati in rete.

In un sistema di protocolli basati su directory, i dati da condividere sono posti in una directory comune che mantiene la coerenza tra le cache. Qui, la directory agisce come un filtro dove i processori chiedono il permesso di caricare una voce dalla memoria primaria alla sua memoria cache. Se una voce viene cambiata, la directory la aggiorna o invalida le altre cache con quella voce.

Meccanismi di sincronizzazione hardware

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

I sistemi multiprocessori usano 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 atomiche, anche alcuni interrupt interprocessori sono usati per scopi di sincronizzazione.

Cache Coherency in macchine a memoria condivisa

Mantenere la coerenza della cache è un problema nel sistema multiprocessore quando i processori contengono memoria cache locale. L’incoerenza dei dati tra le diverse cache si verifica facilmente in questo sistema.

Le maggiori aree di preoccupazione sono –

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

Condivisione dei dati scrivibili

Quando due processori (P1 e P2) hanno lo stesso elemento dati (X) nelle loro cache locali e un processo (P1) scrive sull’elemento dati (X), poiché le cache sono in scrittura attraverso la cache locale di P1, anche la memoria principale viene aggiornata. Ora quando P2 cerca di leggere l’elemento di dati (X), non trova X perché l’elemento di dati nella cache di P2 è diventato obsoleto.

Migrazione dei processi

Nel primo stadio, la cache di P1 ha l’elemento di dati X, mentre P2 non ha nulla. Un processo su P2 prima scrive su X e poi migra su P1. Ora, il processo inizia a leggere l’elemento di dati X, ma poiché il processore P1 ha dati obsoleti, il processo non può leggerlo. Quindi, un processo su P1 scrive sull’elemento di dati X e poi 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à 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 di dati X. Quando il dispositivo di I/O riceve un nuovo elemento X, memorizza il nuovo elemento direttamente nella memoria principale. Ora, quando P1 o P2 (supponiamo P1) cerca di leggere l’elemento X, ottiene una copia non aggiornata. Quindi, P1 scrive sull’elemento X. Ora, se il dispositivo I/O cerca di trasmettere X ottiene una copia non aggiornata.

Uniform Memory Access (UMA)

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

Non-Uniform Memory Access (NUMA)

Nell’architettura NUMA, ci sono più cluster SMP che hanno una rete interna indiretta/condivisa, che sono collegati in una rete scalabile di message-passing. Quindi, l’architettura NUMA è un’architettura di memoria logicamente condivisa e fisicamente distribuita.

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

Cache Only Memory Architecture (COMA)

Le macchine COMA sono simili alle macchine NUMA, con la sola differenza che le memorie principali delle macchine COMA agiscono come cache a mappatura diretta o set-associative. I blocchi di dati sono hashati in una posizione nella cache DRAM secondo i loro indirizzi. I dati che sono recuperati a distanza sono effettivamente memorizzati nella memoria principale locale. Inoltre, i blocchi di dati non hanno una posizione fissa, possono muoversi liberamente in tutto il sistema.

Le architetture COMA hanno per lo più una rete gerarchica di message-passing. Un interruttore in un albero di questo tipo contiene una directory con elementi di dati come sottoalbero. Dal momento che i dati non hanno una posizione iniziale, devono essere cercati esplicitamente. Questo significa che un accesso remoto richiede una traversata lungo gli switch nell’albero per cercare nelle loro directory i dati richiesti. Così, se uno switch nella rete riceve più richieste dal suo sottoalbero per gli stessi dati, le combina in una singola richiesta che viene inviata al genitore dello switch. Quando i dati richiesti ritornano, lo switch ne invia più copie lungo il suo sottoalbero.

COMA contro CC-NUMA

Seguono 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 bisogno del sistema operativo.

• Le macchine COMA sono costose e complesse da costruire perché hanno bisogno di un 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.