RRSplit: implementazione multi-thread su CPU e su GPU = RRSplit: multi-threaded implementation on CPU and on GPU

Il problema del massimo comune sottografo è una questione ben conosciuta in informatica, e consiste nel ricercare, dati almeno due grafi, quello che è contemporaneamente isomorfo e di massima dimensione. Tale questione viene anche sfruttata in altri ambiti, quali la scienza molecolare, per ritrovare somiglianze tra proteine o altre molecole, o, addirittura, nel rilevamento di malware. Tuttavia, il problema del MCS è NP-hard, e questo ha quindi costretto, per molto tempo, chiunque abbia approcciato questo problema, a cercare di approssimare la soluzione, in modo tale da poter essere il più vicino possibile a quella ottimale. Negli ultimi anni, però, in parte grazie allo sviluppo tecnologico, ed in parte grazie alla scoperta di nuovi paradigmi, che permettessero di risolvere il MCS in tempi più accettabili, tale problema è stato, in parte, alleviato. Tra i nuovi metodi di risoluzione del MCS, vi è il cosiddetto McSplit, un algoritmo branch and bound che, nel corso degli ultimi anni, è stato preso come riferimento per la risoluzione del problema, e via via modificato in vari modi, seppur nessuno di questi, a parte il McSplit originale, apparentemente, abbia implementato una versione adatta al multi-thread. Nella seguente tesi, quindi, si prende, come riferimento, una delle ultime "versioni" del McSplit, ovvero RRSplit, pubblicata a febbraio del 2025, e, prendendo gli schemi di parallelismo presenti nel McSplit originale, si cerca di rendere tale lavoro funzionante anche in un contesto multi-thread, su CPU. Successivamente, vengono condotte anche delle analisi per capire: -Quanto l'RRSplit abbia giovato di un'implementazione multithread; -Quanto le modifiche apportate in RRSplit abbiano velocizzato, in un contesto multithread, la ricerca di un MCS, rispetto al McSplit parallelo originale. In aggiunta, sono state condotte anche delle analisi sul dataset che è stato utilizzato, per la risoluzione di tale problema, e come le principali caratteristiche dello stesso possono aver influenzato, positivamente o negativamente, le prestazioni degli algoritmi, soffermandoci, in particolar modo, su come l'impiego di grafi, presentanti determinate caratteristiche, possano essere sottoposti più o meno facilmente al pruning presente nell'algoritmo RRSplit. Come ultima parte di questa tesi, prendendo in considerazione un framework, che andasse ad eseguire l'algoritmo di McSplit su GPU, sono state attuate delle modifiche, tali da permettere l'implementazione, sullo stesso, degli elementi chiavi caratterizzanti RRSplit, e da lì sono state condotte delle analisi per capire l'efficacia di tale approccio, confrontando le prestazioni ottenute su RRSplit, implementato su GPU, con quelle che si sono riscontrate con RRSplit su CPU e McSplit su GPU.