Differences

This shows you the differences between two versions of the page.

--- tesi:tesi [2019/11/11 15:48] – moreno
+++ tesi:tesi [2024/04/16 15:12] (current) – moreno
@@ Line 2: / Line 2: @@
 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 [[http://www.moreno.marzolla.name/publications/|attività di ricerca]].
-Le proposte per tesi triennali sono etichettate con **LT** e quelle magistrali sono etichettate con **LM**. Queste indicazioni non sono vincolanti: nulla vieta ad un laureando triennale di scegliere un argomento marcato **LM**; in tal caso la portata della tesi potrà essere rimodulata in base all'impegno richiesto.
 Se volete fare la tesi con me è utile prendere visione delle [[tesi:suggerimenti|regole per lo svolgimento di una tesi]].
-=== Programmazione parallela con Chapel ===
+=== [NON PIÙ DISPONIBILE] Simulazione del sistema immunitario umano ===
-[[https://chapel-lang.org/|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 è [[https://chapel-lang.org/download.html|liberamente scaricabile qui]].
+Lo studio del sistema immunitario umano è di enorme interesse; il capostipite dei simulatori del sistema immunitario è stato ImmSim, inizialmente scritto in [[https://en.wikipedia.org/wiki/APL_(programming_language)|APL]] (un linguaggio di programmazione ormai scarsamente utilizzato) e successivamente tradotto in linguaggio C. Sfortunatamente, le implementazioni originali non sono più disponibili, ma nuovi e più accurati modelli sono stati sviluppati.
-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.
+Lo scopo di questa tesi è lo sviluppo di un semplice prototipo di un simulatore CUDA di sistema immunitario, basato ad esempio su automi cellulari (si veda il modello Celada-Seiden tra i riferimenti).
 //Riferimenti://
-  * [[https://chapel-lang.org/docs/|Documentazione di Chapel]] (include un tutorial di programmazione)
-=== Progettazione/implementazione/test di algoritmi paralleli  ===
+  * Franco Celada, Philip E. Seiden, [[https://www.sciencedirect.com/science/article/pii/016756999290135T?via%3Dihub|A computer model of cellular interactions in the immune system]], Immunology Today, 1992
+  * [[https://bmcbioinformatics.biomedcentral.com/articles/10.1186/s12859-019-3181-y|Parallelisation strategies for agent based simulation of immune systems]], BMC Bioinformatics, 2019
+  * Kalita, J. K., Chandrashekar, K., Hans, R., Selvam, P., and Newell, M. K. 2006. [[http://dx.doi.org/10.1504/IJBRA.2006.009194|Computational modelling and simulation of the immune system]]. Int. J. Bioinformatics Res. Appl. 2, 1 (Mar. 2006), 63-88.
+  * R. Puzone, B. Kohler, P. Seiden, F. Celada, [[https://www.sciencedirect.com/science/article/abs/pii/S0167739X02000754|IMMSIM: A flexible model for in machina experiments on immune system response]], Future Generation Computer Systems.
+  * M. Bernaschi, F. Castiglione, S. Succi, [[https://www.sciencedirect.com/science/article/abs/pii/S0167739X98000788|A high performance simulator of the immune response]], Future Generation Computer Systems, Volume 15, Issue 3, 1 April 1999, Pages 333-342, ISSN 0167-739X,
+  * [[https://link.springer.com/chapter/10.1007/0-387-29295-0_91|Review of Modeling and Stimulating Human Immune Sysytem]], AIAI 2005
+  * B. Bernaschi, F. Castiglione, [[https://www.sciencedirect.com/science/article/abs/pii/S0010482501000117|Design and implementation of an immune system simulator]]
+  * Alan S. Perelson, Gérard Weisbuch, [[https://journals.aps.org/rmp/abstract/10.1103/RevModPhys.69.1219|Immunology for Physicists]], Reviews of Modern Physics, Vol. 69, No. 4, October 1997
-Questo argomento si colloca nell'ambito della programmazione parallela, tema di particolare interesse visto il proliferare di procesori multicore e il successo di architetture di calcolo come le GPU. Sono interessato allo sviluppo di programmi paralleli in qualunque ambito, con particolare interesse al calcolo di metriche su reti sociali (es. [[http://en.wikipedia.org/wiki/Betweenness_centrality|betweenness centrality]], [[http://en.wikipedia.org/wiki/Clustering_coefficient!clustering coefficient]], cammini minimi, eccetera).
+=== Programmazione parallela con Halide ===
-Le tesi su questi argomenti richiedono l'uso di OpenMP, MPI oppure CUDA/OpenCL.
+[[https://halide-lang.org/|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.
-//Riferimenti://
+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.
-  * M. Marzolla, [[https://arxiv.org/abs/1804.07981|Parallel Implementations of Cellular Automata for Traffic Models]]
-  * M. Lambertini, M. Magnani, M. Marzolla, D. Montesi, C. Paolino [[http://www.informatica.unibo.it/ricerca/technical-report/2011/pdfs/2011-05.pdf|Large-Scale Social Network Analysis]]
-  * L. Severini, [[http://amslaurea.unibo.it/5948/|A Parallel Community Detection Algorithm]]
-  * E. Barbieri, [[http://amslaurea.unibo.it/16759/|Analisi dell'efficienza di System on Chip su applicazioni parallele]]
-=== [LM] Implementazione di protocolli di autenticazione "anonimi" ===
+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.
-Implementare meccanismi di autenticazione "anonimi" che consentano agli utenti di usare "identità" diverse nei confronti di siti Web diversi, impedendo quindi ai fornitori di servizi di colludere per scambiarsi informazioni di tracciamento degli utenti. Un altro argomento di interesse potrebbe essere l'implementazione di una applicazione Android per il pagamento anonimo tramite NFC.
+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://
+  * [[https://halide-lang.org/|Halide]]
+  * [[https://halide-lang.org/tutorials/tutorial_introduction.html|Vari tutorial su Halide]]
-  * D. Chaum, [[http://www.chaum.com/articles/Security_Wthout_Identification.htm|Security without identification: Card Computers to make Big Brother Obsolete]].
+=== [NON PIÙ DISPONIBILE] Algoritmi paralleli per analisi di reti complesse ===
-=== [LM] Implementazione di una versione parallela del linguaggio NetLogo ===
+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 [[https://networkx.org/|NetworkX]] per il linguaggio Python.
-[[http://ccl.northwestern.edu/netlogo/|NetLogo]] è un linguaggio di programmazione che consente di realizzare in maniera semplice simulazioni ad agenti. NetLogo estende il linguaggio di programmazione [[http://el.media.mit.edu/logo-foundation/logo/programming.html|Logo]] implementando più "tartarughe" che operano concorrentemente secondo il paradigma SPMD (//Single Program Multiple Data//). La versione attuale di NetLogo è implementata in Java e sfrutta un singolo core del processore; è però interessante osservare che NetLogo deriva da [[http://en.wikipedia.org/wiki/StarLogo|StarLogo]], un linguaggio di programmazione parallelo implementato in *Lisp sulla [[http://en.wikipedia.org/wiki/Connection_Machine|Connection Machine 2]], un supercomputer parallelo con 65K processori.
+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:
-Scopo di questa tesi è lo sviluppo di un prototipo di una versione "realmente" parallela di NetLogo, in grado di sfruttare tutti i core presenti su un sistema multiprocessore a memoria condivisa. Data la complessità di NetLogo, sarà utile realizzare un prototipo ex novo in linguaggio C/C++, anche privo di interfaccia grafica e considerando solo un sottoinsieme limitato delle primitive di NetLogo. Un possibile punto di partenza potrebbe essere il software [[http://www.cs.berkeley.edu/~bh/logo.html|UCBlogo]], implementazione C del linguaggio Logo.
+  * [[https://graph-tool.skewed.de/|graph-tools]]
+  * [[https://networkit.github.io/|networkit]]
+  * [[https://developer.nvidia.com/nvgraph|nvgraph]]
+  * [[https://rapids.ai/|Rapids.AI]]
+//Riferimenti://
+  * M. Lambertini, M. Magnani, M. Marzolla, D. Montesi, C. Paolino [[https://www.moreno.marzolla.name/publications/papers/UBLCS-2011-05.pdf|Large-Scale Social Network Analysis]].
+  * Dario Floris, [[https://amslaurea.unibo.it/28183/|Applicazione del modello di programmazione CUDA per l'analisi di reti blockchain con DiLeNA]], Laurea Magistrale in Informatica, Università di Bologna.
+=== Sviluppo di codice CUDA per ricostruzione di immagini in ambito biomedico  ===
+Questa tesi, in collaborazione con la collega prof. [[https://www.unibo.it/sitoweb/elena.loli/en|Elena Loli Piccolomini]], riguarda la parallelizzazione tramite CUDA di algoritmi per la ricostruzione di immagini 3D provenienti da tomografia computerizzata (TAC) a scopi diagnostici.
+Sono disponibili diversi tipi di algoritmi per applicazioni in specifici settori dell'imaging biomedico; abbiamo collaborazioni in atto con aziende del settore che sono interessate allo sviluppo e ottimizzazione di codice.
 //Riferimenti//
-  * [[https://www.researchgate.net/publication/307882734_HLogo_A_Parallel_Haskell_Variant_of_NetLogo|HLogo: a parallel Haskell variant of NetLogo]]
+  * R. Cavicchioli, J. Cheng Hu, E. Loli Piccolomini, E. Morotti, L. Zanni, [[https://www.nature.com/articles/s41598-019-56920-y|GPU acceleration of a model-based iterative method for Digital Breast Tomosynthesis]].
-  * [[https://dl.acm.org/citation.cfm?id=2043637|A Distributed Platform for Global-Scale Agent-Based Models of Disease Transmission]]
+  * Marco Sangiorgi, [[http://amslaurea.unibo.it/30324/|Profilazione di software medicale in CUDA]], Laurea Triennale in Ingegneria e Scienze Informatiche, Università di Bologna.
-=== [LT/LM] Implementazione di algoritmi paralleli sulla GPU del Raspberry PI ===
-Il SoC utilizzato nel [[http://www.raspberrypi.org/|Raspberry PI]] include una GPU di cui è stata [[http://www.broadcom.com/docs/support/videocore/VideoCoreIV-AG100-R.pdf|rilasciata la documentazione]]. Programmare la GPU del Raspberry PI è al momento piuttosto difficoltoso, perché bisogna operare in assembler (niente CUDA, OpenMP e simili...). Ciononostante è possibile, e iniziano ad essere sviluppate librerie che ne fanno uso. Scopo di questa tesi è l'implementazione di ulteriori (semplici) algoritmi paralleli sulla GPU del Raspberry PI, ad esempio nell'ambito dell'algebra lineare, dell'elaborazione di segnali o della crittografia.
+=== [NON PIÙ DISPONIBILE] Implementazione OpenMP/CUDA di un filtro mediano in tre dimensioni ===
-//Riferimenti://
+In un [[http://amslaurea.unibo.it/29323/|precedente lavoro di tesi]] è stato implementato un algoritmo ottimizzato per il calcolo del filtro mediano di immagini in due dimensioni. Un [[https://en.wikipedia.org/wiki/Median_filter|filtro mediano]] è una computazione //embarrassingly parallel// di tipo stencil, in cui si sostituisce il valore dei pixel di una immagini con il valore mediano di un opportuno intorno di quel pixel. Solitamente l'intorno è una regione quadrata; il valore mediano è il valore che occuperebbe la posizione centrale se l'array dei valori dei pixel della regione fossero ordinati.
-  * [[http://rpiplayground.wordpress.com/2014/05/03/hacking-the-gpu-for-fun-and-profit-pt-1/|Hacking the GPU for fun and profit]]
+Il filtro mediano è ampiamente utilizzato per l'elaborazione di immagini; tuttavia, l'implementazione efficiente non è banale nel caso in cui la dimensione dell'intorno sia elevata e la profondità dell'immagine sia di 16 o 24 bit per pixel (bpp). In questi casi, infatti, gli algoritmi efficienti descritti in letteratura non possono essere applicati.
-  * [[http://petewarden.com/2014/08/07/how-to-optimize-raspberry-pi-code-using-its-gpu/|How to optimize Raspberry Pi code using its GPU]]
-  * [[http://www.raspberrypi.org/forums/viewtopic.php?f=33&t=77231|SHA-256 implementation on QPUs]]
-  * [[http://www.raspberrypi.org/forums/viewtopic.php?f=72&t=79430&p=578470|GEMM example on the QPU]]
-=== [LT/LM] Implementazione di algoritmi paralleli su Parallella Board ===
+Scopo di questa tesi è l'implementazione di un algoritmo OpenMP oppure CUDA (preferibile) per il calcolo del filtro mediano in una immagine bitmap in tre dimensioni. La definizione di filtro mediano si estende in modo banale al caso 3D (il valore di un voxel viene rimpiazzato dal valore mediano dei voxel di un intorno cubito di lato assegnato), ma l'implementazione richiede attenzione.
-La scheda [[https://www.parallella.org/|Parallella]] (non è un errore, si scrive proprio così) è un dispositivo nel quale il processore è affiancato da un coprocessore parallelo composto da 16 core interconnessi a formare una mesh di dimensione 4x4. L'architettura di tale dispositivo è abbastanza peculiare, ma può rivelarsi interessante per certe applicazioni. Lo scopo di questa tesi è di familiarizzare con l'architettura della scheda Parallella e con gli strumenti di sviluppo, nonché valutarne le prestazioni realizzando una implementazione parallela di qualche algoritmo seriale relativo ad un'area di proprio interesse (es., algoritmi su grafi, per visione artificiale, di simulazione, ecc.).
+È disponibile l'implementazione OpenMP e CUDA della versione 2D, che può essere sfruttata come base di partenza.
 //Riferimenti//
-  * [[https://www.parallella.org/2015/05/25/how-the-do-i-program-the-parallella/|Parallella programming]]
+  * M., Ravaioli, [[http://amslaurea.unibo.it/29323/|Sviluppo di codice CUDA per l'ottimizzazione del filtro mediano su immagini 2D]], tesi di laurea in ingegneria e scienze informatiche, università di Bologna, 2023.
-  * A. Cardace, [[http://amslaurea.unibo.it/14383/|Implementazione del modello di Biham-Middleton-Levine sulla Parallella Board]]
+=== Analisi predittiva dello stato di job in sistemi di calcolo di grandi dimensioni ===
+**Nota**: Si tratta di un argomento di tesi magistrale che richiede conoscenza di machine learning.
+**Contesto**: Il [[https://www.cnaf.infn.it/|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).
+=== Data Distribution Management su GPU ===
+Il servizio di data //distribution management// viene utilizzato nei simulatori paralleli e distribuiti conformi allo standard [[https://standards.ieee.org/standard/1516-2010.html|High Level Architecture (HLA)]] per determinare in sostanza le intersezioni tra coppie di (iper-)rettangoli nello spazio. In [[https://arxiv.org/abs/1911.03456|questo lavoro]], svolto in collaborazione con il collega Gabriele D'Angelo, è stato proposto un algoritmo parallelo per architetture a memoria condivisa per risolvere efficientemente il problema. Resta da esplorare la possibilità di implementare un analogo algoritmo su GPU usando CUDA.
+//Riferimenti://
+  * Moreno Marzolla, Gabriele D'Angelo, [[https://dl.acm.org/doi/10.1145/3369759?cid=81100172949|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.
+  * [[https://pads.cs.unibo.it/doku.php?id=parallelddm-paper|Software Download]].
+  * Alcuni risultati molto preliminari sulla parallelizzazione CUDA sono descritti in due tesi di laurea completate in anni passati:
+    * Alex Baiardi, [[http://amslaurea.unibo.it/24692/|Data Distribution Management: un approccio CUDA]], Laurea Triennale in Ingegneria e Scienze Informatiche, Università di Bologna.
+    * Giovanni Poggi, [[http://amslaurea.unibo.it/24988/|Implementazione CUDA su GPU di un algoritmo sort-based per la distribuzione efficiente di dati in simulazioni distribuite]], Laurea Triennale in Ingegneria e Scienze Informatiche, Università di Bologna.