拓扑网络_折叠式Clos拓扑在片上网络中的应用

拓扑网络_折叠式Clos拓扑在片上网络中的应用 摘要:随着半导体与集成电路技术的进步,网络中用于连接芯片的路由设备得到了很大的发展。通过引入新的技术,路由的“度”数得到了增加,即单个路由可连接的芯片数目变得越来越多,这种路由被称为“高度数”路由。该种路由结构可以显著降低网络延迟和开销,必将在以后得到大量应用。本文将浅析使用该种路由的折叠式Clos拓扑结构在片上网络中的应用,比较该拓扑结构与其他拓扑性能的优劣,介绍几种针对自适应路由算法的中间级模块分配策略。 关键词:片上网络;折叠式克劳斯网络;拓扑结构 The Application of The Folded-Clos Topology on Chip GUO Bin, WANG Changshan (School of Computer Xidian University) Abstract: As the advancement of semiconductor technics and integrated circuits, the routing device which is used to connect chips in the network has great development. Through the introduction of new technology, the degree of routing which is named high radix routing has increased and the number of cores connected on one routing has increased. The high-radix routers will be widely used in future, as it can effectively reduce latency and cost of the network. This paper introduces the application of the folded-clos network, which can take advantage of high-radix routers. We compare the performance of the folded-clos network and other topologies and introduce some allocation strategies of mid-stage models, which fit for adaptive routing algorithm in this paper. Key words: NoC; the folded-clos network; topology 1引言 片上网络(NoC)于20世纪末期被提出,作为一种新型的技术,国际国内对它的研究都还处于初级阶段。提出的初衷是为解决片上系统(SoC)在可扩展性、能耗、时钟统一性、重用性以及服务质量等方面的局限性。其核心思想是将计算机网络技术移植到芯片设计中来,用网络结构来取代传统的总线结构,通过使用可控电参数,使得通信与计算分离,从而提供良好的通信与处理能力。片上网络拓扑结构定义了片上网络中的通信节点是如何在芯片中分布和连接的。作为网络非常重要的一个特性,它对整个网络的性能有很重要的影响。 随着集成电路中信号处理速度的加快,出现了高带宽的路由片。对于传统的低度数拓扑结构,并不能充分发挥高度数路由的优势。基于折叠式Clos拓扑结构的网络则可以通过运用该种技术提供比传统网络更低的延迟,获得更高的吞吐。 本文主要介绍了折叠式Clos网络在片上网络中的应用,分析其使用的路由算法,并通过仿真来验证其性能的好坏。 2拓扑结构介绍 Charles Clos 在1953 年提出了后来以他名字命名的Clos拓扑结构。最常见的Clos拓扑网络是3级Clos网络V(m,n,r),如图1所示,它拥有n个输入输出级模块。每个Clos网络都如同是两个蝴蝶网络叠加起来,其中一个的输出级与另一个的输入级叠加。Clos网络中每个交换模块内部结构都是一个crossbar结构,按照crossbar原理模式进行工作。 Clos网络可以通过使用较小的交换单元来构建较大容量的交叉矩阵。由于其任意输入输出对之间都有多种路由可选择,故它的可靠性很好。并且通过交换模块的横向增加,很容易完成对网络的扩充,其可扩展性很好。 Clos网络的路由过程为由输入级输入,经由任意一个中间级交换单元后再从输出级输出。由于Clos网络的级数总为奇数个,我们可以以最中间的那一级为中轴,将Clos网络折叠起来,形成折叠式Clos网络。图2即为图1所示Clos网络所对应形成的折叠式Clos网络。与传统的Clos网络使用单向链路不同,折叠式Clos网络使用双向链路进行通信。与传统的Clos网络不同,该网络的路由过程并不需要通过所有的中间级路由模块来完成。由于折叠式Clos拓扑结构可以充分地发挥高度数路由的优势,它已经被应用于很多网络当中。 3路由算法分析 3.1 路由算法介绍 对于一个片上网络,合适的路由算法可以降低网络延迟,保证网络负载平衡。按照算法是否具有自适应性分类,可以分为无关路由和自适应路由。无关路由又可分为确定性路由和随机路由。无关路由算法不考虑网络流量及拥塞状况,其中确定性路由算法是基于网络拓扑和平均分组时延要求,以某一固定的准则来选择分组的路径;而随机路由是随机决定分组路径。自适应路由基于某个在时间上不固定的准则来选择在某一段时间内有效的路径。 对于Clos网络,数据包在路由过程中必然要经过所有的中间级交换单元。但折叠式Clos网络并不需要,数据包由输入端口进入网络之后所要做的就是找一个合适的“交汇点”。该“交汇点”到输入端口与输出端口都存在可使用的空闲路径。一旦数据包到达该点,即可直接发送往输出端口,而无需经过所有的中间级。 在路由过程中,首先在最低级的中间级模块中查找看是否有链路存在可以完成路由请求。若有则直接建立链接完成通信请求;若没有,则将请求传向高一级中间模块,使用该级中间模块来完成路由请求。 在折叠式Clos网络中,确定性路由算法与自适应路由算法均可使用。确定性路由算法由于其分组路径的选择方式已确定,故实现起来比较简单,但灵活性不高,容易造成拥塞。而自适应路由算法则相对比较复杂,它需要根据当时的网络状况来为每个数据包选择中间级交换单元,但它具有路径多样性,灵活度比较高,可以很好的降低网络拥塞发生的概率。故总体性能来讲,自适应路由算法要优于确定性路由算法。 一般在实现过程中,由输入端路由到“交汇点”时使用自适应算法,由“交汇点”到输出端的过程使用确定性路由算法。 3.2 自适应路由算法的中间模块分配策略 当输入节点与输出节点并没有连接在同一路由模块上时,完成它们间的路由就需要使用中间级的路由模块,这样便涉及到中间级路由模块的分配问题。 以下是几种中间级路由模块分配策略的介绍: (1) 随机分配策略(random):使用随机函数,为每一个连接请求在其可用的中间模块集中随机分配一个中间模块,如果该集合为空则建立失败。 (2) 顺序分配策略(sequential):为每个请求分配模块时从第k个中间模块开始顺序分配,在仿真部分中我们按照从左到右的顺序选择最左边的中间模块为开始模块来进行仿真分析。 (3) 轮循分配策略(round-robin):与顺序分配类似,如果上一次请求占用了第n个中间模块,那么下一个请求就从第n+1个中间模块开始。 (4) 最多空闲端口优先策略:优先分配空闲端口最多的中间模块,如果不成功再分配负载较轻的中间模块。如果几个中间模块的空闲端口数量相同,则排除上次路由请求使用过的模块之后,在剩余的模块中随机选择一个进行路由。 随机分配策略未考虑中间级模块的空闲端口状态,使用随机方法选取模块。由于顺序分配策略均匀地选取中间级模块,它造成的网络延迟要比随机分配策略低。最多空闲端口优先策略则考虑到了中间级模块的网络状态,它的性能要优于以上几种策略,网络延迟最低。 3.3 重排算法介绍 当网络中没有空闲中间模块可以分配给新到的请求时则发生网络阻塞,可以通过对网络中已有的链路进行重排,以释放出可用的中间模块,从而满足新到的请求。 每当有新的路由请求到达时,就将已经建立的请求和新到来的请求进行一次统一的处理,完成全网的输入输出匹配,该种调整方法称为一次统一调整算法。由于该算法每次都要对整个网络进行调整,需要调整的链路数量较多,工作量比较大。 如果对于一个新来的链路请求,先在第一级中间级交换模块中查找有无空闲模块可以完成路径建立,若无则对网络中部分链路进行调整,以完成链路请求。如果调整后仍无法完成路径建立,则对第二级中间模块进行调整来完成链路请求。该种算法被称为逐条调整算法。 使用重排算法虽然可以满足更多的链路请求,降低网络的延迟,但是会引入额外的链路调整开销。如果重排引入的链路调整数量高于降低的链路阻塞数量,反而会使整个网络的性能降低。 4仿真与分析 本文使用OPNET仿真软件来完成对折叠式Clos网络拓扑结构和算法进行了仿真,以此来评估折叠式Clos网络的性能,同时我们使用相同的网络设置来对其他几种常见的拓扑结构进行了仿真比较。 4.1 仿真参数设定 1) 网络拓扑结构规模:各个拓扑结构都采用16节点的模型。节点注入率设定:仿真中注入率使用bitscycle的网络发送一个数据包需要32个cycles。 2) 数据包结构设定:仿真中数据包的长度可以变化,最小值为32bits。其中包的ID号占15bits,包的源节点与目标节点横纵坐标各占4个bits。 3) 结点模型的设定:使用source-sink对来完成包的产生和销毁。开始由source模块生成并发送数据包,结束时到达sink模块,由它来完成数据量的统计,并对各种类型的包进行销毁。 4) 网络规模的设定:仿真所用的所有拓扑结构均采用16个结点的规模,即由这16个结点来发送并接受数据包,期间的路由过程由其他路由结点来完成。 4.2 仿真结果分析 1) 图3是不同注入率下各种拓扑结构的端到端时延与吞吐率的比较。 从图中可以看出,由于折叠式Clos网络丰富的路径多样性,提供了多条可选路径,使得该拓扑结构具有自适应性,向上路由时拥塞情况很少,端到端延迟和吞吐率方面都有很好的表现。在ETE-delay性能图中,折叠式Clos网络一直保持着很低的延迟,直到注入率(offered load)增至0.4时才有了显著的上升。而其他两种拓扑结构则在0.2 - 0.3处延迟即有了明显的增高。在吞吐性能图中,同样直到注入率增至0.4时折叠式Clos网络的吞吐才逐渐保持水平不变,吞吐性能相比其他两种拓扑提高了近30%左右。当到达0.4时,折叠式Clos网络的吞吐量到达其饱和点,随着注入率的增加,性能基本保持不变。 2) 图4是不同注入率下不同中间级模块分配策略的性能比较。 从图中可以看出,由于最多空闲端口优先策略在选取中间级模块过程中考虑到了该模块的实时状态,优先选择空闲端口多的模块,可以明显减少网络拥塞 ,减低网络延迟,因此在时延与吞吐率方面都有良好的表现。 随机策略由于都会使中间级模块负载达到基本均衡,相比于其他几种策略延迟和吞吐都不是很理想。顺序选择策略与轮询策略可以保证每个中间模块被等概率的选到,将网络请求均匀地分布到各个中间模块,其性能要优于随机策略。 5结论 折叠式Clos拓扑结构可以充分发挥高度数路由的优势,可以显著降低网络的延迟与开销。本文分析比较了用于折叠式Clos网络中的路由分配算法。由于自适应路由算法在路由过程中会考虑到当时的网络状态,并根据此做出路由选择,因此相比于确定性路由算法,合适的自适应路由算法可以更好地提高路由网络的性能,降低网络延迟。 对于自适应路由算法,我们提供了几种中间级模块分配策略,介绍了模块重排的思想。选择空闲端口最多的模块来发送这种策略充分考虑到了路由的状态,避免多个请求拥挤到同一路由,从而造成排队等待而增加了路由延迟,它的性能最佳。随机策略与轮循策略无视了网络与路由器的状态,它们的性能较差,但实现起来比较简单。 随着路由的发展,折叠式Clos拓扑结构会被更多的应用。虽然折叠式Clos网络在时延与吞吐率方面表现良好,但由于其结构比较复杂,路由过程中的跳数比较多,从而造成了较高的开销,在芯片上布线时困难比较大。针对折叠式Clos网络的这些缺点,如何改善它们是下一步研究的重点。 参考文献 1 Kim, J., W.J. Dally and D. Abts.Adaptive routing in high-radix Clos network R. x ACM/IEEE Conference on Supercomputing, SC06, November 11,x - November 17,x. x. Tampa, FL, United states: Association for Computing Machinery. 2 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. x. 253-282. 3 H.Kariniemi, J.Nurmi. Arbitration and Routing Schemes for On-chip Packet Networks. Interconnect-Centric Design for Advanced SoC and NoC C. Kluwer Academic Publishers.x.253 - 282. 4 F. H. Chang, J. Y. Guo, F. K.Wang. Wide-sense nonblocking for symmetric or asymmetric 3-stage Clos networks under various routing strategies C. ISSN: 0304 3975. x. 375 - 386. 5 Wenqing Dou, Enyu Yao. On rearrangeable multirate three-stage Clos networks C.x. 103-107. 6 Frank K. Hwang, Sheng Chyang Liaw. On nonblocking multicast three-stage Clos networks C.2000. pp. 535-539. 7 P Jose R. Correa, PMichel X. Gomemans. Improved Bounds on Nonblocking 3-Stage Clos Networks C. x. pp. 870-894. 8 Phi-Hung Pham, Kumar, Y.,Chulwoo Kim. High Performance and Area-Efficient Circuit-Switched Network on Chip Design J, Computer and Information Technology, x. CIT 06. The Sixth IEEE International Conference on Sept. x . Page(s):243 - 243 9 P. Guerrier and A. Greiner. A generic architecture for on-chip packet-switched interconnections R. Design, Automaion and Test in Euiope Conference and Exhibition 2000. March,2000. pp.250-256. 10 P. P. Pande, C. Grecu, A. Ivanov and R. Saleh. Design of a switch for network on chip applications J. May,2003. Vol.4 pp.1 - 5. (下转第89页) 11 Kim, J., et al. Microarchitecture of a high-radix routerR. In 32nd Interntional Symposium on Computer Architecture, ISCA x, June 04,x - June 08,x. x. Madison, WI, United states: Institute of Electrical and Electronics Engineers Inc. 12 Hung Q.Ngo. A new routing algorithm for multirate rearrangeable Clos networks C. ISSN: 0304-3975. 2003.Page: 2157 - 2167. 13 Tomohiro Morimura, Keisuke Iwai, Hideharu Amano. Hierarchical multistage interconnection network R-ClosC. Electronics and Communication in Japan. No.11.x. Part 3, Vol.89. 作者简介 郭彬,硕士研究生,主要研究领域为片上网络拓扑结构。 王长山,副教授,硕士研究生导师,主要研究领域为软件理论与应用和计算机网络。