Algoritmi paralleli e sistemi distribuiti

Numero di crediti ECTS: 5 (48 ore frontali)

SSD di riferimento: INF/01

Docente: W. Spataro

Prerequisiti

• Analisi Numerica
• Programmazione in C/C++

Obiettivi

Il corso si propone di fornire agli studenti del Corso Specialistica di Informatica:

• conoscenze dei fondamenti e aspetti applicativi del calcolo parallelo
• conoscenze delle tecniche e metodi di progettazione e realizzazione di algoritmi paralleli
• conoscenza approfondita dei principi, strutture e utilizzo dei sistemi di elaborazione paralleli e, in particolare, delle tecniche di programmazione in ambiente Shared-memory e paradigma Message Passing
• conoscenza di diversi settori di applicazione del calcolo parallelo e, in particolare, della HPC (High Performance Computing).

Programma

• Introduzione al Calcolo Parallelo
  • Scopi, Concetti e Terminologie
  • Tassonomia di Flynn
• Architetture Parallele
  • Panoramica sulle macchine parallele
  • Memoria Condivisa (Multiprocessors)
  • Memoria Distribuita (Multicomputers)
  • Architetture Multi-core
  • Cache Coherence
  • Architetture Ibride
• Modelli di Programmazione Paralleli
  • Modello a Threads
  • Modello a Memoria Condivisa
  • Modello a Memoria Distribuita
  • Modelli Data Parallel
  • Altri Modelli
• Disegno di Programmi Paralleli
  • Parallelizzazione automatica e manuale
  • Partizionamento
  • Comunicazioni
  • Sincronizzazione
  • Load Balancing
  • Granularità
  • I/O parallelo
• Panoramica su OpenMP - Il linguaggio di riferimento per la programmazione in ambienti a memoria condivisa/data parallel
  • Concetti generali
  • Loop paralleli
  • Variabili tipo private e shared
  • Sezioni critiche
  • Parallelismo funzionale
• MPI - Il linguaggio di riferimento per la programmazione in ambienti a memoria distribuita
  • Concetti Generali
  • Routine di Gestione Ambiente
  • Comunicazioni Punto-Punto: MPI_Recv e MPI_Send
  • Comunicazioni Non-bloccanti
  • Comunicazioni Collettive
  • Tipi di Dati derivati
  • Comunicatori e Gruppi
  • Topologie virtuali
• Programmazione GPGPU – La nuova frontiera del Calcolo Parallelo
  • CUDA C - Il linguaggio di riferimento per la programmazione su schede grafiche
  • Concetti generali, limiti
  • CUDA, CUDA C
  • Gerarchia dei Thread e della Memoria
  • Concetti di thread, blocco, grid e kernel
  • Strategia di ottimizzazione: utilizzo della shared memory, coalescenza
• Analisi delle Performance
  • Parallel Overhead
  • Speedup e Efficienza
  • Speedup superlineare
  • Effetto della Granularità sulle Performance
  • Scalabilità
  • Legge di Amdahl
  • Isoefficienza
• Algoritmi Paralleli
  • Calcolo Matriciale
  • Integrazione numerica
  • Algoritmi di ricerca e ordinamento
  • Analisi delle prestazioni di algoritmi paralleli
• Laboratorio
  • Sviluppo di elementi di software parallelo in ambiente MPI e OpenMP su calcolatori paralleli
  • Sviluppo di elementi di software parallelo in ambiente GPGPU –CUDA C su schede grafiche NVIDIA
  • Misurazione delle prestazioni

Bibliografia

• Ananth Grama et al., Introduction to Parallel Computing, 2/E, Addison-Wesley.
• Peter Pacheco, Parallel Programming with MPI. Morgan Kaufmann, 1997
• G. Spezzano, D. Talia “Calcolo parallelo, automi cellulari e modelli per sistemi complessi”, Franco Angeli, Milano, 1999.

• I. Foster. Designing and Building Parallel Programs. Addison-Wesley, 1995, Versione online disponibile presso http://www-unix.mcs.anl.gov/dbpp

• Materiale del Docente (Reperibile sul sito web personale)

Tipologia di attività didattiche

Utilizzo di materiale didattico quali slides, etc. Sviluppo di semplici codici on-the-fly. Interazione attiva con gli studenti durante le lezioni. Lezioni tenuti interamente in inglese.

Metodi di valutazione

Il test finale consiste in una prova scritta e nella valutazione di un progetto sviluppato in MPI/OpenMP.