Acceleration of Parallel-Blocked QR Decomposition of Tall-and-Skinny Matrices on FPGAs
Open Access
- 10 May 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Architecture and Code Optimization
- Vol. 18 (3), 1-25
- https://doi.org/10.1145/3447775
Abstract
QR decomposition is one of the most useful factorization kernels in modern numerical linear algebra algorithms. In particular, the decomposition of tall-and-skinny matrices (TSMs) has major applications in areas including scientific computing, machine learning, image processing, wireless networks, and numerical methods. Traditionally, CPUs and GPUs have achieved better throughput on these applications by using large cache hierarchies and compute cores running at a high frequency, leading to high power consumption. With the advent of heterogeneous platforms, however, FPGAs are emerging as a promising viable alternative. In this work, we propose a high-throughput FPGA-based engine that has a very high computational efficiency (ratio of achieved to peak throughput) compared to similar QR solvers running on FPGAs. Although comparable QR solvers achieve an efficiency of 36%, our design exhibits an efficiency of 54%. For TSMs, our experimental results show that our design can outperform highly optimized QR solvers running on CPUs and GPUs. For TSMs with more than 50K rows, our design outperforms the Intel MKL solver running on an Intel quad-core processor by a factor of 1.5×. For TSMs containing 256 columns or less, our design outperforms the NVIDIA CUBLAS solver running on a K40 GPU by a factor of 3.0×. In addition to being fast, our design is energy efficient—competing platforms execute up to 0.6 GFLOPS/Joule, whereas our design executes more than 1.0 GFLOPS/Joule.Keywords
Funding Information
- Office of Naval Research (N00014-18-1-2740)
This publication has 34 references indexed in Scilit:
- High-Throughput FPGA Implementation of QR DecompositionIEEE Transactions on Circuits and Systems II: Express Briefs, 2015
- Intel Math Kernel LibraryPublished by Springer Science and Business Media LLC ,2014
- Synthesis of High‐Purity Ti3SiC2 by Microwave SinteringInternational Journal of Applied Ceramic Technology, 2013
- Communication-optimal Parallel and Sequential QR and LU FactorizationsSIAM Journal on Scientific Computing, 2012
- Robust principal component analysis?Journal of the ACM, 2011
- Towards dense linear algebra for hybrid GPU accelerated manycore systemsParallel Computing, 2010
- FPGA Implementation of QR Decomposition Using MGS AlgorithmLecture Notes in Computer Science, 2010
- A truly two-dimensional systolic array FPGA implementation of QR decompositionACM Transactions on Embedded Computing Systems, 2009
- The decompositional approach to matrix computationComputing in Science & Engineering, 2000
- The WY Representation for Products of Householder MatricesSIAM Journal on Scientific and Statistical Computing, 1987