压缩感知重构算法的GPU加速与实现

作     者：张静 

作者单位：中南民族大学 

学位级别：硕士

导师姓名：熊承义

授予年度：2016年

学科分类：08[工学] 080203[工学-机械设计及理论] 0802[工学-机械工程] 

主      题：压缩感知重构 正交匹配追踪 A*正交匹配追踪 并行计算 加速实现 图形处理器 统一计算设备架构 

摘      要：压缩感知理论打破了传统奈奎斯特采样定理对采样率的限制,它在信号具有稀疏性的前提条件下,以较低的采样率实现对信号的压缩采样。压缩感知提出后,在无线通讯、阵列信号处理、模式识别和生物传感等领域得到广泛关注。压缩感知重构方法通常具有较高的计算复杂度,在信号尺度较大时,压缩感知重建需要的时间会急剧增长,导致大尺度信号压缩感知重构的实时性难以满足需要。压缩感知重构算法的加速实现已成为该领域关注的重要问题。随着基于CUDA架构的图形处理单元(GPU)的推行,最初用于图像加速、处理图形转换和渲染等工作的GPU在高性能计算方面得到大量应用。考虑到图形处理器高效的并行执行能力,以及在大尺度并行数据处理上具有的良好加速潜力,本文探讨了基于GPU的压缩感知重构算法的加速方法与实现技术。论文重点对三种压缩感知重构算法(OMP算法、BP算法和A*OMP算法)进行了分析与比较,以及在对算法模块的并行性进行可行性分析的基础上,探讨了在GPU平台上对OMP和A*OMP两种重构算法耗时长模块的并行加速设计与实现,以有效提高大尺度信号压缩感知重构的实时性。本文的主要研究工作及创新如下:(1)研究了基于图形处理器的OMP算法的加速方法及实现。为降低中央处理器与GPU之间传输的延迟,研究了将OMP算法的迭代过程转移到GPU上并行处理的方法。在GPU端,根据全局内存的存取特点改进CUDA程序,以便使存储器的存取满足合并访问条件,从而降低访问延迟。利用流多处理器(SM)的丰富资源,合理分配SM中共享内存,改进线程访问有效降低区冲突,大大提高数据访存速度。(2)探讨了A*OMP算法的并行实现及基于GPU的加速方法。通过将耗时长的矩阵逆运算转化为可并行的矩阵/向量乘运算,并考虑算法内在的相关性,提出一种迭代实现方法以降低计算复杂度。将算法中的矩阵/向量计算映射到GPU上并行执行,利用Jacket并行编程功能有效提升系统加速性能。