Journal of the Association for Computing Machinery, Vol. 42, No. 1, January 1995, pp. 91–123.

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

ANDREW A. CHIEN

AND

JAE H. KIM

Abstract. 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 deadlock. Previous deadlock avoidance schemes in k-ary n-cubes require an exponential number of virtual channels [Linder and Harden, 1991]. We describe a family of deadlock-free routing algorithms called planar-adaptive routing algorithms, that require only a constant number of virtual channels independent of networks 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 > 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.

Simulation studies show that planar-adaptive routers can increase the robustness of network throughput for nonuniform communication patterns. Planar-adaptive routers outperform deterministic routers with equal hardware resources. Further, adding virtual lanes to planar-adaptive routers increases this advantage. Comparisons with fully adaptive routers show that planar-adaptive routers, limited adaptive routers, can give superior performance. These results indicate the best way to allocate router resources to combine adaptivity and virtual lanes.

Planar-adaptive routers are a special case of limited adaptivity routers. We define a class of adaptive routers with f degrees of routing freedom. This class, termed f-flat adaptive routers, allows a direct cost-performance tradeoff between implementation cost (speed and silicon area) and routing freedom (channel utilization). For a network of a particular dimension, the cost of adaptivity grows linearly with the routing freedom.

Copyright 1995 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.

However, the rate of growth is a much larger constant for high-dimensional networks. All of the properties proven for planar-adaptive routers such as deadlock and livelock freedom, also apply to f-flat adaptive routers.

Categories and Subject Descriptors. B.4.3; C.2.1

General Terms. Algorithms, Performance, Reliability

Additional Key words and Phrases. Adaptive routing, fault tolerance, interconnection networks, multicomputers, packet routing, parallel processing, transmission-order preservation