Abstract
Orthogonal Matching Pursuit (OMP) is one of the most used image reconstruction algorithm in compressed sensing technique (CS). This algorithm can be divided into two main stages: optimization problem and least square problem (LSP). The most complex and time consuming step of OMP is the LSP resolution. QR decomposition is one of the most used techniques to solve the LSP in a reduced processing time. In this paper, an efficient and optimized implementation of QR decomposition on TMS320C6678 floating point DSP is introduced. A parallel Givens algorithm is designed to make better use of the 2-way set associative cache. A special data arrangement was adopted to avoid cache misses and allow the use of some intrinsic functions. Our implementation reduces significantly the processing time; it is 6.7 times faster than the state of the art implementations. We have achieved a 1-core performance of 1.51 GFLOPS with speedups of up to x20 compared to Standard Givens Rotations (GR) algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Candes, E., Wakin, M.: An introduction to compressive sampling. Sig. Process. Mag. IEEE 25(2), 21–30 (2010)
Yang, D., Li, H., Peterson, G.D., Fathy, A.: “Compressed sensing based UWB receiver: Hardware compressing and FPGA reconstruction”, In: Proceedings of 43rd Annual Conference Information Science Systems (CISS), pp. 198–201 (2009)
Dixon, A.M.R., Allstot, E.G., Chen, A.Y., Gangopadhyay, D., Allstot, D.J.: “Compressed sensing reconstruction: Comparative study with applications to ECG bio-signals”, In: Proceedings of IEEE International Symposium Circuits Systems (ISCAS), pp. 805–808 (2011)
Herman, M.A., Strohmer, T.: High-resolution radar via compressed sensing. Sig. Process. IEEE Trans. 57(6), 2275–2284 (2009)
Yu, Y., Petropulu, A., Poor, H.:“Compressive sensing for mimo radar,” in acoustics, speech and signal processing, In: ICASSP 2009 IEEE International Conference, pp. 3017–3020 (2009)
Lustig, M., Donoho, D., Santos, J., Pauly, J.: Compressed sensing MRI. Sig. Process. Mag. IEEE 25(2), 72–82 (2008)
Tropp, J.A., Gilbert, A.C.: Signal recovery from random measurements via orthogonal matching pursuit. IEEE Trans. Inf. Theor. 53(12), 4655–4666 (2007)
El-Amawy, A., Dharmarajan, K.R.: Parallel VLSI algorithm for stable inversion of dense matrices, IEEE Proc. 136(6) (1989)
Heath, M.T.: Numerical methods for large sparse linear least squares problems, ORNL/CSD-114, Distribution category UC-32 (1983)
Nikolic, Z., Nguyen, H.T., Frantz, G.: Design and implementation of numerical linear algebra algorithms on fixed point DSPs, EURASIP J. Adv. Sig. Process. 2007, p. 22 (2007). doi:10.1155/2007/87046
Maoudj, R., Fety, L., Alexandre, C.: Performance analysis of modified Gram-Schmidt Cholesky implementation on 16 bits-DSP-chip. Int. J. Comput. Digit. Syst. 2, 21–27 (2013). doi:10.12785/ijcds/020103
Huang, Z.Y., Tsai, P.Y.: Efficient implementation of QR decomposition for gigabit MIMO-OFDM systems, In: IEEE Transactions on Circuits and Systems—I: Regular Papers, 58(10) (2011)
TMS320C6678, Multicore fixed and floating-point digital signal processor, Data Manual, Texas Instruments, SPRS691E-November 2010-Accessed March 2014, http://www.ti.com.cn/cn/lit/ds/symlink/tms320c6678.pdf
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Najoui, M., Hatim, A., Bahtat, M., Belkouch, S. (2016). Efficient Implementation of Givens QR Decomposition on VLIW DSP Architecture for Orthogonal Matching Pursuit Image Reconstruction. In: El Oualkadi, A., Choubani, F., El Moussati, A. (eds) Proceedings of the Mediterranean Conference on Information & Communication Technologies 2015. Lecture Notes in Electrical Engineering, vol 380. Springer, Cham. https://doi.org/10.1007/978-3-319-30301-7_16
Download citation
DOI: https://doi.org/10.1007/978-3-319-30301-7_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-30299-7
Online ISBN: 978-3-319-30301-7
eBook Packages: EngineeringEngineering (R0)