移动设备GPU上的LDPC解码

抽象的

本文提出了一种灵活的软件LDPC解码器，其利用用于在移动设备上解码移动设备上的同时多元字解码的数据并行性。通过基于OpenCL的图形处理单元进行多线程支持。通过将检查矩阵分为几个部分来充分利用GPU上的本地内存和私人内存并每次正确修改代码容量，我们在手机上的实现显示100 Mbps高于100 Mbps的吞吐量小于1.6毫秒解码，使视频呼叫等高速通信成为可能。为了实现在移动设备上的高效软件LDPC解码，应该更换通信基带芯片上的LDPC解码功能以节省成本并使更容易升级解码器与各种信道接入方案兼容。

1.介绍

低密度奇偶校验检查（LDPC）纠错码是一种线性块代码，由Gallager于1962年提出[1] 1996年被麦凯和尼尔重新发现[2］．它从其稀疏检查矩阵中获取其名称。LDPC代码是接近容量的代码，这意味着它允许将噪声阈值设置为非常接近对称的内部内部存储频道的Shannon限制;因此，存在LDPC代码的实际结构。

LDPC代码的良好性能是非常大的计算成本。DCP解码计算具有非常高的并行计算。目前的商业LDPC解码器基于硬件实现，该硬件实现仅允许同时允许多种特定的LDPC代码，并且难以升级。使用FPGA有大量研究实现高效的LDCP解码器[3.，4］．随着桌面上的图形处理单元（GPU）的快速发展，使用CUDA框架对LDPC解码有很多研究[5，6］．LDPC码广泛应用于第四代移动电信技术，这使得在移动设备上开发有效的软件LDPC解码是重要的。同时，软件LDPC代码可以动态地改变参数，包括代码长度，代码率以及迭代的数量，以便快速处理各种网络环境。

开放计算语言（OpenCL）[7]是编写在由CPU，GPU，DSP，FPGA和其他处理器或硬件加速器组成的异构平台上执行的程序的框架。Khronos成员审查了本技术规范，并于2008年批准了公开发布。计算统一设备架构（CUDA）[8]还使开发人员能够在桌面上的GPU上开发并行计算程序。OpenCL出现稍后，但它支持更多场景。随着移动设备的快速发展，许多移动设备尤其是移动电话开始拥有自己的高性能GPU芯片。一些供应商，如Qualcomm，Imagination PowerVR，ARM和Vivante开始支持他们的移动GPU上的OpenCL [9]，它在基于GPU更容易地制作在移动设备上开发并行计算程序。在本文中，我们试图基于OpenCL在移动GPU上开发LDPC解码器。尽管如此，全球内存受到移动GPU的限制;因此，性能不如桌面GPU那么好。通过充分利用每个计算单元的本地存储器和每个处理单元的私存存储器来改善解码。同时，我们正确地减少了每码字的线程数并在解码过程中添加代码单词，并且获得更好的性能。在我们的实验中，作为解码器的最佳结果，吞吐量达到160 Mbps，这可以满足许多情况下的当前移动无线通信，延迟时间小于2毫秒（MS），可以满足许多实时应用程序像视频呼叫一样。

2.用于LDPC解码的MSA

信仰传播（BP）算法是一种重要的消息传递算法，通常用于人工智能领域[9］．每个节点之间的算法转移信仰信息。例如，来自位节点的信仰信息检查节点要看观察和所有检查节点与之相关，除了．同样，来自检查节点的信仰信息到比特节点要看观察和所有的位节点与之相关，除了．作为BP算法，MIN SUM算法（MSA）是一个非常有效的LDPC解码算法[10.］．它基于如Tanner图表所示连接的节点之间的信仰传播[11.]边缘。数字1显示特定4×8的Tanner图H矩阵。MSA由Gallager提出，在对数概率域内进行运算。

LDPC代码是一种特殊的线性形式（）块代码，由稀疏二进制奇偶校验检查定义H维度的矩阵， 尽管．我们假设该频道是一种添加性白色高斯噪声（AWGN）通道，其平均值为0和方差σ.²．BPSK调制映射一个码字在序列， 根据．收到的序列是， 和．在接收的情况下的对数先验概率是．MSA如图所示2．

在进入循环迭代之前，我们使用接收的序列初始化先前的概率如下：

在这个算法中，我们不计算的后验概率和直接地;相反，我们计算在钻头节点和检查节点之间传输的消息以及硬解码前的后验概率。

在更新消息的步骤中到,因为迭代，访问H在行主要订单中，随着消息发送的到是否根据所连接的任何位节点进行更新在Tanner图中，除了．更新过程称为最低步骤，如下所示：

使用H图中的矩阵和Tanner图1， 例如，由bn更新₁和BN₂，如图所示3.，．

后验概率由先前的概率更新以及连接到的所有检查节点：

同样，在更新消息的步骤中到,因为迭代，，作为消息发送的消息到是否根据连接到的任何检查节点进行更新在Tanner图中，除了．更新过程称为SUM步骤。

使用图中的Tanner图1， 例如，由cn更新₂，如图所示4，．

实际上，更新的步骤和可以交换。如果我们更新首先，结果可用于更新，减少了重复计算。

最终硬解码在迭代结束时执行。

如果被解码的单词，迭代过程将停止c验证所有奇偶校验方程，或达到最大迭代数。

解码器的实现是通过洪水调度算法实现的[12.］．它保证了在更新步骤中的位节点不会在更新步骤中互相干扰，并且在更新检查节点时，检查节点也不会相互干扰。使用此原理允许基于基于流的计算方法对LDPC解码进行真实并行执行MSA。

3. OpenCL用于移动GPU

现代GPU基于超高的并行计算能力和可编程流水线。GPU的流处理器能够进行通用计算[13.］．GPU比CPU的浮点性能更高效，特别是在处理单指令多数据(SIMD)和完成计算密集型任务时，其中数据处理操作需要的时间远远超过数据调度和数据传输[14.］．

与桌面计算机的专用GPU不同，移动GPU通常集成到应用程序处理器中，该应用程序处理器还包括多核CPU，图像处理引擎，DSP和其他加速器[15.］．最近，现代移动GPU等高通adreno GPU [16.[Vivante上的想象力PowerVR GPU，ARM Mali和GPGPU倾向于将更多的计算单元集成在芯片中。由于多核架构和诸如OpenCL等新兴框架，移动GPU已经获得了通用并行计算能力，并且他们可能提供类似于为桌面计算机设计的供应商特定解决方案的灵活性，例如NVIDIA的CUDA。

OpenCL是一个编程框架，专为各种平台的异构计算而设计[17.］．在OpenCL中，主机处理器(通常是CPU)管理OpenCL上下文，并能够将并行任务卸载到多个计算设备(例如GPU)。

并行作业可以分为工作组，每个作业都包括许多工作项，该项目是并行执行内核的基本处理单元。

OpenCL定义包含大型全局内存的分层内存模型，但具有长期延迟和一个小但快速本地内存，可以由同一工作组中的工作项共享;更重要的是，每个工作项都有自己的内存，它没有与其他项目共享，最快的访问。

为了有效地利用移动处理器对移动处理器的有限计算资源以进行更好的性能，我们在CPU和GPU之间分区任务，并探索算法并行性，并且需要仔细考虑存储器访问优化。

在嵌入式平台上，处理各种任务正在成为一个趋势。OpenCL规范描述了手持式和嵌入式平台的OpenCL规范的子集。

OpenCL嵌入式配置文件有一些限制;例如，有对3D图像的可选支持，但不支持64位整数，也不支持64位整数。OpenCL嵌入配置文件的细节可以在Khronos的网站上找到[17.］．

尽管这些规范限制，但可以使用OpenCL来加速移动设备上的程序。移动设备上的计算密集型计算被传送到支持OpenCL的GPU或其他设备;不仅这些任务可以更有效地执行，而且CPU也可以处理更多的任务，即它擅长。实际上，LDPC解码是一种传统的计算密集型计算。

4.移动GPU上的并行MSA LDPC解码

MSA是一种密集处理，应该在高性能的特定计算引擎或高度并行的可编程设备中进行处理。在移动设备上，GPU是一个不错的选择。这种通用模型由使用OpenCL的GPU支持，在多个多处理器上并行执行内核。每个处理器由几个核心组成，这些核心分派多个线程。在本节中，并行处理保存矩阵的信息H展示了工作项目。为了保存私存内存，每个工作项仅保留与其自己的计算相关的压缩信息。之后，介绍了OpenCL内核中的特定并行算法。给出（）LDPC代码，管理计算是对并行编程的支出很重要。而不是使用工作项（是矩阵的最大列重量H），模型使用每个工作组中的工作项，每个工作项都会更新关于一个检查节点的消息，这意味着工作项工作检查节点。

4.1。Tanner图的紧凑型表示

LPDC代码的Tanner图定义为H．我们在两个单独的数据结构中提出它，即，和．这是因为LDPC解码器的一个迭代可以分解为水平和垂直处理，这意味着我们更新消息到和消息从到,分别。

水平步骤中使用的数据结构定义为．它是通过扫描矩阵生成的H中与非空元素相关联的位节点边的映射H由同一行的单个检查节点方程使用。算法1详细介绍了矩阵的此过程行和列。保存在私人内存中。因为每个工作项都在整行中更新消息，无需由任何其他工作项访问。

的在垂直处理步骤中使用数据结构。它可以定义为与非空值相关联的边的顺序表示H．它是通过扫描来生成的H矩阵处于列主要订单。也保存在私人内存中。因为每个工作项更新邻居中的消息行，也不需要被其他工作项访问。

4.2。在OpenCL网格上编程MSA

每个工作组都包含代表线程的工作项。而不是整个矩阵H要么，每个工作项可以保存所需的部分信息在私有内存中，可以更快地访问执行更新。同样，相同的原则适用于更新消息。

根据LDPC代码长度，移动设备上的CPU在GPU中分配内存，包括用于存储检查矩阵的全局存储器H，输入数据，输出数据和本地存储器，用于保存从位节点发送的消息数据以检查节点，标记为从检查节点到位节点，标记为（算法3.）。

在步骤中，紧凑和通过算法在私人内存中生成1和2．

与正常的MSA算法相同，从步骤执行循环将结束，直到输出码字是当前的或它达到最大循环时间。

它执行水平处理，垂直处理和步骤（5） - （9）的所有线程的同步。通常，所有线程都应在水平和垂直处理之后同步，但在该算法中，每个工作项都会负责自己的检查节点，以及数据不与其他工作项共享，因此它能够在水平处理后取消同步以提高性能。数据仍然与所有工作项共享，因此保留垂直处理后的同步。

在同步之后，它计算后部概率每项工作 - 项目涉及按步骤(10)-步骤(13)对节点进行位处理。在第二次同步后，根据本节所述的方法，采用后验概率进行硬解码2．

执行了真正的并行执行，解码一个码字所需的总体处理时间可以显著减少，这将在下一节中看到。通过同时解码多个码字，可以利用更多的数据并行性，但本文没有考虑这一点。

5.实施和实验结果

实验设置为评估GPU上所提出的并行LDPC解码器的性能，包括具有256 MB全局存储器和4 kB本地存储器的PowerVR G6200，并使用C语言和OpenCL编程接口（1.1版）进行编程。在该算法中，每个代码字被解码在工作组中。由于本地内存有限，只能在此测试手机中使用小型LDPC代码。但是，由于GPU上的全球内存相对较大，工作组号可以很大。

要解码一批代码单词，其原始大小为1 Mbit，性能的变化是最小的和图中的5我们只展示了实现的最佳结果。作为144×576矩阵，每个工作组的工作项等于其行号，这意味着我们在本实验中使用每份工作组和1000个工作组的144个工作项。

图中报告的解码时间5定义全局处理时间，包括数据传输时间和解码时间。译码时间随着迭代次数的增加而增加。它们有一个线性关系。充分利用GPU的计算能力。当需要解码的数据大小保持不变时，吞吐量会随着迭代次数的增加而降低。

在移动设备上，我们将延迟视为吞吐量的重要性。数字6显示从10kbps到100mbps的解码延迟。随着速度的指数增长，延迟增加，但缓慢。实际上，在一个解码周期内，GPU上用于解码的数据量太小，浪费了GPU的一些容量，并且在低速下并行效果不明显。

显而易见的是，当GPU解码增加的代码字增加时，延迟增加。然而，解码循环的时间是延迟最重要的部分，速度增加而慢慢地增加了计算能力。代码字的平均时间速度更高。因此，它可以应用于一些高速移动服务，如大文件传输，以及视频呼叫等延迟敏感的服务。

六，结论

本文在运行OpenCL运行OpenCL上的移动设备上的GPU提出了一种多极体词并行LDPC解码器。LDPC广泛应用于第四代移动电信技术，因此实现了在移动设备上的高速LDPC解码很重要。

对于一个实例，流行的视频呼叫软件，Skype，其官方网站上的带宽要求[18.］．Skype所需的带宽取决于呼叫的类型。正常屏幕共享视频呼叫，高质量视频呼叫和高清视频呼叫所需的最低速度为0.3 Mbps，0.5 Mbps和1.5 Mbps。在上面的实验中，解码延迟为0.84ms，0.86ms和图中0.98ms6．高清视频呼叫延迟小于1毫秒。它可以显然满足其要求。

通过对移动设备上的LDPC解码的软件实现，LDPC可以动态地改变参数，包括代码长度，代码率和迭代次数。所有这些都可以在OpenCL设备上快速动态，可以快速处理各种网络环境。通过不良网络，可以减少代码率以提高纠错能力，而当网络正常时可以提高码率。与传统的硬件解码方式相比，我们提出的基于移动GPU上的解码的软件实现的解码算法更有效，因为它可以根据实际环境随时切换。

利益争夺

提交人声明他们没有竞争利益。

参考

1. R. G. Gallager，“低密度奇偶校验码”信息理论上的IRE交易，卷。8，不。1，pp。21-28,1962。查看在：谷歌学术|Mathscinet.
2. D. J. C. Macackay和R. M. Neal，“近山森极限表现低密度奇偶校验代码”，电子字母，卷。32，不。18，pp。1645-1646,1996。查看在：出版商网站|谷歌学术
3. “一种54mbps (3,6)-regular FPGA LDPC译码器”，2014年第4期信号处理系统IEEE车间的程序（SIPS '02），2002年10月。查看在：出版商网站|谷歌学术
4. D. Chanc，F. Yu，Z. Xiao等，“FPGA验证了100 GB / S光学系统的单个QC-LDPC代码，没有错误地板到10-15的BER，”2011年光纤通信会议和博览会和博览会和国家光纤工程师会议（OFC / NFOEC'11）的诉讼程序，洛杉矶，加利福尼亚州，美国，2011年3月。查看在：谷歌学术
5. G.Falcão，V. Silva和L. Sousa，“GPUS如何优于快速LDPC解码的Asics，”第二届超级计算国际会议诉讼程序，约克镇高地，纽约，美国，2009年6月。查看在：谷歌学术
6. G.Falcão，L. Sousa和V. Silva，“GPU的大规模平行LDPC解码”第13届ACM简军的诉讼程序并行编程原理和实践（PPOPP '08），pp.83-90，盐湖城，US，美国，2008年2月。查看在：出版商网站|谷歌学术
7. https://www.khronos.org/opencl/．
8. http://www.nvidia.com/object/cuda_home_new.html.．
9. R. J. MECELIES，D.J.C.Mackay和J.-f.程，“涡轮解码作为珍珠的信仰传播”算法，“在通信中选定区域的IEEE日记帐，卷。16，不。2，pp。140-152,1998。查看在：出版商网站|谷歌学术
10. J. Zhao，F. Zarkeshvari和A. H. Banihashemi，“关于MIN-SUM算法的实施及其解码低密度奇偶校验（LDPC）代码的修改，”IEEE通信交易，第53卷，第53期4，页549-554,2005。查看在：出版商网站|谷歌学术
11. R. M. Tanner，“低复杂性代码的递归方法”信息理论上的IEEE交易，卷。27，不。5，pp。533-547，1981。查看在：出版商网站|谷歌学术|Mathscinet.
12. S. Lin和D. J. Costello，错误控制编码，Pearson教育印度，2004年。
13. D. G. Merrill和A. S.Grimshaw，“重新审视GPGPU流架构”，在第19届并行架构和汇编技术会议的诉讼程序（PACT'10），维也纳，奥地利，2010年9月。查看在：谷歌学术
14. V. W. Lee，C. Kim，J.Chhugani等，“揭示了100X GPU与CPU神话：对CPU和GPU的吞吐量计算评估，”ACM SIGIGIANCH计算机架构新闻第38卷第2期3, 2010。查看在：谷歌学术
15. G. Wang，Y. Xiong，J. Yun和J. R.Cavallaro，“在移动GPU上使用OpenCL框架加速计算机视觉算法 - 一个案例研究”第38届IEEE声学，演讲和信号处理国际会议（ICASSP'13）的诉讼程序，IEEE，温哥华，加拿大，2013年5月。查看在：出版商网站|谷歌学术
16. https://developer.qualcomm.com/category/tags/opencl.．
17. A. Munshi，OpenCL规范，肯索斯OpenCL工作组1,2009。
18. http://skype.gmw.cn/help/content_69_579.html.．

版权

版权所有©2016陆一勤等。这是一篇发布在知识共享署名许可协议如果正确引用了原始工作，则允许在任何媒体中的不受限制使用，分发和再现。