您好,欢迎来到花图问答。
搜索
您的当前位置:首页基于GPU的网络编码并行优化算法研究

基于GPU的网络编码并行优化算法研究

来源:花图问答
《工业控制计算机}201 1年第24卷第12期 59 基于G PU的网络编码并行优化算法研究 一 6 Research of Parallel Network Coding Optimization Algorithm Based on GPU 、 、 6 \,一, 王 任 黄理灿 王高选(浙江理工大学信息电子学院,浙江杭州310018) 摘要 在组播通信网络中,在满足组播速率的前提下,如何使编码资源开销最小化即网络编码优化是一个NP难问题。针对现有 基于基本遗传算法的网络编码优化的不足,提出基于GPU的并行遗传算法应用于网络编码优化。通过在不同的网络拓扑结构 中进行仿真实验,结果表明提出的并行遗传算法能够在更短的时间内找到满意的编码方案,具有更高的性能。 关键词:组播,网络编码,GPU,并行,遗传算法 Abstract The problem of minimizing the resources used for network coding while achieving the desired throughput in a multicast scenario is NP—hard.This paper proposes a GPU—based parallel genetic algorithm compared with the existing basic genetic algorithm and apply it to network coding optimization.In the paper,we carry out simulation experiments on a number of dif— ferent sets of network topologies Keywords:muiticast,network coding,GPU,parallel,genetic algorithm 1 网络编码NP难问题的解决 得出了在无环和有环网络下最小编码节点数的上界,这个上界 网络编码” 是一种新颖的技术,即网络中间节点对传输的 由组播速率和信宿节点数决定。 信息流按照一定的方式进行编码处理,可以提升组播通信网络 Kimt 等人首次提出了应用遗传算法(Genetic Algorithm) 的吞吐量。随机线性网络编码是目前广泛应用的一种编码方式, 解决这一NP难的编码优化问题,然后又对算法作了部分改进 这种编码方法在所有的中间节点都进行编码,可以实现组播网 并提出了分布式算法 。邓 等人在文献【5]的基础上,加入新的 络的最大信息流(即组播速率)。但所有的中间节点都进行编码 处理步骤,并提出一种改进的lGA遗传算法,提高了算法的效 并不是实现组播速率的必要条件。 率。经过对文献[5—7]所提出方法的研究和实践,我们发现,以 在图1(a)所示的网络拓扑中,假定所有链路带宽均相同为 上方法解决网络编码优化问题的性能仍然不令人满意,随着问 1bit(本文中所有链路带宽均为1bit),如果中间节点Z进行编 题规模的增大,遗传算法单次循环需要的时间急剧增加,算法的 码,就可以实现组播网络的最大信息流。而在图1(b)中,即使所 运行时间也增加到惊人的程度。针对以上不足,本文利用GPU 有中间节点不进行编码,也可以实现组播网络的最大信息流。 强大的并行计算能力,设计了一个基于GPU的并行遗传算法 毒(PGA),并应用于网络编码优化,实验结果表明PGA算法的运 、b 行时间大大缩小。 —t 2编码优化问题 设G=(V,E)表示无环有向网络图,图中的每一条链路的带 宽为1bit。在单源组播网络中,设S∈V属于信源节点,T∈V为 信宿节点的集合,任意信宿节点t。∈T,且ITl=d。信源节点S以速 率R发送数据至d个信宿节点,若每个信宿节点都能同时以速 率R接收数据,则R为组播最大信息流(组播速率)。 在满足给定的组播速率R条件下,我们试图找到一个最小 编码节点集合。文献[8】给出一种代数表示方法来描述最小编码 节点集合的问题。假设编码是线性组合编码,且只有多链路输入 图1 简单的网络拓扑图 节点才有可能进行编码。那么,多链路输入节点就是候选的编码 一方面,所有的中间节点都进行编码,会带来很大的编码开 节点,称作汇聚节点。 销;另一方面,如果网络编码应用于网络层,则在网络实际部署 文献[4】证明编码链路数比编码节点数更能够代表编码计 中需要很多昂贵的具有编码功能的路由器,带来了很大的浪费。 算开销。因此,我们的目标是得到最小化编码链路数量。如果一 因此在满足组播速率的前提下,如何减少编码开销,找到最小编 个汇聚节点的输出链路信息流只是一个输入链路信息流的转 码节点集合即网络编码优化问题是非常有意义的研究。 发,则这条输出链路上没有发生编码。判定某一链路是否需要编 寻找最小编码节点集合被证明是NP难问题_2]。因此,这方 码的方法:假定该链路只转发了某一条输入链路的信息流,而其 面最早的工作在于寻找最小编码节点数或编码边数的上下界。 它输出链路都进行编码,如果组播网络的组播速率不变,则该输 Fragouli【3 等人指出对于双源,d个接收点的无环组播网络,编码 出链路不需要编码。 节点的上界为d一1。Langberg c 等人提出通过一定的次序一一 删除不影响组播最大流的链路,将一般的网络转换为每个节点 假定一个汇聚节点具有k(≥2)条输入链路和l(≥1)条输 的出入度之和最多为3的“简单”网络,在这个简单网络中,他们 出链路。对于任意i∈{1,…,k}和J∈{1,…,l}…a=1表示汇聚节 点的输出链路j转发输入链路i上的信息流,而a..=0则表示输 60 出链路i不转发输入链xI x2 x3 基于GPU的网络编码并行优化算法研究 空间大大缩小。本文中遗传算法的基因操作定义如下:选择运算 为锦标赛选择,交叉运算为以块为交换单位的均匀交叉操作,而 对于变异运算,块可以突变为其它(k+1)种状态的一种。 3.2基于GPU的并行遗传算法的实现 ,路i上的信息流。aj= (a )i∈{1,…,k}表示链 v. 2 tI- I ■ 路j与各输入链路之间 的信息流编码关系,是v 一个长度为k的向量 汇 ^ yl ; y2 近年来,图形处理器(GPU)高速发展,提高了计算机图形处 理的速度。同时GPU的高速度、并行计算和可编程功能为通用 计算提供了良好的并行计算平台。NVIDIA推出的GPGPU模型 CUDA,它使用C语言编程。CUDA采用了SIMT(单指令多线 程)执行模型。本节将设计基于CUDA的并行遗传算法。 设遗传算法的种群大小为n,即初始的候选编码方案数量 (染色体数量)为n。在CUDA中,我们设置线程块的数量为1, 线程的数量为n,即一个线程对应一个染色体。GPU线程块中的 al=(1,0,1)‘a2=(O,1,1) b输出链路与输入链路信息流关系 块。我们把aij=1称为活 跃状态, =O为不活跃 状态。如果向量块中有 图2汇聚节点 两个及以上的活跃状态,则表示输出链路j上发生了网络编码。 对于任意的汇聚节点V∈V,d 和d 分别表示节点V的输 入链路和输出链路的数量。则m=Z 为一个候选编码方 案的链路数量,由于用二进制数O和1表示不活跃状态和活跃 X 状态,所以编码方案的空间大小为2 。当m很大时,要找到合适 平 m ,的编码方案是非常困难的任务。遗传算法可以减少搜索空间,~ 可 1) X 以在适当的时间内找到足够好的编码方案,而且遗传算法在组 X、 合优化领域有很多成功的应用。、,T  X V ^ 3基于GPU的并行遗传算法及其在编码优化中的应用 3X  遗传算法是一种基于生物自然选择和遗传机理的随机搜索 与优化方法。最近,遗传算法被应用于网络中的组合优化问题, 用来求解优化问题的近优解。遗传算法对一系列的候选解决方 案进行操作,候选方案被称作种群,每一个方案可以用一个位串 表示,称作染色体。每一个染色体有一个适应度值表示该染色体 解决问题的程度。一般通过选择、交叉、变异三种基本基因操作 不断产生新一代种群。 3.1应用于编码优化的遗传算法 在文献[5]中,GA优化的目标是得到最小化具有编码功能 的链路数量,所给出的适应度函数也是基于这一要求。本文将优 化的具体要求抽象为资源描述函数,并给出利用资源描述函数 和网络编码方案产生适应度函数的一般方法。适应度值是描述 遗传算法中筛选对象优秀程度的值,越优秀的方案所对应的适 应度值越大,反之亦然。而在网络编码中,编码链路数量越小,编 码方案越优秀。因此,需要将按照优秀程度递减的资源消耗总和 函数转换为按优秀程度递增的适应度函数。解决的方法是简单 地用一个足够大的常量减去资源消耗总和来产生需要的适应度 函数。在应用中,只需保证这个常量大于最坏编码方案(即在所 有可能的链路上都进行网络编码)的总资源消耗量,本文的实验 中取这个常量为65535。 文献[6]描述了以位为操作单位和以块为操作单位的遗传 算法,并证明了以块为操作单位的遗传算法具有更高的效率和 性能,因此本节设计一个以块为操作单位的并行遗传算法。本文 中的遗传算法采用二进制编码,长度为k的向量a|_(a )i E{1, …,k}块表示汇聚节点V的输出链路j与其输入链路i的信息流 传输关系,也对应一个染色体上的k个基因。如果一个块a.; (a;.)j∈f1,…,k}包含至少两个1即活跃状态,则表明在此链路 上有编码。如果把此块中的其它0用1代替,不会改变链路编码 的性质。所以,任何具有至少两个1状态的块可以被当作是全1 的块。综上所述,任何一个块都有(k+2)种字符串状态:[000, …,O]表示没有传输信息,[10O…0],[010…0],[001…0],…, 『000…1](共k个)等表示只转发信息不编码,而[111..・11]表 示链路发生编码。设 ∑ 为总的块数量,ki表示第i个块 的长度,则搜索空间为兀 ,( 十2),而以位为操作单位的遗传算 法的搜索空间为 ,可见以块为操作单位的遗传算法的搜索 每一个线程都执行遗传算法的选择运算,交叉运算,变异运 算以及适应度值的计算。算法步骤如下:首先初始化种群,然后 将数据从CPU传输至GPU的全局存储器中,然后再将数据传 输至属于线程块(发射在SM处理器上)的共享存储器中,共享 存储器中的数据对整个线程块的线程是可见的。遗传算法结束 以后,将数据从共享存储器传人全局存储器,最终传输至CPU 中,就可以得到输出的最佳编码方案。流程图如图3所示。 ’数据漶 一—●控制流 图3基于GPU的并行遗传算法流程图 4实验结果 在不同的网络拓扑中,通过仿真实验,我们把本文提出的基 于GPU的并行遗传算法(PGA)与其它文献中的算法进行时间 和性能上的对比分析。为方便比较,我们把文献[5】中的算法称 为GA算法,文献【7】提出的算法称为lGA算法。 实验中PGA算法的参数设置为:种群数量为128,交叉概 率为0.8,基因变异的概率为0.01,迭代代数为500次。GPU显 卡为NVIDIA GeForce GTS 450,它采用最新CUDA Fermi架 构,具有192个SP,1G显存。显卡安装在CPU为2.93GHz Intel Core i3 CPU 530的台式计算机上。 为了便于进行数据对比,在实验中PGA算法采用了与文献[7] 同样的网络拓扑,即一部分拓扑是由BRITE模拟随机生成,另 一部分拓扑是按照固定的模式由人工生成的。无论拓扑的规模 如何增加,按下面的方法所人工所生成的特殊拓扑上的最优化 的网络编码方案却是固定的。因此,我们希望通过固定拓扑测试 算法对最优解的逼近程度,而通过随机拓扑测试收敛速度与各 种情况下算法的性能。 《工业控制计算机/201 1年第24卷第12期 人工生成拓扑的方法如图4所示:图4(a)由一个图1(a) 和两个图2(b)拓扑网络组成,而图4(b)则由一个图1(a)和6 表2 61 个图1(b)组成。按照这个规律,可以获得更大规模的固定人工 拓扑。实验中主要使用了图4中所示的两种拓扑,称为N21和 N49。四元组(节点数、链路数量、信宿节点数、组播速率)代表了 BRITE随机生成的一个拓扑的主要参数。 也比较长。在含有120个节点的随机拓扑上,IGA的总运行时间 也要24min,而PGA只需要两分钟,加速比达到12倍。在实验 中,我们发现在多数的随机拓扑上,网络编码仅仅发生在极少数 链路上,这样的结果说明在所有链路都进行网络编码是巨大的 浪费,本文对网络编码的优化工作是非常有意义的。 5结束语 本文针对现有网络编码优化算法效率不高,耗时较长的问 N2l 4 a b 图4人工生成的网络拓扑 题,提出了一个基于GPU的并行遗传算法,并应用于网络编码 优化。实验结果表明我们提出的算法大大减少了找到满意的编 码方案所需的时间。而在实际应用中,网络拓扑可能比实验中的 拓扑要复杂,各链路容量也不一样,我们下一步的工作是研究更 加复杂的实际网络中的网络编码优化算法。 参考文献 表1为本文提出的PGA算法与GA算法、IGA算法在一组 网络拓扑下进行10次实验的平均测量结果。最佳结果列表示网 络编码优化方案资源消耗(即编码链路的数量)的最小值,平均 结果列表示网络编码优化方案资源消耗(即编码链路的数量)的 平均值。 表1 最佳 半均 [1]R.Ahlswede,N Cai,S—Y R Li,and R.W.Yeung, Net— work information flow. IEEE Trans.Inf.Theory.vo1.46,no 4 PP 1204-1216.2000 [2]M B Richey and R.G.Parker, On multiple steiner sub— graph problems,"Networks,vol 16,no.4,PP.423-438,1986 [3]C.Fragouli and E Soljanin,”Information flow decomposition fornetwork coding, IEEE Trans InfOrm Theory,to appear [4]M.Langberg,A.Sprintson,and J Bruck,”The encoding complexity of network coding,”in Proc.IEEE ISIT 05 [5]Kim M,Ahn CW,Medard M,Effros M On m miz{ng net— work coding resources:An evolutionary approach in:Proc. of the NetCod 2006 [6]Kim M,Medard M,Aggarwal V.O Reilly UM,Kim W,Ahn 表1显示:在各种拓扑网络中,PGA算法的最佳结果列和 平均结果列的数据比GA算法,IGA算法都要小,这说明了我们 提出的PGA算法能够找到更加优秀的编码方案。 然后,我们在各种规模的随机拓扑上对比PGA,IGA以及GA 的总运行时间,他们平均输出网络编码优化方案的时间见表2。 通过分析表2中的数据,我们发现,PGA输出结果所需要 的运行时间远远小于GA,lGA;随着拓扑规模的增加,GA的运 CW,Effros M Evolutionary approaches to m mizing network coding resources.1n:Proc.of the IEEE INFOCOM 2007. Anchorage:IEEE Computer Society 2007 199171999 [7]R Koetter丑nd M.M edard, An algebraic approach to net。 work coding.”IEEE/ACM Trans Networking,vo1.1 1,no 5, PP 782-795,2003 [8]邓亮,赵进,王新基于遗传算法的网络编码优化[J].软件学报, 2009,20(8):2269-2279 行时间增长到实际应用中所无法容忍的程度,IGA所需的时间 [收稿日期:2011.9.5] (上接第58页) 参考文献 [1]杨京ZigBee技术在远程监控系统中应用研究[D]武汉:武汉科技 大学,2010 3.8开发环境 采用IAR集成开发环境,IAR是一个专业用于编译和调试 嵌入式应用程序的集成开发环境,支持众多芯片,IAR编译器支 持C/C++,将编辑器、工程管理、调试工具等有效集成在一起, 完全支持CC2430芯片的编程开发,同时也拥有支持T1 [2]刘玉芳,王绍源,吴免利.铝电解工业中ZigBee无线传感器网络及 其QoS研究[J].传感器学报,2010,23(10):1471—1475 [3]毛继红,陈焙超,陈晓光190KA电解槽三场测试分析报告[R].三门 峡.2001 CC2430 SoC的开发套件,可直接将程序下载至CC2430芯片 中,发便程序的调试与开发。 4结束语 本文介绍的方案满足了铝电解车间无线通信要求,最终解 决了铝电解车间进行可靠无线组网与通讯问题,系统具有智能 [4]IEEE Std 802.15.4 [S】,LAN&MAN Standards Committee Wireless Medium Access Control(MAC)and Physical Layer (PHY) Specifications for Low Rate Wireless Personal Area Networks(WPANs).New York:Inst of Eleet&Eleetronic,2006. 27 303 化,信息化的特点,在满足了铝电解车间进行无线通信要求的同 时,提高了铝厂的信息化建设水平。 [收稿日期:2011 9.23] 

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- huatuowenda.com 版权所有 湘ICP备2023022495号-1

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务