（电路与系统专业论文）公平可扩展网络交换的分布式迭代算法及其fpga实现.pdf

摘要 摘要 基于输入队列调度的网络调度算法从硬件架构角度可以分为单片调度算法和可扩 展调度算法两大类。目前，已经有单片的交换机和调度器的集成电路芯片在产，但是单 片集成电路芯片的交换容量和调度容量都非常有限，通常只能实现3 2 个端口之间的交 换或调度，要想在单片集成电路上实现更大规模的交换和调度功能( 如2 5 6 x 2 5 6 ) 十分困 难。可扩展调度是指通过将较小规模的调度器级联实现大容量多端口调度的调度方法， 主要解决单片调度器规模和输入输出端口数受限的问题。 本文对可公平扩展网络调度系统( f s s a ) 进行了深入的研究。f s s a 是在国家自然科 学基金资助下提出的一种公平可扩展网络交换调度结构，它由若干片容量较小的调度器 串联而成，在中心控制器的控制下，各子调度器并行工作完成大容量、多端口的调度任 务。在实际应用中，f s s a 可根据需要扩展成不同容量和端口数的调度器，不仅速度高， 而且规模可扩展，从根本上解决单个调度器容量和端口受限的问题。 本文重点研究了基于f s s a 的可扩展调度系统的性能提高。通过对f s s a 结构中最 高优先级时隙的优化利用，提出了能够实现多次迭代的分布式迭代算法f s s a - d i 以提高 系统的性能。仿真结果表明，在均匀流量下，延时性能和平均队列长度性能均有明显提 高，在对角线等其它流量模式下性能亦有一定改善。而- 日该算法以较小的硬件代价换取 了系统性能的明显提高，取得了性能与复杂度的良好折中。 本文还用x i l i n xv i r t e x - 4f p g a 对f s s a d i 算法进行了设计和实现。首先给出各主 要模块的定义，用h d l 进行了结构设计并进行了功能仿真，然后通过x i l i n xi s e 工具 对设计进行了布局布线。后仿真结果表明，基于f s s a - d i 的子调度器功能正确，时序满 足设计要求，最大串行速率可达8 0 0 m b p s 。仿真报告表明，与f s s a 算法相比，基于 f s s a d i 算法的硬件资源的增加有限，但算法性能得到了明显提高，从而实现了性能与 成本的良好折中 本文从性能和硬件复杂度折中的角度提出的针对公平可扩展网络调度系统的分布 式迭代算法，不仅提高了f s s a 调度器的性能，而且其算法思想也可用于单调度器中， 具有一定的理论意义和实用价值 关键词：嘲络交换，输入队列，可扩展结构，分布式迭代，f p g a a b s t r a c t a b s t r a c t n e t w o r ks c h e d u l i n ga l g o r i t h m sb a s e do ni n p u tq u e u e ds w i t c h e sc o u l db ed i v i d e dt om o n o l i t h i c s c h e d u l i n ga l g o r i t h m sa n ds c a l a b l es c h e d u l i n ga l g o r i t h m sa c c a ) r d i n gt ot h e i ra r c h i t e c t u r e w h i l em o n o l i t h i c s c h e d u l e rf o r3 2 x 3 2s w i t c h e sh a sb e e ni nm a r k e tf o rs e v e r n ly e a r s i t sc o m p l e x i t va n di on u m b e r sa r c l i m i t e db ys e m i c o n d u c t o rt e c h n o l o g y i no t h e rw o r d s , u s i n gs t a t e - o f - t h e - a r tt e c h n o l o g y , a1 2 8 x 1 2 8o r 2 5 6 x 2 5 6s c h e d u l e ri ss t i l lh a r dt oi m p l e m e n ti nam o n o l i t h i cc h i p c o n s e q u e n t l y , i ti sn e c e s s a r yt oe x p l o i t as c a l a b l es c h e d u l i n ga r c h i t e c t u r et om e e tt h ed e m a n do f n e x tg e n e r a t i o nn e t w o r k as c a l a b l es c h e d u l i n ga r c h i t e c t u r ef s s ah a sb e e np r o p o s e dt oe l i m i n a t et h el i m i t a t i o no fs i n g l ec h i p i ne a p a c i t ya n di on u m b e r s f s s ai saf a i rs c a l a b l es c h e d u l i n ga l g o r i t h mw h i c hi ss u p p o r t e db yn a t i o n a l n a t u r a ls c i e n c ef o u n d a t i o n i nf s s a s e v e r n is m a l l e rs c h e d u l e r sa r ec o n n e c t e ds e r i a l l ya n dw o r ki n p i p e l i n et or e a l i z eal a r g es c h e d u l e rw i t hh i 【g hc a p a c i t ya n dl a r g ep o r tn u m b e r s i na d d i t i o n ，f s s ac a n a c h i e v eg o o dt r a d e o f f b e t w e e np e r f o r m a n c ea n dh a r d w a r ec o m p l e x i t y f s s ad i sp r o p o s e di nt h i sa r t i c l e t h i sf l e wa l g o r i t h mc a l lr e d u c ea v e r a g ed e l a ys i g n i f i c a n t l y 1 1 c o s ti so n l yt h el i t t l ei n c r e s s ei nh a r d w a r e t h ej m p r o v e m e n t so na v e r a g ed e l a ya n dm e a nq u e u el e n o c ha r e a c h i e v e db ya r r a n g i n gt h eb e g i n n i n gc e l lt i m e sd e l i b e r a t e l yi nas c h e d u l i n gc y c l ea n dd i s t r i b u t i n gm u l t i p l e i t e r a t i o n sa m o n gs u c c e s s i v ec e l lt i m e s s i m u l a t i o nr e s u l t ss h o wt h a tt h ea v e r a g ed e l a ya n dm e a nq u e u e l e n g t ha r cr e d u c e ds i g n i f i c a n t l yu n d e rt h eu n i f o r mi r a f f i ca n dn o n - u n i f o f i nt r a f f i cc o m p a r e dt oo t h e r a l g o r i t h m s t h i sd e s i g ni m p l e m e n t sa6 4 x 6 4s c h e d u l e rc o n s i s t i n go f4s u b - s c h e d u l e r sw i t hf o n rc h i p so fx i l i n x v i r t e x 4f p g a s 。a n di tc a nb ee a s i l ye x t e n d e dt ol a r g e ra p p l i c a t i o nw h e nn e c e s s a r y t h ep o s t - s i m u l a t i o n r e s u l t sj n d i c a t et h a tt h ed e s i g nw 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 de a c hs u b - s c h e d u l e r sc a l la c h i e v e 8 0 0 m b p sd a t ar a t et h ei n c r e a s e dh a r d w a r ec o s ti sv e r yl i m i t e dw h i c hc o u l db eo b s e r v e db yc o m p a r i n gt h e p o s tr o u t ea n dp l a c e r e p o r i o f f s s a a n df s s a d i as a t i s f a c t o r y t r a d e o f r b e t w e e n p e r f o r m a n c e a n dc o s t i s a c h i e v e di nt h i sd e s i g n f s s a d ii sp r o p o s e db a s e do nt h et r a d e o f fb e t w e e np e r f o r m a n c ea n dh a r d w a r ec o m p l e x i t y b e s i d e si t i s a d a p t i v ef o rf s s as c h e d u l i n g t h i sn e wa l g o r i t h mi sa l s oq u a l i f i e df o rm o n o l i t h i cc h i ps c h e d u l e t a s k s ，w h i c hd e m o n s t r a t eb o t ht h e o r ya n da p p l i c a t i o nv a l u e k e y w o r d s ：n e t w o r ks w i t c h ，i n p u tq u e u e d ，s c a l a b l e , d i s t r i b u t e di t e r a t i o n , f p g ai m p l e m e n t a t i o n 东南大学学位论文独创性声明 本人声明所里交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 研究生签名： 刍 ：主丝日期：竺兰：兰：兰 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和 纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公 布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生 院办理。 研究生签名： 刍塑l导师签名： 研究生签名：当竹也导师签名： 班 日期：旦望鲨 第一章绪论 第一章绪论 本章介绍了课题背景及意义，并且给出了作者在攻读硕士学位期问的研究工作的主要内容和论 文的结构安捧 1 i 课题背景及意义 计算机技术与通信技术的结合促进了计算机局域网络的飞速发展，从六十年代末a l o h a 的出 现到九十年代中期1 0 0 0 m b p s 交换式以太网的登台亮相，短短的三十年问经过了从单工到双工，从 共享到交换，从低速剑高速。从简单到复杂，从昂贵到普及的飞跃。八十年代中后期，由于通信量 的急剧增加，促使技术的发展，使局域网的性能越来越高，最早的i m b p s 的速率已广泛地被今天的 1 0 0 b a s e - t 和1 0 0 c g a n y l a n 替代，但是，传统的媒体访问方法都局限于使大量的站点共享对一 个公共传输媒体的访问，即c s m a c d 。九十年代初，随着计算机性能的提高及通信量的聚增， 传统局域网已经愈来愈超出了自身的负荷，交换式以太网技术应运而生，大大提高了局域网的性能 与现在基于网桥和路由器的共享媒体的局域网拓扑结构相比，网络交换机能显著的增加带宽。交换 技术的加入，就可以建立地理位簧相对分散的网络，使局域网交换机的每个端口可平行、安全、同 时的互相传输信息，而且使局域网可以高度扩充。 目前，常见的网络交换体系结构主要有三种：输出队列( o q ) 交换，输入队列( i q ) 交换和输入输 出组合( c i o q ) 交换。输出队列交换的优点是能够提供最优的吞吐量和延迟控制，其调度算法在理论 上已得到深入的研究且实现简单。但为了保证输出队列交换的正常运行，交换结构的内部带宽和输 出队列的存储器访问速率必须是输入端口链路速率的n 倍，即要求n 倍的加速比，这里，n 是输入 端口数。输入队列交换仅需要交换结构和内存的运行速度和线路速度相同，这对丁：需要高速线路以 及更多端口的交换设备有很人的吸引力，在高性能的路由器中，输入排队被广泛使用。 i i i 输出队列( o q ) 交换 输出队列交换是指所有缓冲区队列放置于输出端口的交换结构，如图1 i 如示。 图1 i 输出队列交换 由于输出队列方式在输入端口没有缓冲区队列，所有到达的包必须立即送往输出端口。从吞吐 量和时延特性的角度来看，这是有利的。但是所有到达的包同时传送到输出端口需要太多的内部连 接带宽和存储器带宽。对于一个n x n 的交换结构，有可能n 个包同时到达任意一个输出端口。要在 一个时隙里接收n 个包，输出缓冲区队列的存储器必须能在一个时隙里完成n 次写人，传送到存储 器的内部线路速率也必须为包到达速率的n 倍。这样需要一个内部加速比为n 的交换网络。对于高 速路由器，这种结构是不易丁实现的。 东南丈学硕士学位论文 1 1 2 输入队列( i q ) 交换 输入队列交换是指所有缓冲区队列放置于输出端口的交换结构，如图l t 2 指所示。 图1 2 输入队列交换 输入队列交换在同一时隙内晟多只能有一个包到达、一个包离开缓冲区，因而存储器仅需 要工作于2 倍加速比状态。但由于输入排队交换网络不采用内部加速，因此会导致吞吐量降低a 当两个队列首部的包要到同一个输出端口时，就会发生队首位置阻塞( h e a do f l i n e 。h o l ) ， 影响其执行效率。h o l 产生的原因在于输入端口等待交换的分组使垌f i f o ( f i r s ti nf i r s to u t ) 输入摊队策略。即当一个分组移动刭输入队列的队首时，如果目标输出端口正忙，则它将在该 队列中等待，直到目标端口，空闲。当某一个输出端口空闲时，它交换最先处于等待位管的分组a 也就是说，每个时隙到达时，只有在缓冲器队首位置的分组才能参与输出端口的竞争且每个 输出端口最多只能接受一个分组。显而易见，在f i f o 队列中，当队首的分组受阻时，跟在其后 的所有准备发送的分组也都将受阻。即使当前时隙该分组指向的输山端口处于空闲状态也无法 参与交换，分组被挂起在输入端口中而让此时空闻的输出端口处于“饥饿( s t a r v i n g ) 。从理论分 析和计算机模拟研究可知，对于输入缓冲采用f i f o 队列的n x n 交换机，由于h o l 阻塞的影 响，在相同随机流量情况下，交换端口能返到的最大吞吐率被限制在2 一225 8 6 【1 1 。而周 期性的队首位置阻塞则可能导致更差的效果。 为了克服队首位置阻塞的问题，通常不把所有的信元排在一个输入队列里，而是给每个输 入到每个输山都建立一个缓冲队列，称作虚拟输出排队( 、，i m l a lo u t p u tq u e u e s ，v o q ) 。 1 1 3 输入输出组合( c i o q ) 交换 输入输出组合交换是指输入端和输出端都建立缓冲区队列的交换结构，如图1 3 所示。 图1 3 输入输出组合交换 经过精一d r i v e ，对于任何类型到达业务任何规模的交换网络，c 1 0 l q 的如速比为4 时，可以完全相 同地仿效f i f o 输出缓冲队列工作。而且它适用于一大类广泛使用的o q 调度算法，但是目前基于此种 结构提出的调度算法复杂度过高，只具有理论意义。 第一章绪论 1 2 本文主要研究内容和结构安排 本课题的研究背景是国家自然科学基金项目“高性能可扩展网络调度系统”耳前下一代网络不 仅需要更大的容量和更多的端口，而且对交换的延迟、吞吐率和公平性等性能也提出了更高的要求： 一是要能处理更多的端口，二是能实现更高的端口速率三是能支持更高级的服务方式因此，在 调度算法更新的同时，有必要研究发展具有更高性能的网络调度系统。目前，虽然交换机和调度器 都有成功开发的集成电路芯片，但大多都是由国外厂商研制的，其核心技术和知识产权也掌握在国 外开发商的手中，而且受到单个芯片规模、i o 管脚数、功耗等集成电路工艺因素的限制，单片i c 上所能实现的交换容量和调度容量都是有限的( 如通常只能实现3 2 x 3 2 ) ，要想在单片集成电路上实现 更大规模的交换和调度功能( 如2 5 6 x 2 5 6 ) 就十分困难。因此，可扩展调度方式是满足下一代网络交换 所需的多端口、大容量的要求的一种重要参考结构。 本文的主要工作就是在对目前调度算法充分分析的基础上，提出了公平可扩展的分布式迭代算 法( f s s a d i ) ，并在f p g a v i r t e x - 4 器件上成功实现。此新算法极大的提高了网络调度效率，降低 了网络的平均时延，同时硬件开销的增加非常有限。实现了性能与成本的良好折中。 本文的结构安排如下： 第二章介绍了一些基于输入队列的网络调度算法。并对可扩展调度算法与单片调度算法进行了 比较 第三章重点介绍了一种基于公平可扩展调度的分布式迭代算法，并给出了仿真结果。 第四章介绍x i l i n x 开发工具及v i r t e x - 4 系列芯片。 第五章介绍了基于v h t e x - 4f p g a 的f s s a - d i 硬件实现及实现结果分析。 第六章给出了f p g a 的测试验证系统。 第七章对全文进行总结，指出了待进一步要研究的工作及建议。 最后是致谢和作者攻读硕士学位期间发表的论文。 周家自然科学基金项n ( 6 0 4 7 2 0 5 7 ) 3 第二章网络调度算法简介 第二章网络调度算法简介 本章主要对网络调度算法的发展进行了简要的介绍，并对目前主流的网络调度算法进行了分析， 比较和总结 2 1 引言 根据输入队列的状态信息决定哪些输入端口能够通过交换结构传送信元，从而避免交换结构的 访问冲突，此类算法称为输入排队调度算法。网络调度算法从硬件构架角度可以分为单片调度算法 和可扩展调度算法两大类。目前，已经有单片的交换机和调度器的集成电路芯片在产，但是这种单 片的集成电路芯片交换容餐和调度容量都非常有限，通常只能实现3 2 个端口之间的交换或调度，要 想在单片集成电路上实现更大规模的交换和调度功能( 如2 5 6 x 2 5 6 ) 就十分困难。可扩展调度是指通 过将较小规模的调度器级联实现大容量多端口调度的调度方法，主要解决单片调度器规模和输入 输出端口数受限的问题。 国际上针对i o 交换已经提出了诸多有效可行的网络调度算法。评价一个调度算法的优劣，主要 从下几个方面进行： o ) & & ( m a t c h i a ! 口1 ) r e q u e s t ( k j ) ；i，输入螭口t 衄鞋出端口j 发出请求 ，t g r a n tp m * f e r o d l j ) g r a n t o l i f ( n u m _ r e q u e s t j 0 ) ，+ 收到了请求， i 一- o u t p u t _ p o i n t e r ( 1 ) ；产根据r r 规则决定g r a n t ， g r a n t _ r e q u e s t 【k j ) ； ，应答请求i ， * a c c e p tp h a s e * f o r ( a l l1 ) a c c e p t ( 0 l i f ( h u mg r a n t i po ) ，收到了g r a n t - ， j = t n p u t o o i n t e r ( i ) ；，根据r r 规则决定a c c e p t * a c c e p tg r a n t ( k i ) ； ，接受g r a n t 0 1 ， m t c h i i j l l ； 3 2 3f s s a - t d i 算法的仿真 本设计中用s u n 工作站在s o l a r i s 环境下对编写的f s s a - t d i 程序进行了仿真。仿真是在美国 s t a n f o r d 大学开发的仿真平台s i m v 2 3 5 上进行的，它是一个专为a t m 等分组交换开发的基于a n s i c 的模拟器。模拟器中的交换机规模为n x n 且所有通道具有相同的速率。s i m 平台主要包括以下几 个特点： 基于连续时隙：与以往的基于离散事件的仿真方法不同，s i m 主要采取基于连续的时隙的一i ：作 方式。整个所模拟的交换机系统将按照每次调度一个时隙的节奏步进工作，从而实现一段完整调度 周期的性能仿真。尽管这样的工作方式使得s i m 在低流量负载下工作效率并不高，但是却能显著提 高其在高流龋负载下工作效率。 结构模块化：s i m 按照交换机组件功能的不同将其自身结构分成独立的模块包括：调度结构 ( f a r o ，输入队列( h i p l l t o u e u e s ) ，输出队歹d ( o u t p u t q u e u e s ) ，调度算法( s c h e d u l i n g a l g o r i t h m ) ，以及 输入流量( 1 h 掰c ) 等。因此。有助丁实现不同组件的有效组合，以及独立模块的快速更新。 用户可自定义的统计方式：s i m 可以实现多种不同的调度效率衡鬣标准以及参数，用户可以根 据实验情况自由地从中选取所需要的统计方法，并关闭一些额外的特性以加快仿真速度。 文献中常用的几种输入流量模式是均匀流鼍模式( 均匀) 、突发模式( b u r s t ) 、非均匀流虽的对角线 模式( 对角线) 均匀流鼍模式下，每个信元时隙到达各个输入端口的信元数量是均匀分布的，即到达 备个输入端口的机会相等。非均匀流量分布模式下每个信元时隙到达各个输入端口的机会不等。假 设这里定义不均衡因子为，则c o 在均匀流鼍模式下等于零，在非均匀流鼙模式f 按照具体的参数 赋值。令每个输入端口的流量负载为p ，为调度规模，即输入或输出端口数，输入端口f 到输出端 口，的流颦负载p i i 将由公式3 1 给出： 第三章f s s a - d i 可扩展网络调度算法 = 仁蜚3 z 叫) 巧= 枷= p ( 叶x 害 _ p o 2 、， a = 图3 2 均匀流量模式下的8 x 8 流量矩阵 圈3 3 中矩阵b 为非均匀流鼍模式中对角线分布的8 x 8 流量矩阵，图中可以看到处在矩阵对角 线处元素所对应的流量分布明显火于其它输入输出端的流量。 仿真时采用均匀模式、均匀的突发模式( b u a 啪这两种输入流量模式对f s s a - t d i 算法以及其它 几种典型的调度算法进行了仿真，主要研究不同流量模式下各算法的延迟随负载的变化情况，仿真 规模为3 2 x 3 2 的交换，仿真分别对单个调度器和可扩展调度结构进行，其中的可扩展结构用4 个8 x 3 2 子调度器实现，算法的运行时间为20 0 00 0 0 个时隙。模拟时间的长短与仿真规模和流鼍有关，规模 越大或流量越大，仿真时间应越长。在通常情况下，模拟时间设为2 0 0 , 0 0 0 个时隙就能够满足精度 要求。 口= 图3 3 对角线流最模式下的8 x 8 流量矩阵 在仿真结果图中，横坐标代表网络流鼍的规一化负载( n 咖a l i z c dl o a d ) ，纵坐标代表对应的平均 调度延迟( a v e r a g ed e l a y ) ，其单位为信元时隙。 1 7 x z 工x x 茹 x x x x x 工 工工 工工 x x 工石j x 善苫 x 工芹 工善工 工 工 工 工 工工 工x 工x 工 j 工 工工并 工 x 善工x 工 工工x 工 x x 工 工 x ， 工 x 0 o o o o o x h o o o o o 工撕o o o o o x 投o o o o o x h o o o o 0 x h o o o o o 工h o o o o o 工孙o o o o o o h o o o o o o 工 东南大学硕士学位论文 3 2 强一i l o h u 。i 曲rl n h m t 讲c n a l l z e d l o a d 图3 4 均匀模式下的平均时延 图3 4 为输入流量为均匀模式时的仿真结果。其中i s l i p ，l q f ，d s r r 分别表示采h ；l 单个调度 器时这三种算法的仿真结果，f s s ad s r r 和f s s at d i a 则表示采_ i j i 可扩展结构，子调度算法分 别为d s r r 和t d i 的结果。 图3 5 为输入流量为b u r s t y 模式下的仿真结果，由仿真结果可以得出以下结论：在两种流域模 式下，基于可扩展结构的调度器的延迟性能在流鼙低时接近丁一个常龉，该常鼙与采用的子调度器 个数有关，子调度器越多，该值越大。在流鬣高时它们的性能均明显优丁| 单调度器的i s l i p 、d s r r 等算法。同时，同为可扩展结构，本文提出的f s s at d i 算法在i ；| i 流鼙的均匀和b u r s t y 模式下的延 迟都明显低于f s s ad s r r ，使其延迟性能得到了明显改善，在所有情况下l q f 算法的性能最优， 但正如前文所述，其硬件实现复杂，很难实际应用。 3 2 ，- a 女u r , d _ b w n f t o 图3 5 突发模式下的平均时延 3 3 基于最长队列的f s s a p d i 算法 3 3 1f s s a - p d i 算法原理 如3 2 2 节所述。可以通过。卜面两个措施提高交换效率：1 ) 通过增加迭代次数提高输入输出匹 it7； 口& 第三章f s s a - d i 可扩展网络调度算法 配对的数量，2 ) 通过选择权重较大的v o q 提高每次匹配的权重。 与f s s a - t d i 算法相同，由于各子调度器均有一次最高优先级的调度机会，处于最高优先级的 子调度器可以在输入端口和任意一个输出端口之闯进行调度，因此f s s a - p d i 算法仍然在该最高优 先级时隙增加迭代次数来产生匹配数多、匹配权重大的调度结果同样，由于一个子调度器在两次 屉高优先级调度时隙之闯有三个时隙的间隔，而相邻时隙包的缓存情况变化不大，为了不增加整个 系统的延迟时间，可以考虑将迭代提前。 匪嘲 圃豳 麴堕垂习 匪蛔 l 2 8 睦3 16 4 i i7 5 7t 黾譬；l 35 l6 i2 一o 56 3 3 目。l ? i 4 7 艮$ e ”1 ：预选最长队列时隙 ：第5 轮调度域高优先级时隙 图3 6f s s a p d i 时隙分配 考虑到同一个子调度器的两个最高优先级时隙之间存在多个时隙，因此有可能满足l q f 算法对 时问复杂度的苛刻要求。但是l q f 算法对于硬件资源的消耗也很大，若实现时使_ i l j 一套额外运行 l q f 算法的硬件会增加成本增加。本算法中考虑在有限的时间内挑选出输入端口中最长的v o q ( 和 次长的v o q ) ，并把相应的输入输出匹配作为最高优先级时除调度的第一轮迭代结果。这种方式在 提高调度效率的同时，使得硬件开销的增加十分有限。 通过性能与复杂度的综合考虑，本文提出了基于最长队列的分布式迭代算法f s s a p d i ( f s s a b a s e d o n p r e s e l e c t d i s t r i b u t t x i i t e r a t i o n ) 2 ”。该算法的基本思想是对于每个子调度器，在两个展高优先 级时隙之间用简单的查找法挑选出晟跃的v o q ( 和次长v o o ) 并将其作为最高优先级时隙的第一次 迭代结果；在最高优先级时隙再用d s r r 算法进行第二次迭代。这样，在最高优先级时隙。就可以 在保证匹配尺寸的前提下增加匹配的权重。对于其它时隙，均采用一次迭代的d s r r 算法进行调度。 图3 6 说明了f s s ap d i 的工作原理。以子调度器2 为例，它在时隙4 的调度优先级最高，为 了提高该时隙的匹配权重，在时隙l ，2 ，3 先进行晟长队列预选，找出最长的v o q ( 或同时找出次 长的v o q ) ，接着在时隙4 用d s r r 算法进行第4 轮调度的第二次迭代。这样，二次迭代的结果有 望产生权重较大的匹配。 算法的伪码描述如下： 严i u n m l r o f i n p u t s ；j ：n u m b e r o f o n t p u t s * ! * i t e r a t i o np h u l 4 e + | i f ( 1 k f o r ep r i o rh i g h e s tp r i o r i t y ) ，最高优先级时隙之前时隙 f o r ( a l l ia n d j ) t e l e c t m u x ( i , j ) ； ，拽出最长的v o q * m a t c h m u x l l , j l = i ； ，。作为第一次选代结果保留， 1 9 东南大学硕士学位论文 i f ( h i g h e s tp r f o r j l y ) f o r 枷o ，l 誓一岫矗m “i l j 卜l m a t c hi i , j i - l ；l ! 1 r e q u e s tp h a s e | f o “a l ldr e q u e s t ( o f e r ( d l j ) ，最高优先级时骧， ，采用第一轮选代结果， i f ( ( n u m c e l l s l j j 】 o ) & ( m t c h l i j j ! = 1 ) r e q u h l ( i ，1 ) ； * o n t n tp h u e f o r ( a l lj ) g r a n k j ) i f ( a u m _ r e q u e s t u o ) 扛t p u t _ p o i n t e r 0 ) ； g r u tr e q u e s t ( 1 j ) ； ， e p ip h i * f o r ( a n ”t c c e p t ( o i i f ( n u m i g r t n t i l ) l j - h t p u tp o i n t e r ( j ) ； m p i ：0 n n t 【i j ) ； m a t c h t l i l - l ；i ，+ 输入端口i 向输出端i ：1j 发出请求t 严收到了请求， ，根据r r 规则决定g r a n t ， ，应答请求i ， ，收到了g r a n t ， ，根据r r 规则决定a c c e p t * ，接受g r n t 0 ) * 3 3 2f s s a - p d i 算法的仿真 我们在均匀流量模式和非均匀流量下的对角线模式对f s s a p d i 算法以及其它几种典璎的调度 算法进行了平均调度延迟和平均队列长度的仿真，仿真规模为3 2 x 3 2 的交换，仿真分别对单个调度 器和可扩展调度结构进行，其中的可扩展结构埘4 个8 3 2 子调度器实现，算法的运行时间仍为20 0 0 0 0 0 个时隙。 图3 7 和3 8 为输入流鼍为均匀时的延迟和平均队列长度的仿真结果。其中i s l i p ，l q f ，d s r r 分别表示采用单个调度器时这三种算法的仿真结果，f s s ad s r r 则表示采用可扩展结构f s s a ，子 调度算法为d s r r 时的调度结果。f s s a _ p d i 和f s s ad 1 2 则表示采川本节提出的基丁：最长队列的 分布式迭代算法时的调度结果，其中f s s ad i 为选取一个最长v o q 时的结果，f s s ad 1 2 为选取 晟长v o q 和次长v o q 时的结果。 第三章f s s a - d i 可扩展网络调度算法 l l l h 筻曲n - “日b 佣t t t 图3 7 均匀流量下平均时延 a 2 d 2 _ 矾u i d u n g 舶mt i h 0 n o m i 日 图3 8 均匀流量下平均队列长度的仿真结果 可以看出，流量低时，基于f s s a 的调度器延迟性能接近于一个常量，该常量与采用的子调度 器个数有关，子调度器越多，该值越大。流鬣高时，基于可扩展结构的f s s ad i 、f s s a _ d 1 2 及 f s s ad s r r 的延迟性能优于单调度器的i s l i p 和d s r r 算法的性能。而同样都是基于f s s a ， f s s ad i 和f s s ad 1 2 的性能又优于f s s ad s r r 。f s s ad i 和f s s ad 1 2 相比，后者比前者略好。 值得注意的是f s s a - p d i 算法在高流最点时，其网络平均时延只有普通f s s a 的1 孓- 1 2 左右当然， 这几种算法中单调度器的l q f 算法的性能最优，但其硬件实现复杂，很难实际应用。 2 l _0，l 东南大学硕士学位论文 冀斌m a r , hu - d - q 啊- - b h n n m ，嘲 图3 9 对角线模式下的平均时延 对角线模式下的仿真结果如图3 9 和3 1 0 所示，其输入流量可以表示为k = 2 9 3 。v i , k + l = o 3 ， 抽；o ( 其余情况) 。可以看出，采用f s s ad i 及f s s ad 1 2 后，系统不稳定时的负载流量从0 7 2 增加 到0 7 8 ，因此，延迟和平均队列长度性能均比f s s ad s r r 有所提高。 通过上面的分析，可以得出以下结论：在均匀和对角线模式下，流簧高时基于f s s a 的调度算 法的性能明显优于单调度器的i s l i p 、d s r r 算法。同时，与f s s ad s r r 算法相比，f s s ad i 及 f s s a _ d 1 2 算法的性能在流颦高时也明显得到了提高。 ； | 3 各越目硼d u n d e r d a g o l n d i c 图3 1 0 对角线模式下的平均队列长度 3 4 本章小结 本章提出了一种可用于公平可扩展网络交换调度系统的分布式迭代算法。通过对最高优先级时 隙的分布式多次迭代，实现了系统性能的明显提高，取得了性能与复杂度的良好折中。仿真结果表 明，在均匀流簧f ，延时性能和平均队列长度性能均有明显提高，在对角线等其它流鼙模式下性能 亦有一定改善。值得指出的是本文的分布式迭代思想对单调度器也同样适用。 i0oe 第四章f p g a 设计流程与开发工具简介 第四章f p g a 设计流程与开发工具简介 4 1f p g a 设计流程 本课题实现时采用的是x i l i n x v e r t e x - 4 f p g a ，开发环境采用的是x i l i n x 的集成开发环境i s e 8 2 。 在x i l i n xi s e 开发环境下，完整的f p g a 设计流程包括电路设计与输入、功能仿真、综合、综合后 仿真、布局布线、布线后仿真与验证及下载后的在线调试等主要步骤，如图4 1 所示。 厂一，矗f 型堡 图4 1 完整的f p g a 设计流程 ( 1 ) 电路设计与输入 电路设计与输入是指通过某些规范的描述方式，将一翻鼙师电路构思输入给e d a 工具。常用的设 计方法有硬件描述语言( h d l ) 和原理图设计输入方法等。原理幽设计输入法在早期应用得比较广泛， 它根据设计要求，选用器件、绘制原理图、完成输入过程。这种方法的有点是直观、便于理解、元 器件库资源丰富。但是在大型设计中，这种方法的可维护性较差，不利于模块构造与重用。更主要 的缺点就是当所选用芯片升级换代后，所有的原理图都要做相应的改动。目前进行大型工程设计时， 晟常用的设计方法是h d l 设计输入法，其中影响最为广泛的h d l 语言是v h d l 和v e r i l o gh d l 。 他们的共同特点是利朋由顶向下设计，利于模块的划分与复用，可移植性好。通用性好。设计 不因芯片的工艺与结构不同而变化，更利于向a s i c 的移植。波形输入和状态机输入方法是两种常用 的辅助设计输入方法：使_ i j 波形输入时只要绘制出激励波形与输出波形，e d a 软件就能自动地根 东南大学硕士学位论文 据响应关系进行设计；使用状态机输入法时，设计者只需要画出状态转移图，e d a 软件就能生成相 应的h d l 代码或原理图。使用十分方便。x i l i n xi s e 工具包中的s t a t e c a d 就能完成状态机输入的 功能。但是需要指出的是，波形输入和状态机输入方法只能在某些特殊情况下缓解设计者的工作量， 并不适合所有的设计。 ( 2 ) 功能仿真 电路设计完成以后，要用专用的仿真工具对设计进行功能仿真，验证电路功能是否符合设计要 求。功能仿真有时也称为前仿真常用的前仿真工具有m o d e lt e c h 公司的m o d e l s i m ，s y n o p s y s 公 司的v c s c a d e n c e 公司的n c - v e r i l o g 和n c - t h d l 。a l d e c 公司的a c t i c v eh d l 等。通过仿真能及时 发现设计中的错误，加快设计进度。提高设计的可靠性。 ( 3 ) 综合优化 综合优化( s y n t h e s i z e ) 是指将加l 语言、原理图等设计输入翻译成由与，或、非门，r 埘触发 器等基本逻辑单元组成的逻辑连接( 网表) 并根据目标与要求( 约束条件) 优化所生成的逻辑连接， 输出e d f 和e d n 等标准格式的网表文件，供f p g a c p l d 厂家的布局布线器进行实现。常用的专业综 合优化工具有s y n l i p c i t y 公司的s y n l i p f y s r n l i p f y p r o ，a m p l i f y ，s y n o p s y s 公司的f p g a c o m p l i e r i i ，m e n t o r 公司旗+ f 的e x e m p l e rl o g i c 公司的l e o n a r d o s p e c t r u = 等。另外，f p g a 厂商的集成开发 环境也带有一些综合工具，如x i l i n xi s e 中的x s t 等。 “) 综合后仿真 综合完成后需要检查综合结果是否与设计一致，做综合后仿真。在仿真时，把综合生成的标准 延时文件反标忠到综合仿真模型中去，可估计门延时带来的影响。综合后仿真虽然比功能仿真精确 一些，但是只能估计门延时，不能估计线延时，仿真结果与布线后的实际情况还有一定的差距，并 不十分准确。这种仿真的主要目的在于检卉综台器的综合结果是否与设计输入一致。目前主流综合 工具日益成熟，对于一般性的设计，如果设计者确信自己标注明确，没有综合歧义发生，则可省略 该步臻。但是如果在布局布线后仿真时发现有电路结构与设计意图不符的现象，则常常需要同溯到 综合后仿真以确认是否时由于综合歧义造成的问题。 ( 5 ) 布局布线 综合结果的本质是一些由与、或、非门，触发器，r 删等基本逻辑单元组成的逻辑网表，它与 芯片的实际的配置情况还有较大的差