Tags:
create new tag
view all tags
EscherMetamorphosisII1940.jpg

Programmazione di Sistemi Multicore

Corso di Laurea in Informatica, terzo anno

A.A. 2018-2019, primo semestre

Docente: Irene Finocchi

Ricevimento: mercoledì 9:30-10:30 (oppure in altri giorni/orari da concordare via e-mail) durante il corso; 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

  • Cambio aula: tutte le lezioni del terzo anno sono state spostate dall'aula L2 all'aula L6, sempre in Via del Castro Laurenziano. Mi risulta che l'aula L6 si trovi al terzo piano. Ci vediamo quindi lunedì in L6, salvo imprevisti che risolveremo direttamente in sede.

  • Iscrivetevi al Google group per avvisi, notizie last-minute e discussioni sugli argomenti del corso.

Obiettivi e programma sintetico

Il corso affronta problematiche e tecniche di programmazione delle moderne piattaforme di calcolo parallele, dai sistemi multicore presenti sui più comuni laptop, desktop, server e dispositivi mobili, fino alle moderne GPU.

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 e linguaggi di programmazione e discutendo le basi teoriche del parallelismo (grafi delle computazioni, parallelismo ideale, speedup, leggi del parallelismo, data race e determinismo delle computazioni). L'homework farà acquisire allo studente un'esperienza diretta scrivendo software parallelo efficiente in alcuni dei modelli presentati a lezione.

Diario delle lezioni

Lunedì 24 settembre 2018 - Introduzione al corso. Legge di Moore e implicazioni sullo sviluppo di software (the free lunch is over). Differenza tra parallelismo e concorrenza.

Martedì 25 settembre 2018 - 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ì 1 ottobre 2018 - Sistemi paralleli: tassonomia di Flynn, modello di comunicazione (sistemi distribuiti o a memoria condivisa, NUMA vs UMA). Parallelizzazione automatica: storie di successo (vettorizzazione), difficoltà, data dependency. Modelli di programmazione: memoria condivisa con thread espliciti. Java.lang.Thread: nozioni fondamentali, parallel hello world.

Martedì 2 ottobre 2018 - Cenni ad altri modelli di programmazione: scambio di messaggi, dataflow e data parallelism (vedere slide del 1 ottobre). 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 non diminuiscono considerevolmente (anzi, se aumentiamo di molto i thread potrebbero anche aumentare)? 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).

  • Slide della lezione
  • Parallel sum: implementazione, sintesi degli esperimenti e delle analisi svolte

Lunedì 8 ottobre 2018 - 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ì 15 ottobre 2018 -

Martedì 16 ottobre 2018 -

Lunedì 22 ottobre 2018 -

Martedì 23 ottobre 2018 -

Lunedì 29 ottobre 2018 -

Martedì 30 ottobre 2018 -

Lunedì 5 novembre 2018 - prova intermedia prima parte (data da confermare)

Martedì 6 novembre 2018 -

Lunedì 12 novembre 2018 -

Martedì 13 novembre 2018 -

Lunedì 19 novembre 2018 -

Martedì 20 novembre 2018 -

Lunedì 26 novembre 2018 -

Martedì 27 novembre 2018 -

Lunedì 3 dicembre 2018 -

Martedì 4 dicembre 2018 -

Lunedì 10 dicembre 2018 -

Martedì 11 dicembre 2018 -

Lunedì 17 dicembre 2018 -

Martedì 18 dicembre 2018 - prova intermedia seconda parte (data da confermare)

Materiale didattico

Slide

A questo link potete trovare le slide messe a disposizione degli studenti durante l'Anno Accademico 2017-2018.

Le slide per l'Anno Accademico 2018-2019 potrebbero essere aggiornate o modificate a ridosso della lezione, e saranno messe a disposizione settimanalmente nel Diario delle lezioni, corredate da una breve sintesi degli argomenti affrontati.

Modalità d'esame

Per superare l'esame si deve sostenere una prova scritta (divisa in due parti) e svolgere un homework che sarà assegnato a metà corso.

Nella prova scritta occorrerà dimostrare di aver studiato e compreso gli argomenti trattati nelle lezioni:

  • rispondendo a tipiche domande da esame orale volte a verificare la comprensione della materia;
  • svolgendo esercizi che prevedono l'applicazione dei concetti esposti a lezione.

L'homework richiede di implementare ed analizzare sperimentalmente un software parallelo e può essere svolto in gruppi costituiti da al più 3 persone.

Non è previsto un esame orale, salvo su esplicita richiesta del docente in caso di sospetta copiatura - parziale o totale - dell'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 corrente.

Voto. Sia l'homework che la prova scritta saranno valutati in trentesimi e concorrono a determinare il voto finale (homework 30%, prova scritta 70%). Il voto verrà inoltre incrementato di un punto per chi termini nella sessione invernale avendo superato le prove intermedie.

Prenotazioni. Per partecipare alle prove scritte (incluse quelle intermedie) è obbligatoria la prenotazione. Sarà possibile prenotarsi agli appelli d'esame tramite infostud, e alle prove intermedie tramite twiki.

Date d'esame

Prove d'esame

Edit | Attach | Watch | Print version | History: r122 < r121 < r120 < r119 < r118 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r122 - 2018-10-12 - IreneFinocchi





 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback