Constraint-Based Search using GPUs and applications to protein structure prediction
Responsabile: Agostino Dovier
Abstract
Negli ultimi anni la diffusione delle General-Purpose Graphics Processing Units (in breve, GPU) sia come supporto hardware presente nella stragrande maggioranza degli attuali calcolatori (fissi e portatili) che come scheda aggiuntiva capace di offrire un alto grado di parallelismo a basso costo, ha spinto ricercatori di varie discipline ad esplorarne le potenzialità per gli scopi di loro interesse. Dal 2012 il gruppo dei proponenti ha presentato, in lavori su atti di convegno e riviste, diversi contributi per sfruttare le GPU per la ricerca di soluzioni in problemi vincolati, dapprima affrontando la risoluzione del problema SAT, proseguendo nella direzione di sviluppare un, più generale, ASP solver, per arrivare alla definizione di un constraint solver. In questo contesto, la GPU si è mostrata estremamente efficiente per la ricerca approssimata di soluzioni con tecniche di Large Neighborhood Search (LNS) e promettente per la parallelizzazione degli algoritmi di propagazione di vincoli complessi (denominati vincoli globali). La generalità e la capacità di manipolazione numerica di un constraint solver permette una agevole codifica del problema della predizione di una proteina e la tecnica di LNS si è mostrata particolarmente adatta alla rapida predizione di strutture sub-ottime.
Il presente progetto si articolerà principalmente ma non esclusivamente nelle seguenti tre direttive principali
- studio ed implementazione parallela di algoritmi per la propagazione di vincoli globali complessi
- testing delle implementazioni di cui al punto sopra sui benchmarks della Minizinc challenge, competizione annuale dei constraint solver
- testing e tuning delle implementazioni di cui sopra in varianti del problema del protein structure prediction (loop modeling, protein insertion, docking, etc)