压缩感知重构算法的并行化及GPU加速

doi:10.6040/j.issn.1672-3961.0.2017.413

山东大学学报(工学版) ›› 2018, Vol. 48 ›› Issue (3): 110-114.doi: 10.6040/j.issn.1672-3961.0.2017.413

压缩感知重构算法的并行化及GPU加速

何文杰 ¹,何伟超²,孙权森^1*

1. 南京理工大学计算机科学与工程学院, 江苏南京 210094;2. 电子科技大学计算机科学与工程学院, 四川成都 610054

收稿日期:2017-05-09 出版日期:2018-06-20 发布日期:2017-05-09
通讯作者: 孙权森(1966— ),男,山东济宁人,博士,教授,主要研究方向为模式识别. E-mail: sunquansen@njust.edu.cn E-mail:1021458687@qq.com
作者简介:何文杰(1993— ),男,湖北仙桃人,硕士研究生,主要研究方向为并行计算. E-mail: 1021458687@qq.com

Parallelization and GPU acceleration of compressive sensing reconstruction algorithm

HE Wenjie¹, HE Weichao², SUN Quansen^1*

1. School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, Jiangsu, China;
2. School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 610054, Sichuan, China

Received:2017-05-09 Online:2018-06-20 Published:2017-05-09

摘要/Abstract

摘要： 针对压缩感知重构算法计算实时性太差的问题,提出压缩采样追踪匹配(compressive sampling matching pursuit,CoSaMP)算法的并行化加速算法。基于多线程技术实现重构算法的粗粒度并行化,分析CoSaMP算法的计算热点,将其中耗时较多的矩阵操作移植在图形处理器(graphics processing unit, GPU)上,实现算法的细粒度并行化。在测试图像上进行试验,结果表明:并行化加速算法取得50倍的加速效果,有效地降低重构算法的计算时间开销。

关键词: 重构算法, 算法加速, 图形处理器, 并行化计算, 压缩感知

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

中图分类号:

TP391

何文杰 ,何伟超,孙权森. 压缩感知重构算法的并行化及GPU加速[J]. 山东大学学报(工学版), 2018, 48(3): 110-114.

HE Wenjie, HE Weichao, SUN Quansen. Parallelization and GPU acceleration of compressive sensing reconstruction algorithm[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 110-114.

参考文献

[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.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

压缩感知重构算法的并行化及GPU加速

Parallelization and GPU acceleration of compressive sensing reconstruction algorithm

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

多维度评价

本文评价

推荐阅读 0