In order to avoid deadlocks, prevention-based routing algorithms impose certain routing restrictions which lead to high hardware complexity or low adaptability. If deadlock occurrences are extremely rare, recovery-based routing algorithms become more attractive on hardware complexity and routing adaptability. A simple architecture that each router is provided with an additional special flit buffer was developed to achieving deadlock recovery in the literature. Disha_SEQ and Disha_CON are two deadlock recovery schemes based on such architecture to accomplish sequential recovery and concurrent recovery, respectively. In this paper, we propose a simple recovery scheme for a 2-dimensioal mesh with the same router architecture and reduce drawbacks in Disha_SEQ or Disha_CON such as hardwired token, finding the Hamiltonian cycle, Hamiltonian-path labeling for each node, and non-minimal path routing. Moreover, the simulation result shows that the proposed scheme has similar performance as Disha_CON and is better than Disha_SEQ.
Citation:
Shih-Chang Wang, Hung-Yau Lin, Sy-Yen Kuo, Yennun Huang, "A Simple and Efficient Deadlock Recovery Scheme for Wormhole Routed 2-Dimensional Meshes," prdc, pp.210, Sixth Pacific Rim International Symposium on Dependable Computing (PRDC'99), 1999