High-speed bidirectional fano algorithm implementation

Abstract

This thesis is about the implementation of Bidirectional Fano algorithm (BFA) and Unidirectional Fano algorithm (UFA or conventional Fano algorithm) in C and CUDA. BFA is derived from the Fano algorithm used in high speed convolutional code decoding. It is a simultaneous forward and backward codeword search decoder. The high throughput demanded by the latest wireless digital interfaces like WirelessHD may benefit from a parallel computing specific baseband processing unit that runs BFA at a high speed on CUDA. In this thesis, BFA reached a throughput of 4.4Gbps in CUDA with a single thread per codeword. Its iteration is characterised by one thread decoding first forward then backward. Another BFA decoding at 3.1Gbps was performed using dual threads per codeword. One thread is a forward decoder while the other is a backward decoder. Finally, on the same board, GTX650, UFA was found to have 5.0Gbps of throughput. It was concluded that additional memory transactions and check conditions were the source of throughput loss of BFA in comparison to UFA. However, BER, NoI and TpI analysis gave improved results for BFA, meaning that it decoded more efficiently than UFA. In order to obtain such throughputs, several optimization measures were taken such as the use of look-up tables instead of metric, output bit, state calculations. Another technique was to use an indexed circular queue to hold the previous eight steps in memory instead of using a conventional array. This thesis proposes BFA implementation in CUDA application as a complement to the research done by Xu et al. in 2009, in which simulation was conducted in MATLAB. Later, it has been implemented in FPGA at 100Mbps, and here we are aiming a throughput in several Gbps. The research done by Xu and Koçak (2010) proposed the use of LUT for checking merge conditions. LUT were used in this thesis, too, but this time to pre-calculate next metric, state, output bit calculations, and this contribution was applied to both UFA and BFA.

Bu tezin konusu, yüksek süratli ve çift yönlü Fano algoritmasının C ve CUDA dillerinde uygulanmasıdır. Kısa adı BFA olan çift yönlü Fano algoritması, yüksek süratte evrişimli kod çözmede kullanılır. Bu, simültane bir biçimde ileri ve geri kod çözme algoritmasıdır. WirelessHD gibi modern kablosuz dijital iletişim araçları yüksek hız gerektirir. İşte bu yüksek BFA hızı için, CUDA ile paralel işlem yapabilecek bir ana bant işlem birimi kullanılabilir. Bu tezde, CUDA ile BFA’nın 4.4Gbps’lik bir hıza erişmesi sağlanıyor. Her kod ayrı bir thread kullanılarak çözülüyor. Her adımda bir thread başlangıçtan sona doğru kod çözüyor, ardından da sondan başa doğru. 3.1Gbps hızındaki diğer bir BFA kod çözümünde ise her kod için çift thread kullanılıyor. Burada da bir thread başlangıçtan sona doğru, öbür thread sondan başlangıca doğru kod çözüyor. UFA, aynı GTX650 cihazında 5.0Gbps hızına ulaşabiliyor. BFA’nın yavaşlığının, UFA’ya daha fazla hafıza kullanmasından ve ek kontrol mekanizmalarından kaynaklandığını düşünüyoruz. Ancak, BER, NoI ve TpI analizlerinden BFA için daha iyi sonuçlar elde edilebiliyor. Bundan da anlaşılan şu ki BFA daha yavaş olmasına karşı UFA’dan daha verimli kod çözüyor. Bu hızlara ulaşabilmek için metrik, çıkan değer v.b. hesap yerine taramalı tablo kullanımı gibi bazı optimizasyonlar yapıldı. Bir başka yöntem, bir önceki sekiz adımı hafızada tutmak için klasik bir dizi yerine indeksli çember sıra kullanmak oldu. Xu et al. (2009) tarafından yapılan BFA araştırmasının simülasyonu MATLAB’da yapılmıştı. Başka bir simülasyon da FPGA’da 100Mbps hızında olmuştu. Bu tezde, CUDA ile birkaç Gbps hızında BFA araştırması simülasyon yapmayı hedefliyoruz. Xu ve Koçak (2010) tarafından yapılan araştırmada ileri ve geri kod çözücülerinin birleşmesinin kontrol edilmesinde taramalı tablo kullanılmasını önermişti. Bu tezde de metrik, çıkan değer v.b. hesap yerine taramalı tablo okuma yapılmış; üstelik bu hem UFA hem BFA için uygulanmıştır.