Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!samsung!uunet!ncrlnk!ncrcae!hubcap!parker
From: parker@vienna3.tmc.edu (Bruce Parker)
Newsgroups: comp.parallel
Subject: Re: IPSC Communications
Summary: mesh vs. hypercube
Keywords: iPSC Parallel
Message-ID: <7159@hubcap.clemson.edu>
Date: 21 Nov 89 19:19:10 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 21
Approved: parallel@hubcap.clemson.edu

In article <7142@hubcap.clemson.edu> pase@orville.nas.nasa.gov (Douglas M. Pase) writes:
>
>A lot of Intel's ideas are based (at least initially) on William Dally's PhD.
>thesis.  Grossly simplified, the idea is that one can trade the wire layout
>complexity of an n-cube arrangement for higher bandwidth connections (more +
>shorter wires) in a grid/torus.  Most important, he shows that such trades
>favor the 2d arrangements.  With a simple argument it is easily shown that
>a grid/torus constructed in that way has lower latency and contention than
>an n-cube, *even for problems which prefer an n-cube*.

How is it possible for a sqrt(n) by sqrt(n) mesh with
O(sqrt(n)) diameter and bisection width to have lower
latency and contention than an n-node hypercube with O(lg n)
diameter and O(n) bisection?  Is the analysis specialized
for certain problems as opposed to examining a worst- or
even average-case?

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