Dynamic pseudo-receiving: A deadlock-free mechanism for fault-tolerant routing of Networks-on-Chip

Turn model provides a simple approach for the development of deadlock-free routing algorithms by prohibiting some turns to eliminate cycles of the resource dependency graph. However, prohibited turns remarkably limit the fault-tolerant capability of routing algorithms. This paper presents a dynamic pseudo-receiving mechanism (DPR) to enable the prohibited turns and avoid deadlock. It consists of pseudo-receiving (PR) mechanism and dynamic turn management (DTM). The former is similar as the software-based rerouting, but without the support of operating system. Under PR, an additional buffer (noted as PR buffer) is needed for each enabled turn prohibited originally. The packets using enabled turns will be sent to the PR buffer and then sent to the desired output port. The later is a dynamic implementation of turn model. Under DTM, if the number of flits in a PR buffer is more than the constant ß, the turn will be disabled at once. This paper gives a theorem to show that the combination of PR mechanism and DTM makes networks to be deadlock-free in the cost of a few PR buffers. Simulation results show that DPR mechanism is feasible and cost-efficient.