High Performance Computing

Laurea in Ingegneria e Scienze Informatiche, Università di Bologna, 2023/2024

Avvisi

20/10/2023: Le lezioni di mercoledì 25 e giovedì 26 ottobre 2023 sono annullate per motivi di salute.
18/9/2023: Creata questa pagina.

Questa è la pagina del corso di High Performance Computing, corso di laurea in Ingegneria e Scienze Informatiche, AA 2023/2024, Università di Bologna (campus di Cesena). Il corso fornisce le conoscenze teoriche e pratiche necessarie per progettare, implementare e analizzare programmi paralleli su architetture a memoria condivisa e distribuita. In particolare, durante il corso gli studenti e le studentesse impareranno a realizzare programmi paralleli usando OpenMP, MPI e CUDA.

Il docente del corso è Moreno Marzolla.

Orario di ricevimento: mercoledì subito dopo la lezione; è possibile richiedere un incontro via Teams concordando data e ora via mail.

Come contattare il docente:

Usare sempre il proprio indirizzo di posta istituzionale @studio.unibo.it.
Indicare sempre l'oggetto (subject) della mail; infatti, ho notato che spesso i messaggi senza oggetto vengono etichettati come spam dal filtro antispam dell'Ateneo.
Indicare in calce alla mail il proprio nome, cognome e numero di matricola.
Specificare che il messaggio è relativo al corso di High Performance Computing: tengo più insegnamenti e talvolta non è facile capire a quale si fa riferimento.
Nel caso si chiedano chiarimenti su codice non funzionante: allegare alla mail il sorgente del programma in modo da poterlo compilare. Specificare che tipo di problema si ha (il programma non compila: qual è il messaggio del compilatore? il programma non esegue correttamente: che input viene usato, qual è il risultato atteso? ecc.). Per nessun motivo allegare screenshot: per segnalare un messaggio d'errore, lo si incolli nel testo della mail.
Ricordare sempre che la posta elettronica è un mezzo di comunicazione asincrono: non dare per scontato che il destinatario legga la posta elettronica di notte o nei giorni festivi. (Questo vale per tutti).

Prerequisiti: Questo corso richiede una buona conoscenza della programmazione in linguaggio C e delle architetture dei calcolatori (a livello di quanto presentato nel corso di architettura dei calcolatori). Lavoreremo in ambiente Linux utilizzando prevalentemente software libero (compilatore GCC, libreria Open MPI; per la programmazione CUDA useremo il software fornito gratuitamente da NVidia.

Torna in cima alla pagina.

Programma, libri di testo e orario

Programma di massima

Architetture parallele: sistemi a memoria condivisa e distribuita; GPGPU
Pattern per la programmazione parallela: problemi embarassingly parallel; work farm; partitioning; reduce; stencil
Valutazione delle prestazioni di programmi paralleli: speedup, efficienza, scalabilità
Programmazione di architetture a memoria condivisa con OpenMP
Programmazione di architetture a memoria distribuita con MPI
Programmazione di GPU con CUDA/C
Programmazione SIMD su architettura Intel

Laboratorio

Durante il corso verranno svolte esercitazioni di laboratorio per acquisire pratica con le tecniche viste a lezione. Verrà messo a disposizione un server Linux configurato con il software necessario; per le modalità di accesso si faccia riferimento alle istruzioni sulla piattaforma Virtuale.

All'inizio di ogni laboratorio, il docente fornisce le implementazioni seriali di alcuni programmi che risolvono semplici problemi. Scopo dell'esercitazione è di parallelizzare la versione seriale usando le tecniche indicate di volta in volta. Uno degli esercizi verrà di norma svolto dal docente in modo guidato.

Verranno proposti più esercizi di quanti possano essere realisticamente svolti nel tempo disponibile. Non mi aspetto che vengano svolti tutti durante il laboratorio: l'intento è di fornire un po' di scelta in modo che ciascuno possa trovare qualcosa di proprio interessante.

Testi di riferimento

I seguenti testi coprono la gran parte del materiale che vedremo a lezione e in laboratorio; tuttavia, essi non sostituiscono la frequenza di lezioni e laboratori, che restano essenziali per una preparazione solida e completa.

Peter Pacheco, Matthew Malensek, An Introduction to Parallel Programming, 2nd ed., Morgan Kaufmann, 2021, ISBN 9780128046050

Un valido libro didattico sulle architetture e programmazione parallela, su cui si baserà buona parte del corso. A lezione vedremo le parti introduttive e quelle sulla programmazione OpenMP, MPI e CUDA. Va bene anche la prima edizione.
CUDA C++ programming guide

Guida di programmazione CUDA/C, liberamente disponibile sul sito di NVIDIA.

Materiale per approfondimenti

In rete si trova molto materiale per approfondire gli argomenti trattati nel corso. Si tenga presente che i libri su OpenMP, MPI e CUDA tendono ad invecchiare velocemente man mano che nuove versioni delle specifiche sono rese disponibili (tuttavia non tratteremo le ultime versioni delle librerie, dato che comunque sarebbero poco e male supportate dai compilatori).

Georg Hager, Gerhard Wellein, Introduction to High Performance Computing for Scientists and Engineers, CRC Press, 2010, ISBN 9781439811924

Libro consigliato per chi voglia una trattazione approfondita. Contiene una parte introduttiva sulle architetture parallele e sullo sviluppo di algoritmi paralleli; prosegue poi con la programmazione OpenMP e MPI. Il libro è ricco di esempi e considerazioni sulle prestazioni di applicazioni parallele; purtroppo non tratta la programmazione di GPU. Il codice di esempio è in C e FORTRAN.
Roman Trobec, Boštjan Slivnik, Patricio Bulić, Borut Robič, Introduction to Parallel Computing: From Algorithms to Programming on State-of-the-Art Platforms, Springer, 2018, ISBN 978-3-319-98832-0

Libro molto completo che include una parte introduttiva sulle architetture parallel, OpenMP, MPI e OpenCL.
MPI: A Message-Passing Interface Standard Version 4.0 descrive lo standard MPI 4.0 (la versione più recente è sempre disponibile qui)
Specifiche di OpenMP aggiornate all'ultima versione disponibile. Si tenga presente che spesso i compilatori non supportano ancora le versioni più recenti di OpenMP.
Norm Matloff, Programming on Parallel Machines: GPU, Multicore, Clusters and more, liberamente disponibile online con licenza Creative Commons.

Questo libro è liberamente disponibile online, e copre la maggior parte degli argomenti affrontati a lezione, cioè OpenMP, MPI e CUDA. Si tratta di una bozza ancora in fase di stesura, il che significa che certe parti sono incomplete o mancano del tutto. È comunque molto utile come supporto allo studio del materiale di questo corso.
I. Foster. Designing and Building Parallel Programs. Addison-Wesley, 1995, ISBN 978-0201575941

Questo libro è liberamente disponibile online (cliccare sul titolo); il contenuto è un po' datato, ma la parte generale sulle metodologie di programmazione e di valutazione delle prestazioni resta comunque valida.
Jason Sanders, Edward Kandrot, CUDA by Example: An Introduction to General-Purpose GPU Programming, Addison-Wesley, 2010, ISBN 978-0131387683

Questo libro tratta la programmazione delle GPU mediante CUDA. Altre risorse indicate per chi già conosce CUDA e desidera approfondire tecniche efficienti di programmazione, sono GPU Gems 2 e GPU Gems 3 (entrambi disponibili online).
Michael McCool, Arch D. Robison, James Reinders, Structured Parallel Programming, Morgan Kaufmann, 2012, ISBN 978-0-12-415993-8

Contiene una buona introduzione ai pattern per la programmazione parallela. Questo libro è liberamente scaricabile dal sito dell'editore, collegandosi dalla rete di Ateneo.
Per chi non ha molta pratica con l'ambiente Linux (che comunque dovreste aver già usato nel corso di Sistemi Operativi) consiglio questo tutorial GNU/Linux a cura del progetto Debian

Per mancanza di tempo, nel corso non verrà trattata la teoria sulla progettazione e analisi di algoritmi paralleli. Per chi fosse interessato a questi aspetti, vengono forniti alcuni riferimenti bibliografici per approfondimenti. Si presti attenzione al fatto che si tratta di letture molto impegnative, normalmente utilizzate in corsi magistrali (se non addirittura di dottorato di ricerca).

Joseph Jàjà, An Introduction to Parallel Algorithms, Addison-Wesley, 1992, ISBN 978-0201548563

Descrive algoritmi paralleli per vari tipi di problemi usando modello PRAM. È uno dei testi classici sull'argomento, purtroppo fuori catalogo e di difficile reperibilità, oltre che di non facile lettura.
Selim G. Akl, The Design and Analysis of Parallel Algorithms, Prentice-Hall, 1989, ISBN 978-0132000567

Un ottimo testo su algoritmi paralleli per il modello PRAM. Un po' più semplice rispetto al libro precedente; purtroppo anche questo fuori catalogo e difficile da trovare.

Orario delle lezioni

Le lezioni si svolgeranno in parte online e in parte presso il nuovo campus universitario di Cesena. Le lezioni in aula saranno comunque trasmesse in diretta streaming, in modo che sia possibile seguirle anche da remoto.

Alcune lezioni potrebbero subire delle variazioni rispetto all'orario; si prega di fare riferimento al calendario delle lezioni che verrà aggiornato di volta in volta.

*Orario High Performance Computing, AA 2023/2024*
Mercoledì	10-12 Lab 4.2
Giovedì	14-17 Aula 2.5

Torna in cima alla pagina.

Esame

Specifiche del progetto per l'AA 2023/2024

Le specifiche saranno assegnate alla fine del corso.

A titolo di esempio viene reso disponibile il testo del progetto dello scorso anno accademico. Non c'è alcuna garanzia che tale progetto sia rappresentativo di quanto richiesto per il presente anno accademico.

Modalità d'esame

L'esame consiste in una prova scritta e un progetto di programmazione.
Le due prove (scritto e progetto) sono indipendenti e possono essere sostenute in ordine qualsiasi. Ciascuna prova viene superata se si ottiene un punteggio maggiore o uguale a 18/30.
La prova scritta è ha la durata di 60 minuti. Si svolge in presenza, in un laboratorio informatico, usando la piattaforma "Esami Online" dell'Ateneo. La prova è costituita da quattro domande a risposta aperta e/o semplici esercizi, e ha lo scopo di verificare la conoscenza degli aspetti teorici/metodologici del corso e delle basi della programmazione parallela. Il voto della prova scritta è espresso in trentesimi (massimo 30).
Sono disponibili alcuni esempi di domande d'esame.
Il progetto, da svolgere individualmente, ha lo scopo di verificare la padronanza delle tecniche di programmazione parallela illustrate a lezione. Le specifiche del progetto vengono assegnate dal docente alla fine del corso. Il voto del progetto è espresso in trentesimi (massimo 30).
Il progetto dovrà essere accompagnato da una relazione che descriva e giustifichi le scelte implementative, e illustri le prestazioni e la scalabilità della soluzione proposta.
A titolo di esempio è disponibile il progetto dello scorso anno accademico. Il progetto che verrà assegnato potrà essere diverso per contenuto, livello di difficoltà e/o modalità di svolgimento. Ai fini dell'esame farà fede esclusivamente il progetto che verrà assegnato.
I voti restano validi fino all'ultima sessione d'esame dell'edizione corrente del corso, quindi fino al 30 settembre 2024. Dopo tale data, tutti i voti in sospeso vengono persi e si ricomincia da capo con la nuova edizione del corso. Quindi, il progetto va tassativamente consegnato entro le 23:59 del 30 settembre 2024.
Il voto finale si calcola come:

VotoFinale = VotoScritto × 0.4 + VotoProgetto × 0.6

arrotondando il risultato all'intero più vicino (xxx.49 viene arrotondato per difetto, xxx.5 viene arrotondato per eccesso). La lode può essere assegnata, a discrezione del docente, in casi di prova scritta e progetto di qualità particolarmente elevata.

Per sostenere la prova scritta è obbligatorio iscriversi tramite AlmaEsami. Le liste di iscrizione chiudono alcuni giorni prima per consentire la gestione degli aspetti logistici dell'esame, per cui è necessario iscriversi per tempo. Le date delle prove scritte sono riportate nella tabella seguente:

*Prove scritte di High Performance Computing 2023/2024*
Sessione invernale (Gennaio-Febbraio 2024)
I	10/1/2024 ore 10:00 lab 3.1 È obbligatoria l'iscrizione tramite AlmaEsami
II	29/1/2024 ore 10:00 lab 3.1 È obbligatoria l'iscrizione tramite AlmaEsami
Sessione estiva (Giugno-Luglio 2024)
I	TBD
II	TBD
III	TBD
Sessione autunnale (Settembre 2024)
I	TBD

Torna in cima alla pagina.

Lezioni e laboratorio

Codice

HPC-2023-2024.zip: esempi di programmazione illustrati durante il corso.

Per l'accesso al server Linux usato per le esercitazioni fare riferimento alle istruzioni sulla piattaforma Virtuale.

Lucidi e altro materiale

Video delle lezioni 2023-2024
Video delle lezioni degli anni accademici precedenti: 2022-2023, 2021-2022, 2020-2021.

I lucidi non sostituiscono né i testi di riferimento né la frequenza delle lezioni e dei laboratori, che costituiscono importanti elementi per una buona preparazione dell'esame; i lucidi rappresentano uno schema di parte delle lezioni. Ringrazio chi mi segnalerà eventuali errori.

I lucidi al momento disponibili sono quelli usati nel precedente anno accademico; saranno possibili modifiche durante il corso, specialmente prima delle lezioni.

Salvo dove diversamente indicato, i lucidi delle lezioni sono distribuiti con licenza Creative Commons Attribution-Share Alike 4.0 International (CC BY-SA 4.0).

20/9/2023 ore 10:00 lab 4.2

Introduzione al corso (Pacheco cap. 1)
[ODP] [PDF]

Per approfondire

Herb Sutter, The Free Lunch is Over: A Fundamental Turn Toward Concurrency in Software, Dr. Dobb's Journal, 30(3), March 2005.
La Thinking Machines Corporation è stata negli anni '80-'90 una delle più importanti aziende produttirici di supercalcolatori (nonostante questo, l'azienda è fallita nel 1994). In rete si trovano alcuni video promozionali, che risultano molto istruttivi:
The Computer Programme: it's happening now

21/9/2023 ore 14:00 aula 2.5

Parallel architectures (Pacheco cap. 2 escluso 2.3.3)
[ODP] [PDF]

Per approfondire

Introduction to Parallel Computing Tutorial, Lawrence Livermore National Laboratory
Latency numbers every programmer should know
What is Hyper-Threading?, Intel
Hyper-Threading Technology Architecture and Microarchitecture, Intel Technology Journal vol 6 issue 1, feb 2002, ISSN 1535766X

27/9/2023 ore 10:00 lab 4.2

Parallel Programming Patterns parte 1 (McCool et al. cap 3)
[ODP] [PDF]

Per approfondire

Michael McCool, Arch D. Robinson, James Reinders, Structured Parallel Programming, Morgan Kaufmann, 2012, ISBN 978-0-12-415993-8 (il libro è scaricabile liberamente dalla rete di Ateneo); si veda in particolare il Capitolo 3
Guy L. Blelloch, Prefix Sums and Their Applications
Guy L. Steele, Data Parallel Algorithms

28/9/2023 ore 14:00 aula 2.5

Parallel Programming Patterns parte 2

4/10/2023 ore 10:00 lab 4.2

Performance Evaluation of Parallel Programs (Pacheco cap. 2.6)
[ODP] [PDF]

Per approfondire

Sarah Leon, Mistakes, we've drawn a few: Learning from our errors in data visualisation

5/10/2023 ore 14:00 aula 2.5

Performance Evaluation of Parallel Programs (cont.)
Parallelizing Loops
[ODP] [PDF]

Per approfondire

Lealie Lamport, The Parallel Execution of DO Loops, Communications of the ACM 17, vol 2, feb 1974, pp. 83—93. Questo è l'articolo in cui viene introdotto il metodo degli iperpiani per l'allineamento dei loop, ammesso che tale allineamento esista.
Giacomo Aloisi, OPoly: an OpenMP polyhedral compiler. In questa tesi di laurea che ho seguito tempo fa viene presentato un software in grado di allineare automaticamente dei cicli annidati utilizzando il metodo degli iperpiani di Lamport.

11/10/2023 ore 10:00 lab 4.2

Shared-Memory Programming with OpenMP (Pacheco cap. 5)
[ODP] [PDF]

Per approfondire

OpenMP.org; contiene le specifiche ufficiali di tutte le versioni di OpenMP
Blaise Barney, OpenMP Tutorial, Lawrence Livermore National Laboratory.
I programmi di esempio illustrati a lezione sono disponibili nella sezione codice di esempio

12/10/2023 ore 14:00 aula 2.5

Shared-Memory Programming with OpenMP (cont.)

18/10/2023 ore 10:00 lab 4.2

Lab OpenMP
Per l'accesso al server fare riferimento alle istruzioni sulla piattaforma Virtuale.
Nota: vengono proposti più esercizi di quanti realisticamente possano essere svolti nelle ore di laboratorio; quello che non si riesce a fare durante il laboratorio viene lasciato per casa.

19/10/2023 ore 14:00 aula 2.5

Shared-Memory Programming with OpenMP (part 2)

25/10/2023

Laboratorio annullato. Vengono comunque proposti alcuni esercizi da svolgere in autonomia, che potranno essere discussi con il docente all'inizio della prima lezione utile.

26/10/2023

Lezione annullata.

2/11/2023 ore 14:00 aula 2.5

Distributed-Memory Programming with MPI (Pacheco cap. 3)
[ODP] [PDF]

Per approfondire

Blaise Barney, Message Passing Interface (MPI), Lawrence Livermore National Laboratory.
MPI: A Message-Passing Interface Standard Version 4.0 descrive lo standard MPI 4.0 (la versione più recente è sempre disponibile qui)
I programmi di esempio illustrati a lezione sono disponibili nella sezione codice di esempio

8/11/2023 ore 10:00 lab 4.2

Lab MPI

9/11/2023 ore 14:00 aula 2.5

Distributed-Memory Programming with MPI (cont.)

15/11/2023 ore 10:00 lab 4.2

Lab MPI

16/11/2023 ore 14:00 aula 2.5

Distributed-Memory Programming with MPI (cont.)

22/11/2023 ore 10:00 lab 4.2

Lab MPI

23/11/2023 ore 14:00 aula 2.5

CUDA Programming
[ODP] [PDF]

Per approfondire

CUDA Toolkit include il software di sviluppo per CUDA, disponibile per Windows, Linux e MacOSX
CUDA C++ programming guide (la documentazione principale per la programmazione CUDA)
NVIDIA training material and code samples
An Easy Introduction to CUDA C and C++
An Even Easier Introduction to CUDA
CUDA C Best Practices Guide
I programmi di esempio illustrati a lezione sono disponibili nella sezione codice di esempio

29/11/2023 ore 10:00 lab 4.2

Lab CUDA

30/11/2023 ore 14:00 aula 2.5

CUDA Programming (cont.)

6/12/2023 ore 10:00 lab 4.2

Lab CUDA

7/12/2023 ore 14:00 aula 2.5

SIMD Programming
[ODP] [PDF]

Per approfondire

Intel Intrinsics Guide

13/12/2023 ore 10:00 lab 4.2

Lab SIMD

14/12/2023 ore 14:00 aula 2.5

Progetto d'esame

Torna in cima alla pagina.