A randomized algorithm for functional unit sharing

La sintesi ad alto livello e' il processo che si occupa della traduzione della descrizione comportamentale di un circuito in un codice che viene direttamente mappato su schede FPGA. L'efficienza del processo di sintesi ha pertanto un notevole impatto nel determinare le performance in termini di latenza, area e consumo energetico del circuito risultante. La recente diffusione dei dispositivi FPGA, da uno scenario prettamente prototipale a quello dell'elettronica di consumo, ha marcatamente amplificato l'esigenza di approcci efficienti alla sintesi. Tra gli aspetti chiave per raggiungere un sostanziale risparmio in termini di area figura in primo luogo un'allocazione delle unita' funzionali che ne massimizzi l'utilizzo. Il presente lavoro di tesi si focalizza pertanto sullo step di allocazione delle risorse, e in particolare si rivolge all'ottimizzazione dell'area del circuito mediante la condivisione di unita' funzionali. La condivisione di risorse viene modellata come un problema di maximum weighted clique covering, per la soluzione del quale viene proposto l'impiego di un algoritmo di Monte Carlo massivamente parallelizzabile. L'impostazione iterativa dell'algoritmo proposto consente una allocazione di risorse ottimale, massimizzando la condivisione di risorse all'interno del circuito e congiuntamente minimizzandone i costi di interconnessione. Nei seguenti capitoli saranno introdotti i concetti teorici alla base della soluzione proposta. Si mostrera' inoltre come l'adozione dell'algoritmo proposto all'interno del framewok PandA abbia portato a guadagni in termini di area fino al 25% su noti benchmark. Saranno infine fornite indicazioni circa dei possibili sviluppi futuri.