压缩感知算法的并行化研究

并行之美基于GPU的图像压缩感知并行算法研究【摘要】压缩感知是近几年出现的一种新型信号处理方法，以远低于Nyquist频率对信号同时进行压缩与采样，然后通过求解一个最优化问题就能从少量的观测值中以较高的概率重构出原始信号。目前，这种方法已被引入到遥感图像处理领域中，然而，由于遥感图像具有高分辨率、多时相、数据量大等特点，重构信号时间急剧增加，使得压缩感知理论在遥感图像处理实际应用中存在一定待解决的问题。若仅使用传统CPU进行串行处理，运行时间过长，无法满足人们对算法的实时/准实时处理要求。最近几年，GPU计算能力得到很大的提升，具有强大的浮点运算能力，已成为提高算法处理速度最有效的方式之一。因此，本论文利用GPU的并行特性，采用OpenCL编程模型探索了压缩感知算法在GPU平台上并行实现。【关键词】压缩感知算法；GPU；并行计算；图像处理；1引言1.1压缩感知算法随着信息时代的飞速发展，在处理数字信息问题中，传统Nyquist采样定理已无法满足需求。为解决这一问题，Donoho和Candes等人于2006年提出了压缩感知(CompressiveSensing，CS)的全新信号采样理论[1]。这一新颖信息获取理论指出：在某一已知变换域中稀疏表示的高维数据可通过一种不相关的观测矩阵投影到低维空间中，然后从少量的测量数据中采用一定的重构算法就可以高概率地恢复出高维数据。压缩感知通过将压缩和采样合二为一，提高了数据的采样速度，但在解码端却由于重构算法复杂度高，仅采用传统的串行方式进行处理，存在运行时间过长，难以应用到实际中去。近几年，GPU(GraphicProcessingUnit，图像处理器)的并行处理能力不断增强，可以使数据密集型算法获得更快的处理速度[2]。压缩感知是属于数据密集型应用，包含大规模矩阵运算，数据相关性小，特别适合并行处理，将GPU应用到压缩感知算法上进行并行化，是目前的研究热点之一[3]。1.2GPU简介GPU是相对于CPU的一个概念，在1999年，由NVIDIA公司发布GeForce256图形处理芯片时首次提出。近年来，GPU正在高速发展，极大地促进了计算机图形处理速度和质量的提高，不仅加快了相关应用领域的发展，同时也为人们利用GPU进行通用计算提供了良好的处理平台。随着计算机并行处理可编程性的不断发展，目前GPU架构兼具流处理、可编程流水线、高密集并行运算等新的特性，其GPU的并行计算能力得到了各个科学计算领域的高度关注。1,3并行计算简介在当今计算机发展的过程中，计算机处理速度的不断加快是人们一直以来追求的目标，然而发展速度却限制于硬件发展速度的。因此，在新一代的计算机中，为加快算法的处理速度，人们开始采用并行技术来改善其处理速度。并行计算（ParallelComputing）是指同时使用多种计算资源来解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。在并行计算模式上，主要可以分为时间并行和空间并行两种模式。时间并行是指将任务划分为不同的部分，各部分可以在同一时间内同时进行处理。空间并行是指在多个计算单元上同时执行计算任务，具体分为数据并行和任务并行。数据并行是指对于同一任务，将所需处理的数据合理分配给不同的计算单元执行。任务并行则是将一个计算问题进行拆分，分解为多个子任务且能同时进行处理。一般情况下，任务并行中的算法拆解难度较大，而数据并行则针对任务内的数值操作，只需数据间具有相互独立即可。2压缩感知并行算法分析为实现压缩感知重构算法的并行化，首先需要根据算法原理完成算法的串行编码，然后对压缩感知重构算法进行热点分析，找出制约其算法计算效率的关键步骤，为算法并行化做准备。对于并行算法的设计与实现，根据GPU的并行特性，分析这些耗时步骤的可并行性，完成算法的并行化设计，最后采用OpenCL编程模型实现并行算法的编码，重点研究其并行步骤中内核函数的设计与实现。2.1压缩感知算法理论框架美国科学院院士D.Donoho、E.Candes及华裔科学家T.Tao于2006年正式提出压缩感知理论。其理论框架具体由三个核心部分构成，如图1所示。图1压缩感知算法理论框架信号重构算法是解码端的关键所在，目前应用较多的有MP算法、OMP算法、CoSaMP算法等。本文选择以CoSaMP算法为例。2.2串行重构算法实现及热点分析由前一小节可知，CS理论的重构算法采用CoSaMP算法，此部分是本文需进行并行化研究的部分，其串行算法流程图如图2所示。图2CoSaMP算法串行算法流程图为实现压缩感知重构算法的并行化，需要对串行算法进行热点分析，找出算法的耗时步骤。可利用串行程序热点分析实验，通过计算从而得到对串行算法各步骤的时间统计和整个算法的时间，然后得到CoSaMP算法中各步骤占整个算法的百分比，结果如图3所示：图3各步骤时间占比从图中可以看出，CoSaMP算法耗时主要集中在步骤4，其次是步骤1和步骤6。说明这些步骤是串行算法的性能瓶颈所在。因此，为加速CoSaMP算法的处理时间，需对步骤1、4、6在GPU平台上进行并行化设计。2.3算法并行模式根据CoSaMP算法的热点分析，已确定算法的耗时步骤。本文为提高压缩感知重构算法的处理效率，就需在GPU平台上对这些耗时步骤做并行计算，加快算法处理速度。根据上述分析，对CoSaMP算法的并行化设计，其并行化实现主要是将已分析出的耗时步骤中的函数放在GPU上进行计算，其并行设计流程如图4所示。图4并行算法流程从图中可知，并行CoSaMP算法设计主要分为以下几步：（1）首先是在GPU上初始化、分配内存空间、并将随机矩阵Φ和余量r从主机复制到GPU内存上。设置迭代步数1n；（2）在GPU上完成信号代理计算，即1nTngr的乘积；（3）在GPU上完成矩阵的扩充操作，得到n；（4）估计新的信号是整个算法中最耗时的步骤，在GPU上根据最小二乘法原理得到新的估计信号nx；（5）信号剪切操作是从nx中选出最大的K个元素保存为n，向量kx为n。此步在CPU上计算，将结果复制到GPU；（6）完成更新残差的操作，即矩阵向量乘法、向量减法并行操作，得到残差值nr。并行计算二范数，判定是否满足迭代停止条件。若满足迭代停止条件，则重构信号kxx，若不满足，则1nn，继续循环。根据这些步骤，采用OpenCL编程模型实现并行算法的编程，完成压缩感知重构算法的并行化实现。2.4并行算法实现2.4.1硬件平台并行算法可在AMD平台进行测试。AMD平台是台式机上普通计算平台，由CPU+GPU组成的异构计算平台，其中GPU卡采用AMD厂商生产的GPU卡，平台包含一块4核的CPU和一块AMDGPU卡。2.4.2算法实现采用OpenCL实现串行算法的并行化，并行算法主体过程为OpenCL的平台层设计、运行时设计和内核函数设计与实现这三部分。并行算法的实现过程如图5所示。图5并行算法实现流程在上述三个主要部分中，完成耗时步骤中包含的内核函数设计与实现，其内核函数的性能好坏是并行化设计的关键所在。1）信号代理计算并行实现在信号代理计算过程中，主要是完成矩阵向量乘法计算得到ng值，然后从中选出2K个最大值。此步骤完成矩阵向量乘法内核设计与实现。两层并行模型是OpenCL最重要的创新之一，即一个Kernel函数中存在两个层次的并行，即网格中的工作组之间的并行和工作组中的所有工作项之间的并行，工作组中的所有工作项可以同时访问改工作组中的共享内存。本文设计的矩阵乘法并行函数就是基于该方法，实现两级并行：粗粒度并行和细粒度并行。对于矩阵向量乘法，如Axy（mnAR，nxR）在矩阵与向量相乘过程中，在采用OpenCL语言并行设计时，按照两层并行模型，网格中的工作组完成矩阵A的各行向量与向量x相乘，即粗粒度并行。如图6所示，其中block0-blockB是指网格中包含的所有工作组。图6粗粒度并行在粗粒度的并行下，各个工作组中的所有线程完成矩阵对应行向量ia中的元素与向量x中的元素的乘积，即细粒度并行，实现过程如图7所示，T是一个工作组中包含的所有线程数。图7细粒度并行2）矩阵乘法并行实现对于最小二乘法中的矩阵乘法实现，假定矩阵乘法公式CAB，串行程序在数学上定义为0PijijikkjkCCAB。由上式可知，对于矩阵C的计算，在相乘的过程中需要多次访问矩阵A的行和矩阵B的列，在GPU平台内存分配时，是将矩阵A、B存储在GPU中的全局内存中，若直接计算，需完成2*M*N*P次加载和M*N次存储，由于GPU中全局内存访问速度慢，导致整个内核函数计算效率低。而在GPU上局部内存访问速度远远快于全局内存访问速度，同时每个工作组中局部内存大小固定，因此，将矩阵A与矩阵B采用分块的方式移到局部内存中，矩阵A以行的方式进行分块，B以列的方式进行分块，其分块大小设置为BLOCK_SIZE*BLOCK_SIZE，工作中一个线程处理子块中的一个点，则一个工作组大小设置为BLOCK_SIZE*BLOCK_SIZE，表达形式如图8所示。图8分块矩阵乘法并行设计图3结束语压缩感知理论采用非自适应线性投影来保持信号的原始结构，采用以远低于传Nyquist采样定理对信号进行采样，通过数值最优化算法准确重构出原始信号。它已广泛应用于雷达成像、医疗器械、军事、天文学、线性编码等多个领域。然而，由于压缩感知重构算法计算量大，处理时间过长，无法满足人们对算法处理的实时、准实时处理的要求。近年来，GPU在通用计算中有着出色的表现，特别是随着可编程能力、并行处理能力和应用范围方面的不断提升和扩展，使得GPU已成为提高算法处理速度最有效的方式之一。因此，本文在理解压缩感知算法的基础上，基于GPU这一并行处理器，对CoSaMP重构算法进行并行化研究，重点研究了并行算法中包含的内核函数设计与实现。参考文献[1]D.L.Donoho..Compressedsensing[J].InformationTheory,IEEETransactionson,2006,52(4):1289-1306[2]E.J.Candes.Therestrictedisometrypropertyanditsimplicationsforcompressedsensing[J].ComptesRendusMathematique,2008,346(9):589-592.[3]陈建,苏凯雄,朱宇耀.基于压缩感知的视频编码技术研究[J].福州大学学报:自然科学版,2013,40(6):742-747.[4]B.M.Sanandaji,T.L.Vincent,M.B.Wakin.Compressivetopologyidentificationofinterconnecteddynamicsystemsviaclusteredorthogonalmatchingpursuit[C].InProceedingsof201150thIEEEConferenceonDecisionandControlandEuropeanControlConference(CDC-ECC),2011:174-180[5]Z.Liu,H.Yin,B.Fang,etal.Anovelfusionschemeforvisibleandinfraredimagesbasedoncompressivesensing[J].OpticsCommunications,2015,335:168-177.[6]张娜.并行编码算法及压缩感知图像编码算法的实现[D].海南：海南大学，2012[7]陈帅,李刚,张颢,等.SAR图像压缩采样恢复的GPU并行实现[J].电子与信息学报,2011,33(3):610-615[8]T.T.Do,GanL,NguyenN,etal.Sparsityadaptivematchingpursuitalgorithmforpracticalcompressedsensing[C].InProceedingsof200842ndAsilomarConferenc