Ing Ind - Inf (1 liv.)(ord. 270) - MI (365) INGEGNERIA MATEMATICA
*
A
ZZZZ
056974 - ALGORITMI E ARCHITETTURE PER IL CALCOLO AD ALTE PRESTAZIONI
Obiettivi dell'insegnamento
Obiettivo del corso è quello di ampliare le conoscenze di base di architettura dei calcolatori, algoritmi, linguaggi di programmazione e compilazione, acquisite nell'insegnamento di Informatica A, approfondendo le tecniche di progettazione di algoritmi, principi e linguaggi di programmazione parallela e architetture di calcolo parallele per il calcolo ad alte prestazioni. Tecniche di didattica innovativa (“Blended Learning & Flipped Classroom”) verranno utilizzate per stimolare la partecipazione degli studenti al corso e lo sviluppo di capacità di studio autonomo.
Risultati di apprendimento attesi
Conoscenza e comprensione
- Comprendere le strutture dati ed algoritmi fondamentali
- Conoscere le architettura dei calcolatori paralleli e la gerarchia di memoria
- Comprendere i principi di programmazione parallela
- Conoscere i linguaggi e gli strumenti di programmazione parallela
Capacità di applicare conoscenza e coomprensione
- Progettare algoritmi e strutture dati complessi
- Analizzare le prestazioni di algoritmi complessi
- Scrivere algoritmi paralleli partendo dalla loro specifica
- Sfruttare la conoscenza dell'architettura del calcolatore per migliorare le prestazioni dei programmi
Autonomia di giudizio
- Valutare la correttezza delle soluzioni adottate per un determinato problema
- Individuare i colli di bottiglia delle soluzioni esistenti
- Confrontare i benefici e gli svantaggi di diverse architetture rispetto al problema proposto
Argomenti trattati
Argomenti principali del corso
1) Struttura e progetto dei calcolatori
– Il calcolatore: astrazioni e tecnologia – Le istruzioni: il linguaggio dei calcolatori – L’aritmetica dei calcolatori – Il processore – Grande e veloce: la gerarchia delle memorie (una parte flipped) – Processori paralleli: dai client al cloud
2) Algoritmi e loro analisi
– Algoritmi. Insertion Sort - Merge Sort. Analisi asintotica. Master method. Divide and Conquer: ricercar binaria, elevamento a potenza, etc – Parallel Random-access Machine (PRAM) (una parte flipped) – Algoritmi e strutture dati randomizzate – Analisi ammortizzata – Analisi competitive – Dynamic Programming
3) Introduzione alla programmazione parallela
– Progettazione di algoritmi paralleli – Strumenti e linguaggi di programmazione parallela: Posix thread,OpenMP,Message Passing Interface,CUDA (una parte flipped) - Esempi di algoritmi paralleli
La creazione di un programma parallelo efficiente e veloce incide notevolmente sulla riduzione del consumo energetico dello strumento di calcolo. Inoltre, migliorare l'efficienza del programma applicativo scegliendo la corretta tecnologia ridurrà anche il consumo di energia e corrispondentemente le emissioni di carbonio.
Prerequisiti
Il prerequisito ideale consiste nell'avere superato l'esame di Informatica A; è comunque indispensabile avere almeno la capacità di scrivere semplici programmi in linguaggio C.
Modalità di valutazione
E' prevista una modalità di valutazione "continua" (continuous assessment) in cui l’insieme delle attività didattiche concorre a integrare i diversi tipi di valutazione (valutazione sommativa e autovalutazione).
In particolare, sono previste tre prove intermedie, distribuite lungo tutto il semestre di erogazione, nella forma di brevi prove scritte. Ciascuna prova scritta copre uno dei tre macro argomenti trattati nel corso:
PI-1) Struttura e progetto dei calcolatori
PI-2) Algoritmi e loro analisi
PI-3) Introduzione alla programmazione parallela
Ciascuna delle tre prove intermedie PI-1, PI-2 e PI-3 assegna un massimo di 11 punti. Le date delle singole prove saranno comunicate in aula e pubblicate sul Web di Ateneo. L'invalidità di una prova non preclude la partecipazione alle altre. L'esito delle tre prove sarà valido per tutto l'anno accademico.
Negli appelli previsti dal calendario accademico sarà possibile ripetere ciascuna delle tre prove PI-1, PI-2 e PI-3. Il testo dell'esame sarà consistente con la richiesta di quali prove PI-1, PI-2 e PI-3 lo studente vorrà sostenere. Ogni prova ripetuta annullerà il risultato ottenuto precedentemente indipendentemente dall'esito.
Ciascuna delle prove potrà essere integrata da una eventuale discussione orale esclusivamente su richiesta del docente. Il voto dell'esame è ottenuto come somma dei tre punteggi ottenuti per PI-1, PI-2 e PI-3. La lode sarà assegnata in caso di punteggio superiore a 30 punti. Ciascuna prova concorre alla definizione del voto d'esame solo se il suo punteggio è non inferiore a 5 punti.
La partecipazione ad attività in aula di apprendimento innovativo sarà valutata e concorrerà al voto finale di valutazione. In particolare, in caso di voti validi, alcune domande della prova scritta potrebbero essere saltate.
Bibliografia
David A. Patterson, John L. Hennessy, Struttura e progetto dei calcolatori. Progettare con RISC-V., Editore: Zanichelli, Anno edizione: 2019, ISBN: 978-8808820594
T. Cormen, C. Leiserson, R. Rivest and C. Stein, Introduction to Algorithms, Editore: MIT Press, Cambridge; 3rd edition,, Anno edizione: 2009, ISBN: 978-0262533058
Rajeev Motwani, Prabhakar Raghavan,, Randomized Algorithms, Editore: Cambridge University Press, Anno edizione: 1995, ISBN: 978-0521474658
Michael McCool, James Reinders, Arch Robison,, Structured Parallel Programming: Patterns for Efficient Computation, Editore: Morgan Kaufmann, Anno edizione: 2012, ISBN: 0124159931 http://parallelbook.com/David B. Kirk, Wen-mei W. Hwu,, Programming Massively Parallel Processors: A Hands-on Approach,, Editore: Morgan Kaufmann, Anno edizione: 2017, ISBN: 978-0-12-811986-0 Note:
Italiano