Signal MP-Based Sparse Decomposition With GPU-Acceleration

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.