Floating Point versus Fixed point Tradeoffs in FPGA Implementations of QR Decomposition Algorithm



Abstract Views
731

Downloads
481

Citations

Share

##plugins.themes.bootstrap3.article.sidebar##

Submitted Sep 16, 2019
Published Sep 29, 2019
10.24018/ejece.2019.3.5.127

Abstract viewed = 731 times

Table of Contents

##plugins.themes.bootstrap3.article.main##

A wide variety of digital communication systems are encountered with high computational tasks. QR decomposition is one of such algorithms that can be implemented on FPGAs as a solution to large complex matrix inversion problems. A flexible vector processing architecture for the fixed and floating point implementations of the QR decomposition is presented. The design is implemented on the StratixIV device with 230K logic elements and verified with the SignalTap II built-in logic analyzer. Throughputs of 2.4M and 2.11M decompositions per second with maximum clock frequency of 340 MHz and 360 MHz are achieved for 4×4 matrices with the fixed and floating point designs respectively. The FPGA resource utilizations of the two data type implementations are also compared for different matrix sizes for the StratixIV and Arria10 devices.

Keywords: QR decomposition, FPGA, Fixed point, Floating Point.

Downloads

Download data is not yet available.

References

  1. M. Mahmoodi, B. M. Abadi, H. Khajepur, and M. H. Harirchian. "A robust beamforming approach for early detection of readiness potential with application to brain-computer interface systems." In 2017 39th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC), pp. 2980-2983. IEEE, 2017.
     Google Scholar
  2. S. Amin-Nejad, T. A. Gashteroodkhani, K. Basharkhah, "A Comparison of MVDR and LCMV Beamformers? Floating Point Implementations on FPGAs," Wireless Personal Communications, vol.98, no. 2 , pp.1913-1929, 2018.
     Google Scholar
  3. Available: https://link.springer.com/article/10.1007/s11277-017-4953-1
     Google Scholar
  4. A. El-Amawy and K. R. Dharmarajan, "Parallel VLSI algorithm for stable inversion of dense matrices", IEEE Proceedings on Computers and Digital Techniques, Volume 136, Issue 6, , Nov 1989, pp.575-580.
     Google Scholar
  5. M. Mirmozaffari, "Eco-Efficiency Evaluation in Two-Stage Network Structure: Case Study: Cement Companies". Iranian Journal of Optimization (IJO). Dec. 16, 2018.
     Google Scholar
  6. P. N. Ganchosov, G.K. Kuzmanov, H. Kabakchiev, V. Behar, R. P.Romansky, G. N. Gaydadjiev, "FPGA Implementation of Modified Gram-Schmidt QR-Decomposition", Proceedings of the 3rd HiPEAC Workshop on Reconfigurable Computing, Paphos, Cyprus, Jan. 2009, pp. 41-51.
     Google Scholar
  7. Michael Parker and Dan Pritsker "Floating Point Vector Processing using 28nm FPGAs", Proceedings of the 2012 HPEC conference, September 2012.
     Google Scholar
  8. Ali Irturk, Shahnam Mirzaei and Ryan Kastner, "An Efficient FPGA Implementation of Scalable Matrix Inversion Core using QR Decomposition", UCSD Technical Report, CS2009-0938, 2009.
     Google Scholar
  9. P. Luethi, C. Studer, S. Duetsch, E. Zgraggen, H. Kaeslin, N. Felber, and W. Fichtner, ?Gram-schmidt-based QR decomposition for MIMO detection: VLSI implementation and comparison,? in IEEE Asia Paci?c Conference on Circuits and Systems, APCCAS, 2008, pp.830?833.
     Google Scholar
  10. Richard L. Walke, Robert W. M. Smith and Gaye Lightbody,"20-GFLOPS QR processor on a Xilinx Virtex-E FPGA", International Society for Optics and Photonics. Proceeding of SPIE Advanced Signal Processing Algorithms, Architectures and implementations X, 2000, vol.4116, pp. 300-310.
     Google Scholar
  11. H. Firouzkouhi, "FPGA Based Implementation of Cascaded Multi-level Inverter with Adjustable DC Sources", International Journal of Research and Engineering (IJRE), vol. 5, no. 7, pp. 450-456, July 2018.
     Google Scholar
  12. Available: https://hal.archives-ouvertes.fr/hal-02182656/document
     Google Scholar
  13. I. Berkeley Design Technology, ?An Independent Analysis of Altera?s FPGA Floating-point DSP Design Flow,? 2011.
     Google Scholar
  14. M. Mirmozaffari, A. Alinezhad, "Ranking of Heart Hospitals Using cross-efficiency and two-stage DEA," 7th International Conference on Computer and Knowledge Engineering (ICCKE), Mashhad, pp. 217-222, 2017.
     Google Scholar
  15. A. Forooghi Nematollahi, A. Dadkhah, O. Asgari Gashteroodkhani, and B. Vahidi, "Optimal sizing and siting of DGs for loss reduction using an iterative-analytical method," Journal of Renewable and Sustainable Energy, vol. 8, p. 055301, 2016.
     Google Scholar
  16. Michael Parker and Volker Mauer, ?Floating Point STAP Implementation on FPGAs", Radar Conference (RADAR), IEEE, May 2011, pp. 901-904.
     Google Scholar
  17. Chitranjan K. Singh, Sushma Honnavara Prasad, and Poras T. Balsara," A Fixed-Point Implementation for QR Decomposition", proceeding of IEEE workshop on Design, Applications, Integration and Software, October 2006, pp75-78.
     Google Scholar
  18. Martin Langhammer, Tom VanCourt, ?FPGA Floating Point Compiler?, Proceedings of the 2009 17th IEEE Symposium on Field Programmable Custom Computing Machines, pp259-262, 2009
     Google Scholar
  19. M. Langhammer, "High performance matrix multiply using fused datapath operators," in 2008 42nd Asilomar Conference on Signals, Systems and Computers. IEEE, October 2008, pp. 153-159
     Google Scholar
  20. Suleyman S. Demirsoy and Martin Langhammer, ?Fused Datapath Floating Point Implementation of Cholesky Decomposition,? Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, February 22 - 24, 2009
     Google Scholar
  21. Y. Y. K. M. A. Hiroyuki, ?Resource and performance evaluations of ?xed point QRD-RLS systolic array through FPGA implementation, IEICE Trans. on Communications" [Online] (4) (2008) 1068?1075.
     Google Scholar
  22. D. Chen and M. Sima, "Fixed-point CORDIC-based QR decomposition by Givens rotations on FPGA,? International Conference on Reconfigurable Computing and FPGAs, 2011, Nov 2011, pp. 327?332.
     Google Scholar
  23. Boonyi, K, Tagapanij, J and Boonpoonga, A., ?FPGA-based Hardware/Software Implementation for MIMO Wireless Communications", International Electrical Engineering Congress (iEECON), March 2014, pp. 1-4.
     Google Scholar
  24. S. Aslan, S. Niu, and J. Saniie, ?FPGA implementation of fast QR decomposition based on Givens rotation,? in, IEEE 55th International Midwest Symposium on Circuits and Systems, 2012, pp. 470?473.
     Google Scholar
  25. Karkooti, M, Cavallaro, J.R, Dick, C., "FPGA Implementation of Matrix Inversion Using QRD-RLS Algorithm", Thirty-Ninth Asilomar Conference on Signals, Systems and Computers, October 2005, pp. 1625-1629.
     Google Scholar