模拟三维网状网络的路由使用随机部分最小的路由

M.Z.Kurian博士¹,Ashwini.S.Shivannavar²,Anisha亚伯拉罕³

院长和煤斗、部门建设、SSIT Tumkur,卡纳塔克邦,印度
讲师,部门的建设,SSIT Tumkur,卡纳塔克邦,印度
IVth sem, M。技术(VLSI和嵌入式系统),SSIT Tumkur,卡纳塔克邦,印度

文摘

三维硅基集成技术机会的增加了建筑创新的前景广阔。一个增强的扩张二维网格chip-multiprocessor架构分为三个维度。本文主要侧重于提供一个高效的三维网状网络路由算法。本文的主要条款是一个新的路由算法对三维网状网络称为随机partially-minimal (RPM)路由。RPM已经找到实现最佳吞吐量最糟糕的三维网格此外,RPM的修改,称为随机最小第一(RMF)介绍了路由,它利用固有的网络流量的负载均衡性能前提下进一步减少数据包延迟的吞吐量。

关键字

三维集成电路、片上网络路由算法。

介绍

近年来已经有相当多的讨论的好处三维硅基集成多个设备层的放置互相直接垂直互联上的隧道。三维集成承诺解决的许多关键的挑战,来自半导体行业的持续推进深纳米政权。最近的3 d技术的进步领域的散热和microcooling机制缓解热担心堆叠设备层。许多提出的二维瓦chipmultiprocessor架构依赖于二维网状网络拓扑作为触发通信。扩展基于网格瓷砖chip-multiprocessor架构分为三个维度代表了利用三维集成的自然进程。本文的重点是提供高效的路由等三维网状网络。RPM达到三维网状网络的负载平衡算法最坏的吞吐量包统一所有垂直层水平层和路由最低限度。然而,RPM不是最小的延迟,因为它需要数据包路由到一个随机选择的中间层。在本节中,我们提出一个destination-aware层选择技术,可以减少延迟的RPM时,交通是固有的负载平衡,如均匀随机交通。的随机变异RMF更适合对称的网状网络因为它平衡之间的通道负载同样X, Y, Z频道。 However, randomized RMF requires a separate set of counters for load balancing flits along each of the X, Y, and Z dimensions. As in the case of RPM, randomization is not needed for practical asymmetric topologies where load-balancing along the shorter dimension leads to higher throughput.

RPM路由

为实际不对称网格拓扑结构,设备层(Z维度)的数量预计将少于沿着边缘的一层节点的数目(X和Y维度),沿短Z两阶段路由维度和最小路由沿着长X和Y维导致最高平均情况的吞吐量。另一方面,对于对称三维网状拓扑,随机的RPM版本Z-XY / YX-Z X-YZ / ZY-X, YXZ / ZX-Y工艺路线采用等概率收益率最高的平均情况的吞吐量,因为它平衡通道负载在所有三个维度。随机化不改变RPM的最坏的吞吐量,因为每个人的三个路由算法具有相同的算法最坏的吞吐量。

答:虚拟通道和死锁

虚拟通道(VCs)需要在芯片上的路由器避免循环资源的依赖,像缓冲依赖关系,可能导致死锁。如果转由负载均衡实现只沿一维(假设Z维度),两个虚拟渠道每个物理信道是足以实现deadlock-free路由。一种方法是将输入缓冲区链接沿Z Z的维度分为两VCs-VC-0留给第一期路由和Z的但它还是留给第二阶段路由。沿着X和Y维缓冲区链接也分为两个VCs-VC使用X - Y - 0留给数据包路由,但它还是保留使用X路由数据包。这个风险分配方案确保deadlock-free操作对应的通道依赖图是无环。RPM的随机版本包括负载平衡数据包沿着每个维度有相等的概率和路由最低限度沿着两个维度,可以deadlock-free使用三个风投。这风险分配方案的结果在一个非循环通道依赖图随机RPM。这个路由器体系结构的直接延伸5-port路由器中使用2 - D网状网络,添加两个额外的端口的垂直沟通。在每一个输入端口,缓冲区被组织作为独立的FIFO队列,每个风投一个。掠过进入路由器放置在其中一个队列取决于他们的VC ID。路由器通常管线式分成五个阶段组成路由计算、风险分配,分配切换,切换遍历和链接遍历。 The route computation stage determines the output port of a packet based on its destination. This is followed by VC allocation where packets acquire a virtual channel at the input of the downstream router. A packet that has acquired a VC arbitrates for the switch output port in the switch arbitration stage.

掠过,成功地开关仲裁遍历横梁,最后遍历输出链接到达下游路由器。头掠过通过管道阶段同时进行身体和尾巴掠过跳过路由计算和VC分配阶段,继承输出端口和VC分配给头掠过。尾地释放保留VC离任后上游路由器。为了实现一种新的路由算法如RPM代替现有的路由算法和金龟子一样,只有路由器的路由计算和风险分配阶段管道需要修改。

选择一个中间层

因为RPM涉及到负载平衡数据包随机选择的中间层,需要添加一些额外的逻辑基线架构选择一个中间层。在大多数国有石油公司有严格要求所有掠过包的顺序到达目的地。因此,必须进行负载平衡跨层数据包的粒度,而不是掠过。选择一个随机的逻辑中间层可以实现使用一个简单的线性反馈移位寄存器(LFSR),通常用于生成一个伪随机序列。让我们假设数据包负载平衡均匀沿Z维度。如果kz拓扑结构的层数,与log2kz LFSR位足以生成一个伪随机序列kz层。为了增加LFSR序列为小值的随机性kz,伪随机序列可以生成大于kz比特和中间层可以选择通过执行modulo-kz操作生成的序列。例如,在一个8 x8x4网状拓扑与256个节点,层负载均衡可以使用最后两位8位的伪随机序列。确保不同节点独立工作的随机数生成器的LFSR可以初始化一个节点到独特的8位节点地址。一般来说,对于N个节点的网络,一个为log2N LFSR可以用来选择一个中间层。 Each LFSR can then be initialized to an unique initial state (which is the unique log2N bit node address) resulting in different pseudo-random sequences at different nodes. In the special case when the X and Y coordinates of the destination are same as the corresponding coordinates of the source, the decision of the LFSR is overridden and the intermediate layer is forced to be the Z coordinate of the destination. If the pseudo-random sequence generation process and the packet injection process (determining packet size) are independent, over a period of time the number of flits sent to different layers is expected to be equal. If more accurate load-balancing is desired, a more sophisticated credit-based load balancing scheme can be employed for multi-flit packets. In this technique, every node in the network maintains kz credit counters, one for each layer, all initialized to 0. The first layer with non-negative credits is always chosen to route a packet. When layer l* is selected to route an M flit packet, the credit counter corresponding to is decremented by M- M/kz since layer l* receives an excess of M- M/kz flits compared to ideal flit-level load-balancing across layers. At the same time, counters corresponding to all other layers are incremented by M/kz to account for the flit deficit with respect to ideal flit-level load-balancing. The layer selection approach requires counters at each router to keep track of the credits associated with each layer. The counter size depends on the maximum packet length and the number of layers in the topology. If the maximum packet length is flits, the credit values can range from –L to (kz-1)L. As explained earlier, when the X and Y coordinates of a packet’s destination are same as those of the source, the Z coordinate of the destination is forced to be the intermediate layer in order to remove loops. The counters remain unchanged in this special case as no extra load is added to links along the X and Y dimensions of the destination layer. After an intermediate layer is chosen at the time of packet injection, the intermediate layer number must be included in the packet header to enable the route computation stage to route packets to the appropriate layer. The intermediate layer selection can be carried out one cycle in advance to avoid increasing the critical path delay of the router.

c .选择xy / yx路由

RPM使用最少的XY或YX同等概率路由在每个水平层。的逻辑选择XY或YX路由路径,它使用一个签署的计数器跟踪掠过的过度赤字/使用XY或YX路由。决定使用XY或可以采取YX路由数据包注入之前,在中间层的同时选择,和路由决策可以存储作为一个数据包报头的一部分。这种方法避免了在中间路由器添加额外的延迟。

d .路由和风险分配

在基线路由器使用dimension-ordered路由,路由可以分解为X, Y, Z的维度。路线计算阶段第一路由数据包沿着X维度,其次是Y维度和最后,Z维度。的数据包注入,X +和X -输入路由器的路由计算逻辑需要确定X, Y和Z补偿包的最终目的地,选择第一个生产维度。数据包在Y +和Y -输入,路由决策是基于Y和Z补偿包的最终目的地的数据包和Z +和Z -输入,决定只基于Z抵消。

接下来,我们描述一个可能的路线计算阶段的高级实现不对称三维网状网络,数据包负载平衡只沿着维度。一个数据包注入VC组0或VC组1在港口。数据包的路由决策在不同输入端口和输入风投公司采取如下:在任何数据包VC组端口和VC组0和港口,抵消沿Z维度确定中间层以及X和Y抵消到最终目的地。如果数据包到达目的地,它只是逐出网络。如果Z抵消中间层是零,数据包路由沿Z维度在VC组0。另一方面,如果Z抵消为零和选择使用XY路由数据包,数据包转发到输出端口沿着X维度在VC组0,如果X抵消是非零的。如果X抵消也是零,输出端口的数据包转发沿着Y VC set0维度。另外,如果选择使用YX路由数据包,它是转发到输出端口沿着Y维VC组1,如果Y抵消是非零的。如果Y抵消也是零,输出端口的数据包转发沿着X维度在VC组1。

对于对称网格拓扑,随机的RPM版本需要三套使用VCs。除了选择一个中间层和维度的顺序遍历一层内,随机变异也需要选择一个X, Y或Z维度对负载平衡的数据包。这个决定必须在数据包注入和存储在数据包头部。路线计算在中间路由器可以分为三个平行平面处理,X-YZ / ZY-X Y-XZ / ZX-Y和Z-XY / YX-Z路由、基于数据包的路由选择飞机时注入。VC分配阶段看着输入端口,输入VC组,和输出端口的数据包来确定输出VC。VC组输出等于输入VC集+ 1,如果包YX, ZY或ZX转。否则,输出VC等于输入VC集合。

系统实现

项目的系统实现已经能够开发的编程代码Z-XY-Z和ZYX股票- Z路径在路由器体系结构。在Z-XY-Z路由路径源路由X维度然后沿着Y维度。在后一种情况下的路径路由沿着Y维度然后沿着X维度。我们考虑一个3 X 3层每层9路由器。三层是被认为在当前的例子。每一层是归类为它的列和行数连同其层数分别为了区分每个路由器。第一个数字表示层、第二表示行第三列号。以这种方式传播过程可以很容易地管理。在这里,我们考虑源路由器2-0-2和目的地路由器1-2-1。数据包传输的帮助下选择线的头文件被存储在包被传播。 The packet can be transmitted along either routing paths with ease.

结果及输出波形

在图5中我们可以看到输入数据从路由器初始化2-0-1。因此,路由器被认为是当前网络中源节点的数据传输。

在图6中我们可以看到路由器的输出数据达到1-2-1。因此目标节点的路由器被认为是当前网络的数据传输

结论

这些主题的分析帮助我们理解3 d网格路由的设计方面和其优势在网络中的路由。以上我们分析了各种方式的路由能做什么对芯片的负载平衡的影响。虚拟通道的数量需要各种形式的路由也能帮助我们决定,获得必要的之前的角色。专注与获得知识我们设计的新提议设计架构路由使用随机最小路由技术对3 d芯片附近,帮助我们提供最优最坏的吞吐量。目前,路由器体系结构编程,模拟和输出波形验证Z-XY-Z和Z-YX-Z路由路径。

引用

Vivek Halwan扶桑Ozguner和Atakan多根呈现一个¢路由Wormhole-Switched集群网络和应用程序故障零件¢在IEEE反式。Distrib平行。系统。,vol. 10, no. 10, October 1999.
j . Duato¢新理论Deadlock-free自适应路由的虫洞networksA¢在IEEE反式。Distrib平行。系统。,vol. 22, no. 4, April 2011.
Kun-Chih陈、林Shu-Yen Hui-Shun挂和吴An-Yeu呈现在一个¢Topology-Aware自适应路由不稳定的不规则网格在扼杀了3 d NoC SystemsA¢在IEEE反式。Distrib平行。系统。25卷,没有。2012年2月5日。
Sangsu荣格,Jihoon Sung Yonghwan爆炸Malaz Kserawi, Hyeji金姆和June-Koo凯文Rhee¢贪婪的本地路由自治全球负载均衡策略基于三维潜在基坑¢在IEEE通信信件,14卷,没有。2010年9月9日。
佛罗伦萨Dubois,阿巴斯Sheibanyrad,弗雷德里克·Petrot Maryam Bahmani呈现在一个¢首先:Deadlock-Free分布式路由算法垂直部分连接3 d-nocsa¢在IEEE计算机,15卷,2008年。
j•玩弄和陶尔康赠送¢原则和实践的互连NetworksA¢,36卷,没有。5,1987。
m .【在¢3 d包装技术与3 Gbps 4 gbit堆叠DRAM的数据transferA¢,IEEE Int。电子设备的会议,2006年12月11 - 13日。