Planar-Adaptive Routing: Low-cost Adaptive Networks for Multiprocessors
A.A. Chien, Jae Hwan Kim · 2005
Network throughput can be increased by allowing multipath, adaptive routing. Adaptive routing allows more freedom in the paths taken by messages spreading load over physical channels more evenly. The flexibility of adaptive routing introduces new possibilities of dead- lock. Previous deadlock avoidance schemes in k-ary n-cubes require an exponential number of virtual channels [17]. We describe a family of deadlock-free routing algorithms, called planar-adaptive routing algorithms which require only a constant number of virtual channels, independent of network size and dimension. Planar adaptive routing algorithms reduce the complexity of deadlock prevention by reducing the number of choices at each routing step. In the fault-free case, planar-adagtive networks are guaranteed to be deadlock free. In the presence of network faults, the planar adaptive router can be extended with misrouting to pro- duce a working network which remains provably dead lock free and is provably livelock free, In addition, planar adaptive networks can simultaneously sup ort both in-order and adaptive, out-of-order packet delivery. Planar-adaptive routing is of practical significance. It provides the simplest known support for deadlock-free adaptive routing in k-ary n-cubes of more than two dimensions (with k > 2). Restricting adaptivity reduces the hardware complexity, improving router speed or allowing additional performance-enhancing network features. The structure of planar-adaptive routers is amenable to efficient implementation.