Dataflow acceleration of Krylov subspace sparse banded problems
File(s)fpl14pb-final.pdf (298.86 KB)
Accepted version
Author(s)
Burovskiy, PA
Girdlestone, S
Davies, C
Sherwin, S
Luk, W
Type
Conference Paper
Abstract
Most of the efforts in the FPGA community related to sparse linear algebra focus on increasing the degree of internal parallelism in matrix-vector multiply kernels. We propose a parametrisable dataflow architecture presenting an alternative and complementary approach to support acceleration of banded sparse linear algebra problems which benefit from building a Krylov subspace. We use banded structure of a matrix A to overlap the computations Ax, A2x,..., Akx by building a pipeline of matrix-vector multiplication processing elements (PEs) each performing Aix. Due to on-chip data locality, FLOPS rate sustainable by such pipeline scales linearly with k. Our approach enables trade-off between the number k of overlapped matrix power actions and the level of parallelism in a PE. We illustrate our approach for Google PageRank computation by power iteration for large banded single precision sparse matrices. Our design scales up to 32 sequential PEs with floating point accumulation and 80 PEs with fixed point accumulation on Stratix V D8 FPGA. With 80 single-pipe fixed point PEs clocked at 160Mhz, our design sustains 12.7 GFLOPS.
Date Issued
2014-09-04
Date Acceptance
2014-09-02
Citation
24th International Conference on Field Programmable Logic and Applications, FPL 2014, 2014
ISBN
9783000446450
Publisher
IEEE
Journal / Book Title
24th International Conference on Field Programmable Logic and Applications, FPL 2014
Copyright Statement
© 2014 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Source
24th International Conference on Field Programmable Logic and Applications (FPL), 2014
Start Date
2014-09-02
Coverage Spatial
Munich, Germany