（通信与信息系统专业论文）片上网络路由器调度算法的研究.pdf

摘要随着器件特征尺寸的进一步缩小，对超大规模集成电路的集成度和电路时钟频率的要求越来越高，片上网络成为下一代芯片设计的首选方案。高性能路由器可以帮助提高片上网络的网络性能。调度器作为路由器中的核心单元，它的性能好坏直接影响着整个网络的性能。因此，如何设计高效的调度算法来提高片上网络的性能是本文的研究重点。本文首先对片上网络及其常见的路由器结构进行了总结与分析并研究了传统的互连网络中常见的调度算法。继而分析了相关的n o c 路由器调度算法发展现状，并对已有相应的调度算法特性进行了总结。首先，针对传统的调度算法应用于分组随机存放的输入缓存n o c 路由器上的问题进行了改进。接着，针对之前算法存在的时延较大问题，结合片上网络的虫孔交换及路由器结构特点，我们提出了一种适用于n o c 路由器的早到分组先发的结合优先权轮询的调度算法( e p f r r ) 。基于o p n e t 仿真平台，对新算法的时延、吞吐、能耗等性能进行了评估。同时，我们比较了在不同的流量模式下，e p f r r 算法与i s l i p 、i s l m i t e r a t i o n 、p i m 、r r m 相比的性能，仿真对比表明e p f r r 算法改进了轮询策略之后，能更好的提高片上网络的吞吐和时延性能。为了更进一步的验证该算法的可实现性，对算法的各个模块分别在硬件仿真平台m o d e l s i m 上进行了详细的设计和仿真验证。验证结果表明，本设计功能正确，满足设计需求。关键词：片上网络调度算法仲裁0 p n e ta bs t r a c tw i t ht h ef e a t u r es i z eo fe l e c t r i c a ld e v i c e ss h r i n k i n gc o n t i n u o u s l y , t h ei n t e g r a t i o nd e n s i t ya n dc l o c kf r e q u e n c yo ft h ev l s ic i r c u i ti n c r e a s e ss i g n i f i c a n t l y n e t w o r ko nc h i pt e c h n o l o g yb e c o m e st h ef i r s tc h o i c eo ff u t u r el a r g e s c a l ei n t e g r a t e dc i r c u i li nw h i c ht h eh i g h p e r f o r m a n c er o u t e ra r c h i t e c t u r ei sag o o ds o l u t i o nt oi m p r o v et h ep e r f o r m a n c eo fn e t w o r ko nc h i p s c h e d u l e ri st h ek e r n e lc o m p o n e n to ft h er o u t e ra r c h i t e c t u r ea n di t sp e r f o r m a n c ed i r e c t l ya f f e c t st h ep e r f o r m a n c eo fe n t i r en e t w o r k t h e r e f o r e ，t h em a i nc o n t r i b u t i o no ft h i st h e s i si sd e s i g n i n ga ne f f i c i e n ts c h e d u l i n ga l g o r i t h m f i r s t ，r e c e n td e v e l o p m e n t so fn e t w o r ko nc h i pa n db a s i cr o u t e ra r c h i t e c t u r ea r es u r v e y e dw i t l lt h ea n a l y s i so fs o m ec o m m o ns c h e d u l i n ga l g o r i t h m si ni n t e r c o n n e c t i o nn e t w o r ki nd e t a i l s t h e n ，t h es c h e d u l i n ga l g o r i t h m sr e l a t e dt on e t w o r ko nc h i pr o u t e ra n dt h eb a s i cc h a r a c t e r i s t i c so fs e v e r a lp r o p o s e ds c h e d u l i n ga l g o r i t h m sa r es t u d i e d w ei m p r o v et h er a n d o mb u f f e r i n gm e t h o do fi n p u tb u f f e r e dn e t w o r ko nc h i pr o u t e rb yu s i n gt h et r a d i t i o n a ls c h e d u l i n ga l g o r i t h m sw h i c ha r eu s e di nt h ei n t e r a c tr o u t e r f u r t h e r ,a l le a r l y - p a c k e t - f i r s tc o m b i n e d 、) l ，i t l lr o u n d - r o b i ns c h e d u l i n ga l g o r i t h m ，e p f - r r , i sp r o p o s e di nt h i st h e s i s t h i sa l g o r i t h mt a k e st h ep r o p e r t i e so fw o r m h o l es w i t c h i n ga n do n - c h i pm u t e ra r c h i t e c t u r ei n t oc o n s i d e r a t i o n t h ep r o b l e mo fh i 曲d e l a yo fe x i t i n ga l g o r i t h mi se f f e c t i v e l ys o l v e d w ee v a l u a t et h ep e r f o r m a n c eo ft h ep r o p o s e da l g o r i t h mi nt h eo p n e ts i m u l a t i o np l a t f o r m ，i n c l u d i n gp a c k e td e l a y , t h r o u g h p u ta n de n e r g yc o n s u m p t i o n t h es i m u l a t i o nr e s u l t sd e m o n s t r a t et h a tt h ee p f - r rs c h e d u l i n ga l g o r i t h mc a l la c h i e v eb e t t e rn e t w o r kp e r f o r m a n c ec o m p a r e d 诵mi s l i p , i s l i p i t e r a t i o n ，r r m ，p i mi na v e r a g ed e l a ya n dt h r o u g h p u tu n d e rd i f f e r e n tt r a f f i cp a a e r n s f i n a l l y , w ed e s i g na n dv e r i f ye a c hm o d u l eo ft h ee p f r ra l g o r i t h mi nt h em o d e l s i mh a r d w a r es i m u l a t i o np l a t f o r mt og u a r a n t e ei t sf e a s i b i l i t y t h ev e r i f i c a t i o nr e s u l t si n d i c a t et h a tt h ep r o p o s e da l g o r i t h mw o r k sw i t hc o r r e c tf u n c t i o n a l i t ya n dm e e t st h ed e s i g nr e q u i r e m e n t s k e y w o r d s ：n e t w o r k0 1 1c h i ps e h e d u l i n ga l g o r i t h ma r b i t r a t i o no p n e t第一章绪论第一章绪论1 1 引言随着i c 技术的发展，单个芯片上集成的晶体管数目按照摩尔定律的速度逐年增长将达到l o 亿个以上，片上通信的频率也将达到1 0 g h z 以上。目前，被广泛应用于大规模集成电路系统设计的s o c 出现了很多瓶颈问题【1 】。随着处理器和口核数量的进一步增加，s o c 中的总线互连方式将无法适应未来片上数据通信的要求，因此必须寻求一种新的芯片互连结构。集成电路设计效率与芯片集成度之间的剪刀差还在进一步的增加，根据方法学理论扩大可重用单元规模是缩短剪刀差的重要策略。单一时钟同步问题也成为芯片设计的难点导致时钟错位很难精确控制，因此应该考虑采用异步时钟。1 9 9 9 年提出的片上网络( n e t w o r ko nc h i p ，n o c )作为一种新的片上互连方式，将很好的解决未来复杂s o c 设计中遇到的各种问题。如今，集成电路设计已经进入了深亚微米阶段和纳米阶段，一个芯片中将集成更多的处理器或i p 核，而芯片面积却越来越小，单位面积上的集成度极度增加【2 l 。据i t r s ( i n t e r n a t i o n a lt e c h n o l o g yf o rs e m i c o n d u c t o r ) 预测，2 0 1 6 年将实现2 2 n m ，处理能力将在1 0 0 到1 0 0 0 g i p s 之间。因此，n o c 互连通信的研究将成为学术领域的一个新的研究热点，具有广泛的应用前景。1 2 片上网络的研究概述随着处理器内存的存取速度不断提高，通信性能已经极大地受到了总线瓶颈的阻碍。不能满足芯片内部低时延、低功耗、高通信量的要求，而且可扩展性和可并行性也受到很大的限制1 3 j 。虽然，近年来总线的频率也在不断地提升，但是由于总线的资源独占性导致其他通信请求必须等待。同时，随着处理器、口核的数量继续增长，核内通信量会越来越大，传统的共享总线连接方式将极大地限制通信速度，造成不必要的时延。在实现了功能强大的同时，为了解决设计问题实现更好的性能，采用网络互连方式进行通信受到了广泛的关注，即片上网络的应运而生。在n o c 互连模式下，计算单元和通信网络分离设计。网络连接是由路由节点、网络接口和数据链路组成，而计算单元主要是指i p 核。其中的i p 核可以是存储单元、计算单元、中央处理单元、传输控制单元等特定功能模块。网络接口负责m 核与网络之间的分组转换；路由节点负责数据的接收、存储、转发，决定了分组的转发方式，是决定整个网络性能的关键因素。2片上网络路由器调度算法的研究1 2 1n o c 技术的研究背景2 0 世纪9 0 年代中期，s o c 作为一种新的集成电路的发展趋势在i c 产业中取得了日新月异的发展。随着2 l 世纪的到来，电子元器件的特征尺寸进入超深亚微米时代乃至纳米加工时代。于是基于共享总线互连模式的s o c 设计体系结构将无法满足未来更高的芯片设计技术需求。因此，在9 0 年代末，针对s o c 面临的一系列问题n o c 作为一种全新的互连结构被提出来。n o c 将基于网络通信的多处理器系统功能在单一的芯片上实现了，它包括计算和通信两类节点，计算节点完成广义的计算任务，他们可以是s o c 或者是各种单一功能的特定功能模块；通信节点通过节点之间的链路实现计算节点之间的数据通信。借鉴路由和分组交换的技术代替了传统的总线方式完成通信任务。n o c 互连与s o c 相比较有以下本质的不同：( 1 ) 克服了s o c 的总线可扩展性差的缺点，n o c 具有很强的地址空间可扩展性，从理论上讲，可以实现资源节点数目的无限集成1 4 】；其次，提供了良好的分组的并行通信的能力，提高了数据吞吐量及整体性能。( 2 ) n o c 采用全局异步局部同步的工作方式及i p 核可复用技术【3 】。克服了全局同步设计时的时钟同步困难及带来庞大的时钟树问题、降低了时钟功耗并且减小了面积。( 3 ) 具有较强的可测试性。n o c 体系结构的提出伴随着相应的一些关键技术和设计方法的出现。在进行n o c 体系结构的设计时，需要考虑到多方面的因素。如拓扑结构、路由算法、交换机制、路由器设计等。1 2 1 1 拓扑结构n o c 中的拓扑结构定义了网络内节点与链路的布局和互连方式，它对网络的时延、吞吐率、面积、容错、功耗等都有至关重要的影响，进一步影响了网络中的路由算法和映射算法等。现阶段n o c 拓扑结构主要有基于格子的拓扑结构、基于环的拓扑结构、基于树的拓扑结构、混合拓扑结构、多维片上网络拓扑结构及基于多资源连接的路由节点的拓扑结构等。1 2 1 2 路由算法路由算法决定了分组在网络中转发的方向和路径。根据不同的标准分类，主要包括以下几种。按照目的地的数目分为：集中式路由，分布式路由，源路由和多阶段路由。按照路由是否具有自适应性：分为无关路由和自适应路由。按照选择路径是否最短：分为最短路由和绕道路由。当然这种分类之间具有重叠性，一种路由算法可以既属于确定性路由算法又属于最短路由，故对于一个路由算法应进行多角度分析。1 2 1 3 交换机制交换机制定义了数据分组在网络路由器中的输入和输出的时机和方式，并定义了消息沿着这些路径传输的时间。在很大程度上决定了路由算法的选择，以及相应的死锁、活锁、饿死的特性。n o c 应用的基本的交换机制主要有存储转发交第一章绪论换、虚切通交换、虫孔交换、流水电路交换等，在进一步的n o c 研究中又提出了改进的虫孔交换、分层交换、信元交换等新的交换技术。1 2 1 4 路由器设计在n o c 中路由器作为整个网络连接的关键节点，除了连接本地i p 核外还要与周围其他端口的路由节点进行连接。一个经典的路由器结构【5 1 ，包含的主要部分有：输入缓存( b w ，b u f f e rw r i t e ) 、路由计算( r c ，r o u t i n gc o m p u t a t i o n ) 、虚信道分配( v a ，v i r t u a lc h a n n e l a l l o c a t i o n ) 、交叉开关分配( s a ，s w i t c h a l l o c a t i o n ) 、链路传输( s t ，s w i t c ht r a v e r s a l ) 等。路由器是n o c 上最重要的部分，根据路由地址和分组优先级，负责分组从一个输入端口到另一个输出端口的传输，n o c 所有的功能设计基本上都要在路由器上实现，比如路由算法、流控机制、调度算法、拥塞控制、服务质量( q o s ，q u a l i t yo fs e r v i c e ) 等，同时拓扑结构对路由器的设计也有决定性的影响。为了避免死锁、阻塞等现象，在路由器结构设计上还会增加虚信道等缓存管理技术。针对路由设计的优化目标的不同常见的路由器结构设计有基于服务质量要求的路由器设计、基于路由算法的路由器设计、基于三维拓扑的路由器设计等。1 2 1 5 路由仲裁机制n o c 是由大量的路由节点以网络的方式互连组成，使得不同的i p 核之间实现通信。在2 d m e s h 网络结构中每个路由节点通过与其他四个不同的方向( 东南西北) 的其他路由节点连接之外，并通过第五个端口的网络接口与本地p 核互连。端口之间进行分组传输时需要通过交叉开关搭建合理的数据链路。当多个方向传输过来的分组请求信号共同竞争一个输出端口时，需要位于路由器内的调度器中的仲裁器来裁决众多请求传输的顺序。传统仲裁器要求互斥性、无锁性、可复位性等，这些特性保证仲裁器从软件映射到硬件过程中无差错工作。然而，公平性也是其主要特性代表着仲裁器处理数据分组请求的原则。好的公平性可以确保等待请求会被公平处理。一个有效的仲裁器应该在尽量减少n i 缓冲资源消耗的同时考虑避免“饥饿 现象和减少路由器的数据传输平均时延。在以往的n o c 设计中，仲裁机制往往会影响n o c 整体的工作性能。因此如何设计一个高效的、可靠的、低时延并能保证一定服务质量的仲裁器也是一个研究的重点【6 】。1 2 2n o c 国内外研究动态1 2 2 1 国外研究概况随着技术的发展，国际上越来越多的研究机构开始纷纷投入到n o c 的学术前沿领域的研究。在本世纪初，国外就开始了对片上网络的研究。其中影响较大的有瑞典皇家技术学院、斯坦福大学、m i t 和荷兰菲利普研究实验室等。参与研究的国家还有法国、意大利、芬兰、希腊、以色列、巴西、印度、澳大利亚等。4片上网络路由器调度算法的研究2 0 0 0 年3 月，可升级、可集成的网络被法国p i e r r ee tm a r i ec u r i e 大学的p i e r r eg u e r r i e r 等人提出，并在系统芯片的设计中引入了分组交换的方法。在此基础上建立了周期精确的路由器性能模型【7 1 。2 0 0 0 年末，瑞典皇家技术学院等单位首次提出“n e t w o r ko nc h i p ”概念，n o c 定义为在一块芯片上实现的，计算资源、存储资源以及i o 资源等通过交叉开关网络互连的系统结构。文章1 8 j 中研究开发一种新的网络架构，将片上网络上层的体系结构与底层的微体系结构层面上的各种性能参数集成在一起，旨在探索这些参数对于片上互连体系性能的影响。资源节点通过网络搭建的模式，通过一定的路由计算经过交叉开关将分组从源地址传送到目的地址【9 】。接着n o c 研究的热潮，很多国家的研究所纷纷开展了n o c 的路由器微体系结构、拓扑结构、低功耗【l o 】、多处理器网络建模【l l 】等各个方面的研究。g i o v a n n id em i c h e l i 带领其团队开发了一整套的n o c 组件库x p i p e s 及详细的设计流程【1 2 】。2 0 0 7 开始国际上首次组织了以n o c 为主题的国际会议( n o c s 0 7 ) ，如今已经连续成功举办了五届，内容涵盖了片上网络的路由器结构与算法优化、死锁解决、容错及安全性、拓扑结构设计与优化、功耗分析，q o s 保障、测试分析、新颖想法引入等。n o c s 2 0 1 2 也将在2 0 1 2 年五月份在美国p i t t s b u r g h 市召开。除此之外，2 0 0 8 年创建的n o c a r c 会议以及h p c a 、m i c r o 、i s c a 等国际会议专栏里都开始收录了越来越多的关于片上互连网络的文献，为n o c 通信相关知识交流提供了有利的平台。国外的科学家都在试图从各个方面解决n o c 所面临的问题。1 2 2 2 国内研究概况n o c 作为一个崭新的集成电路设计理论体系正处于初创阶段，自2 0 0 6 年开始国内很多研究机构及大学中的科研工作者也逐步从事着n o c 学术领域的前沿工作。为了支持片上网络的相关技术发展，国家也通过设立8 6 3 计划s o c 重大专项和自然科学基金s o c 重大专项。由此可见，n o c 在国内也属于研究的热点。现在据统计，国内从事n o c 研究的主要大学和研究机构有t 清华大学、成都电子科技大学、西安电子科技大学、中国人民解放军国防科技大学、浙江大学、复旦大学、西安邮电学院、合肥工业大学、武汉理工大学、北京邮电大学、东南大学、南京大学、中科院计算所、中科院半导体研究所等。1 3n o c 路由器体系结构概述目前，由于片上网络的资源限制，片上路由器都是由较简单的逻辑元件组成。此外，在片上网络中缓存是最宝贵的资源，片上路由器中的缓存通常很小。因此，与并行计算网络不同，以合理的造价支持高效的路由技术和流控协议将会成为当前和今后一段时间内片上网络路由器发展的方向和趋势。第一章绪论1 3 1n o c 路由器体系结构当n o c 成为集成电路发展道路上不可取代的研究趋势之后，n o c 路由节点的设计逐步成为研究的重点。路由器节点是片上网络的核心元件，路由计算和交换机制等关键技术都是在路由器中实现的，它保证系统数据传输的正确高效进行。如图1 1 所示是一个只需要较少的缓存空间的基于虫孔交换的虚信道路由器，能够进一步降低网络拥塞提高片上网络的吞吐。另外，虚信道还是一种解决自适应路由算法死锁问题的有效方法。因此，基于虫孔交换的虚信道路由器成为当前片上网络中采用的主流路由器结构【5 j 。如图1 1 中所示，片上网络路由器主要由输入端口( i n p u tp o r t ) 、路由单元( r o u t e r ) 、交叉开关( c r o s s b a r ) 、仲裁单元( a r b i t e r ) 、输出端d ( o u t p u tp o r t ) 组成。图1 1 片上网络路由器结构1 3 1 1 输入端口输入端口是由数据链路和控制链路构成的，主要完成两个功能。当有分组到来时，输入端口流控模块负责将数据缓存到相应的输入缓存中；控制链路负责与前一路由器节点之间进行控制信息的传输；在虚信道路由器中，当某个输入端口有k 个虚信道时，还需要一定的仲裁机制来解决输入端口传输链路资源竞争问题。采用虚信道的策略不仅能避免队头阻塞的发生【1 3 】，而且合理的配置虚信道还能实现低功耗、高吞吐、高频率的片上网络通信。与通用路由器相比，提高了路由器端口的资源利用率并提供了很好的网络互连的条件，使得数据分组传输性能更优。1 3 1 2 路由单元路由单元主要由头部译码和路由计算两部分组成。头部译码主要是完成到达的分组微片类型的区分，实现头微片与体微片及尾微片的分开存储。在头部译码完成之后，路由计算模块根据头部译码得到的头微片信息进行路由计算从而得到分组要到达的目的节点的地址信息。避免了通用路由器中查找路由表的过程，也不用再保存路由表信息，从而节省了面积，同时也避免了查表所浪费的时间。1 3 1 3 交叉开关6片上网络路由器调度算法的研究在虚信道路由器中，完成相应的路由计算之后，需要经过交叉开关单元实现数据从输入端口到输出端口的传输。通常在片上网络路由器实现中采用的交叉开关主要有以下两种：如图1 2 所示交叉结点式交叉开关，这种交叉开关结构是采用三态门来控制数据通路的连通性，输入端口和输出端口之间的连接通过交叉结点处建立的互连实现选择性的互连一交叉节点式交叉开关将输入端口和输出端口直接相连，由相应的仲裁器决定三态门的控制逻辑。如图所示，一旦交叉节点处于激活状态时，相应的输入端口便连接到相应的输出端口，例如东输入端口的数据可以发送到北输出端口。一i1 i 已_ 已 已一山 已_ 巳- i。- 巳叫i_ 已- 已_ i_ 已一c _- i_ ii - i- i一i i- i，_ i1 已=图1 2 交叉节点式交叉开关” k ：o 】吣聃：o j 毗o p _ s i s ：o 吣f ：o 】图1 3 基于多路复用器的交叉开关另一种是基于多路复用器的交叉开关。如图1 3 所示，基于多路复用器的交叉开关主要是采用控制信号来控制多路复用器的选通，从而实现相应的输入端口和输出端口的连接，一般在片上网络设计中调度算法除了完成输入和输出的链路匹配之外还会给出多路复用器的控制信息。1 3 1 4 仲裁单元在n o c 路由器中，要实现虚信道和交叉开关调度功能必须采用一定的仲裁器实现数据分组请求资源的分配问题。首先路由计算需要进行路由端口的计算进而进行相应的虚信道调度和交叉开关调度。调度器结构也会相应的比较复杂。其次，当采用高自适应性的路由算法时虚信道采用仲裁器搭建调度器【1 4 1 来完成交叉开关输入和输出链路的连接。然后数据分组才能顺利的通过交叉开关传输到相应的输出链路上，完成数据分组的存储转发。仲裁单元完成的主要功能就是解除交叉开关输入端v ：i 和输出端1 3 的资源竞争问题，从而提供更好的数据通信链跗6 1 5 l 。提高数据传输的质量、保证路由器性能达到更优。1 3 1 5 输出端口输出端口主要实现数据经过交叉开关后的链路传输，并且完成本节点与下一节点之间的控制信息的交互( 例如，两相邻路由节点之间流控信息的转发) 。与通用路由器相比具有更丰富的控制功能，灵活性更强。第一章绪论71 3 2n o c 路由器结构分类缓存队列的位置的不同，片上网络路由器结构主要有三种【1 6 1 ：输入队列【17 1 ( i q ，i n p u tq u e u i n g ) 、输出队列【1 8 1 9 l ( o q ，o u t p u tq u e u i n g ) 、组合输入输出排队( c i o q ，茹三鞲：三三群：翁三高排翁三出队列( v o q ，v i r t u a lo u t p u tq u e u i n g ) 结构。1 4 本文研究的主要内容近年来，随着i c 工艺水平的日趋成熟和新型半导体材料技术的不断进步，为了满足人们高科技应用的需求芯片设计集成技术取得了突破性的进展，使得片上8片上网络路由器调度算法的研究网络应用实现成为可能。路由器是片上网络的核心单元，对整个片上网络性能的优劣具有重要的影响，而且好的路由性能可以减少时延与能耗，因此无阻塞的片上路由也是片上网络中需要解决的一个重要问题。目前，m e s h 互连网络由于拓扑结构简单在片上网络领域得到了广泛的应用1 2 0 1 ，但由于这些拓扑存在大量环路，会产生死锁问题，因而在片上网络中采用虚信道策略防止死锁的产生，同时也克服了以往的队头阻塞现象。但是，数据的传输状况就决定了网络的性能好坏【2 l 】，如果各个虚信道的数据分组之间没有合理的调度来控制，这又会进一步增大片上网络的阻塞问题，反而导致网络性能不理想。因此，本文重点研究如何结合片上网络特定的路由器结构设计合理的调度算法，保证数据分组实现低时延、高吞吐、无饥饿、公平性、高效的传输，并保证路由器资源的合理分配。1 5 论文结构和开展的工作调度算法作为路由器体系结构中的一个重要部分，它直接影响了路由器的性能甚至整个网络的性能。在典型的n o c 虚信道路由器设计中，调度算法主要解决虚信道分配问题以及交叉开关的调度问题，从而解决数据分组对链路资源的竞争。因此，本文主要工作就是研究片上网络路由器调度问题，实现一个高速、简单、低时延、公平、高吞吐、高利用率的调度算法。第二章首先明确仲裁和调度的基本概念，了解仲裁器和调度器的实现原理。其次，通过介绍不同的n o c 路由器结构，分类介绍目前网络上常用的调度算法，总结相应的性能特点。第三章针对主流的n o c 虚信道路由器结构，在传统调度算法的思想基础上结合片上网络的特点提出适合片上网络的路由器调度算法方案，并在o p n e t 仿真平台上进行软件仿真和性能的对比。第四章评估提出的e p f r r 调度算法的整体性能并与之前的经典调度算法进行对比。基于m e s h 直连网络上的算法仿真结果表明，e p f r r 调度算法具有较低的时延和较高的吞吐，网络的整体性能更加优良。最后，对该新算法的功能进行了相应的硬件验证和实现。第五章在之前章节的分析和研究的基础上对全文进行总结并给出了下一步的研究展望。第二章调度算法基础知识9第二章调度算法基础知识2 1 引言片上网络的设计需要考虑到从下到上的多个层次的诸多问题【捌，主要有拓扑结构设计、路由器结构、路由算法、交换机制、调度算法、q o s 、流量控制、资源网络接口、性能评估、定时和映射优化等很多个关键问题。其中调度算法也是一个关键的问题。在具体介绍片上网络调度算法之前，首先需要了解在路由器中调度器的结构。根据不同的调度器结构我们可以采用相应的仲裁器实现不同策略的调度算法。仲裁实质上就是根据特定的算法来分配共享资源给各个不同的访问功能模块，仲裁机制存在公平性和优先级的矛盾。目前，在n o c 中我们认为仲裁就是解决多个数据分组同时竞争同一条链路资源时存在的分配问题。然而，在n o c中调度主要是指交叉开关的多个有数据分组请求的输入端口与输出端口之间的匹配问题，对于虚信道路由器结构有虚信道分配需求时也要进行虚信道调度。2 2 仲裁器对于来自路由器不同方向的到达同一个输入( 输出) 端口的数据分组请求，仲裁器需要从其中选出一个唯一的数据请求成功传输，实现多选一的功能。仲裁器最重要的性能评价标准就是仲裁的公平性 2 3 1 ，尽可能保证所有到达同一个端口的数据请求获得仲裁的机会彼此平等，避免有些请求出现的饥饿现象。有了基本的仲裁器结构我们就可以搭建出实现两级匹配的调度器结构或者其他模式的调度器结构。为了更清楚的理解调度的实现原理，首先对仲裁器的结构进行介绍。2 2 1 固定( 静态) 优先级仲裁器固定优先级的仲裁器是一种仲裁顺序固定不变的仲裁方式【2 3 1 ，如图2 1 ( b )所示是一个4 输入请求的固定优先级仲裁器的示意图，请求r i 表示是否有请求输入，r i 为高电平时表示有请求，为低电平时表示无请求，参数舀表示是否仲裁成功。图2 1 ( a ) 是单比特的实现电路，是整个仲裁器设计实现的最基本的单元。图2 1( b ) 是将基本单元组合成四比特输入的模式，根据具体应用输入请求数目可变。从图中2 1 ( b ) 的逻辑电路分析可知，这样设计之后仲裁器对四个输入请求的仲裁公平性受到很大的限制，只有当请求r o 为低电平时r l 才能获得仲裁的机会，r o和r l 均为低电平时1 2 才能获得仲裁的机会，以此类推直到r o 、r l 和1 2 均为低电平时r 3 才有可能获得仲裁成功。这种仲裁机制下请求被处理的顺序是固定不变的，因此被称为是固定( 静态) 优先级仲裁。1 0片上网络路由器调度算法的研究( a )(b)(a)图2 1 固定优先级仲裁器原理图2 2 2 可变优先级仲裁器( b )图2 2 可交优先级迭代仲裁器后续的研究中为了改进固定优先级仲裁器公平性差的特点，在固定优先级仲裁器的基础上又提出了许多可变优先级的仲裁器。2 2 2 1 无关仲裁优先级参数如图2 2 ( a ) 所示，在每一个输入请求仲裁时加入一个决定优先级高低的参数p i ，决定了每一个输入请求被处理的顺序。如图2 2 ( b ) 所示，四个输入看作是一个输入向量，四个优先级参数组成一个优先级向量，得到一个仲裁向量表示相应的仲裁结果信息。由于优先权参数p i 是采用随机函数产生的与前一组输入请求和仲裁结果信息没有任何关系，所以称为无关仲裁幽j 。2 2 2 2 轮询( r o u n d r o b i n ) 仲裁轮询仲裁方式，基本思想是当前仲裁成功的请求在下一时钟周期仲裁中的优先级最低，最高优先级赋予相邻的下一个仲裁请求【2 4 l 。如图2 3 所示，对于左边这样一组来自4 个输入端口的不同的请求信息，假设上一轮仲裁中端口2 获得了仲裁成功，因此下一轮仲裁的优先级将从端口3 开始，这样一组输入请求经过轮询端口- 一二工正囚端口2 一二 皿c 。加，姒，邡，蝴讹粥：端口3 二皿r r i n d c x端口4 一二珊图2 3 轮询仲裁机制示例后的仲裁结果为：c 1 专d l 专a l 专b l 专c 2 a 2 专c 3 。2 2 2 2 1 带有傈持电路的轮询仲裁轮询仲裁器资源调度都是一个周期一次，一个请求被仲裁成功之后，到下一个时钟周期需要重新再进行轮询仲裁。然而，考虑到某些应用中要求数据请求连第二章调度算法基础知识续服务好几个周期而不被中断，那么就需要为该请求接入交叉开关的请求链路保持相应的周期数。此时需要在轮询仲裁电路中加入保持电路部分维持分配链路1 2 5 1 。2 2 2 2 2 分配权值的轮询仲裁在要求仲裁器仲裁控制程度不同时，就需要保证各个请求链路获得成功仲裁的机会各不相同。带有权值的仲裁机制就是出于这种考虑，给每一个请求链路i单独分配一个权值w ；代表了链路i 将会接收到分配链路的机率【2 3 1 。例如，假如有一个带有权值的轮询仲裁器分别有四个输入请求的权值为1 ，3 ，5 和7 。则输入请求分别可以获得比例为1 1 6 ，3 1 6 ，5 1 6 和7 1 6 的链路分配机会。2 2 3 矩阵仲裁器1 2 6 】以矩阵的模式来存储每一个请求的状态。如图2 4 所示，三角型阵列根据w i j w j i ，vi ：j 来计算每一个请求状态的优先权。当比特目】被设置为1 就表示请求i 具有比请求j 更高的优先权。矩阵仲裁器的实现如下图2 4 所示。如图，当有一个请求线被维持时，它就会与位于行上的状态比特相与来阻止较低优先权的请求。l 、lg oa，j _ 捌回h ! ! 阻岍yv 1 ) 个请求和一个资源的匹配然而一个调度器完成n( n 1 ) 个请求和m ( m 1 ) 个资源的匹配。在一个路由器中，资源可以被看作是虚信道或交叉开关端口。在一个没有虚信道的虫孔路由器中，在交叉开关每一个输出端口处的仲裁器完成该输出端口与请求的输入端口之间的匹配。因此，每一个输出端口有一个p ：1 仲裁器，每一个仲裁器最终匹配p 个输入端口中的一个到一个单独的输出端口。在一个具有多个虚信道的路由器中，我们需要一个虚信道分配器( v a ) 来解决输出端口的虚信道( 下一跳输入虚信道) 竞争问题并且分配一个输出虚信道给相应的输入虚信道请求。在交叉开关分配过程中同样需要在输入和输出端口分别使用仲裁器来解决竞争问题最终完成交叉开关的端口分配。一个分组只有头微片需要进行虚信道分配，然而所有的微片都要进行交叉开关分配并且允许循环的访问交叉开关。2 3 1 分离调度器路由器调度的实现多数都是以可分离调度器为最基本的结构【2 ，如下图2 6 ( a )所示，输入优先的可分离调度器。主要分两级仲裁来实现最终分配：一级是在输入端，一级是在输出端。在输入端先将各个物理信道过来的虚信道请求之间进行一次仲裁，获得成功的输出虚信道请求作为第二级仲裁的输入。如图2 6 ( b ) 所示，如果是没有虚信道的路由器结构，那么可分离调度器在实现交叉开关调度时，就没有第一级仲裁直接进行第二级仲裁就可以完成输入端口和输出端口之间的匹配。此时，调度器的结构就简化了很多。当把分离调度器的输入和输出换一下次n列2lix11i1ox00d，n列ooxo 弘0 xlo l 0、lliillllli-、n“列0oxl 卸oxl 。汀a ，hi，n州列o0 xo 卜ox o 酚，lth)n_=列ooxo 笛oxlotojn“列oox qioxlli e一噱ii第二章调度算法基础知识序也可采用输出优先的分离调度器来实现端口匹配。例如，考虑到如下一个4 输入3 输出的输入优先的分离调度器的实例，请求矩阵、中间矩阵和分配矩阵分别为r 、x 和g 。图2 6 ( a ) 中红色的线就表示了请求矩阵中有请求的情况，例如，第o 个输入端口三个虚信道都有请求，所以请求矩阵的第一行全部为l 。同理，可对应知道其他各个输入端口的请求状况。中间矩图2 6 调度器原理图( a ) 输入优先的分离调度器【2 3 1 ( b ) 无虚信道时简化为一级r =1 l ll l00lool lx =lo olo oolo010g=lo o0 0 001oo o o阵x 表示经过第一级仲裁之后生成的到达第二级仲裁的输入请求矩阵，如图2 6( a ) 中两级中间的红色连线所示。最终的分配结果如图2 6 ( a ) 输出端口的红色短线所示，用分配矩阵g 表示。从g 可以看出，第0 个输出端口和第0 个输入端口的第0 号虚信道匹配成功，第1 个输出端口和第2 个输入端口的第1 号虚信道匹配成功，第2 个输出端口没有请求匹配成功。这里我们采用的仲裁器是轮询仲裁方式，且优先级指针从每个仲裁器的第一个请求开始。这样的调度结果并不是交叉开关的极大匹配结果。为了实现更好的匹配结果在每一轮匹配完成之后，淘汰掉和本轮调度成功的链路存在竞争的请求，在下一轮调度时只对剩余的请求进行匹配即迭代算法，每一轮迭代生成的任何一条链路都要累积起来和先前迭代生成的链路一起形成最终的分配矩阵。例如，对上面的例子进行第二轮的迭代时，为了遵循每个端口只有一个请求传输的原则，除了请求r 3 2 外，所有其他的请求都会被淘汰。因此第二次迭代时的输入矩阵r 2 、中间矩阵x 2 、分配矩阵g 2 以及迭代完两次以后的累积的最终分配矩阵g 分别为：r 2 = x 2 = g 2 =0 0 00 0 00 0 00 0 lg=1 0 00 0 00 1 00 0 1器器饿搬妻童牌妻童恐1 4片上网络路由器调度算法的研究这就是最基本的分离调度器的实现原理，在后续研究中也出现了许多基于可分离调度器改进的调度器结构。2 3 2 单独输出调度器当有一些单独输出的请求不太可能通过输入级仲裁时，很多输入仲裁器都选择同一个受欢迎的输出，可分离调度器经常会出现不好的匹配结果。此时，如图2 7 所示，单独输出调度器通过在输入仲裁器之前再加一级记录要到每一个输出的请求的数目的计数器来克服这个问题1 2 3 1 。根据计数器的统计结果，输入仲裁器给那些具有低的请求数日( 单独输出) 的请求分配优先权。这样就会减少输出端口的竞争从而实现更好的匹配。一个单独输出的调度器的实现需要类似于分离调度器的以下的几种形式的矩阵，包括r 、x 、g 和c 。如图2 7 所示，矩阵c 给出每一个输入端口到同一输出端口的请求的数目。从图中可以看出有两个请求要到输出端口0 和2 ，有四个请求要到输出端口1 。因此，由r 矩阵就可以得出c 矩阵，即r 矩阵的第0 列和第2列的所有非零的数都要被2 取代并且所有的1 列的非零的数都要被4 取代。输入仲裁器在每一行选择一个请求并且将优先权赋给非零的计数较低的请求从而生成中间矩阵x 。这种给低计数的请求高优先权的方式使得输出端口的竞争分布更均匀。这样就会使得输入3 经过调度x 3 2 给输出2 一个单独的输出请求。如下所示，输出级仲裁按轮询方式形成了分配矩阵g 。地晶晶乒每瞄e 钞辅名毯z够涉毽毯茜媳 媳 钐ul = ：= ju图2 7 单独输出调度器图图2 8 波阵面调度器r =l lll l o0 l oo l1c =2 4 22 4 00 4 00 4 2x =1 0 01 0 00 l o0 0 lg =1 0 00 0 00 1 00 0 l第二章调度算法基础知识1 52 3 3 波震面调度器如图2 8 所示，以前面讨论的分离调度器的请求矩阵为例，图中灰色的单元代表了请求矩阵中的请求。波阵面调度器必须是正方形的矩阵 2 6 , 2 8 】，因此为了实现4输入端口和3 输出端口的匹配，增加了第四列没有请求的单元。波阵面调度器将所有的单元分成组p k ，p k 表示( 川) n 余数为k 的单元构成的组，其中i 和j 分别是每个单元的行坐标和列坐标，n 是该矩阵的维数。这样可以得到组p 0 、p l 、p 2 、p 3 。矩阵仲裁器是以组为单位赋予优先级的，最开始获得优先级的组中的单元同时会获得行令牌和列令牌。当某一个单元有请求时，轮到了它最高优先级同时具有行令牌和列令牌则可以仲裁成功。如图2 9 所示，波阵面调度器的工作原理。图中黑色的单元表示仲裁成功，黑色的短箭头表示令牌的传播位置。如图2 9 ( a )所示，我们以p o 优先级最高开始，即令牌首先给p o 组。由于0 0 和3 1 正好有请求，因此会仲裁成功，如图2 9 ( b ) 所示，p o 组中的其他单元没有请求因此没有仲裁成功，但是需要在下一波仲裁前将行( 列) 令牌分别传给右方( 下方) 的单元。由于第二波仲裁时优先权轮到p l 组，但是由于o o 和3 1 分别消耗了行令牌和列令牌，因此只有2 2 和1 3 的令牌传向下一组，导致了第二波没有单元仲裁成功。如此一直进行下去，直到优先权轮了一圈后，就表示一次调度完成。从图2 9 ( d )可以看出这次调度的结果和分离调度器第一轮的结果是一样的都匹配成功了两条链路。但是，分离调度器可以通过多次迭代的方法实现极大匹配，达到比波阵面调度器更好的效果。然而，只看单次迭代的结果，一般情况下波阵面调度器的效果比分离调度器更优。回团团一眇创回回徊倔回母圆日回回圉向(f r l图2 9 波阵面调度器的工作过程示意图2 4 常见的网络调度算法根据前面提到的三种路由器结构可知常用的有三种路由器结构，但是最常用的还是输入队列的路由器结构。因此，这里主要介绍输入队列路由器中的经典路由器调度算法。现在网络中主要采用的调度算法有两类 2 6 1 ：最大匹配( m s m ,m a x i m u ms i z em a t c h i n g ) 和最大权重匹配( m w m ，m a x i m u mw e i g h tm a t c h i n g ) 。最大匹配是指匹配成功的边数达到最大的匹配；最大权重匹配是指每次匹配成功1 6片上网络路由器调度算法的研究的边的权重之和最大。由于这两种算法的实现复杂度太高，所以现在大多以极大尺寸匹配( m s m ，m a x i m a ls i z em a t c h i n g ) 和极大权重匹配( m w m ，m a x i m a lw e i g h tm a t c h i n g ) 来近似相应的最大匹配。极大尺寸调度算法有时也称为极大匹配调度算法，首先，了解现在网络中常见的极大匹配调度算法及常见的极大权匹配调度算法，后续再对片上网络中调度部分进行介绍。2 4 1 极大匹配调度算法2 4 1 1p i m 调度算法p i m ( p a r a l l e li t e r a t i v em a t c h i n g ) 算法【2 9 , 3 0 】是较早应用于互连网络的调度算法，该