遗传算法在片上网络Qos路由中的应用 贝叶斯网络应用实例

　　摘要:由于多媒体和实时通信的大量涌现,关于片上网络QoS路由的技术已经成为研究热点问题,本文利用遗传算法来解决片上网络中QoS路由选择问题,并根据网络连接的特性和拓扑表中各个结点上时延与吞吐来指导种群进行初始化,并进行交叉和变异操作,根据遗传算法用于QoS路由具有全局收敛的特性,可以求取出最佳路径。仿真结果表明,该算法使得时延和吞吐的性能均有所改善。
　　关键词:遗传算法;片上网络;服务质量路由
　　中图分类号:TN915.9 文献标识码:A
　　
　　Application of Genetic Algorithm in NoC QoS Routing
　　
　　 NING Huan,WANG Chang-shan,GUO bin
　　(School of computerXidian University,Xi’an710071,China)
　　
　　Abstract:As well as real-time and multimedia applications are emerging,the quality of service support is become key issue in NOC, in this paper, genetic algorithm has been brought forward to solve this problem, considering the factor like delays,throughput in the network, genes in each chromosome have been supervised in the process of initialization, crossover and mutation, it is help find out the best path corroding to GA algorithms has good convergence in Qos routing, The simulating shows that GA algorithm make an overall improvements in delays and throughput.
　　KeyWord: genetic algorithm; network on chip; quality of service routing
　　
　　1引言
　　
　　 随着半导体技术的发展,系统芯片(System on Chip, SoC) 的规模越来越大, 单芯片多处理器逐渐朝着多核化和异构化的方向发展。而当前基于总线的结构成为限制芯片速度、能耗、面积、数据吞吐率的一个瓶颈问题。为了满足大规模集成电路的发展对可扩展性、能耗、面积、时钟异步、可重用性、服务质量(Quality of Service, QoS)等方面的需求,新的设计方法―片上网络(Network on Chip ,NoC)应运而生,它是对原有设计模式的一次革新。片上网络技术具有支持同时访问、可靠性高、可重用性高等特点,因而被认为是更加理想的大规模片上互连技术。
　　由于大量的多媒体和实时应用技术的出现,这就要求NoC能提供高效的服务质量(QoS)支持。而目前NoC中“尽力而为”的数据传输方式,不能保证数据包传输的时延、吞吐和抖动,对上述的网络业务带来很大的影响,不能满足用户的要求。QoS是指IP分组在一个或多个网络传输过程中所表现的各种性能,它是对各种性能参数的具体描述。这些性能参数包括:业务可靠性、延迟、抖动、带宽、吞吐率和分组丢失率等。研究现有NoC中保证QoS的交换机制和路由算法,在此机制基础之上提出保证QoS的交换机制和路由方法。由于NoC中保证QoS的交换机制和路由算法基本是从因特网中借鉴过来的,而NoC不等同于因特网,传统的交换机制和路由算法不完全适合NoC。所以要深入分析NoC的特点,在此基础之上提出适合NoC的交换机制和路由算法。
　　一是从交换机制出发,结合电路交换和虫孔交换的思想形成一种保证QoS的混合交换机制,并通过仿真分析混合交换机制的性能。二是从路由算法出发,借鉴因特网中保证QoS路由算法和直连网络中的路由算法,提出一种适合NoC的保证QoS路由算法。遗传算法是近几年提出的一种模拟生物进化过程的一种并行优化算法,它具有并行搜索,自适应群体寻优,以及产生一组Pareto最优解集等许多特点,已广泛用于各种具有NP的完全问题。本文主要利用遗传算法来解决片上网络上基于多约束的QoS路由选择问题。
　　 文献[ 1 ]讨论单纯在时延约束下选择最佳路由问题,采用新的交叉、变异算子,使得收敛速度加快,但却没有全面考虑其他约束;文献[ 2 ] 考虑网络时延和传输率两个参数限制下的QoS 路由问题,采用网络树编码机制,算法可以确保遗传操作的有效性,但编码方式不直观,且在等长染色体中会出现冗余基因;文献[ 4 ]是一种基于遗传算法在片上网络中的路径分配方法,使用了完整路径均匀交叉方法,节约了计算时间,但是由于这种交叉方法不会产生新的路径,可能会造成拥挤,减慢进化进程,同时编码方式不直观;文献[ 5 ]则是一种改进的遗传算法应用在宏观网络中解决的多约束QoS单播路由问题,但是其中使用的辅助搜索需要借助数据库操作,这对于片上网络来说很难实现。
　　
　　2QoS路由中的流量控制问题
　　
　　QoS路由算法包含两部分――QoS路由协议和QoS路由策略,其中路由协议用于收集网络信息,路由策略规定选择下一节点的方式。另外,流量控制决定了数据包使用节点缓存的方式,一般是和路由算法绑定在一起。
　　NoC中流控机制是指当一个数据包沿着某条路径路由时,NoC如何来为数据包分配通道和缓存,以及如何解决数据包的资源冲突问题。
　　根据传输信息单位的不同,流控机制分为消息(buffered)流控机制和数据包(bufferless)流控机制。消息流控机制主要用于电路交换,而数据包流控机制主要用于存储转发交换。相对于消息流控机制,数据包流控机制时延更小、吞吐更大。数据包流控机制又可以细分为可信度(Credit Based)、握手(Handshaking Signals)、ACK/NACK、ATALL/GO、T-Error流控机制。
　　可信度流控机制利用一个节点来计算需要转发的数据包和空闲的插槽,。一旦数据包被邻节点处理或者被转发到其他节点,当前节点便收到可信度信号。QNoC采用可信度流控机制。
　　在握手流控机制中,当一个节点发送一个数据片(flit)后,同时紧随数据片发送一个VALID信号。当接收节点接收并处理完数据片后,会发送一个确认VALID信号到发送节点。SoCIN NoC采用握手流量控制。
　　在ACK/NACK流控机制中,当发送节点发送一个数据片到目的节点后,这个数据片的复制品一直滞留在节点中的buffer中。当节点接收到ACK信号,说明数据片成功到达目的节点,这个数据片的复制品就会从buffer移除掉。如果接收到NACK信号,说明目的节点没有接收到数据片,复制品便会从新发送到目的节点。XPIPES采用ACK/NACK流控机制。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文 　　在ATALL/GO流控机制中,在目的节点和源节点中有两条信号线,当目的节点中buffer空时,会发送GO信号到源节点。相反,如果目的节点中buffer满时,会发送ATALL信号到源节点。目前还没有任何NoC结构采用ATALL/GO流控机制。
　　 相对于其他流控机制,T-Error流控机制复杂得多,该机制以降低可靠性来提高系统的性能。一般情况下,实时系统在噪杂的环境中尽量避免采用T-Error流控机制。同样,目前还没有任何NoC结构采用T-Error流控机制。
　　
　　3QoS路由问题
　　
　　 计算机网络可用一个带权的有向图G 来表示,G = (N,E)其中N 是网络中节点的集合,E是网络中边(链路)的集合。对于一个规定的路由请求w,满足条件的路由P(起始节点s,终止节点t)必须有如下的服务性能要求,即路由中包含的节点和边必须满足以下2 种度量:
　　 时延限制:ΣDN(n)+ΣDE(e)≤Dw其中DN(n)和DE(e)分别是节点和边时延。
　　 吞吐限制:ΣTP(n)≥TPn ,其中TP(n)是P在n点上的吞吐。
　　本文采用的是基于2维MESH拓扑结构上的源路由的路由选择机制,即网络中每个源结点均维护一个全局的网络拓扑及各个链路上时延和吞吐等状态的参数,在源端进行计算并确定路由。网络模型如图1所示,其中边链路上有[D,TW],其中D,TW分别代表延时和吞吐。另外由于源路由选择机制简单,但实时性略有欠缺,可以考虑每隔一个时间段发出一个小的请求消息对其上的拓扑表中状态参数进行更新,以确保路由选择和资源分配的合理性,同时累计头片中的时延大小,当该数据片在传输过程中的累积时延超过预期约束时延,则转换成为维序路由。
　　
　　4基于遗传算法的路径分配方法
　　
　　 4.1 遗传算法的基本原理
　　 遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型, 其本质是从一个随机的初始群体出发, 依据优胜劣汰的原则, 通过竞争、选择、交叉、变异等遗传优化作用, 产生性能更优的下一代群体,直到满足环境约束的优良个体或合乎具体应用准则为止,如图2 所示。其中,终止条件的判定通常依据给定的迭代次数要求或者相邻迭代结果间差异最小化的要求。
　　
　　 4.2种群初始化
　　 根据网络拓扑表中数据初始化一张二维路权表,表中数据为拓扑表中时延大小DE(e)和吞吐TP(暂时先不考虑)。从给定的节点中随机选出一点,该点不能是起始或终止节点,再根据路权表中权值大小按照Djkstra算法分别算出该点与起始和终止结点之间最短路径并将这两条路径在该点处合并。如果合并后的路径中间出现两个相同结点则将这两点之间路径去除以保证整个路径中无环路的出现。
　　
　　 4.3 适应度函数
　　适应度函数值是遗传算法中评价染色体个体优越性的标准,并对遗传操作的选择、交叉和变异都起作用。综合考虑QoS 路由中时延、吞吐等度量的要求,为避免单目标函数的缺陷,建立如下的适应度函数。
　　 F(P(s,t))α×f■×f■(1)
　　 Φ■(x)=1,如果x≤0β当x >0,且0 本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文 　　[3] Koyama A, Barolli L, Matsumoto K, Apduhan B O. AGA-Based Multi-Purpose Optimization Algorithm for QoS Routing [A]. 18th International Conference on Advanced Information Networking and Applications [C]. 2004, 1:23-28.
　　[4] 岳培培,刘建,Sheraz Anjum,陈杰. 基于遗传算法的NoC路径分配[J]算法微电子学与计算机, 2008, 25(4):0068-04
　　[5] 吴巍,阮秋琦. 用改进的遗传算法解决多约束Qos单播路由问题[J]第27卷第6期铁道学报2005,27(6): 0071-06.
　　[6] Chang Wook Ahn, Ramakrishna R S. A GeneticAlgorithm for Shortest Path Routing Problem and the Sizing of Populations[J]. IEEE transactions on evolutionary computation,2002, 6(6): 566-580.
　　[7] Zid, M., et al. New generic GALS NoC architectures with multiple QoS. in Design and Test of Integrated Systems in Nanoscale Technology, 2006. DTIS 2006. International Conference on.2006
　　[8]何小燕,费翔,罗军舟,等.Internet中一种基于遗传算法的QoS路由选择策略[J] .计算机学报,2000,23(11):1171-1178.HE Xiao-Yan,FEI Xiang,LUO
　　(下转第42页)
　　Jun-Zhou,et al.A Scheme for QoS-based routing using genentic Algorithm in internet [J] .Chinese Journal of Computers,2000,23(11):1171-1178.
　　[9]黄晓雯,贺细平,唐贤英.基于遗传算法的QoS路由选择与仿真[J].计算机仿真,2003, 20(6): 43-46.
　　[10] P. Guerrier and A. Greiner A generic architecture for on-chip packet-switched interconnections[R]. Design Automaion and Test in Europe Conference and Exhibition 2000. March,2000. pp.250-256.
　　[11] Mehmet Derin Harmanci, Nuria Pazos Escudero, Yusuf Leblebici and Paolo Ienne, Quantitative Modelling and Comparison of Communication Schemes to Guarantee Quality-of-Service in Networks-on-Chip[R], IEEE International Symposium on Circuits and Systems, May 2005 Vol. 2,.pp.1782-1785.
　　[12]Evgeny Bolotin, Israel Cidon, Ran Ginosar, Avinoam Kolodny, Cost considerations in Network on Chip[J], the VLSI Journal archive Integration, 2004.Volume 38 Issue 1 pp.19-42,
　　[13]H Kariniemi, J Nurmi Arbitration and Routing Schemes for On-chip Packet Networks [C]. Interconnect-Centric Design for Advanced SoC and NoC,. Kluwer Academic Publishers. 2004. 253-282.
　　
　　作者简介
　　宁欢,硕士研究生,主要研究领域为片上网络服务质量的研究。
　　王长山,硕士生导师,副教授,研究方向为软件理论与应用和计算机网络.
　　郭彬,硕士研究生,主要研究领域为片上网络拓扑结构研究。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文