Theory

Question 1

Cosa si intende per parallelismo?

Answer 1

Esecuzione di diverse parti di un programma allo stesso tempo. Su unità computazionali differenti (es . threads, processori, cores di gpu)

Question 2

Definizione di Throughput

Answer 2

Tasks completati per unità di tempo

Question 3

Definizione di sequential task

Answer 3

Insieme di operazioni eseguibili su un computing device.

Question 4

Definizione di overhead

Answer 4

Tempo per setuppare la computazione parallela (es. possono essere tempo per dividere un programma sequenziale in task paralleli, ecc.) questo valore non è ovviamente presente quando effettuiamo stessi task in modo sequenziale.

Question 5

Definizione Latenza

Answer 5

Tempo tra invio di un task ed effettivo output. L

Question 6

Definizione di Service Time

Answer 6

Tempo per completare un task, da quando inizia elaborazione, quindi non considero tutto discorso di merge e split. Ts

Question 7

Definizione di completion time

Answer 7

Data una serie di task, è tempo tra invio del primo task e completamento dell’ultimo. Tc

Question 8

Come viene misurato throughput

Answer 8

Misurato come 1/Ts. Ossia numero di tasks completati per unità di tempo.

Question 9

Definizione Speedup

Answer 9

sp(n) = sequential time/ parallel time(con n workers)

Question 10

Definizione di scalabilità

Answer 10

scalab(n) = Tpar(1)/Tpar(n) dove valutiamo esecuzione parallela con 1 worker.

Question 11

Come misurare Efficienza

Answer 11

e(n) = tempo ideale/T par(n) . Dove tempo ideale è dato da T sequenziale/numero di workers. dato che nella formula finale Tempo sequenziale/Tempo parallelo = speedUp possiamo trasformare formula in speedup(n)/n

Question 12

Spiega Amdahl law

Answer 12

In un’applicazione amount di lavoro non parallelizzabile determina massimo speedup per parallelizzare applicazione.

Question 13

Spiega Gustaffsomn law

Answer 13

Se Amdahl law ci da un upper limit per lo speedup che possiamo ottenere. Con Gustaffsomn invece sappiamo che possiamo aumentare la dimensione del problema per poter diminuire portata della parte non parallelizzabile.

Question 14

Cosa è work span model

Answer 14

Un’applicazione può essere vista come un grafo , in cui i nodi sono porzioni di codice e gli archi rappresentano le dipendenze tra i vari nodi. Il modello viene chiamato work span, dove gli span rappresentano il cammino + lungo tra inizio e fine di un lavoro. Corrispondente al tempo totale per completare il lavoro.

Question 15

Cosa migliorano design patterns?

Answer 15

Data parallel decrementa latenza, stream parallel incrementa throughput.

Question 16

Cosa fanno data parallel patterns?

Answer 16

Dividono dati, computano pezzi e poi ricompongono.

Question 17

Analisi del map pattern

Answer 17

Prendo dati da una collezione, divido il lavoro ed ogni unità computazionale eseguirà la stessa operazione in modo indipendente sui dati. La latenza è uguale a numero di elementi*Tempo applicazione funzione diviso numero di workers + tempo di merge + tempo di split. mentre service time = max tra tempo di split, tempo per applicare funzione e tempo per mergiare.

Question 18

Analisi del reduce pattern

Answer 18

Il reduce pattern permette la sommarizzazione degli input in un unico oggetto. La latenza è uguale al tempo di split + log in base 2 del numero di tasks * tempo di completamento di un task. Questo perchè andiamo a creare struttura ad albero. Service time invece = max tra tempo per split e tempo di esecuzione di un task.

Question 19

Analisi stencil pattern

Answer 19

Prendiamo una funzione che prende come input un elemento + vicini e una funzione che sarà eseguita su questi elementi.
Implementazione:
Metodo 1: uso due buffer uno per lettura altro per applicare funzioni.
Metodo 2: Un solo buffer, che implica managment diverso, come sezioni del buffer indipendenti ecc…
Latenza= tempo per splittare + numero di iterazioni * ( m / nworkers * tempo operazione interna stencil + tempo merge) se usiamo metodo 2 contiamo anche gestione del buffer, mentre con metodo 1 tempo per swap buffer. Service time invece = max tra Tempo split, tempo work e tempo merge.

Question 20

Analyze map reduce

Answer 20

Con map reduce noi prendiamo un file di input per esempio, con i vari dati effettuiamo un operazione di mapping che all’inizio restituisce key value, ordiniamo i risultati in modo da rendere piu efficiente fase successiva di reducing che grazie alle coppie key value effettua velocemente operazioni, infine calcoliamo risultato finale.

Question 21

Analizza Pipeline

Answer 21

Nella pipeline abbiamo vari stages, input di ogni stage è output di un altro stage

Question 22

Analizza Farm

Answer 22

Nella farm abbiamo n workers che eseguono stessa funzione su elementi di input stream. Gli elementi sono assegnati da un emitter e ed infine collezionati da un collector c.

Question 23

Trade off da tenere in considerazione quando facciamo parallel programming?

Answer 23

Tempo speso per setup, tempo guadagnato con parallelismo. Aumentano/diminuiscono in base al numero di workers.
Se Tset > Tpar è inutile parallelismo.

Question 24

Quali overhead abbiamo?

Answer 24

Thread, NUMA, cache coherence, false sharing, Migration due over heat,communication.

Question 25

Creazione e join dei threads overhead e come migliorare

Answer 25

Thread ovviamente porta a overhead, ma utilizzando una thread pool possiamo migliorare.

Question 26

Cache e principi di locality

Answer 26

La cache ad oggi funziona seguendo due principi: spaziali se leggiamo da x, prob leggeremo da posizione vicina. Se accediamo ad un dato potremmo riaccedere dopo poco. per avere del buono codice parallelo ci conviene seguire questi principi, per esempio mettendo dati da eleborare per un thread in un singolo chunk

Question 27

Cosa è NUMA overhead?

Answer 27

Non uniform memory access, indica quando poichè i core non possono comunicare direttamente, si accede a memoria Ram.

Question 28

Cache coherence overhead

Answer 28

Poichè solo alcuni livelli di cache condivisi tra cores, bisogno che ci sia hardware che si assicuri dopo ogni scrittura che la cache line per tutti i cores sia aggiornata. Ovviamente questa operazione che porta overhead.

Question 29

False sharing overhead

Answer 29

Abbiamo una memory line dove ci sono due variabili a e b. Due diversi thread sono responsabili uno per a e uno per b. Ad ogni modifica di a viene aggiornata la line anche per il thread responsabile di b e viceversa. Si risolve facile con padding.

Question 30

Overhead per overheat

Answer 30

Quando core troppo caldo cpu potrebbe spostare in auto thread ad altro core con conseguente overhead dovuto a spostamento. Con sistem call possiamo forzare ad utilizzare thread specifico.

Question 31

Communication Overhead e come migliorare

Answer 31

La comunicazione tra threads come per esempio in una pipeline se avviene su cores differenti porta ad overhead. Triplo buffer aiuta a nascondere overhead. Es. uno per output, uno per input da altri cores, mentre abbiamo un thread per la gestione di quest’ ultimo buffer che copia i dati in un terzo buffer quando sono stati ricevuti.

Question 32

Come gestire memoria condivisa per evitare overhead?

Answer 32

Dato che dovremmo gestire con lock/unlock e creare overhead, quello che ci conviene fare è usare chunks di memoria, per ogni thread, con cui gestire il tutto.

Question 33

metodi per static load balancing

Answer 33

Block distribution dove creiamo numero di blocchi di mem/numero di threads blocchi. Downside ovviamente ultimo blocco dimensione minore.
Cyclic distribution chunks di dim k che assegnamo in modo ciclico ai threads. Downside perdiamo caratteristiche di spazialità. (Meno efficienti in memoria)

Question 34

metodi per dynamic load balancing

Answer 34

Auto scheduling: viene richiesto il lavoro quando thread libero. Overhead di comunicazione soprattutto con rete. Leggermente aggirabile mediante utilizzo di triple buffer. + variable chunk size (se vogliamo aggiungere chunks di dimensione sempre minore).
Job stealing, assegnazione statica e quando finisco rubo un job. Problema che ovviamente non so da dove rubare ed avrei bisogno per esempio di dimensione delle code, che per sapere porterebbe ad overhead. Metodo smart prendo coda random evitando overhead.

Question 35

Come funziona vettorizzazione?

Answer 35

La vettorizzazione permette di eseguire un numero di operazioni contemporaneamente. Dobbiamo utilizzare single instruction multiple data per poter effettuare ops. Quando utilizzate queste ops hw ci da un registro dove i componenti sono una collezione di elementi. Il registro può essere diviso in sub registri, su cui viene eseguita la stessa operazione. Operazione importante che segua queste regole se in un loop, ogni operazione deve essere indipendente dalle successive, non dobbiamo usare funzioni esterne, non dobbiamo avere if, non dobbiamo avere overlapping puntatori. Esempio di unroll the loop.

Question 36

Quando implementiamo un pattern con Template based implementation dobbiamo?

Answer 36

Analizzare target architecture per capire se compatibile. Es. Pipelines hanno bisogno di shared memory non disponibile nativamente su architetture cloud.
Costruire grafo delle attivita concorrenti: grafo dove nodo rappresenta attività concorrente e arco comunicazione tra attività
Stimare performance ottenibile con pattern applicato.

Question 37

Come utilizzare regole di refactoring?

Answer 37

Prima di tutto possiamo rifattorizzare il codice andando a creare delle regole di equivalenza es. pipe(x,y) = comp(x,y). Partendo da queste regole possiamo creare un albero con tutte le possibili soluzioni e valutare parametri come velocità o utilizzo performance. 3 metodi possiamo usare per ottimizzare 1) creiamo alberi di equivalenza e valutiamo migliore secondo parametri scelti. 2) applichiamo regole di rifattorizzazione ad albero originale, in modo da minizzare costi. 3) possiamo usare mix, creo k alberi ma mi fermo ad una profondità m. A partire da questi alberi applico metodo 2.

Question 38

Forma normale per una stream

Answer 38

Per ottimizzare service time: 1) costruisco frontiera con tasks indipendenti. 2) trovo come applicare composition e mettere insieme risultati parziali es. somma[2,3,4] + somma[6,6,7]. 3) costruisco una farm per dividere su macchine differenti lavoro.

Question 39

Come utilizzare performance model?

Answer 39

Valutare una metrica interessata, per ogni nodo partendo dalle foglie. Ottimizzare in base a questa metrica
Automatizzare se necessario: potremmo avere flussi non costanti, es. notte. Quello che facciamo allora: 1)monitor che riceva dati da sensori installati in app. 2) Analisi 3) Azioni da eseguire 4) Eseguire azioni indicate.
Strategie: 1) se tempo tra task aumenta diminuire workers. 2) se tempo tra task diminuisce Aumentare workers. 3) Ovviamente bisogna fare attenzione a non cambiare continuamente strategia. Per fare ciò potremmo aumentare tempo che i sensori devono registrare aumento diminuzione di tempo tra tasks.

Question 40

Come implementare strategie per automatic management?

Answer 40

Eventi che triggerano azioni
Condizioni che fanno partire azioni
Azioni eseguite
Composizione di pattern:
user può dare contratto con specifiche richieste di performance.
Possiamo gestire in due modi contratto.
1) propagazione del contratto applico costraints modificando parametri
2) Mantenere contratto soddisfatto, abbiamo n manager uno per ogni pattern. Che effettua azioni quando servono.

Question 41

Mape con + features non funzionali come fare?

Answer 41

Quando abbiamo + features da tenere in considerazione possiamo 1) usare un solo manager globale che prende decisioni 2) Usare piu manager, uno per feature interessata, questo porta problemi da risolvere nella fase di plan. In questa fase prima di procedere con modifiche nel piano, manager chiede auth agli altri, portando a situazioni dove potrebbe non intervenire.