Programmazione di Sistemi Multicore

Corso di Laurea in Informatica, terzo anno

A.A. 2016-2017, primo semestre

Docente: Irene Finocchi Ricevimento: mercoledì 9:00-10: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:45-10:45 Aula 5 - Via del Castro Laurenziano 7A Martedì 9:00-10:45 Aula 5 - Via del Castro Laurenziano 7A

Avvisi Obiettivi e programma del corso Diario delle lezioni Libro di testo e materiale didattico Modalità e date d'esame Prove d'esame

Avvisi

• Risultati appello 6 giugno 2017: parte 1, parte 2

• Risultati appello 31 gennaio 2017: parte 1, parte 2

• Data verbalizzazioni (esoneri e appelli invernali): 15 febbraio, Aula Seminari (via Salaria 113), 9:30.

• Risultati appello 10 gennaio 2017: parte 1, parte 2

• Appelli invernali: i due appelli si svolgeranno il 10 e il 31 gennaio, alle ore 9:00, in Aula 13. E' obbligatoria la prenotazione su Infostud. La prova sarà divisa in due parti: chi deve sostenere solo la seconda parte può presentarsi direttamente alle 10:30.

• Voti esonero 2. Gli studenti che hanno superato entrambi gli esoneri e hanno consegnato (o sono in procinto di consegnare) gli homework, possono prenotarsi in uno degli appelli aperti su Infostud per la verbalizzazione. Comunicherò dopo la valutazione degli homework i voti definitivi e una data verbalizzare.

• Voti esonero1 (traccia A e B). Sto ultimando la correzione dell'esonero del 22 dicembre, i risultati entro pochi giorni. Ricordo che superare l'esame con gli esoneri comporta un bonus sul voto (da aggiungere dopo la valutazione degli homework, in fase di verbalizzazione).

• Homework 2: descrizione, modalità di svolgimento e di consegna.

• Il secondo esonero si svolgerà martedì 20 dicembre dalle 8:30 alle 11:00 in Aula 5. Prenotatevi al seguente link

• Homework 1. Alcune istanze su cui testare il codice sono le seguenti:
  • debugInstances.tar.gz: istanze di Sudoku utili per il debugging. Le istanze game0.txt, game1.txt e game2.txt hanno una soluzione unica, mentre game3.txt ha 50142 soluzioni
  • Screenshot di una esecuzione: Screenshot game3
  • test1.tar.gz: benchmark 1
  • test2.tar.gz: benchmark 2

• Soluzioni degli esercizi

• Preparazione esonero: in aggiunta a questi esercizi, alla prova intermedia di novembre 2015 (traccia A e B) e alla parte 1 delle prove d'esame di gennaio e febbraio 2016, potete svolgere gli esercizi disponibili sul sito di Grossman (limitandovi alla parte di programma svolta finora nel corso).

• Foglio di prenotazioni per la prova intermedia dell'8 novembre. La prenotazione è obbligatoria e va fatta entro il 6 novembre.

• 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ì 26 settembre 2016 - Introduzione al corso. Legge di Moore e implicazioni sullo sviluppo di software (the free lunch is over). Differenza tra parallelismo e concorrenza.

• Slide della lezione
• The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software, articolo di Herb Sutter apparso in Dr. Dobb's Journal, 30(3), Marzo 2005.

Martedì 27 settembre 2016 - Speedup ed efficienza. Limiti teorici e pratici del parallelismo: legge di Amdahl, legge di Gustafson, overhead di comunicazione e sincronizzazione.

• Slide della lezione

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

Lunedì 3 ottobre 2016 - 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. Parallelismo fork/join in Java. Un primo esempio: somma degli elementi in un array.

• Slide della lezione

Martedì 4 ottobre 2016 - 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).

• Somma degli elementi di un array in parallelo: implementazione naive usata a lezione
• Sintesi degli esperimenti e delle analisi svolte in aula

Lunedì 10 ottobre 2016 - 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. Svolgimento degli esercizi di riepilogo A.

• Slide della lezione

Martedì 11 ottobre 2016 - 1) Quanti thread nell'implementazione ricorsiva? Un semplice conteggio su alberi binari. Due importanti ottimizzazioni: cutoff sequenziale e dimezzamento del numero di thread. 2) 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.

• Slide della lezione

Esercizi di riepilogo (B)
Prova intermedia del 3 novembre 2015. Traccia A, domanda 3. Traccia B, domanda 1 e domanda 3.

Lunedì 17 ottobre 2016 - Analisi di algoritmi paralleli: il DAG di esecuzione, work e span, ovvero T₁ (numero di nodi) e T_∞ (lunghezza del cammino critico). Generalizzazione delle analisi ad un numero arbitrario P di processori. Lower bound: T_P ≥ max{T₁/P, T_∞}. Come ottenere un'esecuzione che richiede tempo O(T₁/P+T_∞): l'importanza dello scheduling, gli scheduler greedy funzionano bene! Analisi 2-approssimazione, cenni al work stealing. Esercizi (applicazione delle leggi di Moore e di Amdahl).

• 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).

Lunedì 24 ottobre 2016 - 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.

• Slide della lezione

Martedì 25 ottobre 2016 - 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.

• Slide della lezione

Lunedì 31 ottobre 2016 - ponte per la festa di Ognissanti

Lunedì 7 novembre 2016 - svolgimento di esercizi di preparazione alla prova intermedia

Martedì 8 novembre 2016 - prova intermedia

Lunedì 14 novembre 2016 - 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.

• Slide della lezione

Martedì 15 novembre 2016 - 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.

• Slide della lezione

Lunedì 21 novembre 2016 - 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).

• Slide della lezione

Esercizi di riepilogo (C)
Esonero dicembre 2015. Domande 1 e 2.
Appello gennaio 2016. Domanda 4.
Appello febbraio 2016. Domande 4 e 5.

Lunedì 28 novembre 2016 - 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.

• Slide della lezione

Martedì 29 novembre 2016 - 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. Svolgimento esercizi: domanda 2 esonero dicembre 2015; domanda 4 appello febbraio 2016.

• Slide della lezione

Esercizi di riepilogo (D)
Esercizi 6, 7, 8 e 9 dal sito di Grossman

Lunedì 5 dicembre 2016 - 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.

• Slide della lezione
• OpenCl 2.0 quick reference card
• OpenCL 2.0 specification
• La macchina virtuale con OpenCL è disponibile nella sezione "Libri di testo e materiale didattico"

Martedì 6 dicembre 2016 - ore cedute al corso di Automi, calcolabilità e complessità (professoressa Fachini)

Lunedì 12 dicembre 2016 - 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ì 13 dicembre 2016 - Esempi al calcolatore. 1) Calcolo parallelo dei quadrati dei valori contenuti in un array (square). Parallelismo su dati di input ad una dimensione: numero di work items e dimensione dei work group (global e local size). 2) Moltiplicazione di matrici (quadrate) come esempio di parallelismo su dati di input a due dimensioni. Implementazione naive in cui ciascun work item calcola uno degli n² elementi di output come prodotto scalare di una riga e una colonna delle matrici di input.

• Il codice dei programmi square e matmul è contenuto nel tar gzippato disponibile nella sezione "Libri di testo e materiale didattico"

Esercizi di riepilogo (E)
Esercizi OpenCL

Lunedì 19 dicembre 2016 - La tecnica del blocking: moltiplicare due matrici tramite molteplici moltiplicazioni di matrici più piccole (blocchi). Implementazione basata su blocking tramite uso di memoria locale e barriere. Confronto prestazionale sul calcolatore.

• Il codice dei due programmi per la moltiplicazione di matrici è contenuto nel tar gzippato disponibile nella sezione "Libri di testo e materiale didattico". Usare con cautela: come discusso in classe il codice che utilizza memoria locale funziona sotto ipotesi piuttosto stringenti: ad esempio, il lato delle matrici deve essere un multiplo del work group size.

Martedì 20 dicembre 2016 - secondo esonero

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 (esercizi da fare a casa) che saranno assegnati durante il corso e sostenere una prova scritta.

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.

Se durante la correzione degli homework emergeranno indizi significativi che portino a sospettare una copiatura parziale o totale, gli homework saranno sostituiti / integrati da un esame orale obbligatorio.

Prova intermedia. E' prevista una prova intermedia nella settimana di interruzione della didattica (inizio novembre, maggiori dettagli a breve). La 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 sufficienza ottenuta alla prova intermedia 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

• Prova intermedia novembre 2016
• Testo esame del 2 febbraio 2016
• Testo esame del 13 gennaio 2016
• Esonero seconda parte - dicembre 2015
• Prova intermedia novembre 2015: traccia A, traccia B