%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename  = "chienk95.ltx",
%%%     date      = "20 November 1995",
%%%     time      = "21:41:30 EST",
%%%     author    = "David M. Jones",
%%%     email     = "jacm@theory.lcs.mit.edu",
%%%     url       = "http://theory.lcs.mit.edu/~jacm/",
%%%     address   = "Journal of the ACM
%%%                  MIT Laboratory for Computer Science
%%%                  Room NE43-316
%%%                  545 Technology Square
%%%                  Cambridge, MA 02139
%%%                  USA",
%%%     telephone = "(617) 253-5936",
%%%     FAX       = "(617) 253-3480",
%%%     checksum  = "49423 132 677 5674",
%%%     codetable = "ISO/ASCII",
%%%     supported = "yes",
%%%     docstring = "Copyright (c) 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.
%%%                  
%%%                  This is a LaTeX2e file.  To process it, you will
%%%                  need a copy of the acmabs document class, which is
%%%                  available via the following URL:
%%%
%%%                  http://theory.lcs.mit.edu/~jacm/acmart/acmabs.cls
%%%                  ",
%%%  }
%%% ====================================================================

\documentclass{acmabs}

\begin{document}

\Journal{Journal of the ACM}

\refkey{ChienK95}

\title{Planar-Adaptive Routing: Low-Cost Adaptive Networks for Multiprocessors}

\author{Andrew~A. Chien \and Jae~H. Kim}

\Pages{91--123}

\Month{January}

\Year{1995}

\Volume{42}

\Number{1}

\maketitle

\begin{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 \emph{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. \par 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. \par
  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. \par 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
  \emph{$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. 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.

\end{abstract}

\begin{categories}

B.4.3; C.2.1

\end{categories}

\begin{terms}

Algorithms, Performance, Reliability

\end{terms}

\begin{keywords}

Adaptive routing, fault tolerance, interconnection networks, multicomputers,
  packet routing, parallel processing, transmission-order preservation

\end{keywords}

\end{document}
