片上网路自适应路由算法的设计与性能分析

发布时间：2018-03-14 02:53

本文选题：片上网络　切入点：路由算法　出处：《曲阜师范大学》2015年硕士论文　论文类型：学位论文

【摘要】：随着半导体制作工艺技术的高速发展,系统网络的总线结构严重制约着其自身的发展,其网络传输速率无法满足用户的需求。为了解决总线所带来的问题,人们提出了“片上网络”的思想,片上网络的研究越来越引起人们的关注。现阶段片上网络研究的主要方向有拓扑结构、路由算法、流量控制、无死锁、容错与性能分析等方面。本文主要研究的方向是自适应路由算法,自适应路由算法不仅要考虑网络的可通性,还要考虑网络的需求,以便达到网络性能的最优化。分析了片上网络国内外发展的现状以及本课题的意义,同时研究了NoC各类路由算法的工作原理以及它们的优缺点。在此基础上,根据低时延、低功耗、无死锁、无拥塞等网络性能之间的平衡原则,本文提出了两种自适应路由算法,此算法优化网络的性能,满足用户的网络需求。针对2D Mesh结构下XY路由算法易出现路径单一与拥塞的问题,本文提出了一种基于虚拟通道的自适应路由算法。此算法先分析网络通信状态,并根据网络适应度进行选取一条合适的路由路径进行数据传输,同时每个路由节点加入拥塞控制机制,避免网络发生拥塞,进而提高网络传输的吞吐量。与XY路由算法相比,在性能方面本算法在吞吐量、传输时延与功耗等方面有很大的提高。针对2D Mesh结构下的片上网络在传输数据包时,源节点与目标节点之间相距较远时所消耗的时延与功耗会相应升高,并有可能出现路径局部拥塞现象,本文提出的基于Mesh-Tree拓扑结构下的自适应路由算法可以解决此问题。此算法在设计网络拓扑结构方面先将网络结构划分成若干区域,并于此区域上增加了一个上层路由节点,此节点作为数据包在源/目标节点之间传输的中介,从而缩短了网络的时延与功耗,减少网络拥塞现象的产生。本文所提出的两种路由算法都是牺牲网络某方面的性能,从而提高网络其它方面的性能:第一种VARA路由算法的适用范围为2D Mesh结构,提高了吞吐量、时延与功耗等方面的性能;第二种路由算法从拓扑结构为入口,虽然它能够改变网络性能和增加网络路径,但是此路由算法不能很好的拓展,只能适用于特定的路由结构。因此NoC的设计时选取合适路由算法至关重要,这不仅关系着用户的需求,而且还与网络的性能有关。
[Abstract]:With the rapid development of semiconductor manufacturing technology, the system network bus structure seriously restricts its own development, its network transmission rate can not meet the needs of users. People have put forward the idea of "on-chip network", and the research of on-chip network has attracted more and more attention. At present, the main research directions of on-chip network are topology, routing algorithm, flow control, deadlock-free, etc. The main research direction of this paper is adaptive routing algorithm. Adaptive routing algorithm should consider not only the network passability, but also the network requirement. In order to optimize the network performance, this paper analyzes the current situation of on-chip network development at home and abroad and the significance of this topic, and studies the working principle of various routing algorithms of NoC and their advantages and disadvantages. On this basis, according to the low delay, In this paper, two adaptive routing algorithms are proposed to optimize the performance of the network, such as low power, deadlock-free and congestion free network performance. To meet the network requirements of users, an adaptive routing algorithm based on virtual channel is proposed to solve the problem of single path and congestion in XY routing algorithm based on 2D Mesh structure. According to the network fitness, a suitable routing path is selected for data transmission. At the same time, each routing node adds a congestion control mechanism to avoid network congestion and improve the throughput of network transmission. In terms of performance, the algorithm has a great improvement in throughput, transmission delay and power consumption. When the distance between the source node and the target node is far away, the delay and power consumption will increase correspondingly, and the local congestion of the path may occur. The proposed adaptive routing algorithm based on Mesh-Tree topology can solve this problem. In the design of network topology, the network structure is divided into several regions, and an upper routing node is added to this region. This node acts as an intermediary between source and target nodes, which shortens the delay and power consumption of the network and reduces the network congestion. The two routing algorithms proposed in this paper sacrifice the performance of some aspect of the network. So as to improve the performance of other aspects of the network: the first VARA routing algorithm for 2D Mesh structure, improve the throughput, delay and power consumption, and other aspects of the performance of the second routing algorithm from the topology as the entry, Although it can change the network performance and increase the network path, but this routing algorithm can not be extended very well, it can only be applied to specific routing structure. Therefore, it is very important to select the appropriate routing algorithm in the design of NoC. This is not only related to the needs of users, but also related to the performance of the network.
【学位授予单位】：曲阜师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TN47

【参考文献】