Parallel implementation of orthogonal matching pursuit in OpenCL

Abstract

ABSTRACT: Orthogonal matching pursuit (OMP) is one of the most effective techniques to recover a sparse signal from limited number of measurements. However, when the number of measurements necessary is very large recovering the sparse signal would a challenge for CPU. In this thesis we aim to improve the performance of large array reconstruction by using parallel computing technology. We use Open Computing Language (OpenCL) in implementing parallel OMP in CPU and GPU. We also make some modification in pseudoinverse algorithm (i.e. using QR decomposition instead of naive matrix inverse) to improve the robustness of the implementation. To examine the performance and quality of implementation, we consider signals of four different sizes (i.e. small, medium, large and massive) and evaluate the results. We can obtain better performance (over 2 times faster) for signals of large and massive sizes in terms of the speed and accuracy of the reconstruction. Thanks to portability of OpenCL, the proposed implementation can be run on all kind of devices such as embedded devices, smart phones, and laptops. Keywords: Compressive Sensing, Orthogonal Matching Pursuit, OpenCL, Graphic Processing Unit, Central Processing Unit.

………………………………………………………………………………………………………………………………………………………………………………………………………… ÖZ: Dik Eşleştirme Takib tekniği, sınırlı sayıda ölçümlerden bir seyrek sinyal kurtarmak için en cazip tekniklerinden biridir. Ancak, bu sınırlı sayıda ölçümlerin pek çok olduğu zaman, orijinal sinyal kurtarma işi CPU için çok zor olacaktır. Bu tezde önerilen yöntem, CPU tarafından kurtarılması zor olan büyük sayıda olan ölçümler için iyidir. Bu tezde, Heterojen bilgisayar teknolojisini kullanarak, büyük miktarda olan ölçümlerin hızlıca hesaplanması için yeni bir yöntem öneriyoruz. Bu son teknolojinin gücünü kullanmak için, bize ölçümleri işlemekte tüm kaynakları kullanmak için OpenCL yi kullanıyoruz. Deneylere göre, işlem hızında hemen hemen üç kat iyileştirme vardır. Ayrıca bu hesaplama deneyi bize küçük bir hata ile çok net bir sonuç verebilir olduğunu gösteriyoruz. Eğer OpenCL yeni atom fonksiyonunu kullanırsak, kata yakın daha hıza ulaşmamız mümkün olacaktır. Ayrıca, en yüksek performans elde etmek için daha hızlı bir donanım kullanmak da mümkündür. Önerdiğimiz yöntem ile, gömülü cihazlar, akıllı telefonlar ve dizüstü bilgisayarlar gibi her türlü cihazları çalıştırmak için OpenCLyin taşınabilirliğinden yalarlanabiliriz. Anahtar Kelimeler: Ortogonal Eşleştirme Takip, OpenCL, Grafik İşleme Birimi, Merkezi İşlem Birimi.