HIGH PERFORMANCE COMPUTING

L'obiettivo dell'insegnamento è di dare allo studente le conoscenze necessarie per la progettazione e lo sviluppo di algoritmi di analisi di grandi volumi di dati in ambienti altamente paralleli (multi-core, GPU) e distribuiti (cloud). Alcuni casi di studio verranno scelti tra temi quali data mining, web search, e social network analysis.

Il corso illustra le tecniche impiegate per risolvere problemi di analisi su grandi volumi di dati con algoritmi paralleli, discutendo metodologie per architetture CPU multi-core fino ad architetture che sfruttano Graphics Processing Units (GPU).
Gli studenti acquisiscono conoscenze sui modelli di architetture di High Performance Computing, sui paradigmi e sugli ambienti di programmazione parallela, e sulla valutazione delle prestazioni dei sistemi paralleli.

Gli studenti raggiungeranno i seguenti risultati di apprendimento:

Conoscenza e comprensione: i) comprensione dei concetti base del multi-threading e del calcolo distribuito; ii) comprensione dei costi di un programma parallelo (cache, memory, network) e loro modellazione; iii) comprensione dei pattern di programmazione parallela.

Capacità di applicare conoscenza e comprensione: i) capacità di progettare e sviluppare algoritmi paralleli ii) capacità di stimare e misurare la performance di un programma parallelo; iii) capacità di sviluppare algoritmi paralleli tramite l'uso dei pattern di programmazione parallela

Capacità di giudizio: i) capacità di analizzare e confrontare differenti pattern o soluzioni parallele e di scegliere la più appropriata ad un dato problema sulla base di un modello di costo

Abilità comunicative: i) saper esporre in maniera esausitva i risultati sperimentali di una analisi comparativa tra differenti soluzioni parallele

Lo studente deve possedere una buona conoscenza di architettura degli elaboratori, programmazione, linguaggi C++ e python, sistemi operativi.

1. Introduction to High Performance Computing
- Motivations for Parallel Computing
- Different granularities: Instruction Level Parallelism, Multi-Core, GPU, Distributed Computing
- Examples of large scale applications that require High Performance Computing
2. Instruction level Parallelism
- Introduction to instruction level parallelism
- SIMD paradigm
- SSE and AVX instruction sets
- Intel Intrinsincs
3. Auto-Vectorization
- Data/control dependencies
- Loop Optimizations
- Compilers Auto-vectorization
- Pointer aliasing
- Guidelines for auto-vectorization
4. Cache Aware Algorithms
- Impact of cache in modern architectures
- Cache coherence protocols
- Cache-aware algorithms
- Cache-aware matrix multiplication.
5. Cache Oblivious Algorithms
- Cache-oblivious Models and Algorithms
- Cache-oblivious matrix multiplication
- Cache-oblivious sorting
- Using micro kernels to optimize cache usage and compile auto-vectorization.
- Software tools for evaluating cache performance
6. Thread Parallelism
- Modeling of parallel programs: speed-up, cost-optimality, scalability
- Threads vs. processes, shared memory programming
- C++ std threads, mutexes and condition variables (già fatti ...)
- The OpenMP paradigm: Managing threads and memory management, Parallelizing loops and scheduling policies, Managing parallel sections, Synchronization and introspection
- Multi-threaded algorithms, Impact of parallelism to cache efficiency
- Matrix Multiplication algorithms
7. Patterns of Parallelism
- Modeling parallelism: Task dependency graphs, Task interaction graphs, Parallelism degree and task granularities, Critical path, Mapping guidelines
- Patterns of Parallelism: Embarrassingly parallel problems, Thread pool (farm), Exploratory search, Pipelining, Vertex-centric
- Static vs. dynamic mapping
- Algorithms: quicksort, shellsort, bitonic-sort, prefix sum, connected components
9. HPC on large clusters:
- Distributed file systems
- Fault Tolerance
- The MapReduce paradigm
- The Spark framework
- Algorithms: All Pairs Similarity Search
10. Large-scale data parallelism on GPU:
- GPU architectures
- CUDA for GP-GPU computing
- GPU threads and memory hierarchies
- Parallel patterns and algorithms for GPUs

Note del docente.

T. Rauber, G. Rünger, Parallel Programming for Multicore and Cluster Systems, 2nd Ed, Spinger

La verifica dell'apprendimento avviene tramite una prova scritta e l'implementazione di un progetto.

La prova scritta consiste in domande di carattere teorico sugli argementi trattati durante il corso.

Il progetto richiede di sviluppare un algoritmo per uno specifico problema di data anlysis. Lo studente deve scegliere e motivare la soluzione parallela secondo lui più opportuna e consegnare un report che verrà discusso con il docente.

scritto e orale

Lezioni teoriche e sessioni pratiche.