Cache-Aware Implementation of Compressed Sensing Reconstruction using Walsh-Hadamard Transform on a Multicore Architecture

Search for this publication on Google Scholar
Ramgopal, A. (2014). Cache-Aware Implementation of Compressed Sensing Reconstruction using Walsh-Hadamard Transform on a Multicore Architecture. Unc Charlotte Electronic Theses And Dissertations.
Download PDF

Analytics

47 views ◎
26 downloads ⇓


Abstract

The recent development of the compressed sensing (CS) theory has given rise to several algorithms being proposed for signal acquisition and reconstruction. Implementing these algorithms are computationally demanding and pose several challenges for effective shared resource utilization. We describe a native, parallelized realization of the compressed sensing problem on a commercially available multicore architecture. A quick and efficient reconstruction algorithm, Smoothed L0 (SL0), is parallelized and adapted to benefit from the multicore implementation of the sampling basis, the Walsh-Hadamard transform (WHT).Valuable insights on data cache locality are presented from the characterization of miss rate patterns using a cache profiler. We develop performance models for the algorithms using regression, correlating response time with application parameters, memory utilization and other overheads. The matrix generation algorithm shows a high degree of parallelizability with speedup up to 5.6 on an 8-core Intel Xeon, while the recovery algorithm shows a speedup up to 4.5. Our models also demonstrate the synchronization bottlenecks and cache limitations of such threaded multicore implementations.

Details
Author

Ramgopal, Aneesh

Title

Cache-Aware Implementation of Compressed Sensing Reconstruction using Walsh-Hadamard Transform on a Multicore Architecture

Physical Description

1 online resource (56 pages) : PDF

Date

2014

Degree Granting Institution

University of North Carolina at Charlotte

Abstract

The recent development of the compressed sensing (CS) theory has given rise to several algorithms being proposed for signal acquisition and reconstruction. Implementing these algorithms are computationally demanding and pose several challenges for effective shared resource utilization. We describe a native, parallelized realization of the compressed sensing problem on a commercially available multicore architecture. A quick and efficient reconstruction algorithm, Smoothed L0 (SL0), is parallelized and adapted to benefit from the multicore implementation of the sampling basis, the Walsh-Hadamard transform (WHT).Valuable insights on data cache locality are presented from the characterization of miss rate patterns using a cache profiler. We develop performance models for the algorithms using regression, correlating response time with application parameters, memory utilization and other overheads. The matrix generation algorithm shows a high degree of parallelizability with speedup up to 5.6 on an 8-core Intel Xeon, while the recovery algorithm shows a speedup up to 4.5. Our models also demonstrate the synchronization bottlenecks and cache limitations of such threaded multicore implementations.

Genre

masters theses

Subjects--Topics

Electrical engineering
Computer engineering

Degree

M.S.

Keywords

Compressed Sensing
Hadamard
Multicore

Subject Area

Electrical Engineering

Advisor(s)

Joshi, Bharat

Committee Members

Fiddy, Michael
Mukherjee, Arindam

Degree Note

Thesis (M.S.)--University of North Carolina at Charlotte, 2014.

Rights Statement

This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s). For additional information, see http://rightsstatements.org/page/InC/1.0/.

Rights Holder Information

Copyright is held by the author unless otherwise indicated.

Identifier

Ramgopal_uncc_0694N_10658

Permalink

http://hdl.handle.net/20.500.13093/etd:152