Lorenzo Cardone vince l'Outstanding Student Presentation Award durante la 31ª edizione dell'IEEE European Test Symposium
Che cosa accomuna un circuito elettronico, una molecola e una rete informatica? A prima vista sembrano appartenere ad ambiti completamente diversi. Dal punto di vista dei modelli matematici, però, possono essere rappresentati nello stesso modo: come grafi, strutture costituite da nodi, che corrispondono agli elementi del sistema, e archi, che ne descrivono le relazioni. Da questa rappresentazione nasce uno dei problemi classici dell'informatica e della matematica applicata: il problema del massimo comune sottografo, al centro della ricerca del dottorando Lorenzo Cardone, svolta presso il Dipartimento di Automatica e Informatica-DAUIN sotto la supervisione dei professori Stefano Quer e Paolo Bernardi, attività che di recente è stata riconosciuta con due importanti premi internazionali.Il problema consiste nell'individuare, all'interno di due grafi, la struttura più grande che essi condividono: un insieme di nodi e archi che possa essere messo in corrispondenza preservando le relazioni tra gli elementi. Nella variante indotta, considerata in uno dei due lavori premiati, la corrispondenza deve preservare anche l'assenza di collegamenti tra le coppie di nodi selezionate.È un problema estremamente complesso dal punto di vista computazionale: il numero delle possibili corrispondenze cresce combinatoriamente con la dimensione dei grafi e, nel caso generale, non sono noti algoritmi capaci di garantire la soluzione ottimale in tempo polinomiale. Esplorare esaustivamente tutte le alternative diventa quindi rapidamente impraticabile.Eppure, riuscire a trovare queste corrispondenze è fondamentale in moltissimi ambiti.In bioinformatica e chimica computazionale, ad esempio, il confronto tra grafi molecolari permette di individuare sottostrutture comuni e possibili proprietà condivise. Nella sicurezza informatica può aiutare a riconoscere analogie strutturali tra reti, programmi o sistemi complessi. Nella progettazione elettronica, invece, consente di identificare automaticamente porzioni equivalenti di circuiti digitali, semplificando alcune attività di verifica e collaudo.È proprio quest'ultima applicazione a essere al centro della ricerca del gruppo del DAUIN.I moderni microprocessori contengono miliardi di transistor e vengono verificati prima della produzione mediante simulazioni software e piattaforme hardware dedicate basate su FPGA (Field-Programmable Gate Array), dispositivi riconfigurabili che possono emulare il comportamento del circuito. L'emulazione su FPGA accelera notevolmente i test rispetto alla sola simulazione, ma i sistemi necessari per ospitare progetti sempre più complessi possono richiedere molte risorse hardware e comportare costi elevati. Riconoscere automaticamente le porzioni equivalenti presenti in circuiti diversi permette di condividere o riutilizzare parte dell'infrastruttura di test, riducendo le risorse hardware dedicate e rendendo più efficiente l'intero processo di verifica.
