Abstract: Aimed at the poor real-time performance of the compression sensing reconstruction algorithm, the parallel acceleration of the compressive sampling matching pursuit(CoSaMP)algorithm was proposed. Coarse grained parallelization of reconstruction algorithm was realized based on multithreading technology. The hotspot of CoSaMP algorithm was analyzed, and the matrix operation which was time-consuming was transplanted to graphics processing unit(GPU)to achieve fine grained parallelization of the algorithm. The experiments on the test image showed that 50-fold acceleration speedup was achieved and the study reduced the computing time cost of the reconstruction algorithm effectively.

Key words: reconstruction, algorithm acceleration, graphics processing unit, compressed sensing, parallelization computing [1] DONOHO D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4):1289-1306.
[2] LUSTING M, DONOHO D, PAULY J M. Sparse MRI: the application of compressed sensing for rapid MR imaging [J]. Magnetic Resonance in Medicine, 2007, 58(6):1182-1195.
[3] FIGUEIREDO M A T, NOWAK R D, WRIGHT S J. Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems[J]. IEEE Journal of Selected Topics in Signal Processing, 2008, 1(4):586-597.
[4] GHAHREMANI M, GHASSEMIAN H. Remote sensing image fusion using ripplet transform and compressed sensing[J]. IEEE Geoscience & Remote Sensing Letters, 2014, 12(3):502-506.
[5] WANG L, LU K, LIU P. Compressed sensing of a remote sensing image based on the priors of the reference image[J]. IEEE Geoscience & Remote Sensing Letters, 2015, 12(4):736-740.
[6] BLANCHARD J D, TANNER J. GPU accelerated greedy algorithms for compressed sensing[J]. Mathematical Programming Computation, 2013, 5(3):267-304.
[7] CHO M, MISHRA K V, XU W. Computable performance guarantees for compressed sensing matrices[J]. Eurasip Journal on Advances in Signal Processing, 2018, 2018(1):16.
[8] KARAHANOGLU N B, ERDOGAN H. A*orthogonal matching pursuit: best-first search for compressed sensing signal recovery[J]. Digital Signal Processing, 2012, 22(4):555-568.
[9] ZHAO Y, YOSHIGOE K, BIAN J, et al. A distributed graph-parallel computing system with lightweight communication overhead[J]. IEEE Transactions on Big Data, 2017, 2(3):204-218.
[10] ASANOVIC K, BODIK R, DEMMEL J, et al. A view of the parallel computing landscape[J]. Communications of the Acm, 2009, 52(10):56-67.
[11] GARLAND M, GRAND S L, NICKOLLS J, et al. Parallel computing experiences with CUDA[J]. Micro IEEE, 2008, 28(4):13-27.
[12] SHI L, CHEN H, SUN J. VCUDA: GPU accelerated high performance computing in virtual machines[J]. IEEE Transactions on Computers, 2012, 61(6):804-816.
[13] EGEL A, PATTELLI L, MAZZAMUTO G, et al. CELES: CUDA-accelerated simulation of electromagnetic scattering by large ensembles of spheres[J]. Journal of Quantitative Spectroscopy & Radiative Transfer, 2017, 199:103-110.
[14] JIANG H, GANESAN N. CUDAMPF: a multi-tiered parallel framework for accelerating protein sequence search in HMMER on CUDA-enabled GPU[J]. Bmc Bioinformatics, 2016, 17(1):1-16.
[15] GILBERT R, MIJAILOVICH S. Distributed multi-scale muscle simulation in a hybrid MPI-CUDA computational environment[J]. Simulation, 2016, 92(1):19-31.
[16] HANAPPE P, BEURIVÉ A, LAGUZET F, et al. Famous, faster: using parallel computing techniques to accelerate the FAMOUS/HadCM3 climate model with a focus on the radiative transfer algorithm[J]. Geoscientific Model Development Discussions, 2011, 4(3):1273-1303.
[17] MAROOSI A, MUNIYANDI R C, SUNDARARAJAN E, et al. Parallel and distributed computing models on a graphics processing unit to accelerate simulation of membrane systems[J]. Simulation Modelling Practice & Theory, 2014, 47(47):60-78.
[18] HUANG J W, ZHANG L Q, JIANG Z Y, et al. Heterogeneous parallel computing accelerated iterative subpixel digital image correlation[J]. Science China Technological Sciences, 2018, 61(1):74-85.
[19] ROMERO-LAORDEN D, VILLAZÓN-TERRAZAS J, MARTÍNEZ-GRAULLERA O, et al. Analysis of parallel computing strategies to accelerate ultrasound imaging processes[J]. IEEE Transactions on Parallel & Distributed Systems, 2016, 27(12):3429-3440.
[20] GUNARATHNE T, ZHANG B, WU T L, et al. Scalable parallel computing on clouds using Twister4Azure iterative MapReduce[J]. Future Generation Computer Systems, 2013, 29(4):1035-1048.
[21] LI S, FENG J. An optimized data processing model for computer big data platform based on parallel computing[J]. Boletin Tecnico/Technical Bulletin, 2017, 55(8):318-324.
[22] BLANCHARD J D, TANNER J. GPU accelerated greedy algorithms for compressed sensing[J]. Mathematical Programming Computation, 2013, 5(3):267-304.
[23] MOUSTAFA M, EBEID H M, HELMY A, et al. Rapid real-time generation of super-resolution hyperspectral images through compressive sensing and GPU[J]. International Journal of Remote Sensing, 2016, 37(18):4201-4224.
[24] BERNABÉ S, MARTÍN G, NASCIMENTO J M P, et al. Parallel hyperspectral coded aperture for compressive sensing on GPUs[J]. IEEE Journal of Selected Topics in Applied Earth Observations & Remote Sensing, 2016, 9(2):932-944. 地址: 济南市山大南路27号（250100）　 电话: 0531-88366735　 E-mail: xbgxb@sdu.edu.cn 本系统由 北京玛格泰克科技发展有限公司 设计开发