%%% ====================================================================
%%%  @LaTeX-file{
%%%     filename  = "bhattchlors96.ltx",
%%%     date      = "7 June 1996",
%%%     time      = "13:44:10 EDT",
%%%     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  = "08026 147 756 6193",
%%%     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{BhattCHLORS96}

\title{Optimal Emulations by Butterfly-Like Networks}

\author{Sandeep~N. Bhatt \and Fan R.~K. Chung \and Jia-Wei Hong \and
F.~Thomson Leighton \and Bojana Obreni{\'c} \and Arnold~L. Rosenberg
\and Eric~J.  Schwabe}

\Pages{293--330}

\Month{March}

\Year{1996}

\Volume{43}

\Number{2}

\maketitle

\begin{abstract}

The power of butterfly-like networks as multicomputer interconnection
networks is studied, by considering how efficiently the butterfly can
\emph{emulate} other networks. Emulations are studied formally via
graph embeddings, so the topic here becomes: How efficiently can one
embed the graph underlying a given interconnection network in the
graph underlying the butterfly network?  Within this framework, the
\emph{slowdown} incurred by an emulation is measured by the sum of the
\emph{dilation} and the \emph{congestion} of the corresponding
embedding (respectively, the maximum amount that the embedding
stretches an edge of the guest graph, and the maximum traffic across
any edge of the host graph); the \emph{efficiency of resource
utilization} in an emulation is measured by the \emph{expansion} of
the corresponding embedding (the ratio of the sizes of the host to
guest graph). \par Three main results expose a number of optimal
emulations by butterfly networks. Call a family of graphs
\emph{balanced} if complete binary trees can be embedded in the family
with simultaneous dilation, congestion, and expansion $O(1)$.
\begin{enumerate} \item The family of butterfly graphs is balanced.
\item \begin{enumerate} \item Any graph $\mathcal{G}$ from a family of
maxdegree-$d$ graphs having a recursive separator of size $S(x)$ can
be embedded in any balanced graph family with simultaneous dilation
$O(\log (d \sum_i S(2^{-i}|\mathcal{G}|)))$ and expansion $O(1)$.
\item Any dilation-$D$ embedding of a maxdegree-$d$ graph in a
butterfly graph can be converted to an embedding having simultaneous
dilation $O(D)$ and congestion $O(dD)$.  \end{enumerate} \item Any
embedding of a planar graph $\mathcal{G}$ in a butterfly graph must
have dilation $\Omega \left( \frac{\log
\Sigma(\mathcal{G})}{\Phi(\mathcal{G})} \right)$, where:
$\Sigma(\mathcal{G})$ is the size of the smallest (1/3,
2/3)-node-separator of $\mathcal{G}$, and $\Phi(\mathcal{G})$ is the
size of $\mathcal{G}$'s largest interior face. \end{enumerate}
Applications of these results include: \begin{enumerate} \item The
$n$-node X-tree network can be emulated by the butterfly network with
slowdown $O(\log \log n)$ and expansion $O(1)$; no embedding has
dilation smaller than $\Omega(\log \log n)$, independent of expansion.
\item Every embedding of the $n \times n$ mesh in the butterfly graph
has dilation $\Omega(\log n)$; any expansion-$O(1)$ embedding in the
butterfly graph achieves dilation $O(\log n)$. \end{enumerate} These
applications provide the first examples of networks that can be
embedded more efficiently in hypercubes than in butterflies. \par We
also show that analogues of these results hold for networks that are
structurally related to the butterfly network. The upper bounds hold
for the hypercube and the de~Bruijn networks, possibly with altered
constants. The lower bounds hold---at least in weakened form---for the
de~Bruijn network.

\end{abstract}

\begin{categories}

C.1.2 [\textbf{Processor Architectures}]: Multiple Data Stream
Architectures (Multiprocessors)---\emph{interconnection
architectures}; 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}

Embeddings, emulations, mapping algorithms, mapping problems, parallel
  architectures, processor arrays

\end{keywords}

\end{document}
