FPGA için Seyrek Fourier Paralel Algoritmasının Uygulanması
Yang Chao, Qian Hui
(Fizik ve Bilgi Mühendisliği Okulu, Fuzhou Üniversitesi, Fuzhou, Fujian 350108)
: Optimal aramaya dayalı Seyrek Fourier Dönüşümü (SFT) için paralel bir uygulama tasarımı önerdi. İlk olarak, giriş sinyali paralel olarak N gruba bölünür ve hızlı Fourier dönüşümü (FFT) sırasıyla sinyal frekansı bileşenlerinin modül işlemesini gerçekleştirmek için gerçekleştirilir ve daha sonra sıralama ve arama yoluyla elde edilir. FFTW ile karşılaştırıldığında, sinyal uzunluğu 524288'den büyük olduğunda yürütme süresinin daha iyi performansa sahip olacağı doğrulanmıştır; kareleme eşleştirme algoritması ve diğer SFT FPGA uygulamalarıyla karşılaştırıldığında, sistem karmaşıklığı azalır.
: Seyrek Fourier dönüşümü; paralel çerçeve; alan programlanabilir kapı dizisi
: TN911.7 Belge tanımlama kodu: ADII: 10.19358 / j.issn.1674-7720.2017.10.020
Alıntı biçimi : Yang Chao, Qian Hui. FPGA J için seyrek Fourier paralel algoritmasının uygulanması. Mikrobilgisayar ve Uygulama, 2017,36 (10): 70-73.
0 Önsöz
Seyrek Fourier Dönüşümü (Sparse Fourier Transform, SFT) yeni bir algoritma çerçevesidir ve aynı zamanda seyrek spektrum sinyallerini işlemede Hızlı Fourier Dönüşümünün (FFT) bir uzantısıdır. 2003 yılında, AYDINER A A ve diğerleri, seyrek frekans alanı sinyalleri için Fourier dönüşümü temel fikrini önerdiler [1]. Frekans etki alanı seyrek sinyali için, frekans spektrumu, çok seviyeli alt küme spektrumu aracılığıyla elde edilebilir. Daha sonra, IWEN MA ve arkadaşları sıkıştırılmış algılama, entegre örnekleme ve hızlı Fourier dönüşümüne frekans tahmininden ilham aldılar ve klasik bir SFT çerçevesi önerdiler [2]. Bundan sonra, SFT, seyrek spektrum sinyallerinin (ses sinyalleri, tıbbi görüntü sinyalleri gibi) işlenmesinde ve spektrum algılama alanında [3] yaygın olarak kullanılmaktadır. Çok sayıda SFT algoritması önerilmiştir ve bunlar, Nyquist alt örnekleme noktalarının bir alt kümesinin Fourier dönüşümü yoluyla seyrek frekans noktalarını yeniden yapılandırmak için çoğunlukla klasik frekans tahmin algoritmalarını kullanır [4]. Bununla birlikte, klasik SFT'nin alt Nyquist oran örnekleri çoklu örnekleme yoluyla elde edildiğinden, klasik SFT'nin radar sinyalleri gibi gerçek zamanlı sinyalleri işlemek için FFT'nin yerini alması imkansızdır.
2010'dan beri, SFT algoritmasının paralel yapısı büyük ilgi gördü [5]. Paralel SFT, ilk önce paralel alt örnekleme yoluyla hesaplama için gereken tüm zaman alanı verilerini toplar ve ardından FFT aracılığıyla alt doğrusal spektrum tahmin yöntemi aracılığıyla sinyalin seyrek frekansını ve genliğini elde eder. Bu tür bir yöntem, spektrum tahmini için gerekli tüm bilgileri elde etmek için yinelemeli olarak yerini aldığından, çeşitli frekans etki alanı seyrek sinyallerini gerçek zamanlı olarak işleyebilir ve bu da klasik SFT'yi geliştirir. Buna dayanarak, referanslar [6] ~ [8] GPU ve çok çekirdekli CPU üzerinde seyrek Fourier dönüşümünün uygulanmasını tartıştı. Bu çalışmalar, GPU hızlandırmaya dayalı uygulamaların, CPU tabanlı uygulamalardan önemli ölçüde daha hızlı çalıştığını göstermektedir. Bununla birlikte, GPU tabanlı uygulamaların tümü, ana depolama alanı ile GPU depolama alanı arasında bağlantı ve etkileşim sorununa sahiptir, bu nedenle normal veri akışı daha iyi desteklenemez.
GPU'nun paralel veri işleme sınırlamasını çözmek için, bu makale SFT'nin paralel algoritmasını inceler ve FPGA üzerinde uygular ve sinyali yeniden yapılandırmak için Çin kalan teoreminin (CRT) temel ilkelerini uygular. Geleneksel SFT ile karşılaştırıldığında, bu makaledeki yöntem, sistemin karmaşıklığını büyük ölçüde azaltabilir ve donanım ek yükünü azaltabilir. Bu makale önce SFT'nin paralel çerçevesini tanıtır, ardından SFT'nin FPGA uygulama mimarisini tartışır ve son olarak sistemi hem simülasyon sonuçlarından hem de donanım uygulamasından değerlendirir.
1SFT paralel algoritma
SFT paralel algoritması temel olarak aşağı örnekleme, frekans tahmini ve genlik tahmininden oluşur. Aşağı örnekleme sürecinde, giriş sinyali N grubuna bölünür ve her grubun örnekleme faktörü 1, 2, ..., N'dir. Frekansı ve genliği tahmin etmek için Çin Kalıntı Teoremini (CRT) kullanın ve her grubun örnekleme faktörlerini nispeten asal olacak şekilde ayarlayın.
Paralel SFT algoritması, K gecikme parametreleri ve K genlik parametreleri dahil olmak üzere L örnekleme noktalarından 2 K parametresini yeniden oluşturur. Yeniden yapılandırma yönteminin spesifik hesaplama adımları aşağıdaki gibidir: İlk olarak, örnekleme kanallarının sayısının N olduğunu ve her kanalın örnekleme noktalarının sayısının sırasıyla qi, i = 1,2, ..., N olduğunu varsayalım. X ~ = M * X'i hesaplayın, burada M aşağı örnekleme matrisidir ve X örneklenen örnektir. Bundan sonra, X ^ = DFT (X ~) elde etmek için X ~ üzerinde DFT dönüşümü gerçekleştirin. X ^ vektöründeki değerleri büyüklüğe göre büyükten küçüğe sıralayın ve hk'yi hesaplayın:
hk = kthMAX | X ^ j |, k [0, K] (1)
K, belirlenmiş yeniden yapılandırılmış sinyalin parametresidir. Hk elde edildikten sonra, kalan bilgi r1, khk konum modq1 kalan işlemle elde edilebilir. Paralel sorgulama yoluyla geri kalanın en uygun çözümünü arayın:
tminmint [0, qj] | hk-X ^ t * q1 + r1, k |, j [2, N] (2)
rj, k = r1, k + tmin * q1modqj, j [2, N] (3)
k ile r1, b, ..., rN, b arasındaki gecikme parametresini yeniden yapılandırmak için CRT'yi kullanarak, genlik tahmin parametresi formül (4) ve (5) ile elde edilebilir:
x = gerçek (hk) | k
y = görüntü (hk) | k (4)
ak = | x + iy | (5)
2SFT'nin ana bölümünün FPGA uygulaması
Bu makale, SFT örnekleme algoritmasının FPGA uygulama mimarisini oluşturmak için MATLAB-Simulink aracını kullanmayı ele almaktadır. Şekil 1, esas olarak aşağı örnekleme, frekans tahmini ve genlik tahminini içeren örnekleme kanallarının sayısı N = 3 olduğunda SFT paralel yapısını gösterir.
Şekil 1'de gösterildiği gibi, frekans tahmini ve genlik tahmini aynı donanım yapısını paylaşır.Sinyal aşağı örneklendikten sonra, FFT işlemi ile karmaşık çıkış sinyali elde edilir.Karmaşık sinyali sıralamak için, karmaşık sinyal modüle edilir ve gönderilir Ayırma ağında, ayırma ağının yapısı, her kanal tarafından ayırma ağına gönderilen farklı sayıda nokta nedeniyle biraz farklı olacaktır. Sinyalin genliğini ve frekansını tahmin etmek için CRT'yi kullanmadan önce, sinyalin geri kalanı ve optimum çözüm gibi işlemleri gerçekleştirmek gerekir. Bunlar arasında, optimum çözüm işleminin özü, giriş sinyalinin maksimum değerini elde etmek ve sıralanan sinyalin orijinal giriş sinyalindeki konumunu elde etmek için ayırma ağı fikrini kullanan ayırma ağıdır; CRT modülü, bazı toplayıcılardan ve çarpanlardan oluşur.
Giriş sinyali, aşağı örneklenmiş sinyali elde etmek için çoklayıcıdan geçer, bu nedenle bu kısım esas olarak aşağı örneklenmiş sinyalin frekans tahminini ve genlik tahminini inceler Frekans tahmini, optimum çözüm modülünü ve CRT yeniden yapılandırma modülünü içerir. Ek olarak, donanım yapısı departmanı ayrıca bir depolama ve kontrol ünitesi içerir.Her kanalın örnekleme faktörü ql, parametre t ve sıralama pozisyon bilgisi depolama ünitesinde saklanır.Kontrol ünitesi okuma ve yazma hafıza işlemlerini gerçekleştirmek için adres değerleri üretir ve gerekli çıktıları verir. Aritmetik modülü başlatmak için kontrol sinyali.
Bu tasarımda, sinyal uzunluğunu N = 223, K parametrelerinin sayısını ve M = 3 örnekleme kanallarının sayısını ayarlayın. Her kanalın örnekleme noktaları q1, q2, q3; q1, q2, q3 karşılıklı olarak hazırlanır ve Ürün, sinyal uzunluğu N'den daha büyüktür. Bu nedenle, Çin'in kalan teoremi aracılığıyla, orijinal sinyalin tüm bilgileri, genlik ve frekans tahmini için gereken örnekleme noktalarının sayısını azaltan q1 + q2 + q3 örnekleme noktalarından elde edilebilir. Her bir ana işlev modülünün tasarımı aşağıda tanıtılmıştır.
2.1 Frekans tahmini
2.1.1 Optimal çözüm modülü uygulama mimarisi
Frekans tahmin modülünün temel kısmı, en uygun çözümü elde etmektir ve optimum çözüm uygulama mimarisi Şekil 2'de gösterilmiştir. Şekilde X ^ t * q1 + r1, k çoklayıcı MUX ile numuneler örneklenerek elde edilebilir. T'nin farklı değerine göre çoklu sabit noktalı örneklemenin örnek değeri elde edilebilir. Ayırma ağının üç girişli bir yapısı olduğunda, rl, k, ayırma ağının optimal çözüm modülü yapısı ağ modülünde elde edilen konum bilgisi verilerine karşılık gelen k1,1, k1,2, k1,3 ile elde edilen değeri temsil eder. T'nin değer aralığı 0 ~ qj, j = 2,3'tür, burada j = 2, q2 = 4 ve benzer şekilde q3 = 5 olduğunda; her iki durumda da sadece t değerindeki değişiklik sabit noktalı örneklemenin örnek noktasına götürür Değer değişir ve ilgili modül mimarisi aynıdır, bu nedenle burada sadece j = 2'deki durum analiz edilir.
Ayırma ağı yapısına göre, iki set gerekli girdi verisi vardır, biri minimum değeri bulmak için sıralanması gereken veriler, diğeri ise verilere karşılık gelen konum bilgisidir. Bu şekilde, ayırma ağı minimum değeri elde ettikten sonra, karşılık gelen t değeri başka aritmetik işlemler olmaksızın doğrudan elde edilebilir. Bu nedenle, sıralanacak veriler, sıralama ağının veri giriş arabirimine paralel olarak aktarılır ve karşılık gelen konum bilgisi t değeri de paralel olarak sıralama ağının konum bilgisi arabirimine aktarılır.
Şekil 3'te gösterildiği gibi, orijinal 3 giriş sinyali numaraları 1, 2, 3'tür. Bu modül, üç sinyali büyükten küçüğe sıralamayı gerçekleştirir ve sıralanan sinyalin sıra numarasını orijinal sırayla yani pozisyon alınır. Şekil 3, 3-girişli yapının sıra diyagramını göstermektedir.4-girişli ve hatta daha fazla giriş yapısı diyagramının prensibi aynıdır.Resimdeki karşılaştırıcının çıkışı, çoklayıcının sel seçim ucunun girişi olarak kullanılır ve karşılaştırıcı ve çoklayıcının donanım devresi kullanılır. Bağlantı, mantıksal karşılaştırma ve seçim sıralaması gerçekleştirir. k1,1, k1,2, k1,3 sıralama ağından sonra 3 giriş sinyalinin çıkış sinyalleridir, k1,1 vardır > k1,2 > k1,3. k1,1_loc, k1,2_loc, k1,3_loc orijinal dizide sırasıyla k1,1, k1,2, k1,3'ün pozisyonlarını kaydeder. Aynı zamanda konum bilgisi, konum bilgisi hafızasında saklanır.
2.1.2 CRT modülü mimarisi
Optimal çözüm modülü, bir dizi kalan bilgiyi çıkarır Çin geri kalan teoremini kullanarak, frekans seti, bir dizi kümülatif toplam işlemiyle kolayca elde edilebilir ve ayrıca gecikme parametresi k elde edilebilir. Çin'in kalan teoreminden aşağıdaki denklemler elde edilebilir:
xr1 (modq1)
xr2 (modq2)
xrn (modqn) (6)
Bunlar arasında, ri (i = 1,2, ..., n) bir frekans noktaları koleksiyonudur ve qi (i = 1,2, ..., n) bir örnekleme noktaları koleksiyonudur. Q'nun q1'in qn'ye çarpımı olduğunu varsayalım ve Qi = Q / qi, i {1,2, ..., n} olarak ayarlayın, ti Qi modulo qi'nin tersidir, sonra:
x = ni = 1ritiQi (7)
Şekil 4, CRT yeniden yapılandırma modülü mimarisini bir frekans noktasında göstermektedir.
2.2 Genlik tahmini
Genlik tahmininde, CRT yeniden yapılandırma modülünde elde edilen frekans setleri w1 ve w2 sırasıyla L1 ve L2 ile kalan işlemler için kullanılır ve buna göre hk elde edilir.Orijinal denklemler (4) ve (5) orijinali elde etmek için kullanılabilir. Sinyalin genliğinin tahmini. Bunlar arasında, frekans kümeleri w1 ve w2, CRT modülü tarafından elde edilir ve Şekil 5'teki kalanı hesaplama işlevi, frekans kümeleri w1 ve w2'nin, sırasıyla, L1 ve L2 örnekleme noktalarının sayısı üzerinde kalan işlemi gerçekleştirmesidir. Girdi dizisi xl, seyreklik değeri, örnekleme kanallarının sayısı ve her kanalın örnekleme noktalarının sayısı, çarpanın çağırması için kayıtta depolanır. Giriş sinyalinin gerçek ve sanal kısımlarının maksimum değerini elde etmek için sıralama ağını kullanmak ve ardından genlik değerinin tahminini elde etmek için modülü almak. Genlik tahmin modeli, ayırma ağının 4 girişli bir yapıya sahip olduğu Şekil 5'te gösterilmektedir.
3 Sonuç analizi ve performans değerlendirmesi
Algoritma çerçevesinin etkinliğini değerlendirmek için, bunu çok çekirdekli CPU'lar ve GPU'lar üzerinde çalışabilen, hızlı hesaplama ayrık Fourier dönüşümü için bir kitaplık olan FFTW ile karşılaştırın. Seyreklik k 1000'de sabit olduğunda sinyal uzunluğundaki değişimin yürütme süresi üzerindeki etkisi ve sinyal uzunluğu N 223'te sabit olduğunda seyreklik değişiminin yürütme süresi üzerindeki etkisi dikkate alındığında, karşılaştırma sonuçları Şekil 6'da gösterilmektedir.
Bu makalede tartışılan seyrek Fourier dönüşümü örnekleme çerçevesinin performansı, bilinen OMP algoritma çerçevesi ile karşılaştırılır ve sinyal uzunluğu N = 32, parametre sayısı K = 2 ve örnekleme noktası sayısı olan bir örnekleme çerçevesi gerçekleştirilir. Bunların arasında, gerekli tüm vektörlerin, sabitlerin veya matrislerin depolanmasını gerçekleştirmek için RAM bloğunu kullanın. OMP mimarisi [9] ve SFT mimarisi [10], bu makalenin algoritma mimarisi ile karşılaştırmak için aynı platformda uygulanmıştır Sonuçlar Tablo 1'de gösterilmiştir.
OMP mimarisi ile karşılaştırıldığında, bu makalede önerilen mimari DSP48E sayısını ve gerekli yazmaçları büyük ölçüde azaltır. Literatürde [10] önerilen SFT mimarisi ile karşılaştırıldığında, bu makalenin mimarisi hala iyi performans gösterebilir.
4. Sonuç
Bu makale, SFT'nin FPGA paralel uygulama şemasını önermektedir ve FPGA uygulama çerçevesini oluşturmak için Simulink'teki XSG geliştirme aracını kullanır. Bağımsız fonksiyon bloklarının paralel olarak işlenmesi, yürütme süresini büyük ölçüde azaltabilir. Daha sonra FPGA üzerinde donanım uygulaması değerlendirildi.FFTW uygulaması ile karşılaştırıldığında, örnekleme noktalarının sayısı yeterince büyük olduğunda sistem çalışma hızı artar ve hesaplama süresi OMP algoritmaları gibi diğer FPGA'lara göre kısalır. Gerçekleştirme şeması, kaynak tüketimini azaltır ve sistemin karmaşıklığını azaltır.
Referanslar
1 AYDINER A A, WENG C C, SONG J, et al. A seyrek veri hızlı Fourier dönüşümü (SDFFT) J Anten. Antenler ve Yayılma Üzerine IEEE İşlemleri, 2003, 51 (11): 3161-3170.
[2] IWEN M A. Uyarlanabilir olmayan sıkıştırılmış algılama yöntemleri aracılığıyla deterministik bir alt doğrusal zaman seyrek Fourier algoritması C On dokuzuncu yıllık ACM-SIAM Ayrık Algoritmalar sempozyumunun bildirileri, 2008: 20-29.
[3] Na Meili, Zhou Zhigang, Li Peipi. Seyrek Fourier dönüşümüne dayalı düşük örnekleme hızlı geniş bant spektrum algılama J. Elektronik Teknoloji Uygulaması, 2015, 41 (11): 85-88.
4 GILBERT A C, STRAUSS M J, TROPP J A. Hızlı fourier örnekleme üzerine bir eğitim J. IEEE Signal Processing Magazine, 2008, 25 (2): 57-66.
5 Wang Cheng, ARAYAPOLO M, CHANDRASEKARAN S, ve diğerleri. Paralel seyrek FFT C. Düzensiz Uygulamalar Üzerine 3. Çalıştayın Bildirileri: Mimariler ve Algoritmalar. ACM, 2013: 10: 1-10: 8.
6 Hu Jiaxi, Wang Zhaosen, Qiu Qiyuan ve diğerleri.GPU'larda ve çok çekirdekli CPU'larda seyrek hızlı Fourier dönüşümü C .2012 IEEE 24th International Symposium on Computer Architecture and High Performance Computing (SBACPAD), IEEE, 2012: 83-91.
7 BRAUN T R. Seyrek rekonstrüksiyon için GPU hızlandırmasının bir değerlendirmesi J. SPIE'nin Bildirileri The International Society for Optical Engineering, 2010, 7697.
8 Wang Cheng, CHANDRASEKARAN S, CHAPMAN B. cusFFT: GPU'larda yüksek performanslı seyrek hızlı fourier dönüşüm algoritması C. 30. IEEE Uluslararası Paralel ve Dağıtılmış İşleme Sempozyumu (IPDPS), 2016: 936-972.
9 RABAH H, AMIRA A, MOHANTY B K, vd. Sıkıştırmalı yeniden yapılandırma için ortogonal eşleştirme arayışının FPGA uygulaması J. Çok Büyük Ölçekli Entegrasyon Sistemlerinde IEEE İşlemleri, 2015, 23 (10): 2209-2220.
[10] AGARWAL A, HASSANIEH H, ABARI O, ve diğerleri. Bir milyon noktalı seyrek Fourier Dönüşümünün yüksek verimli uygulaması C. Alan Programlanabilir Mantık ve Uygulamalar IEEE Konferansı (FPL), 2014: 1-6.
