稀疏分解论文：基于GPU加速的信号MP稀疏分解.doc

稀疏分解论文：基于GPU加速的信号MP稀疏分解【中文摘要】信号稀疏分解以其简洁、稀疏、灵活的优良特性成功的应用到信号处理的诸多方面中,成为信号处理研究的热点之一。匹配追踪算法实现简单、便于理解,在稀疏分解诸算法中算法复杂度最低,是信号稀疏分解中运用最广泛的算法。但即使这样,基于MP的信号稀疏分解依然面临分解速度慢、算法复杂度高、计算耗时长的问题。与CPU相比,GPU对大量数据的处理能力更加出色。GPU的存储器带宽也较CPU更有优势。GPU为大量数据的运算提供了新的解决方案,特别是CUDA的提出,使GPU有向通用计算机发展的趋势。针对CPU实现信号MP稀疏分解出现的问题,本文采用NVIDIA公司发布的统一运算设备架构CUDA来进行信号稀疏分解的GPU加速,提高信号稀疏分解的运算速度。首先本文介绍了一维信号稀疏分解的基本原理,特别是基于MP的信号稀疏分解算法思想。接着阐述了NVIDIA公司的GPU产品CUDA,并从硬件和软件两方面介绍了CUDA编程模型、存储器模型、软件体系、执行模式等。然后针对基于MP的信号稀疏分解分解速度慢的缺点,对其采用GPU进行加速来实现。在实现的过程中,本文提出了符合硬件特性的内积运算并行方案及改进方案。与CUDA库函数中的内积运算函数进行比较,内积并行方案的运算效率更出色。该方案成功应用到基于MP的信号稀疏分解中的原子能量运算、信号或其残差与冗余字典中原子的内积运算中。基于CUDA平台,本文对局部运算中冗余字典生成并行实现,提高了字典中原子的生成速度。实验表明,与CPU串行运算相比,在待分解信号长度为8192时,GPU实现基于MP的信号稀疏分解,加速比可达37.10倍。最后针对GPU实现基于MP的信号稀疏分解存在冗余字典过大的问题,对基于FFT的信号MP稀疏分解算法采用GPU进行加速。在实现过程中,本文对冗余子字典、快速傅里叶变换及其反变换等局部运算进行GPU并行实现。同时本文提出的内积并行运算方案成功运用于字典中原子的能量计算中。实验表明,在待分解信号长度为16384时,GPU加速基于FFT的信号MP稀疏分解的速度是CPU串行实现的12.29倍。【英文摘要】Signal sparse decomposition has been successfully applied in many fields with its simple, sparse, flexible characteristics. So signal sparse decomposition becomes one of hot spots in signal processing research. Compared with other sparse decomposition algorithms, Matching Pursuit is easier to understand and realize which making it widely used in sparse decomposition. But there are still some problems for MP algorithm, such as huge algorithm complexity and computational cost.Compared with CPU, GPU has the stronger ability in processing large amounts of data and much wider memory bandwidth. It provides a solution for the large amounts of data computation. With the proposed CUDA, GPU has developed from graphic processing unit to general purpose unit.This thesis concentrates on the matching pursuit algorithm based on CPU. We carry out further research for matching pursuit algorithm based on GPU to improve sparse decomposition rate.Firstly, this thesis introduces the basic principle of signals sparse decomposition, especially the principle for sparse decomposition based on matching pursuit. Then this thesis introduces GPU of NVIDIA Corporation, especially parallel computing features with CUDA, including CUDA programming model, CUDA software system, CUDA memory model, CUDA execution modes and so on.Paying attention to the slow rate of sparse decomposition, GPU is used to accelerate and realize. In the process of realization, inner product parallel computing solutions meeting the hardware features have been proposed. Compared with the inner product CUDA library functions, the solutions in this thesis are more efficient. Then CUDA platform is used to generate over-complete dictionary of atoms. And the proposed inner product parallel scheme is successfully applied to the atomic energy operations and inside accumulated computation of signals or its residual signals with atoms. No matter it is local data parallel computing, or the overall signal MP-based sparse decomposition, the operation efficiency of GPU is much higher than that of CPU. When the length of signal is 8192, the speedup of GPU is 37.10.After the realization of signal MP-based sparse decomposition on GPU, there is one problem:redundant dictionary is too big. Signal MP-based sparse decomposition using FFT on GPU has been implemented. In the processing, operations on generating over-complete son dictionary, fast Fourier transform and inverse fast Fourier transform have been implemented in parallel. And the parallel scheme also has been applied successfully to atomic energy calculation. When the length of signal is 16384, the speedup of GPU is 12.29.【关键词】稀疏分解 匹配追踪 FFT GPU CUDA【英文关键词】Sparse Decomposition Matching Pursuit(MP) Fast Fourier Transform GPU CUDA【目录】基于GPU加速的信号MP稀疏分解摘要6-7Abstract7-8第1章 绪论11-161.1 论文研究背景及意义11-121.2 国内外研究现状12-151.2.1 稀疏分解研究现状12-131.2.2 GPU高性能运算特性13-151.3 本文的章节安排15-16第2章 信号MP稀疏分解和CUDA运算平台16-232.1 信号MP稀疏分解算法16-192.1.1 信号MP稀疏分解算法思想16-172.1.2 信号质量评价标准17-182.1.3 超完备冗余字典182.1.4 基于FFT的信号MP稀疏分解18-192.2 基于CUDA的GPU通用计算19-222.2.1 GPU体系架构19-202.2.2 CUDA编程平台概述20-222.2.3 性能测试平台222.3 本章小结22-23第3章 GPU加速基于MP的信号稀疏分解23-473.1 信号MP稀疏分解并行运算结构设计23-253.2 基于GPU的MP稀疏分解整体算法的构建25-273.3 内积运算并行分析27-343.3.1 内积并行运算方案一27-283.3.2 内积并行运算方案二28-293.3.3 内积并行运算方案三29-303.3.4 内积并行运算方案四30-343.4 基于MP的信号稀疏分解中数据的并行性实验分析34-413.4.1 冗余字典的并行生成及实验分析34-373.4.2 原子能量运算并行实现及实验分析37-413.5 稀疏分解的GPU实现实验结果与分析41-463.6 本章小结46-47第4章 GPU加速基于FFT的信号MP稀疏分解47-