Studio e Sviluppo di un algoritmo di routing per FPGA radiation-hardened ottimizzato per GPGPU = Study and Development of a Routing Algorithm for Radiation-Hardened FPGAs Optimized for GPGPU

I Field Programmable Gate Arrays (FPGAs) sono circuiti integrati riprogrammabili un numero indefinito di volte dopo la produzione. Questa caratteristica permette di adattare il comportamento del dispositivo ad applicazioni specifiche e di rispondere rapidamente a nuove esigenze. Il routing è una delle fasi cruciali del flusso di implementazione di un nuovo design su FPGA. Influenza sia l'implementabilità del design che il rispetto dei vincoli temporali dei segnali interni all'FPGA. Questa fase riceve in input le specifiche delle connessioni tra i vari componenti interni del circuito e ha il compito di determinare i percorsi specifici da seguire per ciascun segnale, ottimizzando il loro attraversamento all'interno del dispositivo per garantire efficienza e affidabilità del sistema. Tuttavia, questo processo può essere molto dispendioso in termini di tempo e risorse, spesso rappresentando un collo di bottiglia nella toolchain per FPGA. In questa tesi presentiamo il primo router personalizzato progettato specificamente per le architetture FPGA di NanoXplore resistenti alle radiazioni. Le FPGA di riferimento utilizzate sono NG-Medium e NG-Ultra. Il router, accelerato tramite tecnologia GPU NVIDIA, rappresenta le sue risorse fisiche su un grafo di risorse di routing. Su questo grafo sono applicate due tecniche di parallelizzazione su GPU, ciascuna operante a un diverso livello. La tecnica di basso livello implementa una variante concorrente della ricerca in ampiezza ottimizzata per GPU, parallelizzando l'esplorazione delle risorse sul grafo di routing. La seconda tecnica, operante a livello più alto, suddivide i percorsi da trovare in set indipendenti dal punto di vista topologico delle risorse. Così facendo, è possibile generare contemporaneamente diversi percorsi ognuno appartenente ad un set distinto. È importante notare che i percorsi all'interno dello stesso set devono essere generati in modo sequenziale per evitare conflitti di multithreading relativi alle risorse. Infine, è stata condotta un'analisi delle performance e del consumo di memoria del router. Per quanto riguarda le performance è stato eseguito un confronto tra tre varianti del router. La prima variante è completamente sequenziale su CPU, e utilizza un algoritmo le cui fondamenta poggiano sulla ricerca in ampiezza su grafo. La seconda variante implementa esclusivamente la tecnica di parallelismo a basso livello su GPU, generando quindi i percorsi in modo sequenziale ma parallelizzandone le singole ricerche dei percorsi ottimali. La terza variante implementa entrambe le tecniche di parallelismo. Il confronto ha evidenziato un notevole incremento delle performance, con un miglioramento di circa 100 volte rispetto alla versione sequenziale. Inoltre, l'integrazione della tecnica ad alto livello ha ulteriormente raffinato le performance complessive del processo di routing. Per quanto riguarda il consumo di memoria, è emerso che questo aumenta linearmente rispetto al numero di percorsi generati contemporaneamente. Ciò è dovuto all'allocazione di strutture dati extra necessarie per supportare più ricerche concorrenti sul grafo.