In questa sezione sono raccolti alcuni argomenti per tesi di laurea triennali e magistrali. Sono comunque disponibile a valutare anche argomenti diversi da quelli elencati sotto, purché non troppo distanti dalla mia attività di ricerca.

Se volete fare la tesi con me è utile prendere visione delle regole per lo svolgimento di una tesi.

Halide è un linguaggio di programmazione (DSL, Domain-Specific Language) specializzato per lo sviluppo di algoritmi di tipo stencil, frequentemente utilizzati nella programmazione grafica; ad esempio, vari tipi di filtri applicabili su immagini bitmap possono essere rappresentati da computazioni di tipo stencil che è possibile realizzare con Halide.

Halide non è un linguaggio autonomo, ma sfrutta i costrutti di metaprogrammazione del linguaggio C++ per consentire all'utente di includere i kernel computazionali direttamente nei programmi in C++ che vengono poi compilati dal compilatore di sistema. Halide genera automaticamente codice ottimizzato per vari tipi di CPU e GPU, in quest'ultimo caso usando CUDA oppure OpenCL.

Lo scopo della tesi è di valutare Halide dal punto di vista dell'efficienza e della facilità d'uso, sia considerando le applicazioni per le quali è stato pensato (computazioni di tipo stencil), sia per applicazioni parallele generiche.

Questa tesi richiede un minimo di dimestichezza con il linguaggio C++, sebbene non dovrebbe essere necessario scrivere codice ad oggetti e quindi si possa utilizzare il C++ come se fosse una sorta di “linguaggio C più potente”.

Riferimenti:

• Halide
• Vari tutorial su Halide

L'analisi delle reti complesse è un tema di ricerca sempre attuale. Una rete complessa è rappresentata da un grafo di cui interessa calcolare una serie di metriche standard (es., betweenness centrality, node centrality, numero di “triangoli”, diametro della rete, distribuzione dei gradi dei nodi, eccetera). Esistono algoritmi sequenziali efficienti per il calcolo di tali metriche, che sono prontamente disponibili in diversi software liberi; uno dei più usati è probabilmente NetworkX per il linguaggio Python.

Dato che l'analisi di reti di grandi dimensioni può richiedere molto tempo, è naturale cercare di sfruttare il parallelismo multicore o basato su CUDA. Scopo della tesi è la valutazione delle prestazioni di implementazioni parallele di alcuni algoritmi per il calcolo di metriche su reti complesse presenti ad esempio nelle librerie seguenti:

• graph-tools
• networkit
• nvgraph
• Rapids.AI

L'obbiettivo ultimo è l'integrazione degli algoritmi paralleli nel tool DiLeNa sviluppato dall'Università di Bologna per l'analisi di vari tipi di DLT (Distributed Ledger Technologies) considerate come reti complesse. Il tool DiLeNa è scritto in Python ed èì liberamente disponibile su GitHub.

Riferimenti:

• M. Lambertini, M. Magnani, M. Marzolla, D. Montesi, C. Paolino Large-Scale Social Network Analysis
• DiLeNa

Questa tesi, in collaborazione con la collega Elena Loli Piccolomini del DISI, riguarda la parallelizzazione tramite CUDA di algoritmi per la ricostruzione di immagini 3D provenienti da tomografia computerizzata (TAC) a scopi diagnostici. È già disponibile codice C seriale da usare come base di partenza.

Riferimenti

• R. Cavicchioli, J. Cheng Hu, E. Loli Piccolomini, E. Morotti, L. Zanni, GPU acceleration of a model-based iterative method for Digital Breast Tomosynthesis

Chi ha seguito il corso di High Performance Computing ha potuto toccare con mano la quantità (e, mi auguro, anche la qualità) di esercizi che vengono proposti nei laboratori. In realtà sono stati sviluppati molti altri esercizi, che per ovvie ragioni di tempo non è stato possibile assegnare.

Ritengo che gli esercizi sviluppati per il corso possano essere di interesse per la comunità scientifica che si occupa di calcolo parallelo, sia per ricerca che per didattica. Per rendere più utili gli esercizi, però, sarebbe opportuno che la maggior parte di loro fosse presente sia in versione OpenMP che MPI che CUDA/OpenCl. Al momento alcuni dei problemi sono stati risolti in una o due delle tecnologie precedenti.

Scopo della tesi è il porting di alcuni esercizi (quelli per i quali abbia senso farlo) alle tecnologie che non sono ancora state usate per la soluzione. A tale scopo verranno forniti tutti i programmi sviluppati fino ad ora con le soluzioni disponibili, allo scopo di usarle come scheletro per quelle mancanti.

È stato sviluppato un programma CUDA per il calcolo del numero di intersezioni tra due insiemi di intervalli in una dimensione (in pratica ogni intervallo ha la forma [a, b]). Il programma andrebbe ora confrontato con altre applicazioni esistenti, tra cui:

• BedTools
• BedTk
• BITS

Si rende necessario scaricare e compilare i programmi di cui sopra, individuare alcuni dataset su suggerimento del docente, ed effettuare i test in modo appropriato.

(Tesi da svolgere in collaborazione con il collega prof. Andrea Bartolini).

Sono disponibili alcuni prototipi di nodi di calcolo basati su processori con architettura RISC-V. Su tali server è installato Linux con la consueta toolchain (compilatore GCC, ecc.). Scopo della tesi è la realizzazione ed esecuzione di benchmark per testare l'efficienza del prototipo; si prevede di utilizzare OpenMP ed eventualmente MPI.

(I colleghi aerospaziali si sono detti disponibili a fornire ulteriori informazioni sugli argomenti seguenti, che al momento sono solo abbozzati qui).

1. Ottimizzazione di Starfish (codice PiC - Particle in Cell - sviluppato in Java): controllare strutture dati, gestione delle macro-particelle e risoluzione dei sistemi lineari. La tesi potrebbe risultare impegnativa per una laureatriennale, dato che riguarda codice già strutturato (in Java) e con passaggi legati alla fisica.
2. Creazione di un codice PiC in C++ : codice completamente nuovo in cui si inizializzano particelle (anche solo neutri), si introducono urti, condizioni al contorno e mesh. Può essere un ottimo inizio di lavori per la produzione di un codice OpenFOAM in futuro.
3. Finite difference Radial Base Function PDE solver. L'idea finale di questo progetto consiste nel realizzare un solutore di PDE (Partial Differential Equations) basato sulle differenze finite e le Radial Base Function. Il primo obbiettivo di questo progetto consiste nel realizzare un Nearest neighbor search, cioè un programma che dati dei punti sparsi nello spazio per ognuno di essi identifichi i “k” punti più vicini al punto dato. Questo programma servirà come base per calcolarsi i coefficienti delle differenze finite. Il secondo obbiettivo (facoltativo) del progetto consiste nel risolvere l'equazione di diffusione del calore, una semplice PDE lineare a coefficienti costanti.
4. Ottimizzazione del metodo di verifica delle mesh per l’identificazione delle sel-intersections. Si tratta di analizzare un algoritmo che è stato per il momento implementato in ambiente Matlab e ottimizzarlo passando ad un altro linguaggio di programmazione più efficiente ed in grado di gestire la parallelizzazione dei processi.

Nota: Si tratta di un argomento di tesi magistrale che richiede conoscenza di tecniche di machine learning.

Contesto: Il CNAF gestisce un grande centro di calcolo utilizzato da comunità di ricercatori di fisica delle particelle, astrofisica e altro. Il centro è composto da numerosi sistemi interagenti e per ciascuno esistono informazioni di stato già raccolte o raccoglibili tramite strumenti di monitoring. In questo scenario sono possibili diverse applicazioni di ML, orientate alla failure prediction o predictive maintenance o altro ancora. Alcuni esempi

Job classification. Un centro di calcolo con circa 40K cores in O(10^3) host fisici esegue job singlecore o multicore (1 o 8). I job appartengono a diversi gruppi di utenti (O(50)) e sono accodati da un batch system (HTCondor) che ne schedula l'esecuzione in base ad algoritmi di fairshare. Lo stato dei job durante l'esecuzione viene rappresentato da alcune grandezze (tra molte disponibili) quali per es. memoria, disco, cputime campionate ogni 3 minuti e raccolte in un database. I job di interesse hanno durata tipicamente compresa tra 4 ore e 4 giorni. Si desidera classificare la famiglia di appartenenza dei job osservando l'evoluzione del loro stato x(t) nelle fasi iniziali (per es. job I/O intensive oppure CPU intensive), oppure predire se i job termineranno con successo o fallimento (per il training sono disponibili dati di accounting per i job conclusi, compreso lo stato d'uscita).

WN failure. Lo stato dei nodi di calcolo (Worker Node) è campionato ogni tre minuti sia dal punto di vista del batch system che del S.O. I WN appartengono a circa 4 o 5 modelli distinti. si desidera prevedere se un particolare WN rischia di guastarsi per problema hardware o per le correnti condizioni di carico (in tal caso si considerano anche i job in esecuzione nella macchina e nell'intero cluster).

Il problema da affrontare riguarda il calcolo del volume minimo che è richiesto per contenere un insieme di _N_ sfere rigide in modo da eviare che si compenetrino. Questo problema ha molte applicazioni pratiche in ambito aerospaziale, e viene affrontato in collaborazione con il dipartimento di Ingegneria Aerospaziale dell'Università di Bologna.

È già stato realizzato un primo prototipo di algoritmo parallelo in C+OpenMP per la risoluzione di tale problema secondo un meccanismo iterativo combinato con un approccio “a forza bruta” per determinare e risolvere le compenetrazioni. L'argomento della tesi consiste nel completare il programma in conformità ad una versione MATLAB precedente, aggiungere alcune caratteristiche che al momento mancano (gestione di condizioni al contorno cicliche oppure “a parete” in modo definibile dall'utente), in modo da dare risposta ad una serie di quesiti pratici legati al problema in questione.

Per questa tesi è necessaria una buona padronanza della programmazione parallela su architetture a memoria condivisa usando OpenMP; sono richieste conoscenze di base di architettura dei calcolatori (utili per l'ottimizzazione del codice) e di algoritmi e strutture dati (per l'ottimizzazione della parte algoritmica).

Il servizio di data distribution management viene utilizzato nei simulatori paralleli e distribuiti conformi allo standard High Level Architecture (HLA) per determinare in sostanza le intersezioni tra coppie di (iper-)rettangoli nello spazio. In questo lavoro, svolto in collaborazione con Gabriele D'Angelo, è stato proposto un algoritmo parallelo per architetture a memoria condivisa per risolvere efficientemente questo problema. Resta da esplorare la possibilità di implementare un analogo algoritmo sulle GPU usando CUDA.

Riferimenti:

• Moreno Marzolla, Gabriele D'Angelo, Parallel Data Distribution Management on Shared-memory Multiprocessors, ACM Transactions on Modeling and Computer Simulation (TOMACS), volume 30, issue 1, February 2020, ISSN 1049-3301.

Chapel è un linguaggio per la programmazione parallela sviluppato da Cray. Il linguaggio mette a disposizione costrutti di alto livello che consentono di sviluppare applicazioni parallele per sistemi multicore e cluster in modo relativamente semplice (più semplice rispetto ai classici MPI+OpenMP). Il compilatore Chapel è disponibile come software libero ed è liberamente scaricabile qui.

Scopo di questa tesi è di familiarizzare con il linguaggio, e implementare qualche (semplice) algoritmo parallelo in Chapel, magari simile a qualcuno di quelli visti a lezione o in laboratorio, in modo da confrontare le prestazioni di Chapel con quelle di MPI+OpenMP.

Riferimenti:

• Documentazione di Chapel (include un tutorial di programmazione)

Nel capitolo 4 del rapporto tecnico Introduction to Data Level Parallelism (il link si trova sotto) viene descritto un algoritmo parallelo per tracciare le linee di livello di un'area geografica partendo da due immagini stereo. L'algoritmo era stato pensato per la Connection Machine CM-2 ed è espresso in *Lisp, una estensione parallela del linguaggio Lisp. Sebbene tale linguaggio non sia più utilizzato, l'algoritmo risulta comunque comprensibile, anche grazie alla spiegazione dettagliata fornita nel testo. L'obbiettivo di questo lavoro di tesi è l'implementazione dell'algoritmo su una GPU utilizzando CUDA/C.

Riferimenti:

• Introduction to Data Level Parallelism, Thinking Machines Corporation
• *Lisp reference manual, Thinking Machines Corporation