---
tags: architetture-parallele
---
# Lezione 1 – 02/03/2022
## Esame
esame: 2 opzioni
- scritto + orale (nelle date prestabilite)
- progetto + orale. Il progetto:
- si fa quando si vuole
- si parte da un problema (scelto da me o dal prof)
- si interagisce con il prof (“scopri dopo un mese che era sbagliato”)
- relazione (circa 10 pagine)
- risultati sperimentali sul problema
- come scala all’aumentare nell’input? e nel numero di core? ecc.

Esempi problemi:
- algoritmi su grafi
- algoritmi di AI, ML, Big Data
- algoritmi di algebra lineare

## Introduzione al parallel computing
### Che cos’è?
Che cosa NON è? non è computazione seriale

Comp. seriale:

risolvo un problema/scrivo un programma come una sequenza di istruzioni
con un unico esecutore.

Determinismo:

si sa sempre qual è la prossima istruzione

### Esempio: logistica
Prendi un pacco, Portalo al camion, Caricalo, Torna indietro
1 istr. alla volta, unico esecutore, in ogni istante conosco la prossima istruzione
Per ogni istr., può impiegare un certo tempo. (durata)
La durata complessiva è la somma delle durate singole.
**Come diminuire il tempo globale?**
- assumo un magazziniere più forte e rapido.
- do al magazziniere ad un carrello
- assumo più magazzinieri

Nel calcolatore:
- acquisto CPU più potente/aumento frequenza CPU
- aumento memoria/velocità memoria
- creo una sorta di pipeline, una “coda” di magazzinieri che si passano il pacco

Siamo sicuri che ci serve veramente il parallelismo?
- le idee 1,2 (potenziamento performance) sembra essere la cosa migliore, l’idea è anche sostenuta dalla Legge di Moore (se aspetti abbastanza, arriverà un processore abbastanza veloce da rendere il tuo programma efficiente senza che tu debba cercare l’ottimizzazione parallela)
- velocità aumenta (automaticamente) in modo esponenziale
- diminuendo le dimensioni anche proprio la velocità della luce ci mette di meno

Purtroppo, non è vero:
- è vero che il numero di transistor cresce esponenzialmente
- la tecnologia diventa però più complicata (lastre di silicio più pure possibile, tecnologicamente è più costoso fare chip più densi)
- più vado avanti più ho problemi di riscaldamento ed energia (calore cresce con il cubo del clock), dovrei gestire il raffreddamento. Per questo motivo, c’è anche una sorta di tetto alla frequenza di clock.

Al contrario, il numero di core può crescere (è più vantaggioso fare due core più semplici e lenti che uno più potente). Stesso lavoro (o maggiore) e consumano di meno.
Idea generale: tanti core, molto deboli, che fanno cose semplici ma tutti assieme

**Qual è il contro di avere più core?**
L’algoritmo deve essere progettato per essere parallelo, devo aderire a vincoli dettati dall’architettura, ho punti forti e punti deboli.

**Quali problemi si parallelizzano bene?**
Tutti i lavori che possono essere facilemente “divisi” in sottoproblemi indipendenti.

Parallel computing:

risoluzione di un problema usando più risorse computazionali assieme

ho un programma, lo spezzo in parti
ciascuna parte viene data in esec. ad un esecutore diverso
Al suo interno, ciascuna parte è un’esecuzione seriale
ad ogni istante, ogni esecutore sta eseguendo un’istruzione della sua parte
costo: meccanismo di controllo/coordinamento tra esecutori + devo anche poi combinare le soluzioni in un'unica finale

## Le architetture per la comunicazione parallela
### I processori
- processori multi-core (con bus)
- sistemi multi-nodo (tanti nodi inter-connessi da una rete)
- arch. per domini specifici
- scheda grafica: tantissimi core, molto più semplici di quelli di un processore (dominio elaborazione grafica computazionale, tensor processing unit – cioè ML, processo in parallelo di grosse moli di dati in struttura vettoriale/matriciale, …
- general purpose GPU: usare le GPU per scopi che non c’entrano con la grafica)
- system on Chip: in un unico chip, c’è tutto

### Le memorie
#### Memoria condivisa (shared).
Nel primo si ha unico spazio di indirizzamento accessibile da tutti (e.g., Uniform Memory Access) con la stessa efficienza.

*Problemi*:
ci sono processori che possono accedere alla stessa locazione in contemporaneo => devo disciplinare l’accesso alla memoria.

Inoltre, di solito ogni processore accede alla memoria tramite una cache, che succede quando lo stesso dato sta in cache diverse e si effettua una modifica? Dovrei “invalidare” la cache degli altri!

Problema del false sharing: la cache raccoglie dati della memoria per rendere i dati più accessibili dal processore. Detto ciò, la cache ha una “granularità” (quali “blocchi” di dati?). Se viene modificato un certo sotto-blocco, potrei invalidare l’intero blocco anche se magari non avrei bisogno (e.g., variabili x e y in blocco A, processore 1 modifica x, processore 2 stava lavorando su y e si trova il blocco invalidato anche se non serviva)

#### Memoria distribuita (distributed)
Nel secondo, ogni processore – nodo – ha una sua porzione della memoria. Per avere i dati che stanno in parti di memoria altrui, deve esserci una richiesta tramite messaggio all’altro processore (e.g., Non-Uniform Memory Access).

**Programmazione tramite scambio messaggi**
vantaggio: scalabilità. Il potere computazionale cresce linearmente con numero di nodi
problema: localizzazione dei dati, il programmatore deve premurarsi di far avere i dati al processore che deve elaborarli

### La parallelizzazione di un algoritmo (suddivisione dominio vs task)

**data/domain decomposition**
spezzo i dati, lancio lo stesso programma su porzioni dei dati diverse

Prendere l’algoritmo, individuare task NELLA STRUTTURA DELL’ALGORITMO e li assegno a diversi esecutori (spezzo il problema in sotto-problemi, che fanno proprio cose diverse). Può anche essere che gli esecutori siano eterogenei. Complicazione: non è detto che questi task siano completamente indipendenti, potrebbe esserci “dipendenza dei sotto-problemi”.

Soluzioni ibride (e.g., approccio map-reduce dove ho sia suddivisione del dominio che dei task

#### Prospettiva del problema
Fino a qualche anno fa, il problema del parallelismo era “facciamo architetture parallele”. Non basta => ci sono altri livelli da affrontare:
- i compilatori devono essere predisposti al parallelismo
- i programmatori devono essere consapevoli dell’architettura parallela
- ci devono essere modelli di programmazione e implementazione
- ci devono essere librerie e primitive adeguate

### Algoritmi e performance
Le performance di un algoritmo di solito si misurano come “tempo di computazione”. Altre misure:
- energia che ho consumato, uso di meno risorse, ecc.
- operazioni per unità di tempo (quante istruzioni, quante istruzioni di un certo tipo, quante cose di un certo tipo ho processato in un secondo, ecc.)
- portabilità: quando sviluppo app efficienti per un’architettura non è detto che ottengo le stesse performance su altre architetture, quanta indipendenza c’è dall’architettura sottostante?
- produttività del programmatore: quanto sforzo ci devo mettere per scrivere un certo codice (rapporto sforzo programmatore/efficienza)