High Performance Computing
Laurea in Ingegneria e Scienze Informatiche, Università di Bologna, 2023/2024
Salta all'introduzione
- 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.
Salta al programma del corso e libri di testo
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.
Salta alla modalità d'esame
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.
Salta ai lucidi delle lezioni
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:
Torna in cima alla pagina.
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
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]
- 21/9/2023 ore 14:00 aula 2.5
- Parallel architectures
(Pacheco cap. 2 escluso 2.3.3)
[ODP] [PDF]
- 27/9/2023 ore 10:00 lab 4.2
- Parallel Programming Patterns parte 1 (McCool et al. cap 3)
[ODP] [PDF]
- 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]
- 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]
- 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.
- Decifrare un messaggio cifrato [Soluzione]
- Calcolo del valore approssimato di π [Soluzione]
- Frequenze dei caratteri in un documento [Soluzione]
- Crivello di Eratostene [Soluzione]
- 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.
- Simulare la clausola schedule(dynamic) [Soluzione]
- Ray tracing [Soluzione]
- La mappa del gatto di Arnold [Soluzione]
- Merge Sort [Soluzione]
- 26/10/2023
- Lezione annullata.
- 2/11/2023 ore 14:00 aula 2.5
- Distributed-Memory Programming with MPI (Pacheco cap. 3)
[ODP] [PDF]
- 8/11/2023 ore 10:00 lab 4.2
- Lab MPI
- Comunicazione ad anello [Soluzione]
- Calcolo del valore approssimato di π [Soluzione]
- Comunicazione broadcast [Soluzione]
- 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
- Insieme di Mandelbrot [Soluzione]
- Prodotto scalare [Soluzione]
- Calcolo dell'area dell'unione di cerchi [Soluzione]
- 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
- Automa cellulare della
regola 30
[Soluzione]
- MPI Datatype [Soluzione]
- Bounding Box [Soluzione]
- 23/11/2023 ore 14:00 aula 2.5
- CUDA Programming
[ODP] [PDF]
- 29/11/2023 ore 10:00 lab 4.2
- Lab CUDA
- Prodotto scalare [Soluzione]
- Inversione di array [Soluzione]
- Odd-Even Transposition Sort [Soluzione]
- 30/11/2023 ore 14:00 aula 2.5
- CUDA Programming (cont.)
- 6/12/2023 ore 10:00 lab 4.2
- Lab CUDA
- Somma di matrici [Soluzione]
- Automa cellulare della
regola 30
[Soluzione]
- L'automa cellulare
ANNEAL
[Soluzione]
- 7/12/2023 ore 14:00 aula 2.5
- SIMD Programming
[ODP] [PDF]
- 13/12/2023 ore 10:00 lab 4.2
- Lab SIMD
- Prodotto scalare
- Prodotto matrice-matrice
- Mappatura livelli di grigio di una immagine
- 14/12/2023 ore 14:00 aula 2.5
- Progetto d'esame
Torna in cima alla pagina.