【作者】 谢同飞；

【导师】 韩国栋；

【作者基本信息】 解放军信息工程大学 ， 通信与信息系统， 2011， 硕士

【摘要】 片上网络(Network-on-Chip,NoC)是解决复杂系统芯片通信问题的重要手段,拥塞直接影响NoC的通信性能。但受芯片面积、功耗和硬件资源等因素的限制,计算机网络中相对成熟的拥塞控制策略难以直接应用于NoC领域。当前NoC拥塞控制主要集中在结构改进、路由算法设计和负载管控等方面,但没有将结构和算法研究有机结合起来,在设计路由算法时单方面追求高性能,带来算法复杂度较高、硬件开销较大等问题。本文在深入分析现有NoC拥塞控制方法的基础上,分别从负载均衡和负载管控的角度对拥塞控制技术进行了研究,提出了一种局部互连结构调整和路由算法改进相结合的拥塞控制方法,以及两种基于负载管控的拥塞控制策略。另外,为进一步提升拥塞控制的效果,降低系统缓存需求,设计了一种基于数据流向的动态缓存分配机制。本文的具体研究工作如下:1、提出一种局部互连结构调整和路由算法改进相结合的拥塞控制方法。对NoC网络接口结构进行改进,通过增加多路复用器,使大通信量模块与邻近的多个路由器相连,降低单个路由器发生拥塞的概率。然后,针对调整后的NoC结构,设计了一种基于区域的XY-YX路由算法,根据源节点和目的节点的相对位置,选择对应方位的路由器,采用XY或YX路由算法确定数据传输路径,提高片上负载的均衡性。仿真结果表明该方法可以在硬件开销增加较小的情况下,有效降低数据包的平均传输延时,增大系统吞吐率。2、提出两种基于负载管控的拥塞控制机制。首先,设计了一种端到端Credit-based负载管控方案,以控制每次发送到网络中的数据量;然后,提出一种具有加权比例公平性的数据注入率控制算法,将节点间的通信概率作为加权因子,并引入具有比例公平性的效用函数,将源端数据注入率控制问题转化为目的节点缓存约束下的优化问题,通过拉格朗日乘数法求解最值得到优化的数据注入率。仿真结果表明,所提方法可以有效的控制网络中的负载量和瞬时负载强度。3、提出一种基于数据流向的动态缓存分配机制。该方法根据传输方向,将输入端口接收到的数据分成不同的“组”,发往不同输出端口,并将数据以“组”的形式进行存储。控制逻辑根据各个“组”的数据规模为其动态分配缓存资源,并通过可用缓存容量监测拥塞状态。拥塞控制直接针对具体端口,提高了控制的精确性。仿真结果表明,该方法在同等性能条件下可以有效降低系统的缓存需求。更多还原

【Abstract】 Network-on-Chip (NoC) represents a scalable solution to on-chip communication of complex SoC, but congestion severely affects the overall performance of NoC. Due to the constraints of area, power consumption and hardware resources, those effective congestion control techniques used in computer network are hardly implemented in NoC. At present, the congestion control methods in NoC mainly resort to structure improvement, routing algorithm design and load regulation. However, there is a lack of integrated consideration with network structures alteration and routing algorithms improvement, and researchers are usually absorbed in performance improvement while ignore hardware overhead, which lead to issues of great complexity and high hardware overhead.Based on the analysis of existing congestion control mechanism in NoC, this dissertation presents a method combining alteration of local interconnection and improvement of routing algorithm for load balance, and a mechanism to regulate load. Furthermore, in order to improve congestion control effect and reduce the demands of buffer, a dynamic buffer allocation scheme based on data flow direction is put forward.Main work and contributions of this dissertation are outlined as follows:1. A method combining alteration of local interconnection and improvement of routing algorithm is proposed to alleviate congestion in NoC. By adjusting the structure of network interface, the communication hot-spot could connect to multiple adjacent routers with multiplexer, thus reducing the probability of congestion resulted from excessive traffic. Thereafter, a region-based XY-YX routing algorithm is presented for the adjusted NoC topology. According to the relative position between source node and destination node, this algorithm chooses the router in corresponding orientation, and adopts XY or YX routing algorithm to determine the data transmission path. The simulation results show that this method not only effectively reduces the average packet transmission delay and increases network throughput, but also makes a better trade-off between performance and hardware cost.2. Two methods based on regulation of traffic are presented for congestion control in NoC. The first string applies an end-to-end Credit-based policy to control the amount of data sent to network each time. In addition, an injection rate control algorithm with weighted proportional fairness is proposed, which uses the communication probability between nodes as weighted factor, and introduces a utility function with proportional fairness. Thus, the injection rate control is transformed into constrained optimization under buffer of destination node router, and the optimized injection rate could be gained by Lagrange Multiplier method. The simulation results show that these methods can effectively control network load and instantaneous load strength.3. A novel dynamic buffer allocation scheme based on data flow direction is proposed. In this mechanism, the concept of "group" is put forward and "group" corresponds to one and only output port. The data sent to different output ports are stored in the form of "group", and the control logic dynamic allocates buffer resources according to the data size in various "group". By monitoring the available buffering capacity, congestion control directly target specific port and the accuracy of control improve. The simulation results show that this method can effectively reduces demands of buffer resources as well as gain similar performance.更多还原