%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename  = "kochlmrrs1997.ltx",
%%%     date      = "28 March 1997",
%%%     time      = "15:15:53 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  = "28206 128 579 4964",
%%%     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{KochLMRRS1997}

\title{Work-Preserving Emulations of Fixed-Connection Networks}

\author{Richard~R. Koch \and F.~T. Leighton \and Bruce~M. Maggs \and
  Satish~B. Rao \and Arnold~L. Rosenberg \and Eric~J. Schwabe}

\Pages{104--147}

\Month{January}

\Year{1997}

\Volume{44}

\Number{1}

\maketitle

\begin{abstract}

In this paper, we study the problem of emulating $T_G$ steps of an
  $N_G$-node guest network, $G$, on an $N_G$-node host
  network,~$H$. We call an emulation \emph{work-preserving} if the
  time required by the host,~$T_H$, is $O(T_G N_G/N_H)$, because then
  both the guest and host networks perform the same total work (i.e.,
  processor-time product), $\Theta(T_G N_G)$, to within a constant
  factor. We say that an emulation occurs in \emph{real-time} if $T_H
  = O(T_G)$, because then the host emulates the guest with constant
  slowdown.  In addition to describing several work-preserving and
  real-time emulations, we also provide a general model in which lower
  bounds can be proved. Some of the more interesting and diverse
  consequences of this work include: \begin{enumerate} \item a proof
  that a linear array can emulate a (much larger) butterfly in a
  work-preserving fashion, but that a butterfly cannot emulate an
  expander (of any size) in a work-preserving fashion, \item a proof
  that a butterfly can emulate a shuffle-exchange network in a
  real-time work-preserving fashion, and vice versa, \item a proof
  that a butterfly can emulate a mesh (or an array of higher, but
  fixed, dimension) in a real-time work-preserving fashion, even
  though any $O(1)$-to-1 embedding of an $N$-node mesh in an $N$-node
  butterfly has dilation $\Omega(\log N)$, and \item simple
  $O(N^2/\log^2 N)$-area and $O(N^{3/2}/\log^{3/2} N)$-volume layouts
  for the $N$-node shuffle-exchange network. \end{enumerate}

\end{abstract}

\begin{categories}

C.1.2 [\textbf{Processor Architectures}]: Multiple Data Stream
  Architectures (Multiprocessors)---\emph{parallel processors};
C.2.1 [\textbf{Computer-Communication Networks}]: Network Architecture
  and Design---\emph{network topology};
F.1.1 [\textbf{Computation by Abstract Devices}]: Models of
  Computation---\emph{networks of machines};
F.2.2 [\textbf{Analysis of Algorithms and Problem Complexity}]:
  Nonnumerical Algorithms and Problems---\emph{computations on
  discrete structures};
G.2.1 [\textbf{Discrete Mathematics}]:
  Combinatorics---\emph{combinatorial algorithms};
G.2.2 [\textbf{Discrete Mathematics}]: Graph Theory---\emph{graph
  algorithms}

\end{categories}

\begin{terms}

Algorithms, Design, Theory

\end{terms}

\begin{keywords}

Graph embeddings, network emulations, parallel architectures, processors arrays

\end{keywords}

\end{document}
