Coerenza Della Memoria Cache in Architetture Multiprocessore

Universit degli Studi di Napoli Federico II

Calcolatori Elettronici II

Prof.re Nicola Mazzocca

1.2.6. Architetture a memoria condivisa centralizzata Un protocollo di coerenza delle cache: lo snooping

Nei sistemi di elaborazione un ruolo forte giocato dallhardware, tale componente del sistema pu

aumentare le prestazioni complessive. In particolare nellambito dei sistemi distribuiti maggiore la

possibilit di implementare reti totalmente connesse, maggiore la possibilit di migliorare il

funzionamento complessivo dellarchitettura.

Ma qual lapporto dato dallhardware al miglioramento dellimplementazione della distribuzione

del sistema? E quindi al miglioramento delle prestazioni?

Per rispondere a questa domanda bisogna distinguere due casi, quello dei sistemi multicomputer e

quello dei sistemi multiprocessore.

Diciamo innanzitutto che in entrambe le situazioni lobbiettivo che ci si prefigge quello di

diminuire i costi di interazione senza agire sul software, ma solo sullhardware. Ricordiamo che il

costo di interazione il carico introdotto sulla elaborazione, dalla comunicazione, per lo scambio di

informazioni che avviene tra due o pi processi.

Per un sistema multiprocessore tale costo determinato dal carico a cui sottoposto il bus comune

dai processi che interagiscono per mezzo della memoria condivisa.

Al fine di diminuire literazione tra i processi necessario introdurre, come gi accennato

precedentemente, allinterno della architettura una gerarchia di memorie, che si traduce nel

corredare i diversi processori di una propria memoria, possibilmente pi veloce di quella comune,

quindi una memoria cache.

Con lutilizzo della soluzione illustrata, per, nasce un problema di gestione della coerenza della

memoria condivisa, non per le istruzioni eseguite dai diversi processori, le quali devono essere

solamente lette, ma per i dati che sono condivisi e possono essere modificati.

Tale problema deve essere affrontato in maniera diversa a seconda che la tecnica usata per la

gestione della cache sia write through o write back.

Nel caso in cui la politica utilizzata sia del tipo write through, ogni qual volta un dato viene

modificato, il suo valore viene immediatamente aggiornato in memoria condivisa, mentre nel caso

P1

m1

Memoria Condivisa

P4

m4

P2

m2

P3

m3

Figura 63: Sistema multiprocessore.

P4

Figura 62: Sistema multiprocessore.

P1

Memoria Condivisa

P2 P3

in cui la politica sia write back allora le modifiche non sono riportate immediatamente, ma lo

saranno in un secondo momento.

Per entrambe le tecniche, quindi, si necessita di una politica di invalidazione dei dati modificati da

un processo ed eventualmente presenti allinterno delle cache di altri processori, o della memoria

comune. Ovviamente, nel caso della write through, la memoria condivisa viene aggiornata alla

modifica dei dati per cui non possiede mai valori da invalidare.

Tutto ci porta unulteriore sovraccarico nellutilizzo del bus comune.

Lidea che sta alla base di tale tecnica la seguente: ogni processore spia gli altri per verificare se

un dato presente nella propria cache viene modificato. Un dato viene identificato attraverso il suo

indirizzo in memoria condivisa.

Per, la realizzazione dellhardware necessario per creare il meccanismo di invalidazione e di

arbitraggio della comunicazione tra i processori sul bus condiviso, molto complessa, quindi il

numero di processori presenti sulla stessa motherboard nei sistemi commerciali risulta essere

limitato (2, max 4).

Limplementazione varia a seconda della politica di gestione utilizzata (write through oppure write

back) e pu essere descritta attraverso gli schemi di automi a stati finiti.

Analizziamo dapprima il caso in cui la memoria cache si comporti secondo la tecnica write through.

In questo caso la spia opera sulle linee indirizzo del bus comune.

Per capire il funzionamento descritto dal diagramma degli stati utile fare le seguenti ipotesi:

1) Ci sono due processori iP e jP che operano sugli stessi dati.

2) Lautoma rappresenta il comportamento di un processore iP (processore spia) a fronte

delle azioni compiute sui dati, sia da se stesso, che dal processore jP (processore spiato).

Ogni dato presente in cache pu assumere solo due stati: Valido e Non valido.

- Tutte le operazioni di lettura e scrittura effettuate dal processo iP portano i dati coinvolti

nello stato di validit [W(i);R(i)]. In tale stato, eventuali letture o rimozioni dei dati dalle

memorie locali degli altri processori sono ininfluenti [R(j);Z(j)].

- Si passa nello stato di Non validit nel momento in cui i dati in esame sono rimossi dalla

memoria cache di iP [Z(i)] oppure il processore jP li modifica con unoperazione di

scrittura [W(j)]. In tale stato ulteriori operazioni di lettura o scrittura da parte di altri

processori (diversi da iP ) [R(j); W(j)] ed eventuali operazioni di rimozione dei dati da parte

di qualsiasi processore (compreso iP ) [Z(i); Z(j)] mantengono i dati nella condizione di

invalidit.

VALIDO NON

VALIDO

W(i)

R(i)

R(j)

Z(j)

Z(i)

Z(j)

W(j)

R(j)

R(i) W(i)

Z(i) W(j)

Figura 64: Automa nel caso Write-Throught.

R(i) op.di read da parte del processore i. W(i) op.di write da parte del processore i. Z(i) il processore i elimina il dato dalla propria memoria locale.

Passiamo ora a considerare il caso write-back, bisogna tenere conto che laggiornamento del dato in

memoria comune non avviene subito ma in un secondo momento. Lo stato RW quello in cui il

iP pu effettuare qualunque tipo di operazione sul dato. Se jP legge il dato, si va in uno stato RO

(read); si deve cio tener conto del fatto che adesso anche altri processori stanno leggendo il dato in

questione e, perci, in tal caso affinch questo sia possibile bisogna effettuare un flush in memoria

comune. Da questo stato non si esce mai fintantoch i vari processori si limitano a leggere il dato.

Una eventuale riscrittura da parte di iP riporta nello stato RW. Questa operazione corrisponde a

invalidare il dato dal punto di vista di jP . Possiamo rendercene conto osservando sempre lo stesso

grafo: sia che ci troviamo in RW o che ci troviamo in RO, loperazione W(j) porta nello stato

Non Valido dal punto di vista di iP da qui si capisce che entrambi gli stati (RO e RW)

identificano la validit del dato in memoria. Quindi in regime write-back una qualunque operazione

di scrittura dal parte di un processore rende il dato invalido per tutti gli altri, come daltra parte

ovvio.

Da uno stato invalido si pu tornare se iP legge o scrive il dato. In particolare, R(i) porta in RO, e

W(i) in RW. Ci si pu domandare perch abbiamo distinto i due stati, entrambi validi, RW e

RO. In effetti, nel caso in cui da Non Valido si passa a RW il processore iP si limita ad

aggiornare nella propria memoria locale. Se invece si passa ad RO (R(i)) si forza il sistema di

gestione a prelevare il dato dalla memoria centrale e a scaricarlo nella cache di iP . Le due situazioni

sono quindi sostanzialmente diverse.

Da quanto detto lo stato che risulta pi critico per il sistema quello di RW, dove in pratica i dati

modificati dal processore iP sono validi solo per se stesso e quindi non allineati alla memoria

condivisa. Come si vede il meccanismo molto complicato e la gestione del bus deve essere

abbastanza accurata per poter stabilire una convenzione nella comunicazione. Infatti il bus stesso

riveste un ruolo di fondamentale importanza perch stabilisce attraverso i suoi collegamenti

READ READ &

WRITE

R(j)

R(i)

W(i)

Z(j)

R(i)

R(j)

Z(j)

W(i)

Z(i) Z(j)W(j) R(j)

NON

VALIDO

W(i)

R(i)

W(j)

Z(i)

Figura 65: Automa nel caso Write-Back

R(i) op.di read da parte del processore i. W(i) op.di write da parte del processore i. Z(i) il processore i elimina il dato dalla propria memoria locale.

Z(i)

W(j)

linsieme di protocolli disponibili. Inoltre necessario un hardware aggiuntivo che consenta di

applicare la politica di arbitraggio.

Accanto alle tecniche standard di write-through e write-

back stata ideata lulteriore tecnica detta di write-once,

nella quale la prima volta viene eseguito il write through;

se in seguito risulta necessario effettuare altre scritture

sullo stesso dato, si passa alla modalit write-back, per

evitare di appesantire il traffico sul bus. Osserviamo che

lautoma a stati finiti per la tecnica write-once richiede 4

stati.

Una ulteriore tecnica per la coerenza fa uso di puntatori.

C una shared memory che dice in quale cache

presente un certo dato, e dei puntatori che consentono di

reperire i dati. Quando una cache invalida il dato, invece

di spostare materialmente i dati si possono usare i

puntatori per creare delle catene logiche che consentono

di andare a prendere sempre la versione corretta del dato.

Si vengono cos a creare delle gerarchie di memoria che

in particolare assumono la struttura di alberi, con foglie

valide e foglie invalide.

Si parte dallassunto che uno dei

nodi conosce sicuramente la versione

aggiornata del dato, per cui gli altri

devono rivolgersi a lui per poterla

utilizzare; inoltre nel sistema ci deve

essere una unit (memoria condivisa)

che permette di localizzare tale nodo

di riferimento. Si comprende

facilmente come questo approccio,

peraltro poco diffuso, sia fortemente

centralizzato e ben poco distribuito.

Osservazione: la macchina virtuale

non sa assolutamente dove si trovano

i dati validi; tutto gestito

dallhardware. Quindi la

realizzazione della macchina virtuale

risulta semplificata, non dovendo

preoccuparsi dei problemi sollevati

dalla coordinazione distribuita che

sono risolti a livello hardware.

ovvio comunque che semplificazione

software comporta complicazione

hardware. Lo stato del sistema

conservato in linea di principio nella

shared memory, che una struttura

statica, ma la tipologia di accesso ai

dati variabile dato che le cache

sono fortemente dinamiche.

1.2.7. Architettura dei

Figura 61: Automa con tecnica write-once

Figura 62: Tecnica con puntatori

sistemi multicomputer (topologia di interconnessione reti dirette e indirette) - Esempio di sistema di interconnessione per architetture parallele (Vulcan Sw)

Passiamo ad analizzare il caso in cui larchitettura del sistema sia di tipo multicomputer.

In questa configurazione, a differenza dei sistemi multiprocessore, non vi una simmetria nella

comunicazione dettata dalla presenza di un bus ed una memoria comune, bens esiste il concetto di

diametro che rappresenta la massima distanza tra due processori in termini di unit di elaborazione.

In questo caso lobbiettivo di ridurre il costo di iterazione ulteriormente complicato dal fatto che

molto spesso non possibile ottenere una totale connettivit (come invece avviene per i sistemi

multiprocessore usando il bus comune), quindi grafo del problema e grafo dellarchitettura molte

volte non coincidono.

In generale, poi, esiste anche un problema di allocazione dei processi. Infatti, qualora questi siano in

numero maggiore rispetto ai processori, esistono diverse possibilit per ottenere una configurazione

che consenta di diminuire loverhead introdotto dalla comunicazione.

In linea di principio la regola quella di far girare sullo stesso processore, processi che comunicano

molto tra di loro, mentre occorre allocare su nodi diversi processi che necessitano di molte risorse di

calcolo cos, da ridurre sia il numero di messaggi scambiati che quello dei conflitti interni per

lutilizzo di una risorsa.

Per ottenere ci, devono essere formulate delle specifiche funzioni obbiettivo che tengano conto di

entrambi gli aspetti considerati. Ma questo non semplice da attuare poich le operazioni svolte dai

processi dipendono in gran parte dai dati su cui essi operano.

Nellottica in cui ci poniamo (punto di vista puramente hardware), la configurazione descritta

dallarchitettura non pu risolvere il problema dallallocazione dei processi, ma pu far fronte a

quello della connettivit, cercando di rendere quanto pi semplice possibile la comparazione tra

grafo del problema e quello dellarchitettura.

Esistono due soluzioni: reti dirette e reti indirette.

Le reti dirette definiscono una topologia fissa per cui la compatibilit tra i grafi realizzata in

maniera analitica attraverso lutilizzo di formule matematiche che fanno riferimento al campo della

ricerca operativa.

Le reti indirette per antonomasia sono realizzate

attraverso particolari dispositivi chiamati

switch, che consentono di ottenere una totale

connettivit attraverso limplementazione di un

sistema dinamico di comunicazione.

Per capire meglio come questo sia possibile,

risulta necessario approfondire ulteriormente i

dettagli di realizzazione che consentono di

implementare gli switch.

Innanzitutto, il problema principale di tali

dispositivi quello della gestione dei conflitti,

ovvero di situazioni in cui, due o pi nodi

cercano di comunicare contemporaneamente

con un altro.

A questo proposito, possibile classificare gli switch in due categorie:

- a singolo stadio (Diretti) - a N stadi (Indiretti)

Per creare uno switch a connessione diretta tra due nodi diversi, necessario avere due informazioni

fondamentali: lindirizzo del nodo sorgente e quello del nodo destinazione.

Il dispositivo che si vuole realizzare dovr avere n nodi in ingresso ed n nodi in uscita

(nellipotesi che il numero di nodi della rete sia n), mediante gli indirizzi del sorgente e della

Mm M2 M1

Pn P2 P1

MUX

DEMUX

Figura 63: Reti dirette ed indirette

destinazione si stabilir la comunicazione tra i nodi. Per poter implementare tale architettura si deve

scomporre il sistema in due sottosistemi diversi, quello di ingresso e quello di uscita. Tale

suddivisione viene realizzata mediante lutilizzo di un dispositivo Multiplexer, per quanto riguarda

lingresso ed un dispositivo Demultiplexer per quanto riguarda luscita, entrambi generalmente

realizzati in logica three-state.

Linconveniente implicito del meccanismo

implementato, che automaticamente si realizza una

mutua esclusione tra i nodi dovuta al fatto che, potr

essere attivo un solo collegamento per volta. Quindi,

per realizzare un collegamento di 2

n comunicazioni

simultanee, si dovr replicare lhardware 2

n volte.

Si elencano di seguito le propriet di questa soluzione:

- Assenza di stadi intermedi - Buona efficienza - Basso parallelismo - Parallelismo fisico ottenuto riproducendo lo stesso elemento pi volte.

La soluzione trovata non esente dal problema dei conflitti, poich aumentando il parallelismo in

hardware si va semplicemente a rendere possibile la comunicazione parallela, ma se i nodi di

ingresso vogliono comunicare con lo stesso nodo di uscita inevitabile che si creano collisioni.

Si rende necessario, quindi, predisporre un gestore dei conflitti.

Laltra soluzione architetturale, citata in precedenza, per poter realizzare uno switch, si basa

sullutilizzo di pi stadi intermedi per stabilire la comunicazione tra i nodi.

Sono state proposte nel tempo varie topologie per implementare la logica degli n-stadi.

In particolare, facile rendersi conto che, utilizzando dispositivi costituiti da due ingressi e due

uscite per realizzare gli stadi, con nLog2 stadi possibile risolvere il problema della connettivit,

avendo tra laltro il vantaggio di usare blocchi molto semplici che devono solo decidere se

procedere in una direzione o in unaltra ( 2Log dovuto dal fatto che i blocchi hanno due ingressi e

due uscite). Ad esempio con 8 nodi servono 3 stadi per garantire la connettivit totale del sistema.

Ovviamente esiste un problema non banale, come si fa a collegare i blocchi tra di loro? O meglio,

quale la topologia di interconnessione dei fili da adottare?

E inoltre, come si fa a gestire lindirizzamento?

Per switch a connessione diretta lindirizzamento semplice perch gli indirizzi vanno direttamente

nel multiplexer e nel demultiplexer per creare il path.

Nel caso di architetture multistadio invece, lindirizzo disposto in k bit, deve essere diviso in tante

parti quanti sono gli stadi, in modo da comandare opportunamente i blocchi.

Vediamo alcuni esempi

16 nodi lindirizzo di uscita codificato in 4 bit

log216 = 4 stadi

0011 0 indirizzo I stadio

0 indirizzo II stadio

1 indirizzo III stadio

1 indirizzo IV stadio

8 nodi lindirizzo di uscita codificato in 3 bit

M

U

X

D

E

M

U

X

Indirizzo

Sorgente

Indirizzo

Destinazione

Figura 64: Switch a singolo stadio

log28 = 3 stadi

110 1 indirizzo I stadio

1 indirizzo II stadio

0 indirizzo III stadio

Cos facendo non esiste una logica di controllo centralizzata come nel caso precedente ma la logica

di controllo distribuita negli stadi.

Il nodo a cui arriva il messaggio analizza lindirizzo e si comporta di conseguenza. Ovviamente

una condizione abbastanza forte dal punto di vista dellarchitettura, che possibile realizzare

soltanto utilizzando particolari propriet topologiche della rete. Un esempio che implementa una

soluzione molto interessante rappresentata dalla omega network la quale si basa sul concetto del

perfect shuffling

Il perfect shuffling, una tecnica che fa riferimento al modo con cui le carte di un mazzo vengono

mischiate, infatti, se si divide il mazzo di carte in due parti uguali e si mischiamo perfettamente,

dopo nLog2 volte si ritorna allordine iniziale, questa tecnica ci permette di ottimizzare i percorsi

da seguire indicando i modi di collegamento tra i diversi stadi.

Mischiare perfettamente significa che la prima carta della prima met viene accoppiata con la prima

della seconda met, la seconda della prima met con la seconda della seconda met, e cos via.

Descriviamo il funzionamento del perfect shuffling con un esempio:

IPOTESI: mazzo di 8 carte; TESI: dopo 3 passaggi si ritorna allordinamento iniziale;

Ordinamento

(Stato del

mazzo di carte)

Schematizzazione (2 met

del mazzo di carte)

Accoppiamento per stadio

0 1 2 3 4 5 6 7

I met del mazzo di carte

0 1 2 3

II met del mazzo di carte

4 5 6 7

0 con 4 I stadio

1 5

2 6

3 7

0 4 1 5 2 6 3 7


0 4 1 5


2 6 3 7

0 con 2 II stadio

4 6

1 3

5 7

0 2 4 6 1 3 5 7


0 2 4 6


1 3 5 7

0 con 1 III stadio

2 3

4 5

6 7

0 1 2 3 4 5 6 7


0 1 2 3


4 5 6 7

Si ripristinato lordinamento iniziale

Di seguito riportiamo la topologia di interconnessione degli stadi, che implementa la tecnica del

perfect shuffling appena descritta.

Inoltre illustriamo una serie di esempi che mettono in evidenza la strategia utilizzata per

determinare il percorso da uno specifico nodo sorgente ad uno destinazione.

In particolare, in base al bit dellindirizzo di destinazione associato ad ogni stadio, viene selezionato

il collegamento da percorrere, utilizzando il seguente criterio:

- Se il valore del bit 0, si procede con il ramo di uscita superiore del blocco considerato - Se il valore del bit 1, si procede con il ramo di uscita inferiore del blocco considerato

Ad esempio se abbiamo lindirizzo destinazione 110 nel terzo stadio si considera il terzo bit

(nellipotesi che si procede dal bit pi significativo a quello meno significativo). Nel nostro caso

0, quindi si percorrer il ramo superiore del blocco in cui ci troviamo.

Proseguiamo con una serie di esempi molto pratici che ci permettono di capire le problematiche di

funzionamento.

Esempio: Dal nodo 2 si vuole andare al nodo 4; indirizzo 100, quindi:

I stadio Gi; II stadio Su; III stadio Su N.B. Lindirizzo v considerato dal bit pi

significativo a quello meno significativo

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

00

41

0/1

10

51

0/1

20

61

0/1

30

71

0/1

00

21

0/1

40

61

0/1

10

31

0/1

50

71

0/1

00

11

0/1

20

31

0/1

40

51

0/1

60

71

0/1

Verso di percorrenza


I stadio Su; II stadio Su; III stadio Su N.B. Lindirizzo v considerato dal bit pi

significativo a quello meno significativo

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

00

41

0/1

10

51

0/1

20

61

0/1

30

71

0/1

00

21

0/1

40

61

0/1

10

31

0/1

50

71

0/1

00

11

0/1

20

31

0/1

40

51

0/1

60

71

0/1


Nel caso in cui lindirizzo destinazione, viene esaminato a partire dal bit meno significativo, basta

invertire il verso di percorrenza della rete, come illustrato nel seguente esempio

Il vantaggio evidente, come detto prima, risiede nella semplicit dei componenti usati per realizzare

il dispositivo che implementa il routing, ovvero blocchi con due ingressi e due uscite. Lunica nota

negativa, invece, risulta proprio lutilizzo di pi stadi. Va notato che, la flessibilit indotta

dallarchitettura, grazie alla forte modularit dei componenti, rende lo switch molto scalabile, infatti

facile realizzarne uno di grandi dimensioni, cosa che non semplicemente possibile per gli switch

diretti.

Il problema che si verifica , per sempre lo stesso, se due nodi di ingresso vogliono parlare con lo

stesso nodo di uscita simultaneamente generano un conflitto, inoltre la contesa pu anche avvenire

nei nodi intermedi. Infatti, possibile vedere che, anche se, due nodi diversi non vogliono

comunicare con lo stesso nodo, si genera una collisione.


I stadio Gi; II stadio Gi; III stadio Su N.B. Lindirizzo v considerato dal bit

meno significativo a quello pi significativo

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

00

41

0/1

10

51

0/1

20

61

0/1

30

71

0/1

00

21

0/1

40

61

0/1

10

31

0/1

50

71

0/1

00

11

0/1

20

31

0/1

40

51

0/1

60

71

0/1


Per esempio, ci avviene quando simultaneamente il nodo 2 vuole comunicare con il nodo 1 ed il

nodo 6 vuole comunicare con il nodo 0; oppure quando il nodo 7 vuole comunicare con il nodo 0 e

contemporaneamente il nodo 5 vuole comunicare con il nodo 1.

Bisogna capire a questo punto come gestire i conflitti.

Prima di fare ci opportuno ribadire alcune differenze fondamentali tra le due diverse architetture

presentate:

- Nel caso di switch diretti lindirizzo valutato in un solo passo, mentre per switch indiretti viene valutato in pi passi.

- Negli switch a pi stadi la generazione dei conflitti pu avvenire anche negli stadi intermedi e dipende fortemente dallalgoritmo di routing scelto per implementare la topologia di

interconnessione dei fili, mentre negli switch a uno stadio le collisioni sono dovute alla

presenza dei hardware replicato che di fatto aumenta il parallelismo ma non permette nessun

meccanismo di prevenzione dei conflitti.

Esempio: Dal nodo 2 si vuole andare al nodo 1; indirizzo 001; Dal nodo 6 si vuole andare al nodo 0

indirizzo 000:

N.B. Lindirizzo v considerato dal bit pi significativo a quello meno significativo

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

00

41

0/1

10

51

0/1

20

61

0/1

30

71

0/1

00

21

0/1

40

61

0/1

10

31

0/1

50

71

0/1

00

11

0/1

20

31

0/1

40

51

0/1

60

71

0/1


Collisione!

Per gestire conflitti in una rete multi-stadio, ricordiamo anzitutto che la comunicazione pu

avvenire seguendo due diverse filosofie: warm-all e store&forward (questultima usata in internet

dove, di fatto, non ci sono conflitti o per meglio dire, eventuali conflitti non bloccano il canale di

comunicazione, poich sono rilevati ed analizzati quando si effettua loperazione di store). Nel

primo caso, per far interagire due nodi, le informazioni vengono scambiate attraverso un canale di

comunicazione definito dal percorso effettuato dai bit dellindirizzo destinazione attraverso la rete.

Tutti i nodi intermedi sono abilitati a trasmettere i dati, lungo il percorso stabilito ed ogni messaggio

viene inviato un blocco alla volta (ad esempio, un byte). Nel caso store&forward, il mittente

instaura una comunicazione solo con il nodo direttamente connesso, il quale preleva lintero

messaggio, lo memorizza e lo inoltra ad un nodo successivo quando il canale libero , e cos via

fino a destinazione.

La tecnica warm-all comporta un risparmio complessivo di tempo(ottimizza il

tempo di risposta), perch dopo aver conquistato il canale ci si pu lavorare sopra

senza ulteriori ritardi. Inoltre, normalmente nessuno dei nodi intermedi deve

memorizzare dati, ma solo instradarli lungo il precorso prefissato. Si realizza,

difatti, un meccanismo di comunicazione a pipeline. Viceversa, la tecnica

store&forward, evita lassegnazione esclusiva di un canale, aumentando

loccupazione di banda (troughtput) ma introduce dei ritardi nella comunicazione.

Un esempio tipico di tale tecnica la posta elettronica, poich per linvio di una e-

mail non si pu pretendere di riservare un canale che pu snodarsi anche da un capo

allaltro del mondo. Si pensi, inoltre, alla situazione in cui il collegamento fra due sottoreti sia reso

possibile da un solo canale. Se il mittente sta nella prima sottorete ed il destinatario un nodo della

seconda sottorete, il canale in questione sarebbe sicuramente presente nel percorso prefissato e ogni

altra comunicazione fra le due sottoreti sarebbe resa impossibile per tutto il tempo necessario a

trasmettere la e-mail.

Daltro canto, il warm-all una tecnica accettabile solo se esiste unesigenza di accoppiamento fra

gli interlocutori (come avviene negli switch).

Si pu anche dire che il warm-all effettua una negoziazione di percorso, mentre lo store&forward

realizza una negoziazione di tratta. La negoziazione del percorso nel warm-all non avviene per in

via preliminare alla comunicazione, ma dinamicamente ed guidata dal primo blocco di dati, che

nel raggiungere la destinazione traccia il percorso che sar poi seguito da tutti gli altri blocchi

(serpentone).

Cosa accade, dunque, se il serpentone dei dati si ferma da qualche parte a causa di un conflitto

nelluso di un canale, o per qualunque altra ragione? Sono note 4 tecniche principali per gestire tale

situazione:

- La prima una tecnica bloccante, conservativa e non efficiente, nella quale il nodo che non in grado di propagare i blocchi interrompe lavanzare del serpentone, finch non riesce a

risolvere il problema e si pu quindi riprendere con la trasmissione. Ovviamente in tale

evenienza si pu essere costretti a bloccare un elevato numero di nodi intermedi

- La seconda, si limita a distruggere i messaggi che incontrano tale problema (rete con perdita di dati).

- La terza consiste nel re-instradare il messaggio lungo un percorso alternativo a quello bloccato. Questa eventualit di re-instradamento possibile solo se le tabelle di routing non

sono statiche e se la topologia della rete lo permette (nel perfect shuffling ci non

possibile). Ad esempio nel caso della rete toroidale con il tracciamento del percorso

realizzato con i bit (e quindi cablato in hardware) non esiste alcuna possibilit di re-

instradamento.

- La quarta ed ultima tecnica realizza il cut-through, che in effetti consiste nelladottare una filosofia store&forward allinterno del warm all. Il messaggio viene memorizzato nel nodo

che ha riscontrato il conflitto, il quale continua a ricevere i blocchi del messaggio e li

conserva fino alla soluzione del problema. Questa versione apparentemente brillante

presenta linconveniente per cui se nel frattempo arriva un altro serpentone di dati nello

stesso nodo, il buffer potrebbe essere stato riempito dal precedente per cui il nuovo

messaggio non pu essere propagato. I nodi in questo quarto modello devono quindi

possedere una memoria; in realt sufficiente che possiedano uno shift-register ed un

contatore di blocchi.

Infine, c da dire che spesso il warm-all non viene realizzato sullintero messaggio, ma il

messaggio viene spezzettato in un certo numero di frammenti o pacchetti la cui trasmissione viene

effettuata come descritto. Si noti che in questo caso, se si adotta la tecnica del re-instradamento, i

pacchetti possono giungere a destinazione in disordine, e quindi serve un software che permetta di

ricostruire lordine giusto.

Ricapitolando, abbiamo visto che uno switch, se non prevede la bufferizzazione, semplicemente

strutturato in unarchitettura multiplexing/demultiplexing. Se invece la bufferizzazione necessaria,

occorrer mettere intelligenza negli switch, prevedendo ad esempio la possibilit di bloccare i

messaggi in ingresso, ed eventualmente di re-instradarli per un diverso percorso.

Per gli switch seriali (es: switch ATM), per i quali cio la comunicazione seriale (canali di

collegamento singoli), la dotazione comprende essenzialmente shift-register e contatori. A tal

proposito concludiamo presentando un esempio reale di switch per una macchina parallela:

Vulcan Switch IBM.

Uno dei principali problemi correlati alla fabbricazione dei circuiti integrati che quanto pi il

numero di piedini verso lesterno diventa elevato, tanto pi difficile si rende lintegrazione.

Supponiamo ad esempio che lo switch debba interfacciarsi con 8 dispositivi, e che possa trasferire

un byte in parallelo per ogni dispositivo. Gi cos abbiamo ben 8*8 = 64 fili. Se poi lo switch

bidirezionale, occorreranno fili di output oltre che di input e quindi si passerebbe a 128 fili.

Osserviamo infine che i processori moderni hanno un parallelismo a 64 bit e oltre, e non certo a

byte.

Lesigenza di realizzare switch con molti piedini ha portato alla scelta di fare uscire questi piedini

non pi solo alla periferia, ma anche dalla parte inferiore dellintegrato (si sfrutta la sua area e non

pi solo il perimetro). Questa scelta comporta per anche uno svantaggio, dal momento che la

densit di fili diviene elevatissima, aumenta con essa la dissipazione di calore ed il rischio di

incrociare i fili stessi. Un modo per aggirare il problema di realizzare le schede multilivello

(tridimensionali): le odierne schede possono essere anche su 12 o 14 strati.

In un Vulcan Switch per processori a 64 bit, la parola in ingresso allo switch (per ciascun nodo)

di soli 8 bit. Come mai? Osserviamo che se volessimo procedere nel modo che appare pi naturale,

dovremmo avere 64 * 8 (numero dispositivi di ingresso) * 2 (I/O) = addirittura 1024 contatti. La

parola del processore non pu dunque essere parallelizzata per intero: decidiamo di limitare il

numero di contatti per nodo verso lesterno ad 8 scomponendo cos il parallelismo interno (64) da

quello esterno (8). Sulla scheda su cui si monta lo switch (e non sullo switch stesso) dovr essere

presente un dispositivo che prende le stringhe da 64 bit in uscita da ogni processore e le impacchetta

in 8 gruppi di 1 byte ciascuno (8*8=64).

Supponiamo di avere anche 8 dispositivi in uscita. Gli 8 ingressi possono trovarsi in una situazione

di conflitto con le 8 uscite: due o pi ingressi possono ritrovarsi a cercare di inviare informazioni

alla stessa uscita. Si pu pensare di bloccare uno dei canali di ingresso che causano conflitto, ovvero

arrestare la scheda del processore che sta impacchettando i 64 bit, ma cos si impedirebbero ulteriori

comunicazioni con problematiche da parte dello stesso processore.

Il problema viene risolto con un deserializer su ogni canale di ingresso, un serializer su ogni uscita

e un buffer di memoria intermedio. Il deserializer prende 8 bit per volta (un buffer di memoria) e li

accumula in parole da 64 bit; il serializer compie loperazione opposta..

Serializer

Serializer

.

.

. Memoria

M Matrice di

commutazione

Deserializer

Deserializer

.

.

.

8

Dispositivi

8

Dispositivi

Schema Logico di riferimento

64

64

64

64

64

64

8

8

8

8

A valle del deserializer sistemiamo una singola memoria-buffer usata da tutti i canali cos da

implementare una tecnica di tipo cut-through; se per esempio intendiamo accumulare al massimo n

byte per ciascun dispositivo, tale memoria dovr avere una capacit di 8*n byte. Perch usare una

sola memoria condivisa e non 8 memorie separate? Il motivo semplice, utilizzando una sola

memoria si ottimizza la quantit di spazio usato, poich se il buffer (deserializzatore) di uno dei

canali si riempie con una frequenza maggiore rispetto agli altri, questi pu utilizzare lo spazio libero

non sfruttato dagli altri.

Il parallelismo di scrittura tra ogni deserializzatore e la memoria M di 64 bit (la memoria ha

quindi un parallelismo di 64 bit). M serve come buffer per la memorizzazione di dati che non

possono essere inviati direttamente perch causerebbero conflitti, e deve essere dimensionata

tenendo conto della probabilit che tali conflitti si verifichino (per esempio non probabile che tutti

i canali causino conflitto).

Scrivere direttamente in M sarebbe dannoso, poich causerebbe un elevato numero di conflitti

nelluso di M da parte dei canali. Invece ogni nodo di ingresso inserisce 64 bit di dati, un byte alla

volta, in una memoria locale (deserializzatore), dopodich ogni memoria locale riempie la memoria

centrale M. Cos facendo, i canali sono stati disaccoppiati e la macchina risulta avere una elevata

produttivit. Ovviamente per evitare collisioni nellaccesso alla memoria, questultima dovr avere

una velocit di almeno 8 volte superiore rispetto a quella dei deserializzatori.

Incrementare la dimensione della memoria M risulta un vantaggio per tutti i nodi.

M pu essere ad accesso duale, in modo che

mentre uno degli ingressi vi scrive, una delle

uscite vi pu leggere. I dati in M comprendono

anche informazioni di indirizzamento per

identificare mittenti e destinatari di ciascun

messaggio.

Figura 71: Schema Logico di riferimento

Figura 70: Vulcan Switch IBM

Coerenza Della Memoria Cache in Architetture Multiprocessore

Documents

Transcript of Coerenza Della Memoria Cache in Architetture Multiprocessore