FPGA hardware designs to solve the top-K sparse eigenproblem

Large-scale eigenvalue and eigenvector computation is a key component of many machine learning pipelines, spanning from graph analytics, information retrieval, to recommender systems. Often such pipelines require ingestion and subsequent processing of considerably sized datasets which, in turn, call for architectures that efficient from both a computational and an energy perspective. In this setting, the computation of all eigenpairs of a given matrix is both impractical from an execution time perspective and often unneeded, as algorithms in this frame of application only need a handful of eigencomponents and can retrieve the more relevant behaviors of the problem in matrix form by examining them. As a consequence, this thesis studies the applicability of the FPGA platform to the computation of the most relevant eigenvalues and eigenvectors on large scale sparse matrices representing graph topologies, by proposing a FPGA eigensolver which can independently optimize for both the memory bound and the compute bound workloads of the algorithms needed for this computation. The FPGA eigensolver is evaluated against a state of the art implementation of a Top-K CPU eigensolver on large scale matrices obtaining, on average, a 6.22 times speedup which is agnostic to various matrix distributions and has negligible error. Additionally, the energy consumption of such platform is evaluated to be about a tenth the one consumed by theCPU, making this design viable for datacenter deployments.

Il calcolo di autovalori e autovettori su matrici di larga scala è uno dei componenti principali di vari processi di machine learning, da graph analitics, information retrieval fino ad arrivare a recommender systems. Tali processi richiedono di poter processare dataset estremamente grandi che, come conseguenza, presuppone l'utilizzo di architetture che sono sia efficienti dal punto di vista computazionale che dal punto di vista energetico. In questo contesto, la computazione di tutte le coppie di autovalori e autovettori di una data matrice non solo è poco pratica dal punto di vista del tempo di esecuzione, ma, il più delle volte, non necessaria in quanto gli algoritmi che operano in questi contesti possono ottenere tutte le informazioni di interesse esaminando anche pochi autovalori e autovettori. Per far fronte a questi problemi, questa tesi studia l'applicabilità degli FPGA al calcolo degli autovalori e autovettori più importanti di matrici di larga scala e propone un design FPGA ottimizzato per algorithmi che richiedono sia larga banda di memoria, sia la computazione di molte operazioni matematiche contemporaneamente. La bontà del design FPGA verrà valutata rispetto a una implemenentazione allo stato dell'arte su CPU che può operare su matrici sparse di larga scala, per ottenere uno speedup medio di 6.22 volte che non dipende dalla distribuzione dei valori all'interno della matrix e con errori minimi. In aggiunta a ciò, il rapporto tra i consumi energetici delle due piattaforme è di circa un decimo, che rende il design FPGA applicabile all'utilizzo in ambito datacenter.