Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uunet!ncrlnk!ncrcae!hubcap!parker
From: parker@vienna3.tmc.edu (Bruce Parker)
Newsgroups: comp.parallel
Subject: Re: IPSC Communications
Summary: mesh emulation on butterfly
Keywords: butterfly mesh emulation
Message-ID: <7161@hubcap.clemson.edu>
Date: 21 Nov 89 19:20:06 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 28
Approved: parallel@hubcap.clemson.edu

In article <7143@hubcap.clemson.edu> argosy!workman@decwrl.dec.com (Will Workman) writes:
>The CM-2 really suffers a performance penalty by not having
>a physical grid interconnect system on applications like
>image and signal processing which are heavily dependent on
>fast nearest neighbor and reduction techniques.
>
>Will Workman, Dir of Fed Mkt, MasPar Computer

Those of you who are less biased towards selling a
particular architecture might consider that these guys may
not have the best mapping of mesh nodes to hypercube nodes.
There does exist a "real-time" (O(1) delay) emulation of a
mesh on a butterfly network ("Work-preserving emulations of
fixed-connection networks", by Koch, Leighton, Maggs, Rao,
and Rosenberg, 1989 STOC, pp. 227-240).  Hypercube emulation
of a butterfly is trivial (simulate each column by a single
node), although the load is now O(lg n).  I haven't read
Koch, et al's construction yet, but it may be possible to
sidestep the butterfly-hypercube emulation and implement the
emulation directly on the hypercube.  All this suggests that
mesh-style communication may be comparable on a hypercube,
albeit with a slight slowdown (perhaps a small constant
times slower).

Bruce Parker
305 Weston Hall					(201) 596-3369
Computer and Information Science Department 	parker@mars.njit.edu
New Jersey Institute of Technology