language: en

Planar-Adaptive Routing: Low-cost Adaptive Networks for Multiprocessors

Andrew A. Chien and Jae H. Kim
achien@cs.uiuc.edu kim@cs.uiuc.edu
Department of Computer Science University of Illinois at Urbana-Champaign
1304 W. Springfield Avenue Urbana, IL 61801

Abstract Network throughput can be increased by allowing mul-tipath, 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 deadlock. 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-adaptive networks are guaranteed to be deadlock-free. In the presence of network faults, the planar-adaptive router can be extended with misrouting to produce a working network which remains provably deadlock free and is provably livelock free. In addition, planar adaptive networks can simultaneously support 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 &gt; 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.

Keywords: Multicomputers, Routing Networks, Adaptive Routing, Deadlock Avoidance, Transmission-Order Preservation, Fault Tolerance

1 Introduction