Solving Large Top-K Graph Eigenproblems with a Memory and Compute-optimized FPGA Design
Autor: | Francesco Sgherzi, Marco Siracusa, Marco D. Santambrogio, Alberto Parravicini |
---|---|
Jazyk: | angličtina |
Rok vydání: | 2021 |
Předmět: |
FOS: Computer and information sciences
010302 applied physics Speedup Computer science Computation Bandwidth (signal processing) MathematicsofComputing_NUMERICALANALYSIS Hardware Acceleration Sparse Linear Algebra 010103 numerical & computational mathematics 01 natural sciences Computational science Hardware Architecture (cs.AR) 0103 physical sciences SpMV Hardware acceleration Approximate Computing 0101 mathematics Spectral method Field-programmable gate array Eigenvectors Computer Science - Hardware Architecture Eigenvalues and eigenvectors FPGA Sparse matrix |
Zdroj: | FCCM |
Popis: | Large-scale eigenvalue computations on sparse matrices are a key component of graph analytics techniques based on spectral methods. In such applications, an exhaustive computation of all eigenvalues and eigenvectors is impractical and unnecessary, as spectral methods can retrieve the relevant properties of enormous graphs using just the eigenvectors associated with the Top-K largest eigenvalues. In this work, we propose a hardware-optimized algorithm to approximate a solution to the Top-K eigenproblem on sparse matrices representing large graph topologies. We prototype our algorithm through a custom FPGA hardware design that exploits HBM, Systolic Architectures, and mixed-precision arithmetic. We achieve a speedup of 6.22x compared to the highly optimized ARPACK library running on an 80-thread CPU, while keeping high accuracy and 49x better power efficiency. |
Databáze: | OpenAIRE |
Externí odkaz: |