GPU加速随机线性网络编码的研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇GPU加速随机线性网络编码的研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要： 网络编码近年来被广泛用于各种分布式系统以提高吞吐量，并且能在网络发生动态变化时的数据传输提供弹性。但是，网络编码引起的大量的额外计算量和编码时间成为了实际应用的障碍。在这个研究中，我们使用gpu的强大计算能力来加速网络编码。通过将大量可并行的计算安排到GPU上执行，有效地缩短了网络编码所需要的时间，为网络编码的实际应用提供了帮助。

Abstract： Network coding has recently been widely applied in various distributed systems for throughput improvement and/or resilience to network dynamics. However， the computational overhead introduced by network coding operations is not negligible and has become the obstacle for practical deployment of network coding. In this study， we exploit the computing power of commodity many-core Graphic Processing Units （GPUs） and multi-core CPUs to accelerate the network coding operations. With the implementation of the algorithms， it is able to achieve significant encoding and decoding throughput， providing a solution for the practical use of network coding.

关键词： 网络编码；随机；线性；图形处理器

Key words： network coding；random；linear；Graphics Processors Units

中图分类号：TP391 文献标识码：A 文章编号：1006-4311（2012）29-0193-02

1 课题背景

网络编码是一个相对较新的研究领域，因为这个概念在2000年才由Ahlswede等人[1]引入。近年来，学者在网络编码的各个方面及它在实际网络系统中的应用进行了大量的研究。Fragouli等[2]对网络编码的相关研究进展进行了一个全面的总结。对线性网络编码的一个简短定义是：在一个分组包传输的网络中，中间节点发出的数据包是其之前接收到的信息的线性组合。这个方法有这些优点：提高网络吞吐量（throughput）；增加数据传输的可靠性；增强安全性；复杂度低。

和其它很多编码模式相同，网络编码能用于减少网络传输中的丢包问题。传统的编码模式一般都为端对端节点的编码。而在应用了网络编码的网络中，中间节点也会参与编码。Ho等在2003年发表了一篇关于随机网络编码的标志性论文，引起了对网络编码的研究从理论研究逐渐转移到更加偏向实际应用的研究。很多的研究都表明，网络编码的计算复杂度和编码时间是阻碍网络编码被实际应用的一个重要因素。

近年来，图形处理器（Graphics Processing Units，GPUs）获得了快速的发展[3]。从NV30到G92，GT200以及最新的Fermi，Nvidia公司的GPU不仅被用来做图形图像处理，也被用来做通用计算。现代的GPU的理论峰值性能和内存带宽相比以前的产品大大增强了。越来越多的硬件资源被集成在芯片中，包括大量的寄存器、共享内存、缓存等。GPU的系统架构被不断地改良。这些提升使得GPU越来越适合高效地同时运行大量的轻量级的线程。由于这些GPU的系统结构上的改进，GPU被用在了各种面向吞吐量的计算领域，包括分子动力学、天体物理模拟、生命科学、核磁共振影像的重构等，获得了超过100倍的加速比。除了GPU硬件的发展，GPU的软件开发环境等也快速发展。如Nvidia的CUDA编程模型使得在GPU上的编程设计非图形图像处理的应用程序变得简单。CUDA将GPU当作宿主计算机的一个特殊协处理器，允许同样的代码在多个GPU核（GPU Processors）上以多个线程的方式同时运行。

在这个研究中，我们将会应用GPU来加速网络编码的计算，为网络编码的实际应用提供一种方法。近年来有一些相关研究关注于加速网络编码的计算。Shojania等在嵌入式平台—iPhone上进行了随机网络编码，并随后使用GPU加速计算获得了更好的性能[4]。然而，在GPU上进行网络编码的计算并不像看上去那么简单：首先，需要将GPU上的全部运算核都用起来；其次，要将内存访问的开销最小化；第三，设计和实现要匹配实际的GPU的架构；最后，需要调整GPU内几种不同的内存的使用，以取得最佳的吞吐率。

2 基于GPU的计算和网络编码

随机线性网络编码：

2.1 编码

在随机线性网络编码过程中，原始数据被分解为n个块[b1，b2，…bn]T，每个块bi由k字节组成。k是固定的值，称为块的大小。要将原始的块bi编码得到块xj，编码的节点（即网络中的一个节点）首先独立机地从Galois Field GF（28）中选择一个子集做为编码系数[cj1，cj2，…cjn]。子集的元素个数等于待编码的块数。得到块xj的方法如下：

xj=■cji·bi

2.2 解码

节点发送数据时，编码系数的子集也会随数据发送。当一个节点接收到n个线性独立的编码后的块X=[x1，x2，…xn]T，就可以立即开始解码。它首先使用接收到所有块的的编码系数向量构造一个n×n的系数矩阵C，解码的方法如下：