Impianti informatici

Impianti informatici

Cap. 1 — Introduzione e concetti di base

Filo conduttore: la molteplicità

Il corso tratta sistemi non monolitici, cioè sistemi composti da più elementi che collaborano. Il passaggio da "mono" a "multi" è il tema centrale di tutto il corso.

Ragioni della molteplicità

• Intrinseca: il mondo reale impone più entità (persone, sedi, oggetti)
• Preferita: si sceglie per ottenere vantaggi rispetto alla soluzione singola

Vantaggi della molteplicità

• Moltiplicazione di capacità (N dischi → N volte la capacità)
• Moltiplicazione di prestazioni grazie al parallelismo
• Specializzazione (componenti dedicati a compiti specifici)
• Scalabilità (aggiunta/rimozione modulare di componenti)
• Fault tolerance: il guasto di un componente non blocca l'intero sistema — impossibile nel caso monolitico

Svantaggi della molteplicità

• Maggiori costi
• Maggiore complessità (progetto, programmazione, gestione)
• Overhead di comunicazione e sincronizzazione
• Costi di gestione della coerenza tra copie multiple

Due casi critici da evitare

Bottleneck e SPOF sono concetti distinti: uno stesso componente può essere entrambi, oppure solo uno dei due.

Definizione generale di impianto informatico

"A collection of processing elements that communicate and cooperate to solve/offer a large set of problems/services fast and reliably."

Architettura astratta: FU + CA + Interconnect

Ogni componente è concettualmente diviso in:

• FU (Functional Unit): svolge l'elaborazione utile
• CA (Communication Assist): gestisce la comunicazione

Le tre famiglie di Interconnect:

• Bus: mezzo broadcast condiviso
• Switch: griglia di collegamenti diretti
• Multistage: struttura con collegamenti indiretti, richiede instradamento

Communication vs. Computation (elaborazione)

• Si chiama elaborazione (computation) tutto ciò che avviene all’interno delle FU.
• Si chiama comunicazione (communication) tutto ciò che avviene “fuori” dalle FU, tramite CA e Interconnect.
• Communication is slower than computation (assunzione modellistica, non fisica)

Communication Abstraction

Ogni CA fornisce alle FU una visione (astrazione) delle operazioni di comunicazione definita da:

1. Quali atti comunicativi sono possibili e con quali vincoli
2. Come denominare gli oggetti (nomi simbolici → oggetti fisici)
3. Quali garanzie di sequenzialità sono garantite

Cap. 2 — Dai costi di comunicazione ai livelli di parallelismo

Costi di esecuzione

Ora sappiamo che i CA si occupano di astrarre i problemi di comunicazione alle FU… risulta utile valutare in modo schematico il costo (tempo) dell’esecuzione di un insieme di operazioni.

Metriche di base

Esecuzione sequenziale

Le N operazioni vengono considerate tutte con latency uguale; e la valutazione diventa molto semplice.

Cost = N × Latency

BW = 1 / Latency

Esecuzione con Pipeline

Ogni operazione divisa in fasi, gli stadi eseguono fasi diverse in parallelo.

BWmin = 1 / Latency (pipeline sempre vuota → caso sequenziale)

BWmax = #stadi / Latency (pipeline sempre piena)

N / BWmax ≤ Cost ≤ N / BWmin

La latency della singola operazione non cambia. Migliora solo la throughput.

Costi di comunicazione

In uno scenario rigidamente sequenziale, la vita di un componente si alterna tra attività di elaborazione e attività di comunicazione.

I costi di comunicazione sono la somma delle durate delle singole operazioni di comunicazione.

Ridurre i costi di comunicazione: Overlap

Per ridurre i costi (percepiti!) di comunicazione si può adottare una tecnica furba!

Se l’attività di comunicazione è delegata ad altri componenti (CA) e nel frattempo la FU può operare liberamente, si ottiene overlap tra le due attività (con riduzione dei costi!).

Idealmente i costi di comunicazione rispetto all’elaborazione possono ridursi a zero.

Quindi si delega la comunicazione al CA mentre la FU continua a elaborare.

• Idealmente i costi percepiti di comunicazione si riducono a zero
• Limiti: setup tra FU e CA, dipendenza della computazione (elaborazione) dal risultato della comunicazione

Tecniche per superare la dipendenza dalla comunicazione:

• Precommunication: avvio le comunicazioni in anticipo rispetto a quando mi servono i dati, in modo da poter procedere con altre attività nel frattempo;
• Multiprocessing/Multithreading: la computazione procede grazie all’alternanza tra diverse attività di elaborazione. Bisogna però fare attenzione ai costi di switch!

Elementi di costo di una comunicazione

Nelle fasi di un'operazione di comunicazione si può individuare costi fissi e costi variabili.

Implicazione: i costi fissi suggeriscono di fare pochi messaggi di grandi dimensioni… ma questo è in contrasto con la precommunication.

Due diversi tipi di trasferimento di dati: Communication vs Replication

Problema della replication: è l’allineamento tra copie multiple (coerenza) che esse rappresentano logicamente un solo dato quindi se uno cambia anche gli altri devono cambiare.

Artifactual Communication

Trasferimenti né necessari né utili — puro overhead. Cause principali:

• Poor allocation of data: dati lontani da chi li usa
• Redundant repeated communication: aggiornamenti inutili
• Unnecessary data in a transfer: si trasferisce più del necessario
• False sharing: il sistema percepisce condivisione inesistente
• Finite replication capacity: cache miss per esaurimento spazio

Legge di Amdahl

Lo speedup è il rapporto tra le velocità di esecuzione sullo stesso carico con due sistemi diversi.

È il “vantaggio” che si ottiene passando da sequenzialità a “parallelismo” grazie all’overlap.

T mono- Speedup= T multi

Gli overhead impediscono il raggiungimento dello speedup ideale ma esso è anche limitato dal fatto che all’interno di un programma ci sono parti non parallelizzabili (per dipendenze che impongono sequenzialità).

Dato che la percentuale parallelizzabile del carico è p:

1. p = percentuale parallelizzabile del tempo di esecuzione di un carico.
2. La percentuale (1− p) non beneficia del parallelismo.
3. Poniamo e supponiamo lo speedup sulla sola parte parallelizzabile: T s= 1 mono par=(1−p)+T p/ s 4) multi par

Quindi: T 1mono =Speedup=- (1−T p)+ p/ smulti par

Da cui segue : 1Speedup ≤- 1− p

Essendo: 1lim Speedup=- 1− ps → ∞par

Conclusione: anche con parallelismo infinito, lo speedup è limitato dalla parte non parallelizzabile del carico. La sequenzialità residua è il vero collo di bottiglia.

Cap. 3 — Dai livelli di parallelismo alle tassonomie

Tre livelli di parallelismo

1. A livello di bit (es. ALU a 64 bit vs 8 bit)
2. A livello di istruzione (ILP — Instruction Level Parallelism)
3. A livello di thread (Thread Level Parallelism)

Nelle architetture moderne i tre livelli coesistono.

Tassonomia di Flynn

Classifica le architetture in base al numero di flussi di Istruzioni e Dati:

• SISD: architettura tradizionale monoprocessore; fully sequential e nessun parallelismo.
• MISD: capace di eseguire più operazioni in contemporanea sullo stesso dato. Teoricamente quasi inesistente
• SIMD: stessa istruzione eseguita su più dati, sono elaborazioni su vettori e matrici, GPU moderne
• MIMD: caso generalissimo di parallelismo thread-level; istruzioni diverse di thread diversi eseguite in parallelo su dati diversi.

SIMD in pratica: GPU

• Il mercato dei videogiochi ha rilanciato le tecniche SIMD
• Le GPU moderne sono processori SIMD general purpose affiancati ai CPU tradizionali

MIMD: suddivisione fondamentale

Multi processore: tante unità di elaborazione lavorano su una memoria condivisa, a cui hanno accesso tutte.

Multicomputer: ciascuna unità lavora con uno spazio di indirizzamento privato. Per comunicare si “scambiano messaggi”.

Tassonomia per la Fault Tolerance (definita dal corso)

Due dimensioni: molteplicità (Single / Multiple / Zero) × ruolo (Active / Idle=scorta)

Tipologie di spare

• Hot spare: acceso e sincronizzato, failover immediato
• Warm spare: parzialmente pronto, failover rapido
• Cold spare: spento, failover lento (richiede avvio)

Non bisogna trascurare il failback: senza ripristino, le scorte si esauriscono progressivamente.

Cap. 4 — Architetture UMA e coerenza della cache

Definizione UMA

Uniform Memory Access: il tempo atteso di ogni accesso alla memoria è uniforme, indipendente dall'indirizzo e dal processore che accede.

• Nel caso mono era scontato; nel multi è un obiettivo da garantire
• Il tempo effettivo può variare (es. per effetti del caching) — l'uniformità è sul tempo atteso

Sottoclassi in base all'interconnessione: bus (caso predominante), crossbar switch, multistage.

Struttura base UMA bus-based

CPU1 CPU2 CPU3 CPU4
| | | |
Cache1 Cache2 Cache3 Cache4
|_____|_____|_____|
BUS
|
RAM

Il bus è il bottleneck principale e uno SPOF dell'architettura.

La cache riduce il traffico sul bus (soluzione già adottata nel caso mono).

Problema della coerenza della cache

Con più processori che hanno cache private, uno stesso dato può essere replicato in più cache → rischio di race condition se non gestito.

Due politiche di scrittura:

Snoopy Cache

Cache dotata di uno snooper: componente che osserva tutto il traffico sul bus, anche se non direttamente coinvolto.

Se lo snooper rileva che un altro processore sta modificando un dato presente nella propria cache:

Automa minimale (2 stati: Valid / Invalid)

• Politica: write-through + write-invalidate
• Concettualmente semplice, ma penalizzante per il bus
• Possibile artifactual communication

Protocollo MESI

4 stati per ogni blocco di cache, implementati in hardware come automa a stati finiti.

Transizioni chiave:

• I → S/E (read miss): si carica il dato; se altri ce l'hanno → S, altrimenti → E
• I → M (write miss): si carica con BusRdX, si invalida nelle altre cache → M
• S → M (write hit): BusRdX, si invalida nelle altre → M (senza ricaricare il dato)
• E → M (write hit): si scrive senza comunicare sul bus (nessun altro ce l'ha) → M
• M → S (altro legge): Flush del dato sul bus → S
• M → I (altro scrive): Flush del dato sul bus → I

Vantaggio di E rispetto a S.

Stato E: esiste apposta per distinguere il caso "nessun altro ha il dato" da S → permette la transizione E→M senza traffico sul bus.

Accessi concorrenti: gestiti tramite il bus come punto di serializzazione + stati transitori (IS→S/E, IM→M, SM→M).

Cache multilivello

Di solito L1, L2, L3:

• L1: più piccola e veloce, più vicina al processore
• L2: intermedia
• L3: più grande e lenta, più vicina al bus — fa le snoopate e le passa ai livelli interni

Compromesso tipico: L1 private + L2/L3 condivisa.

Cap. 5 — UMA: split-transaction bus e altre interconnessioni

Il bus è il principale collo di bottiglia delle architetture UMA perciò cercare di usarlo il meno possibile e riprogettarlo per migliorarne le prestazioni.

Bus atomico

Bus atomico (tradizionale): una transazione occupa il bus ininterrottamente dalla richiesta alla risposta.

Problema nel caso multi: tra richiesta e risposta il bus è occupato ma inutilizzato (attesa della memoria o di un'altra cache). Questo tempo morto è un overhead critico.

Split-transaction

Split-transaction bus: le transazioni vengono divise in fasi separate (es. arbitraggio → richiesta → risposta). Il bus viene rilasciato tra le fasi e può essere usato da altri.

Outstanding requests (richieste pendenti)

• Più richieste possono essere attive contemporaneamente
• Ogni richiesta ha un tag univoco per abbinare la risposta corretta
• Il numero di bit del tag determina il max di outstanding requests
• Buffering necessario: chi richiede deve ricordare le richieste pendenti; chi risponde deve bufferizzare la risposta in attesa di accedere al bus

I buffer si possono riempire.

Conflicting requests (richieste in conflitto)

• Due richieste per lo stesso dato possono essere attive simultaneamente
• Nel bus atomico era impossibile (una alla volta)
• Va gestito esplicitamente: possibile NACK + retry
• Opportunità: una risposta può servire entrambe le richieste

Questioni progettuali del split-transaction bus

1. Suddivisione in fasi: quante fasi, vincoli di ordinamento tra di esse, possibilità di azioni speculative
2. Outstanding requests: quante max totali, quante per singolo processore, ordine delle risposte
3. Conflicting requests: politica di risoluzione, uso del NACK

Crossbar switch (fabric)

P1 P2 P3 P4
M1 [ x . . . ]
M2 [ . x . . ]
M3 [ . . x . ]
M4 [ . . . x ]

• Permette connessioni multiple simultanee tra processori e banchi di memoria
• Maggior parallelismo rispetto al bus
• Problema: la coerenza non è garantita → serve un bus apposito solo per lo snooping

UMA multistage

• Interconnessione a più stadi tra processori e memorie
• La latenza di attraversamento e i conflitti sui percorsi possono pesare sulle prestazioni
• Rimane il problema della coerenza

Limiti di scalabilità degli UMA

Il vincolo di accesso uniforme alla memoria impone interconnessioni non scalabili:

• Numero di processori limitato (tipicamente decine al massimo)
• Il bus rimane bottleneck e SPOF

Cap. 6 — UMA: fault tolerance e sistemi operativi

SPOF nell'architettura UMA

Schema hardware fault tolerant (hardcore)

Obiettivo: rendere la singola CPU non SPOF.

Schema:

• Cache L2 condivisa tra 2 processori
• Inclusione garantita di L1 in L2 + write-through da L1 a L2
• Ogni CPU ha un hardcore (HC): componente resistente ai guasti che recupera i registri e li salva in cache L2 se la CPU si guasta

HC-CPU1 HC-CPU