Efficient parallel implementation of three-point viterbi decoding algorithm on CPU, GPU, and FPGA

摘要

In wireless communication, Viterbi decoding algorithm (VDA) is the one of most popular channel decodingrnalgorithms, which is widely used in WLAN, WiMAX, or 3G communications. However, the throughput ofrnViterbi decoder is constrained by the convolutional characteristic. Recently, the three-point VDA (TVDA)rnwas proposed to solve this problem. In TVDA, the whole procedure can be divided into three phases, thernforward, trace-back, and decoding phases. In this paper, we analyze the parallelism of TVDA and proposernparallel TVDA on the multi-core CPU, graphics processing unit (GPU), and field programmable gate arrayrn(FPGA). We demonstrate approaches that fully exploit its performance potential on CPU, GPU, and FPGArncomputing platforms. For CPU platforms, we perform two optimization methods, single instruction multiplerndata and multithreading to gain over 145× speedup over the naive CPU version on a quad-core CPU platform.rnFor GPU platforms, we propose the combination of cached memory optimization, coalesced globalrnmemory accesses, codeword packing scheme, and asynchronous data transition, achieving the throughputrnof 404.65 Mbps and 12× speedup over initial GPU versions on an NVIDIA GeForce GTX580 card andrn7× speedup over Intel quad-core CPU i5-2300, under the same manufacturing year and both with fullyrnoptimized schemes. In addition, for FPGA platforms, we customize a radix-4 pipelined architecture for thernTVDA in a 45-nm FPGA chip from Xilinx (XC6VLX760). Under 209.15-MHz clock rate, it achieves arnthroughput of 418.30 Mbps. Finally, we also discuss the performance evaluation and efficiency comparisonrnof different flexible architectures for real-time Viterbi decoding in terms of the decoding throughput, powerrnconsumption, optimization schemes, programming costs, and price costs.