GPU并行计算技术的恶码检验范文

《无线通信技术杂志》2014年第二期

1现有的检验卷积码编码器的方法

Massey和Sain［4］通过数学推导验证卷积码编码器生成多项式对于一个(n，1，m)卷积码编码器，生成矩阵G(D)有前馈逆G－1(D)，当且仅如果该码字在BSC上传播，其中三个非零比特被信道噪声变为零，则接收序列全是零。最大似然译码器则会产生全零码字作为其估计，因为这是一个有效码字，并且正好和接收序列相同。因此，估计的信息序列式v(D)=0(D)，意味着有限数量(这里仅有三个)的信道错误引起了无数的译码错误。明显地这是不希望的，译码器被称为遭受了恶性误码扩散，即它是一个恶性编码器［5］。因此，在选择编码器用于差错控制编码系统时，避免选择恶性编码器是非常重要的。数学推导的方法偏重于计算约束长度较小的卷积码编码器。现有的恶码检验方法是使用数学工具Matlab的检验方法。该方法首先要构造出一种栅格型结构，在栅格结构中找到输出为零重量的结点，然后以此结点作为运算的起点。遍历码树中每一个零重量的结点。寻找栅格结构中的零重量环。首先寻找长度为2的零重量环，再寻找长度为3的零重量环……，直到找完长度为约束长度的零重量环。这种栅格结构主要用于建立各种状态之间的转换，实际上就是一个矩阵，将所有的状态转换关系在矩阵中表示出来。首先需构造2m－1*2m－1(m为约束长度)个元素构成的矩阵。这样做的好处是可以根据当前的状态以及输入变量确定下一刻的状态，但有一个很大的缺点就是随着约束长度的增加，需要存储的数据在急剧的膨胀，最终会因为需要存储的数据量过大超过计算机的内存存储范围而无法进行正常的检验。现有的工具进行检验恶码的方法有二个突出特点:(1)运算量大，每一次循环都要做一次矩阵乘，总共需做2m－1次矩阵乘法，当约束长度较大时，计算量是非常惊人的。实验仿真有效的见证了这一点。(2)进行检验所需的内存过大。

2适用于检验卷积码生成

多项式的并行计算方法假定编码器开始在开始状态S0(全零状态)，通过在状态图中沿着信息序列决定的路径且记录分支上的相应输出，我们可以得到对应于任何给定信息序列的码字。沿着最后的信息分组，收尾的编码器通过一个附加到信息序列的m个输入分组序列回到状态S0。图2给出了图1所示的卷积码编码器的状态图。一个编码器是恶性的，当且仅当状态图除了有一个围绕状态S0的零重量圈之外，还包含一个零输出重量圈。图2所示(2，1，3)编码器的状态图中，我们注意到，围绕状态S7的单个分支圈有零重量输出［6］。为了对约束大长度的卷积码编码多项式进行检验，我们必须运用一种能够克服现有检验方法自身不足的新方法对计算机搜索到的大约束长度的卷积码编码器进行检验。考虑到恶性卷积码编码器有一个围绕初始状态(S0)的零重量环之外还有至少一个零重量环的这一特性，我们借助于计算机对卷积码编码器的所有状态都进行遍历，可以得到基于这一特性的一个卷积码编码多项式检验算法。(n，1，m)卷积码编码器的单个状态检验算法的步骤如下:(1)任意选择当前寄存器中的状态为开始时的状态放到长度为m的移位寄存器;(2)每次左移一位，判断是否回到了开始时状态，移出寄存器的最高位放到寄存器的末位，计算输出的码重，根据输出的码重判定是否进行下一次操作;(3)如果编码器输出的码字重为0，则重复(2)中的操作直到m次，使寄存器中的状态在经过m次循环移位后回到开始时的状态，移位操作结束，跳出循环;否则移位结束，跳出循环;(4)当移位操作结束时，如果输出的码字重为0，则该编码器是恶性编码器，否则该状态不能说明编码器是恶性的。(n，1，m)卷积码编码器的全状态检验算法的步骤如下:(1)从初始状态开始;(2)对每个状态分别进行单个检验;(3)如果检验的结果能说明编码器是恶性的，跳出循环，否则让状态加一进入下一个状态;(4)重复(2)和(3)中的操作，直至当寄存器中的状态为全一仍未跳出循环，则跳出循环。图3给出了检验卷积码编码器是否是恶性编码器的流程图。

3基于GPU的恶性编码器检验

当卷积码编码器的约束长度是m时，则该编码器中共有2m个状态，随着约束长度的增加状态的数量呈几何倍数的增加，检验编码器的生成多项式的计算量在指数倍增加，如果这些计算量全部由一个顺序执行的程序完成，则耗费的时间会随着长度的增加急剧的增加，针对这一问题的解决办法只能是并行处理所有的状态。进行并行处理时由于单个的计算单元之间不能进行通信，并且进行并行处理的初始的数据结构应该是一致的。由于所需检验的编码器的所有状态在一定的程度上可以认为是一样的，并且单个状态之间互不影响，这为我们进行并行处理提供了前提条件。如果把需要处理的所有状态均分到N个线程中进行并行处理，将会获得巨大的性能提升，这在实际应用中是十分可观的。GPU进行科学运算时，事实上采用的是一种GPU/CPU协同的工作模式:CPU负责逻辑判断和数据调配;GPU则完成数据量大、线性度高的并行任务。GPU采用的是SIMT(singleinstruction，multiplethread)执行模型。从硬件上看GPU上的计算核心为SM流处理器，每个SM中包括8个标量流处理器(SP)，SP只是执行单元。SM包括取指、解码、分发逻辑执行单元和存储器，是一个完整的计算单元。从编程逻辑上看，GPU上的并行程序采用双层并行，即网格中的线程块并行和block间的线程并行。CUDA［6］(UnifiedDeviceArchitecture，统一计算设备架构)是一种将GPU作为并行计算设备的软硬件架构。在CUDA编程环境中，CPU作为主机(Host)，负责进行逻辑性强的事务处理和串行计算，以及GPU上线程的创建、显存的申请与数据存取等工作［7，8］;GPU作为设备(Device)，专用于执行高度线程化的并行运算。在GPU上运行的并行计算函数称为Kernel。Kernel是以线程块(Block)为单位执行的。Block之间并行、无序执行，且各Block之间无法进行通信。每个Block可以由1～512个线程(Thread)组成，但是具体分配多少个线程要根据实际情况来定。合理的线程划分对程序的执行效率具有很大影响。我们按照GPU的构架特点把需要处理的数据进行了等量的分配。把等量的状态分配给GPU内核进行处理，CPU起到控制的作用，等到所有的处理完成后，GPU再把处理的结果反馈给CPU。例如，当我们要验证约束长度为32的卷积码编码器时，我们可以在GPU内核上开512个线程块，在其中每个线程块中启动512个线程，分配到每个线程需要检验的状态由232下降到216，得到的性能提升时相当的可观的。

4实验仿真

GPU计算实验平台参数如下:CPU为Intel(R)Xeon(R)CPUE56202．40GHz;内存4G;GPU采用GeForce210，核心频率589MHz，流处理单元数16个;CUDAToolkit3．2版本;操作系统Win-dowsServer2003;编译环境VisualStudio2008(．NETFramework3．5)。我们将GPU和CPU在验证相同约束长度的编码器所耗费的时间上进行比较。表1给出了各自的在等量的计算下所耗费的时间。实验仿真的结果表明当编码器的约束长度较小时，GPU的高效并行运算能力并没有得到发挥，甚至其性能尚没有CPU表现出的性能好，但是随着约束长度的增加GPU的高效并行运算效能逐渐显露出来。在使用GPU进行并行计算时由于GPU和主机之间有数据的交互，也就是主机要对GPU进行控制，当数据量较大时，主机给GPU分配数据时所耗费的时间较长，如果我们能够进一步的压缩主机和GPU之间所传递的数据量，而尽量把数据放到GPU上进行处理，则运算的速度将会在一定程度上得到提高，所耗费的时间将进一步的降低。

作者：葛勤革徐大勇张涛涛单位：海军司令部信息化部科研办 海军工程大学电子工程学院