The case for reconfigurable architectures in high-performance graph and sparse information retrieval

Graph analytics, information retrieval, and recommender systems are a pervasive component of our society, helping billions of users in finding web pages, movies to watch, and products to buy. Sparse linear algebra is now an essential building block of these workloads. By not storing redundant information, it enables real-time processing of an increasingly large amount of data. In particular, Sparse Matrix-Vector Multiplication (SpMV) is the cornerstone of many complex applications, from graph ranking to approximate search. SpMV does not perform well on general-purpose hardware architectures with traditional caching strategies, as it contains little data reuse and unpredictable memory access patterns. Modern Field Programmable Gate Array (FPGA) accelerator cards have a few tricks up their sleeve. With abundant on-chip memory and HBM they enable novel data representations that maximize operational intensity and parallelism. Reduced-precision fixed-point arithmetic, a distinctive feature of FPGAs, opens the doors to trade-offs between performance and numerical accuracy in error-tolerant workloads such as recommender systems. This thesis proposes a set of SpMV FPGA hardware designs targeted at the needs of graph analytics and recommender systems. These SpMV designs can quickly adapt to different workloads, such as graph ranking, sparse eigensolvers, and sparse embedding similarity search. In all cases, we provide state-of-the-art performance and energy efficiency and study the impact of reduced precision on accuracy. Overall, we establish that FPGAs are a fearsome contender in the race for high-performance sparse computations in graph analytics and recommender systems.

Graph analytics, information retrieval, e recommender systems sono ormai componenti imprescindibili della nostra società, e permettono a miliardi di utenti di trovare pagine web, film da guardare, e oggetti da comprare. L'algebra lineare sparsa è un elemento fondamentale di queste tecnologie. Eliminando i valori ridondanti, permette analisi in tempo reale di una mole sempre crescente di dati. In particolare, la Moltiplicazione di Matrice Sparsa per Vettore (SpMV) è alla base di complesse applicazioni come graph ranking e ricerca approssimata. SpMV non è però efficace su hardware general-purpose con politiche di caching tradizionali, avendo scarso riutilizzo di dati e accessi in memoria imprevedibili. Le più recenti FPGA accelerator card hanno però diversi assi nella manica. Dispongono di abbondante memoria on-chip e di HBM, permettendo elevato parallelismo e l'uso di nuove strutture dati più efficienti. L'aritmetica fixed-point a precisione ridotta, un tratto distintivo delle FPGA, spalanca le porte a compromessi tra performance e accuratezza in applicazioni come recommender system che tollerano approssimazioni. Questa tesi propone un set di design FPGA per SpMV, ottimizzati per le necessità di graph analytics e recommender systems. Questi design di SpMV possono rapidamente adattarsi a svariate applicazioni, come graph ranking e ricerca approssimata di embedding sparsi. In tutti questi casi dimostriamo performance e efficienza allo stato dell'arte, e misuriamo come la precisione numerica ridotta impatta l'accuratezza. Nel complesso, validiamo come le FPGA siano un temibile avversario nella gara per ottimizzare le computazioni sparse in graph analytics e recommender systems.