High Performance Architectures for OMP Compressive Sensing Reconstruction Algorithm

Amey Kulkarni
Tinoosh Mohsenin
Energy Efficient High Performance Computing Lab
Computer Science and Electrical Engineering
University of Maryland Baltimore County


Compressive Sensing (CS) is a novel scheme, in
which a signal that is sparse in a known transform domain can
be reconstructed using fewer samples. The signal reconstruction
techniques are computationally intensive and have sluggish
performance, which make them impractical for real-time processing
applications . The paper presents novel architectures for
Orthogonal Matching Pursuit algorithm, one of the popular CS
reconstruction algorithms. We show the implementation results
of proposed architectures on FPGA, ASIC and on a custom
many-core platform. For FPGA and ASIC implementation, a
novel thresholding method is used to reduce the processing time
for the optimization problem by at least 25%. Whereas, for the
custom many-core platform, efficient parallelization techniques
are applied, to reconstruct signals with variant signal lengths
of N and sparsity of m. The algorithm is divided into three
kernels. Each kernel is parallelized to reduce execution time,
whereas efficient reuse of the matrix operators allows us to reduce
area. Matrix operations are efficiently paralellized by taking
advantage of blocked algorithms. For demonstration purpose,
all architectures reconstruct a 256-length signal with maximum
sparsity of 8 using 64 measurements. Implementation on Xilinx
Virtex-5 FPGA, requires 27.14 micro sec to reconstruct the signal using
basic OMP. Whereas, with thresholding method it requires 18 micro sec.
ASIC implementation reconstructs the signal in 13 micro secs. However,
our custom many-core, operating at 1.18 GHz, takes 18.28 micro sec
to complete. Our results show that compared to the previous
published work of the same algorithm and matrix size, proposed
architectures for FPGA and ASIC implementations perform
1.3x and 1.8x respectively faster. Also, the proposed many-core
implementation performs 3000x faster than the CPU and 2000x
faster than the GPU.



A. Kulkarni and T. Mohsenin, "High Performance Architectures for OMP Compressive Sensing Reconstruction Algorithm", 39th Annual GOMACTech Conference, April 2014

BibTeX Entry

author={Amey Kulkarni and Stanislaus, J.L.V.M.  and Tinoosh Mohsenin}, 
title = {High Performance Architectures for OMP Compressive Sensing Reconstruction Algorithm},
journal = {39th Annual GOMACTech Conference},
month = {April},
year = {2014},}

EEHPC Laboratory |CSEE Dept. | University of Maryland Baltimore County

Last update: April 4, 2014