A tiling-scheme Viterbi decoder in Software Defined Radio for GPUs

Chih Sheng Lin, Wei Lun Liu, Wei Ting Yeh, Li Wen Chang, Wen-Mei W Hwu, Sao Jie Chen, Pao Ann Hsiung

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we propose a parallel design of Viterbi decoder for Software-Defined Radio (SDR). Our method implements a divide-and-conquer approach by tiling decoding sequences, performing independent speculated Viterbi decoding, and merging partial candidate paths into the final path. For each independent Viterbi decoding, the best path is selected by calculating Hamming distances trellis-by-trellis in parallel. Our method shows up to 14.6x speedup on an NVIDIA 8800 GTX over a sequential C implementation on a 2.4GHz Intel Core 2 CPU. Also, compared with existing GPU-based implementation in [3], our method outperforms up to 2.5x.

Original languageEnglish (US)
Title of host publication7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011
DOIs
StatePublished - Oct 31 2011
Event7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011 - Wuhan, China
Duration: Sep 23 2011Sep 25 2011

Publication series

Name7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011

Other

Other7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011
CountryChina
CityWuhan
Period9/23/119/25/11

Fingerprint

Decoding
radio
Hamming distance
Merging
Program processors
candidacy
Graphics processing unit
software

Keywords

  • Compute unified device architecture (CUDA)
  • Graphics processing units (GPUs)
  • Software-defined radio (SDR)
  • Viterbi decoder

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Communication

Cite this

Lin, C. S., Liu, W. L., Yeh, W. T., Chang, L. W., Hwu, W-M. W., Chen, S. J., & Hsiung, P. A. (2011). A tiling-scheme Viterbi decoder in Software Defined Radio for GPUs. In 7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011 [6036680] (7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011). https://doi.org/10.1109/wicom.2011.6036680

A tiling-scheme Viterbi decoder in Software Defined Radio for GPUs. / Lin, Chih Sheng; Liu, Wei Lun; Yeh, Wei Ting; Chang, Li Wen; Hwu, Wen-Mei W; Chen, Sao Jie; Hsiung, Pao Ann.

7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011. 2011. 6036680 (7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Lin, CS, Liu, WL, Yeh, WT, Chang, LW, Hwu, W-MW, Chen, SJ & Hsiung, PA 2011, A tiling-scheme Viterbi decoder in Software Defined Radio for GPUs. in 7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011., 6036680, 7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011, 7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011, Wuhan, China, 9/23/11. https://doi.org/10.1109/wicom.2011.6036680
Lin CS, Liu WL, Yeh WT, Chang LW, Hwu W-MW, Chen SJ et al. A tiling-scheme Viterbi decoder in Software Defined Radio for GPUs. In 7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011. 2011. 6036680. (7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011). https://doi.org/10.1109/wicom.2011.6036680
Lin, Chih Sheng ; Liu, Wei Lun ; Yeh, Wei Ting ; Chang, Li Wen ; Hwu, Wen-Mei W ; Chen, Sao Jie ; Hsiung, Pao Ann. / A tiling-scheme Viterbi decoder in Software Defined Radio for GPUs. 7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011. 2011. (7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011).
@inproceedings{befcf7609ae144808aafd86e379af183,
title = "A tiling-scheme Viterbi decoder in Software Defined Radio for GPUs",
abstract = "In this paper, we propose a parallel design of Viterbi decoder for Software-Defined Radio (SDR). Our method implements a divide-and-conquer approach by tiling decoding sequences, performing independent speculated Viterbi decoding, and merging partial candidate paths into the final path. For each independent Viterbi decoding, the best path is selected by calculating Hamming distances trellis-by-trellis in parallel. Our method shows up to 14.6x speedup on an NVIDIA 8800 GTX over a sequential C implementation on a 2.4GHz Intel Core 2 CPU. Also, compared with existing GPU-based implementation in [3], our method outperforms up to 2.5x.",
keywords = "Compute unified device architecture (CUDA), Graphics processing units (GPUs), Software-defined radio (SDR), Viterbi decoder",
author = "Lin, {Chih Sheng} and Liu, {Wei Lun} and Yeh, {Wei Ting} and Chang, {Li Wen} and Hwu, {Wen-Mei W} and Chen, {Sao Jie} and Hsiung, {Pao Ann}",
year = "2011",
month = "10",
day = "31",
doi = "10.1109/wicom.2011.6036680",
language = "English (US)",
isbn = "9781424462520",
series = "7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011",
booktitle = "7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011",

}

TY - GEN

T1 - A tiling-scheme Viterbi decoder in Software Defined Radio for GPUs

AU - Lin, Chih Sheng

AU - Liu, Wei Lun

AU - Yeh, Wei Ting

AU - Chang, Li Wen

AU - Hwu, Wen-Mei W

AU - Chen, Sao Jie

AU - Hsiung, Pao Ann

PY - 2011/10/31

Y1 - 2011/10/31

N2 - In this paper, we propose a parallel design of Viterbi decoder for Software-Defined Radio (SDR). Our method implements a divide-and-conquer approach by tiling decoding sequences, performing independent speculated Viterbi decoding, and merging partial candidate paths into the final path. For each independent Viterbi decoding, the best path is selected by calculating Hamming distances trellis-by-trellis in parallel. Our method shows up to 14.6x speedup on an NVIDIA 8800 GTX over a sequential C implementation on a 2.4GHz Intel Core 2 CPU. Also, compared with existing GPU-based implementation in [3], our method outperforms up to 2.5x.

AB - In this paper, we propose a parallel design of Viterbi decoder for Software-Defined Radio (SDR). Our method implements a divide-and-conquer approach by tiling decoding sequences, performing independent speculated Viterbi decoding, and merging partial candidate paths into the final path. For each independent Viterbi decoding, the best path is selected by calculating Hamming distances trellis-by-trellis in parallel. Our method shows up to 14.6x speedup on an NVIDIA 8800 GTX over a sequential C implementation on a 2.4GHz Intel Core 2 CPU. Also, compared with existing GPU-based implementation in [3], our method outperforms up to 2.5x.

KW - Compute unified device architecture (CUDA)

KW - Graphics processing units (GPUs)

KW - Software-defined radio (SDR)

KW - Viterbi decoder

UR - http://www.scopus.com/inward/record.url?scp=80054925893&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80054925893&partnerID=8YFLogxK

U2 - 10.1109/wicom.2011.6036680

DO - 10.1109/wicom.2011.6036680

M3 - Conference contribution

AN - SCOPUS:80054925893

SN - 9781424462520

T3 - 7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011

BT - 7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011

ER -