New CMOS processes offer cheaper but less reliable transistors. This trend foreshadows the apparition of processors consisting of hundreds and thousands of cores prone to defects. In this context, the performance of t...
详细信息
ISBN:
(纸本)9781479953936
New CMOS processes offer cheaper but less reliable transistors. This trend foreshadows the apparition of processors consisting of hundreds and thousands of cores prone to defects. In this context, the performance of the core interconnect under faults will be critical. In this work, we propose the combination of a novel adaptiveroutingalgorithm and several related router mechanisms, which firstly ensure message transfers under transient and permanent faults and second adapt to congestion in order to improve the interconnect performances. In effect, the widespread 2D mesh topology offers a high redundancy of routes. Hence, a fault-tolerant congestion-aware routingalgorithm is able to improve substantially the interconnect efficiency under degraded conditions. Besides, the Virtual Channel allocation is optimized for performance, and a message truncation mechanism is added to cope with dynamic permanent and transient faults.
An adaptiveroutingalgorithm is one in which the path a packet takes from its source to its destination may depend on other packets it encounters, Such algorithms potentially avoid network bottlenecks by routing pack...
详细信息
An adaptiveroutingalgorithm is one in which the path a packet takes from its source to its destination may depend on other packets it encounters, Such algorithms potentially avoid network bottlenecks by routing packets around ''hot spots.'' Minimal adaptiveroutingalgorithms have the additional advantage that the path each packet takes is a shortest one. For a large class of minimal adaptiveroutingalgorithms, we present an Omega(n(2)/k(2)) bound on the worst case time to route a static permutation of packets on an n x n mesh or torus with nodes that can hold up to k greater than or equal to 1 packets each, This is the first nontrivial lower bound on adaptiveroutingalgorithms, The argument extends to more general routing problems, such as the h-h routing problem, It also extends to a large class dimension order routingalgorithms, yielding an Omega(n(2)/k) time bound. To complement these lower bounds, we present two upper bounds, One is an O(n(2)/k + n) time dimension order routingalgorithm that matches the lower bound, The other is the first instance of a minimal adaptiveroutingalgorithm that achieves O(n) time with constant sized queues per node, We point out why the latter algorithm is outside the model of our lower bounds. (C) 1996 Academic Press, Inc.
暂无评论