Il Supercalcolo
Architetture dei sistemi di calcolatori
Tassonomia di Flynn




SISD: Single instruction, single data
SIMD:Single instruction, multiple data
MISD: ??
MIMD
 Multiprocessore
 UMA: Uniform Memory Access
 COMA: Cache Only Memory Access
 NUMA: Not Uniform Memory Access
 Multicomputer
 MPP: Message Passing Processor
 COW: Cluster of Workstation
UMA
 L’accesso alla memoria è uniforme
 Architettura a Bus
 Sul Bus sono attestati i processori, le
memorie e gli eventuali bridge (PCI, SCSI …)
 Il problema è il mantenimento della
coerenza dei dati tra le caches
 Cache write through (pesante per il bus)
 Snooping Cache
 Cache write back con protocollo MESI
UMA
 Il bus diventa il collo di bottiglia
 Usare uno Split Transaction Bus migliora le
prestazioni ma non troppo
 Esistono anche reti di interconnessione Crossbar
Switch tra processori e memorie ma devo
aggiungere uno snooping bus per la coerenza delle
cache
 Importante la disposizione dei dati nelle memorie
 Queste sono soluzioni estreme che costano molto
UMA
 Potrei usare una rete multistage ma:






Costano comunque
Non standard
Ritardo aggiuntivo degli stages
Più bloccanti degli altri
Risoluzione confitti
Problemi di routing
UMA: e il S.O.?
 Varie soluzioni per il kernel
 Master/Slave: un processore dedicato al
S.O.,gli altri solo applicazioni
 Separate Executive: ogni processore fa girare
una copia separata del S.O.
 Simmetric Multi Processing: il S.O. gira dove
capita => necessari punti di sincronizzazione
nel kernel
NUMA
 Ogni processore ha la sua memoria e accede
più velocemente lì
 È una soluzione scalabile: posso arrivare fino a
migliaia di processori
 Non causano problemi
 Bandwidth tra CPU e memoria: si ingrandisce
automaticamente
 Latency: più o meno costante
 Cost: crescita lineare
 Phisical: problemi fisici (consumi, raffreddamento…)
NC-NUMA
 No Cache NUMA
 Metto in cache solo quello che ho nella
mia memoria
 Cruciale il piazzamento dei dati tra le
memorie
CC-NUMA
 Cache coherent NUMA
 Come garantisco la coerenza?
 Meccanismi directory based
 Directory memory-based
 L’elemento di directory, associato a una linea di
memoria ha un array di processori dove è il dato
 Directory cache-based
 Lista linkata tra i processori
COMA
 Cache only memory access
 Esistono solo cache
 Non usate
 Problema dell’ultima copia
 Problemi vari
Multicomputer
 Caratterizzati dal Message Passing
 Importante la rete di interconnessione
Rete di interconnessione: caratteristiche
 Topologia
 Diametro: distanza max o media tra due
nodi
 Bisection bandwidth: la larghezza di banda
che attraversa ogni bisezione della rete
 Dimentionality: numero di percorsi
alternativi (per la fault tolerance)
Rete di interconnessione
 Problemi di Routing
 Store & forward è troppo lento
 Cut Through
 Decido sul routing all’inizio del messaggio
 Se incontro un ostacolo
 Virtual cut through: il messaggio si ammassa nel
nodo ostacolo
 Wormhole routing: blocco tutto e il messaggio
resta spalmato su più nodi
Routing
 Tipo di decisione di routing
 Aritmetico
 Decisione matematica a partire dall’indirizzo del
destinatario
 Topologia fissa e semplice
 No fault tolerance
 Souce based
 La sorgente precalcola il percorso
 Table driven
 Gli algoritmi deterministici usano male la rete
 Problemi di velocità
 Rischio deadlock
I/O ad alte prestazioni
 Due orientazioni:
 Mass transfer: sequenziali e “prevedibili”
 Importante il transfer rate
 Transaction processing
 Importante l’access time
I/O ad alte prestazioni
 Anche i dischi crescono esponenzialmente
 Nella densità (lineare e per traccia)
 Meno nelle prestazioni
 Sia in terminio di seek time che di transfer
rate
 Problematico perché intervengono
problematiche fisiche (velocità di rotazione
dei dischi e movimento dei bracci)
I/O ad alte prestazioni
 Non blocking I/O (read)




Read anticipato
Chiamata bloccante dopo
Serie di chiamate non bloccanti
Call back signal (interrupt software)
 O/S Bypass
 Comunicazione diretta tra dispositivi e
applicazioni
 Pinning della memoria: divieto di paginazione
I/O ad alte prestazioni
 Parallelismo: più dischi
 Striping: suddivido i dati a strisce su più dischi
 Stripe factor: numero dischi
 Stripe depth: quanto è grande l’unità di suddivisione
dati
 RAID:
 Redundant Array of Independent – Inexpensive
Disk
 Fault tolerance (duplicazione e controlli di errore)
Tecnologia RAID
 RAID 0:




Separo i dati su più dischi
Parallelizzo le letture
Bene per i mass transfer
Bene per i transazionali
Tecnologia RAID
 RAID 1




Mirroring
Raid 0 duplicato
Fault tolerance perché ho duplicazione
Non miglioro le prestazioni in lettura
Tecnologia RAID
 RAID 2





Su alcuni dischi metto la codifica di Hamming
Poco usata
Costa e richiede sincronizzazione bit a bit
Bene solo per i mass transfer
Coda delle transazioni poco parallelizzabili
Tecnologia RAID
 RAID 3
 Come level 2 ma con la parità e non bit a bit
 L’hamming code crea gli svantaggi come in
RAID 2
Tecnologia RAID
 RAID 4
 Parità blocco a blocco su un disco
 Bene per il transfer rate
 Operazioni durante la modifica:
 Leggere old data
 Leggere old parity
 Old data (XOR) old parity per avere la parità degli altri dischi
 Trovare la nuova parità
 Store data
 Store parity
 Male per le transazioni: gli aggiornamenti delle parità sono
serializzati
 Mai usati
Tecnologia RAID
 RAID 5
 Come RAID 4 ma i blocchi di parità sono distribuiti
sui dichi
Tecnologia RAID
 RAID 6 o RAID DP
 Doppio meccanismo di ridondanza con bit su
dischi distinti
 Schema bidimensionale
Tecnologia RAID
 RAID 1-0
 Doppia virtualizzazione
 È un array RAID 0 di dischi virtuali, ogni disco
è un RAID 1
 RAID 0-3
 È un array RAID 0 di dischi virtuali e ogni
disco è un RAID 3
SCSI
 Il problema si sposta sull’I/O interconnect
 Small Computer System Interface
 Protocollo di comunicazione verso periferiche
generiche
 Bus o catena SCSI con indirizzamento
(settato a mano)
 Transazioni I/O di tipo Split Transaction
Esempi reali
 HIPPI
 SUPER HIPPI
 HPN: High performance Network
 SAN: System Area Network
 Fast Ethernet-Gigabit Ethernet
 Myrinet
 Fibre Channel
 NASD: Network Attached Storage Device
Constellation
 Nome “esotico” per un CC-NUMA
 Cluster di pochi nodi con molti processori
per nodo
COW
 Cluster Of Workstation
 Un insieme di calcolatori indipendenti e di
tipo COTS che cooperano per ottenere
alte prestazioni su un grosso problema (o
un grosso insieme di problemi)
 Indipendenti perché funzionano anche
fuori dal Cluster
 COTS: componenti “di serie”
Cluster
 Obiettivi:





Fault Tolerance
Scalabilità di costo
Scalabilità di prestazioni
Orientati al supercalcolo
Orientati al superlavoro transazionale
Caratterizzazione





Ruolo dei server aggiuntivi: attivo o passivo
Connessione ai dischi: interni ai nodi o nodo storage
Condivisione dati: shared nothing o shared data
Accesso ai dati: Read Only o Read & Write
Visione amministrativa: single image o configurazioni
separate
 Visione al programmatore: programmazione tradizionale
o message passing
 Visione esterna: Fuori (alle altre macchine) vedo la
molteplicità?
 Disposizione geografica: Locale o sparpagliata?
Esempi
 A mano!
 Download da Tucows o Download.com
 Seti@home o cracking codici
 HTTP redirect
 Rotating DNS
 Prodotti di load balancing