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

doi:10.1109/wicom.2011.6036680

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 proceeding › Conference 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 language	English (US)
Title of host publication	7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011
DOIs	https://doi.org/10.1109/wicom.2011.6036680
State	Published - 2011
Event	7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011 - Wuhan, China Duration: Sep 23 2011 → Sep 25 2011

Publication series

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

Other

Other	7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011
Country	China
City	Wuhan
Period	9/23/11 → 9/25/11

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

Access to Document

10.1109/wicom.2011.6036680

Fingerprint Dive into the research topics of 'A tiling-scheme Viterbi decoder in Software Defined Radio for GPUs'. Together they form a unique fingerprint.

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 proceeding › Conference contribution

Lin, CS, Liu, WL, Yeh, WT, Chang, LW, Hwu, WMW, 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 WMW, 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",

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",

note = "7th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2011 ; Conference date: 23-09-2011 Through 25-09-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

Y1 - 2011

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

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

Y2 - 23 September 2011 through 25 September 2011

ER -