ABSTRACT
This chapter focuses on deadlock prevention and avoidance by restricting routing adaptivity while still maintaining fault tolerance capability. Virtual channels and virtual networks are commonly used to achieve deadlock-free, adaptive, and/or fault-tolerant routing. The chapter explores how the freedom from deadlock is ensured using network partition. Adaptive routing without constraints is subject to deadlock. Therefore, the objective is to increase the degree of adaptivity without causing deadlock. The number of faulty components plays an important role in designing a fault-tolerant routing algorithm. Usually, it is relatively easy to design a routing algorithm that can tolerate a limited number of faults. Cycle in the extended channel dependence graph may or may not correspond to a deadlock situation. In many routing algorithms, routing adaptivity is traded for a small number of virtual channels. Such algorithms belong to partially adaptive routing. A routing algorithm is optimally adaptive if any further flexibility in communication will result in deadlock.
