负载均衡的NoC路由算法研究

发布时间：2018-04-13 02:25

本文选题：片上网络 + 监测机制　；参考：《合肥工业大学》2017年硕士论文

【摘要】：片上网络(Network on Chip,NoC)相对于基于总线的通信架构实现了高效的并行通信,但随着网络规模的扩大以及应用复杂度的增加,网络的冲突环境会变得复杂,传统的维序路由方式可能会导致网络某些链路长期处于通信繁忙状态,而另一些链路处于饥饿状态,即负载分布不均衡。长时间负载过大的节点可能会成为网络局部热点,引起稳定性问题。另一方面,当某些链路长期被占用有可能导致网络进入局部拥塞模式,数据流不能及时转发,网络延迟过大。针对以上问题,本文研究一种基于监测机制的负载均衡路由算法,在不增加NoC延迟的前提下实现网络全局的负载均衡。本文主要工作如下:(1)设计实现了一种基于监测机制的负载均衡路由算法。针对传统负载均衡路由算法易陷入局部最优陷阱问题,设计网络监测模块,统计各节点在一定时间窗口内的历史通信量,进行路由路径分配,权衡整个网络的状态,为目标流选择一条从源节点到目的节点全局负载较小的路径。该算法可以实现目标流在传输的过程中避开网络中历史负载较大的节点,而选择历史负载较小的节点进行传输,原NoC通信量最大节点的负载降低了 30%左右。(2)设计实现了一种兼顾延迟优化的负载均衡路由算法。面向特定应用,以延迟和负载线性叠加的和作为综合参数,进行路由路径的选择,为目标流选择一条从源节点到目的节点全局负载较小且能降低延迟的传输路径。该算法能在均衡网络负载的基础上,降低数据传输的延迟,提高网络的性能。与原有NoC平台相比,在流长度和包长度为4的情况下对延迟的优化达56%,在包长度为4,流长度为128的情况下延迟优化19%。在网络冲突流数目为2时延迟优化35%,在冲突流数目为10时延迟优化55%。
[Abstract]:Network on chip (Network on Chip, NoC) compared to the bus based communication architectures to achieve efficient parallel communication, but with the expansion of network scale and the increasing application complexity, conflict environment network will become more complex, the traditional way of e-cube routing may lead to network communication link in some long-term busy state, and another link in hungry condition, namely the unbalanced load distribution. Long time high load of nodes may become a network of local hot spots, causing stability problems. On the other hand, when some link long occupied may lead to local congestion in network mode, data flow can not be timely forwarding, network delay is too large to solve the above problems. In this paper, a load balancing routing algorithm based on monitoring mechanism, in order not to increase the NoC delay under the load balancing global network. The main work is as follows: ( 1) the design and implementation of a load balancing routing algorithm based on monitoring mechanism. According to the traditional load balancing routing algorithm is easy to fall into local optimum trap design, network monitoring module, traffic statistics in the history of each node within a certain time window, the routing path allocation, balance state of the entire network, choose a smaller from the source node to the destination node global load path for the target stream. The algorithm can achieve the goal of avoiding the large load flow history of nodes in the network in the transmission process, and node selection history less load transmission, load the original NoC traffic maximum node to reduce by about 30%. (2) the design and implementation of a taking into account the delay load balancing routing algorithm. For specific applications, to delay and load of linear superposition and as integrated parameters, routing path selection, select a target flow From the source node to the destination node load smaller and can reduce the transmission path delay. The algorithm based on network load balancing, reduce the data transmission delay, improve the network performance. Compared with the original NoC platform, the length of the stream and the packet length is 4 under the condition of delay optimization in 56% the packet length is 4, the flow length is 128 under the condition of delay optimization of 19%. in the network conflict flow number as the 35% optimization delay 2, number 10 in the current conflict delay optimization 55%.

【学位授予单位】：合肥工业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN47

【参考文献】