Architettura degli elaboratori

CPU.

3. Sistemi distribuiti, computer distribuiti su un’are geografica estesa come

internet, i messaggi impiegano da 10 a 100 ms.

Multiprocessori

497.

498. Un multiprocessore a memoria condivisa (o semplicemente

multiprocessore) è un calcolatore in cui tutte le CPU condividono una

memoria comune.

499. L’unica proprietà inusuale che ha un multiprocessore è che una CPU

può scrivere un valore in una parola di memoria e trovarvi un differente

valore alla successiva lettura (perché un altra CPU può averla modificata). I

sistemi operativi utilizzati nei multiprocessori sono normali sistemi operativi.

500. Esistono due differenti tipologie di multiprocessori:

Architettura dei Sistemi di Elaborazione 102

501. Multiprocessori UMA (Uniform Memory Access) in cui ogni parola di

memoria può essere letta alla stessa velocità.

502. Multiprocessori NUMA (NonUniform Memory Acess) in cui non tutte le

parole di memoria possono essere lette alla medesima velocità.

UMA

503. UMA con singolo bus

504.

505. I più semplici multiprocessori sono basati su un singolo bus che

interconnette tutte le CPU alla memora condivisa.

506. Una CPU che vuole leggere/scrivere una parola in memoria, se il bus è

occupato, deve attendere che si liberi. Questa architettura funziona bene con

due o tre CPU (il contenzioso sull’accesso al bus può essere gestito

agevolmente). Per poter incrementare il numero di CPU, e quindi di

performance, occorre aggiungere delle ulteriori memorie.

UMA con singolo bus e cache nelle CPU

507.

508. L’aggiunta di una memoria cache all’interno delle singole CPU può

ridurre il traffico sul bus. Il Caching non viene eseguito sulle singole parole di

memoria ma su blocchi di 32 o 64 byte. Quando una parola è referenziata,

l’intero blocco che la contiene chiamato, linea di cache, è caricato nella CPU

che l’ha richiesta. Ogni blocco di cache è contrassegnato come Read-Only o

Read-Write.

509. Se una CPU scrive una parola che è contenuta anche in altri blocchi di

cache remote, l’hardware del bus percepisce la scrittura e lo segnala alle

altre cache che possono avere:

- Una copia “pulita” del blocco di memoria, allora la cache la sovrascrive

con il valore aggiornato

- Una copia modificata del blocco di memoria, allora la cache lo deve

prima trascrivere in memoria e poi applicare la modifica.

510. L’insieme di tali regole, utilizzate per la gestione della cache, è

chiamato protocollo di coerenza della cache.

UMA con singolo bus e CPU dotate di RAM

511.

512. Con l’aggiunta di memorie RAM in un bus interno dedicato per ogni

CPU la memoria condivisa è utilizzata esclusivamente per scrivere variabili

condivise (globali). Questa soluzione riduce il traffico sul bus ma richiede una

Architettura dei Sistemi di Elaborazione 103

collaborazione attiva del compilatore che deve separare gli oggetti locali

(programma, stack, variabili locali, …) da quelle globali.

513.

UMA con crossbar switch

514.

515. Anche con le migliori tecniche di caching, l’uso di un solo bus di

interconnessione limita la dimensione dei multiprocessori UMA a circa 16 o

32 CPU. Per superare questo limite occorre utilizzare un diverso tipo di rete di

interconnessione. Il circuito più semplice che collega n CPU a k memorie è il

crossbar switch. 516.

517. A ogni intersezione tra una linea orizzontale (CPU) e una verticale

(RAM) c’è un crosspoint (“punto di incrocio”). Un crosspoint è un piccolo

interruttore che permette di stabilire il collegamento tra CPU e RAM.

518. Attraverso questo sistema si realizza una rete non bloccante: ad alcuna

CPU è mai vietata la connessione verso una memoria di cui ha bisogno

perché la linea è già occupata.

519. Inoltre non c’è bisogno di alcuna pianificazione anticipata. è sempre

possibile collegare una CPU alla memoria aprendo o chiudendo un

interruttore.

Architettura dei Sistemi di Elaborazione 104

520. Rimane il problema della competizione per la memoria, qualora due, o

più, CPU vogliono accedere allo stesso modulo nel medesimo istante

(partizionando la memoria in n unità, la competizione si riduce di un fattore n

rispetto al modello con bus singolo).

521. Una delle peggiori caratteristiche di questo schema è che il numero

n 2

degli incroci cresce come . Con 1000 CPU e moduli di memoria occorrono

un milione di crosspoints.

522. Costruire un crossbar di queste dimensioni non è fattibile.

UMA con rete di commutazione multilivello

523.

524. Una progettazione di multiprocessori differente è basata

su commutatore 2x2 (due input e output). I messaggi che

arrivano nei due input possono scambiarsi in una due uscite.

525. Ogni messaggio contiene:

- Modulo: quale memoria usare;

- Indirizz: specifica l’indirizzo nel modulo; - Opcode: il

codice di operazione da eseguire; - Valore: il valore

dell’operando.

526. Lo switch utilizza il campo Modulo e lo usa per scegliere dove spedire il

messaggio (su X o Y). Gli switch possono essere organizzati in molti modi per

costruire reti di commutazione multilivello.

527. Una possibilità economica e semplice è la rete omega.

528.

529. In questo caso ci sono 8 CPU connesse a 8 memorie tramite 12

log n

commutatori (switch). Per n CPU e n memorie ci vogliono livelli con

2

Architettura dei Sistemi di Elaborazione 105

n/2 (n/2)log n

commutatori per livello, per un totale di commutatori: è un

2

n 2

numero molto inferiore a , specie per valori grandi di n.

530. Lo schema di connessione di una rete omega è detto shuffle (o

miscuglio) perfetto.

531. Per capire il funzionamento di una rete omega, supponiamo che la CPU

3 (011) voglia leggere una parola dal modulo di memoria 6 (110).

532.

533. Quindi, a differenza dell’interconnessione con crossbar switch la rete

omega è una rete bloccante: non tutti gli insieme di richieste possono essere

processati contemporaneamente.

534. È auspicabile distribuire i riferimenti alla memoria in modo uniforme

rispetto ai moduli. Una sistema di memoria in cui le parole consecutive sono

in moduli diversi è detto interleaved. Le memorie interleaved massimizzano

il parallelismo perché la maggior parte dei riferimenti a memoria è in indirizzi

consecutivi.

535. È sempre possibile progettare reti di switch non bloccanti.

NUMA

536.

537. Con i processori UMA a singolo bus si può arrivare a connettere fino a

12 CPU, con un rete di interconnessione, a cause dei costi dell’hardware, si

può arrivare a connettere insieme meno di 100 CPU.

538. Per eccedere questo valore occorre introdurre una nuova architettura in

cui si rinuncia a qualcosa: che i tempi di accessi della memoria siano

uniformi. In un processore NUMA il tempo di accesso au moduli di memoria

locale è minore rispetto a quello dei moduli remoti.

Architettura dei Sistemi di Elaborazione 106

539. Tutti i programmi che girano su multiprocessori UMA continuano a

girare sulle macchine

540. NUMA, ma naturalmente hanno performance degradate

541. Le macchine NUMA hanno tre caratteristiche chiavi:

- C’è un unico spazio di indirizzamento visibile a tutte le CPU;

- L’accesso alla memoria remota è attraverso istruzioni di LOAD e STORE;

- L’accesso alla memoria remota è più lento dell’accesso rispetto alla

memoria locale.

542. Ci sono due tipi di macchine NUMA:

- No Cache NonUniform Memory Access (NC-NUMA): quando il tempo di

accesso alla memoria distante non è nascosto (perché non c’è caching);

- Cache Coherent NonUniform Memory Access (CC-NUMA): quando sono

presenti cache coerenti.

Multiprocessori NC-NUMA

543.

544. Una macchina NC-NUMA contiene varie CPU, ciascuna dotata di una

piccola memoria cui accedeva tramite un bus locale. Inoltre, le CPU erano

collegate attraverso un bus di sistema.

545. Quando la MMU (opportunamente modificata) riceveva una richiesta di

accesso a memoria, stabiliva per prima cosa se la parola si trovava in

memoria locale. In tal caso la richiesta veniva inoltrata lungo il bus locale per

ottenere la parola. In caso contrario, la richiesta veniva instradata lungo il

bus di sistema verso il processore che conteneva la parola, che rispondeva di

conseguenza. Naturalmente questa seconda evenienza impiegava molto più

tempo della prima.

546. La coerenza della memoria in una macchina NC-NUMA è garantita dal

fatto che non c’è caching. Ogni parola di memoria si può trovare in una sola

locazione, perciò non c’è pericolo che ne esista una copia difforme: non ci

sono copie.

547. D’altro canto, la collocazione di una pagina in memoria diventa molto

importante perché il degrado delle prestazioni dovuto a un cattivo

posizionamento dei dati è molto rilevante.

Architettura dei Sistemi di Elaborazione 107

548.

Multiprocessori CC-NUMA

549.

550. Dover accedere alla memoria remota ogni volta che si fa riferimento a

una parola di memoria non locale vuol dire pagare un alto prezzo in termini

di prestazioni. Se però si aggiunge il caching, bisogna assicurare anche la

coerenza delle cache. Un modo possibile per garantirla è permettere lo

snooping del bus di sistema.

551. L’approccio più comune utilizzato per costruire grandi multiprocessori

CC-NUMA è il multiprocessore basato sulle directory (directory-based

multiprocessor).

552. L’idea di fondo è di mantenere una base dati delle linee di memoria ed

il loro stato. Quando è referenziata una linea di cache, viene interrogata la

base dati per sapere dove si trova e se è pulita o sporca.

553. Poiché ogni istruzione che accede alla memoria interroga questo

database, occorre che sia gestito su un hardware specifico velocissimo.

L’unione di tutte le memorie dei nodi costituisce l’intero spazio di

indirizzamento.

554.

7.e Tipi di sistema operativo multiprocessore

555. Cenni di memoria virtuale

556.

557. All’inizio dell’era informatica, le memorie dei computer erano costose e

poco capienti. In quel periodo, i programmatori impiegavano molto tempo

Architettura dei Sistemi di Elaborazione 108

nel tentativo di “assottigliare” i programmi perché entrassero in memorie

minuscole.

558. La soluzione tradizionale a questo problema era l’uso di una memoria

secondaria, per esempio di un disco. Il programmatore divideva il

programma in un certo numero di pezzi, detti overlay (“ricoprimento”),

ciascuno dei quali poteva entrare in