片上网络的高效拥塞感知及协同拥塞控制方法研究

How to control congestion is the key problem in the design of network on chip. Currently, there are mainly two kinds of congestion control methods: adaptive routing algorithm and throttling flow control method. Although these two kinds of methods are both dynamically congestion-aware, it is difficult for them to attain three aims simultaneously for congestion information awareness of network on chip: high resolution，global view and scalability. Therefore for adaptive routing algorithms they can only avoid the hotspot router with low probability so that end-to-end delay is difficult to be degraded. And for throttling flow control methods they are prone to over-throttling or under-throttling so that system performance is difficult to be promoted. . In this project, highly efficient congestion-awareness strategy will be proposed based on the stationary and visibility characters of flow communication region of network on chip. By our congestion-awareness strategy, this project will also analyze the impact of router hotspot position on the performance of adaptive routing algorithms and throttling flow control methods, and propose improved adaptive routing algorithms and throttling flow control methods. Finally, the problem of no effective collaboration between these two kinds of congestion control methods will be also solved by quantifying the congestion conditions adaptive to them respectively, and then presenting one collaborative congestion control strategy. Therefore excellent congestion control result and system performance will be promoted for whole network on chip that end-to-end delay can be reduced efficiently with high throughput.

网络拥塞是片上网络设计需要解决的一个关键问题。对网络拥塞进行控制的方法主要有两类：适应性路由算法与限流方法。已有的适应性路由算法所采用的拥塞感知策略效率较低，难以兼顾拥塞信息的高清晰度、全局性与可扩展性，能够成功避让路由器热点的概率较小，使得端到端延时较大；已有的限流方法在拥塞感知时同样难以兼顾拥塞信息的高清晰度、全局性与可扩展性，使得精确的限流比例难以被设定，出现因限流不足或限流过度导致的系统性能下降问题。. 本课题拟利用片上网络中流(flow)传输范围固定且可见等特征，研究片上网络的高效拥塞感知策略；在此基础上，分析路由器热点位置对适应性路由算法和限流方法性能影响的规律，研究更高性能的适应性路由算法和限流方法；此外，针对这两类拥塞控制方法间未能有效协同的问题，将量化其各自适用的网络场景，研究其协同拥塞控制策略，在保持高吞吐量的情况下有效降低端到端延时，提升系统性能。

随着片上网络中节点数目的不断增加，错误节点或拥塞节点等特殊节点在片上网络中出现的可能性也在不断地增加。如何高效感知这些特殊节点，以及标记出网络中的这些特殊节点及其之间的位置分布关系成为了片上网络设计中的重要问题。如果有一种能够高效解决该问题的方法，那么可以应用于片上网络的多种应用场景中，比如容错、拥塞控制、可靠性等。重要的研究内容及其结果有：.1，针对高效拥塞感知问题，提出了RSD(Rectangle defined by Source node and Destination node )的概念。对相互进行通信的源节点和目标节点来说，在采用曼哈顿路径的前提下，其在进行拥塞感知时，只需感知RSD范围内的拥塞节点即可，从而大幅度降低了感知的开销以及延时，提升了感知的效率。.2，在RSD概念的基础上，提出了一种路径计数理论，能够高效地标记出网络中的所有特殊节点及其之间的位置分布关系，其标注的复杂度与网络规模成线性关系。.3，针对容错路由问题，提出了基于路径计数方法的部分适应性的容错路由方法, 其可以避让开大部分的网络拥塞节点。理论分析和网络仿真的结果表明，应用本方法，可以将已有的部分适应性容错路由方法的性能从O(n^2)降低为O(n),n为网络规模。此外，本方法还支持任意分布和任意数目的错误节点，支持路径的存在性判断功能等。.4，针对网络拥塞场景，提出了一种基于路径计数的精确限流算法：已有的源限流方法要么将网络当做黑盒处理，难以精确确定网络拥塞位置；要么只能根据经验值来设定限流系数，导致网络限流的效果并不是很理想。本课题提出的基于路径计数的精确限流方法，可以精确量化限流对象，并精确计算限流系数，与以往的经验方式确定限流系数的限流方法相比，可以大幅度提升网络吞吐量，降低网络延时，比如在在随机模式下精确限流算法的平均延时比Self-tuned、INC算法、不限流算法分别好23.3%、34.6%、46.6%；.5，针对QoS可靠性场景，提出了一种基于路径计数的分离路径计算方法。在mesh拓扑结构下，与已有的分离路径方法相比，在同样能够找到分离路径的情况下，本方法可以将算法复杂度从O(n^2)降低为O(n),n为网络规模。. 研究过程中产生的一些成果还应用到了其它一些领域如地铁网络的调度等的问题解决中。总的说来，本课题的研究取得了较多的重要成果，具有较好的学术价值。