PLANAR-ADAPTIVE ROUTING - LOW-COST ADAPTIVE NETWORKS FOR MULTIPROCESSORS

Network throughput can be increased by allowing multipath, adaptive ro uting. Adaptive routing allows more freedom in the paths taken by mess ages, spreading load over physical channels more evenly. The flexibili ty of adaptive routing introduces new possibilities of deadlock. Previ ous deadlock avoidance schemes in k-ary n-cubes require an exponential number of virtual channels [Linder and Harden, 1991]. We describe a f amily of deadlock-free routing algorithms, called planar-adaptive rout ing algorithms, that require only a constant number of virtual channel s, independent of networks size and dimension. Planar-adaptive routing algorithms reduce the complexity of deadlock prevention by reducing t he number of choices at each routing step. In the fault-free case, pla nar-adaptive networks are guaranteed to be deadlock-free. In the prese nce of network faults, the planar-adaptive router can be extended with misrouting to produce a working network which remains provably deadlo ck free and is provably livelock free. In addition, planar-adaptive ne tworks can simultaneously support both in-order and adaptive, out-of-o rder packet delivery. Planar-adaptive routing is of practical signific ance. It provides the simplest known support for deadlock-free adaptiv e routing in k-ary n-cubes of more than two dimensions (with k > 2). R estricting adaptivity reduces the hardware complexity, improving route r speed or allowing additional performance-enhancing network features. The structure of planar-adaptive routers is amenable to efficient imp lementation. Simulation studies show that planar-adaptive routers can increase the robustness of network throughput for nonuniform communica tion patterns. Planar-adaptive routers outperform. deterministic route rs with equal hardware resources. Further, adding virtual lanes to pla nar-adaptive routers increases this advantage. Comparisons with fully adaptive routers show that planar-adaptive routers, limited adaptive r outers, can give superior performance. These results indicate the best way to allocate router resources to combine adaptivity and virtual la nes. Planar-adaptive routers are a special case of limited adaptivity routers. We define a class of adaptive routers with f degrees of routi ng freedom. This class, termed f-flat adaptive routers, allows a direc t cost-performance tradeoff between implementation cost (speed and sil icon area) and routing freedom (channel utilization). For a network of a particular dimension, the cost of adaptivity grows linearly with th e routing freedom. However, the rate of growth is a much larger consta nt for high-dimensional networks. Ah of the properties proven for plan ar-adaptive routers, such as deadlock and livelock freedom, also apply to f-flat adaptive routers.