Adaptive stochastic routing in fault-tolerant on-chip networks

Due to shrinking transistor geometries, on-chip circuits are becoming vulnerable to errors, but at the same time on-chip networks are required to provide reliable services over unreliable physical interconnects. A connection oriented stochastic routing (COSR) algorithm has been used on one NoC platform that provides excellent fault-tolerance and dynamic reconfiguration capability. A probability model has been built to analyze the COSR algorithm. According to the model, the performance may be improved by implementing a self learning mechanism in each router. Thus a new adaptive stochastic routing (ASR) algorithm is proposed whereby each router learns the network status from acknowledgement flits and stores the outcomes in a routing table. Simulation of both algorithms reveals that the ASR algorithm shows a higher path reservation success rate and a larger maximal accepted traffic than the COSR algorithm. The simulations also show that the learning procedures are accurate and that both algorithms are fault-tolerant to intermittent/permanent errors.