Programmazione di Sistemi Multicore
Corso di Laurea in Informatica, terzo anno
A.A. 2017-2018, primo semestre
Docente: Irene Finocchi
Ricevimento: mercoledì 9:00-11:00 durante il corso (da confermare via mail prima di venire), per appuntamento al termine del corso. Ufficio: sede di Via Salaria, stanza 345/A. Tel: 06-49918426. E-mail: finocchi AT di.uniroma1.it
|
Orario delle lezioni
Giorno |
Ore |
Aula |
Lunedì |
8:00-10:30 |
Aula 2 - Via del Castro Laurenziano 7A |
Martedì |
8:00-10:30 |
Aula 2 - Via del Castro Laurenziano 7A |
|
|
|
Avvisi
- Proposte di voto
per gli studenti che hanno superato lo scritto nell'appello del 29 gennaio e consegnato entrambi gli homework. Contattatemi entro venerdì 23 febbraio se non intendete accettare il voto. Se non ricevo mail entro venerdì, procederò con la verbalizzazione su Infostud.
- Voti appello 29 gennaio 2018
. A breve pubblicherò le proposte di voto per gli studenti del secondo appello che hanno consegnato entrambi gli homework. Per eventuali domande sul compito, ho fissato un ricevimento per mercoledì 21 febbraio dalle 9:30 alle 11:00.
- Proposte di voto
per gli studenti che hanno superato entrambe le parti scritte entro il primo appello (8 gennaio) e consegnato entrambi gli homework. Contattatemi entro venerdì 9 febbraio se non intendete accettare il voto. Se non ricevo mail entro venerdì, procederò con la verbalizzazione su Infostud.
- Seconda prova intermedia: martedì 19 dicembre, ore 8:00 - 10:30. La prenotazione è obbligatoria.
- L'homework 1 è disponibile a questo link
. Deadline: 30 dicembre 2017.
- Iscrivetevi al Google group
per discussioni sugli argomenti del corso, avvisi e notizie last-minute.
Obiettivi e programma del corso
Il corso affronta problematiche e tecniche di programmazione delle moderne piattaforme di calcolo parallele e distribuite, dai sistemi multicore presenti sui più comuni laptop, desktop e dispositivi mobili, fino alle GPU e alle recenti infrastrutture cloud.
Il parallelismo offre enormi opportunità nello sviluppo di applicazioni con requisiti computazionali stringenti: basti pensare ai benefici in aree come computer graphics e big data computing. Ma un maggior parallelismo nell'hardware risulta inefficace se non è opportunamente sfruttato a livello software. Ciò impone cambiamenti fondamentali nello stile di programmazione e, ad un più alto livello di astrazione, nella progettazione degli algoritmi e delle strutture dati utilizzate. Ad oggi, la maggior parte degli algoritmi sono pensati secondo una visione sequenziale del modello di calcolo soggiacente e i linguaggi di programmazione offrono poche astrazioni per programmare sistemi multiprocessore.
Scopo del corso è di insegnare agli studenti a "pensare in parallelo", rivisitando sia il modo in cui i programmi sono espressi che alcune tecniche algoritmiche tradizionalmente pensate per modelli sequenziali. La prima parte del corso utilizza Java come linguaggio di programmazione e si focalizza su un modello a memoria condivisa con thread espliciti. Presenteremo successivamente tecniche di programmazione di GPU (OpenCL) e - tempo permettendo - di problem solving su cluster a larga scala (MapReduce).
Il corso ha una natura trasversale, coniugando aspetti di algoritmi, linguaggi di programmazione e sistemi. Gli homework svolti faranno acquisire allo studente un'esperienza diretta scrivendo programmi paralleli efficienti in alcuni dei modelli presentati a lezione.
Diario delle lezioni
Lunedì 25 settembre 2017 - Introduzione al corso.
Legge di Moore e implicazioni sullo sviluppo di software (the free lunch is over). Differenza tra
parallelismo e concorrenza.
Martedì 26 settembre 2017 -
Speedup ed efficienza. Limiti teorici e pratici del parallelismo:
legge di Amdahl,
legge di Gustafson, overhead di comunicazione e sincronizzazione.
Esercizi di riepilogo (A)
Prova intermedia del 3 novembre 2015. Traccia A: domanda 1, domanda 2 punti 1 e 2. Traccia B: domanda 2 punto 1
Appello gennaio 2016. Domanda 1 punti a) e c)
Appello febbraio 2016. Domanda 1
Prova intermedia novembre 2016. Domanda 1, parte A
Lunedì 2 ottobre 2017 -
Sistemi paralleli: tassonomia di Flynn, modello di comunicazione (sistemi distribuiti o a memoria condivisa, NUMA vs UMA).
Modelli di programmazione: memoria condivisa con thread espliciti, cenni a scambio di messaggi, dataflow e data parallelism.
Java.lang.Thread: nozioni fondamentali. Parallel hello world. Soluzione domanda 1A prova intermedia novembre 2016.
Martedì 3 ottobre 2017 - Parallelismo
fork/join in Java. Un primo esempio: somma degli elementi in un array.
Esperimenti al calcolatore. 1) Alcuni problemi pratici: come aumentare la dimensione dell'heap, perché iterare un esperimento, come misurare i tempi di esecuzione
real,
user e
system con il comando time. 2) Un primo esperimento:
cosa accade all'aumentare del numero dei thread? Analisi dello speedup ottenuto in pratica: perché all'aumentare del numero di thread i tempi di esecuzione possono aumentare considerevolmente?
Memory bottleneck. 3) Un secondo esperimento:
computazioni memory- o CPU-bounded, differenze ottenute in termini di speedup (nel codice per la somma degli elementi di un array, decommentate la linea ans += (long)... nel metodo run). Soluzione domanda 1 appello febbraio 2016.
- Slide
della lezione
- Parallel sum
: implementazione, sintesi degli esperimenti e delle analisi svolte
Lunedì 9 ottobre 2017 - Scelta del
numero di thread: portabilità del codice, thread vs processori: è una buona idea usare tanti thread quanti sono i
processori disponibili all'inizio dell'esecuzione?
Load balancing. Una diversa soluzione:
divide-and-conquer parallelism. Implementazione ricorsiva della somma in un array tramite fork di un nuovo thread per ciascuna chiamata ricorsiva. Quanti thread nell'implementazione ricorsiva? Un semplice conteggio su alberi binari. Due importanti ottimizzazioni:
cutoff sequenziale e
dimezzamento del numero di thread.
Lunedì 16 ottobre 2017 - La
libreria Java ForkJoin: ForkJoinPool, RecursiveAction e RecursiveTask<V> 3) Due utili astrazioni:
map e
reduce, implementazione con thread espliciti tramite ForkJoin, cenni al framework MapReduce di Google. 4)
Strutture dati e parallelismo: array, alberi bilanciati, liste collegate.
Martedì 17 ottobre 2017 - Analisi di algoritmi paralleli: il
DAG di esecuzione,
work e
span, ovvero
T1 (numero di nodi) e
T∞ (lunghezza del cammino critico). Generalizzazione delle analisi ad un numero arbitrario P di processori.
Lower bound:
TP ≥
max{T1/P, T∞}. Come ottenere un'esecuzione che richiede tempo
O(T1/P+T∞): l'importanza dello scheduling, gli
scheduler greedy funzionano bene! Analisi 2-approssimazione, cenni al work stealing.
- Slide
della lezione
- L'analisi dello scheduling greedy si basa sul Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (3rd edition). Il capitolo su algoritmi multithreaded può essere scaricato gratuitamente a questo link
(sample chapter).
Esercizi di riepilogo (B)
Prova intermedia del 3 novembre 2015. Traccia A: domanda 3, domanda 2 punto 3. Traccia B: domanda 1, domanda 2 punto 2, domanda 3
Appello gennaio 2016. Domanda 1 punto b), domanda 2
Appello febbraio 2016. Domanda 2
Prova intermedia novembre 2016. Domanda 1, parte B, domanda 2, domanda 4
Lunedì 23 ottobre 2017 -
Somme prefisse: definizione del problema, work e span dell'algoritmo sequenziale, due algoritmi paralleli con span O(log n). Un'applicazione delle somme prefisse:
array packing.
Martedì 24 ottobre 2017 - Un'applicazione del packing:
partitioning. Un'applicazione del partitioning:
parallel quicksort. Analisi del quicksort nel caso peggiore e migliore,
equazioni di ricorrenza per work e span.
Parallel mergesort. Analisi della parallelizzazione naive (con merge sequenziale). Fusione (ricorsiva) di due array in parallelo: analisi di work e span dell'algoritmo merge. Integrazione nel mergesort ed analisi.
Esercizi di riepilogo (C)
Prova intermedia del 3 novembre 2015. Traccia A: domanda 4. Traccia B: domanda 4.
Appello gennaio 2016. Domanda 3.
Appello febbraio 2016. Domanda 3.
Prova intermedia novembre 2016. Domanda 3.
Appello 28 giugno 2017. Tutta la parte 1.
Appello 10 gennaio 2017. Tutta la parte 1.
Martedì 31 ottobre 2017 - svolgimento di
esercizi di preparazione alla prova intermedia
Lunedì 6 novembre 2017 - svolgimento di
esercizi di preparazione alla prova intermedia
Martedì 7 novembre 2017 -
prova intermedia
Lunedì 13 novembre 2017 -
Programmazione concorrente: accessi alla memoria sovrapposti,
bad interleaving, il problema della
mutua esclusione.
Lock come ADT: caratteristiche di un mutex e di un reentrant lock. Concorrenza in Java: la keyword
synchronized.
Martedì 14 novembre 2017 -
Race condition:
bad interleaving vs.
data race. Metodi reader e metodi writer, possibili
interleaving tra le istruzioni (quali istruzioni? A che livello di astrazione? Il ruolo del compilatore), uso di synchronized,
stati intermedi inconsistenti. La keyword
volatile: quando è corretto usarla? Una distinzione fondamentale:
memoria thread-local,
immutable e
synchronized.
Lunedì 20 novembre 2017 -
Linee guida per usare i lock correttamente.
Locking consistente, granularità dei lock (
fine vs coarse grained locking),
granularità della sezione critica e il problema
A-B-A. Deadlock: tecniche di
deadlock avoidance (acquisizione ordinata dei lock).
Martedì 21 novembre 2017 - Lock in pratica: un esempio basato su
liste concorrenti. Coarse-grained locking. Fine-grained
hand-over-hand locking: perchè serve prendere il lock su elementi consecutivi della lista, esempio relativo alla rimozione di un nodo della lista. Ulteriori meccanismi di sincronizzazione:
reader/writer locks.
Esercizi di riepilogo (D)
Esonero dicembre 2015. Domande 1 e 2.
Appello gennaio 2016. Domande 4 e 5.
Appello febbraio 2016. Domande 4 e 5.
Lunedì 27 novembre 2017 - Ulteriori meccanismi di sincronizzazione:
condition variables. Come implementare una
attesa passiva, le operazioni
wait,
notify (signal) e
notifyAll (broadcast), errori di programmazione tipici (e soluzioni), costrutti ed idiosincrasie di Java. Correzione del primo homework e visione compiti.
Martedì 28 novembre 2017 -
Heterogeneous computing: CPU vs GPU, genesi di
OpenCL. Architettura di una GPU,
platform model,
execution model e
memory model in OpenCL. Concetti fondamentali: host, compute device, compute unit, processing element, contesto, programma, kernel, work item, work group, coda dei comandi, tipi di memoria (host, private, local, global).
API OpenCL: ottenere informazioni sui dispositivi, creazione del contesto e della coda dei comandi.
Lunedì 4 dicembre 2017 - didattica sospesa per IT Meeting
Martedì 5 dicembre 2017 - Ancora
API OpenCL: memory objects, program objects, kernel objects, gestione delle code dei comandi. Un primo esempio, con discussione dettagliata del codice host: OpenCL Hello World. Discussione dettagliata del
layout di memoria: quali dati risiedono in memoria host, globale, privata?
Task parallelism e
data parallelism in OpenCL: le funzioni
clEnqueueTask e
clEnqueueNDRangeKernel.
- Slide
della lezione
- Il codice del programma hello è contenuto nel tar gzippato disponibile nella sezione "Libri di testo e materiale didattico"
Martedì 12 dicembre 2017 - Parallelismo su
dati di input ad una dimensione: numero di
work items e
dimensione dei work group (global e local size).
Esempio al calcolatore: calcolo parallelo dei quadrati dei valori contenuti in un array (square).
- Slide
della lezione
- Il codice del programma square è contenuto nel tar gzippato disponibile nella sezione "Libri di testo e materiale didattico"
Libro di testo e materiale didattico
- Dan Grossman, A Sophomoric Introduction to Shared-Memory Parallelism and Concurrency
, reading notes, febbraio 2015.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, Introduction to Algorithms
, terza edizione, capitolo 27 (Multithreaded Algorithms, sample chapter scaricabile gratuitamente sul sito web del libro).
- Codice OpenCL contenente tutti gli esempi visti in classe
- Macchina virtuale
contenente una distribuzione Linux Slitaz minimale (32 bit) con OpenCL 1.2 preinstallato, read me. Per poter utilizzare la macchina virtuale è necessario installare VirtualBox (disponibile sul sito di Oracle).
Modalità e date d'esame
Per superare l'esame si devono svolgere due
homework che saranno assegnati durante il corso e sostenere una
prova scritta.
Gli homework sono esercizi implementativi (uno in Java, l'altro in OpenCL) e possono essere svolti in gruppi costituiti da al più 3 persone.
Nella prova scritta occorrerà dimostrare di aver studiato e compreso gli argomenti trattati nelle lezioni del corso:
- rispondendo a tipiche domande da esame orale volte a verificare la comprensione della materia;
- svolgendo semplici esercizi di ragionamento che prevedono l'applicazione dei concetti esposti a lezione.
Non è previsto un esame orale, salvo su esplicita richiesta del docente in caso di sospetta copiatura - parziale o totale - degli homework o della prova scritta.
Prove intermedie. Sono previste due prove intermedie: la prima nella settimana di interruzione della didattica (tipicamente inizio novembre), la seconda al termine del corso. La prima prova intermedia riguarderà tutti gli argomenti svolti fino alla data della prova stessa e sarà strutturata come la prova scritta, ovvero con domande aperte ed esercizi di ragionamento. La seconda prova intermedia coprirà gli argomenti svolti nella seconda parte del corso. La sufficienza ottenuta alle prove intermedie sarà valida fino all'ultimo appello dell'anno accademico di riferimento.
Voto. Sia gli homework che la prova scritta concorrono a determinare il voto finale. Quest'ultimo verrà inoltre incrementato di un punto per chi termina nella sessione invernale avendo superato la prova intermedia.
Prenotazioni. Per partecipare alle prove scritte (inclusa quella intermedia) è obbligatoria la prenotazione. Sarà possibile prenotarsi agli appelli d'esame tramite infostud, e alla prova intermedia tramite twiki.
Prove d'esame