Backward probing deadlock detection for networks-on-chip

To accurately detect deadlocks in Network-on-Chip (NoC) as early as possible, a novel deadlock detection mechanism called Backward-probing Deadlock Detection (BDD) is proposed in this work, which can detect and resolve all existing deadlocks. It was realized using probe systems that generate probes for deadlock detection. A probe system includes a probe System Manager (SM) for turning on probe system, a probe Generator (GEN) for generating probes, a Link Selection (LS) connected to a Switch Allocation (SA), which is used for copying the generated probes, transmitting probes backward, and discarding probes when the probes find that the traversal path is just a congestion not a deadlock or when probe congestion occurs. There is also a TB Calculation (TBC) in LS for TB settings. Finally, a probe comparator (PB Comparator) is used for claiming deadlocks. Note that each port except the local one in a router has its own probe system.