Path: utzoo!attcan!uunet!lll-winken!lll-tis!helios.ee.lbl.gov!pasteur!ames!ncar!gatech!hubcap!bjornl
From: bjornl@tds.kth.se (Bj|rn Lisper)
Newsgroups: comp.parallel
Subject: Re: Hmm!
Message-ID: <3406@hubcap.UUCP>
Date: 1 Nov 88 17:58:23 GMT
Sender: fpst@hubcap.UUCP
Lines: 34
Approved: parallel@hubcap.clemson.edu

In article <3386@hubcap.UUCP> wen-king@cit-vax.Caltech.Edu (King Su) writes:
%In article <3363@hubcap.UUCP> vrdxhq!ogccse.ogc.edu!pase@uunet.UU.NET
%(Douglas M. Pase) writes:
%>Another nice thing about hypercubes is that a large number of useful
%>topologies
%<such as grids, tori, and cubes, are all easily embedded within them.  Another
%>slick feature is that a number of applications, such as FFTs, matrix ops, and
%<sorts (ie. bittonic (sp?)) map directly to a hypercube, and thus all links
%>are used with high efficiency (multihop messages need not occur).

%I do not understand how you equate the lack of multi-hop messages with high
%efficiency.  When you map a 16x16 mesh onto an 8-D cube, you cannot possibly
%get more than 50% channel utilization because 4 of the 8 channels in each
%node are idle -- expansive hardwares that you paid for but can't use.

Efficiency is not necessarily measured in channel utilization. It may
as well be measured in, say, speedup towards sequential execution. If there
are critical communication paths in the algorithm that are unnecessarily
delayed by poor process placement resulting in several hops, well, then
*this* efficiency measure is affected.

%Even if you can make use of all of the channels by mapping cube graph to cube
%machine, the node memory bus will not be able to spew out data fast enough to
%keep all of the channels busy all the time.  Even in the original iPSC/1, the
%memory bus becomes saturated when more than 3 or 4 of the channel chips are
%doing DMA at the same time (in a 7-D iPSC, there are 14 channels, I+O).
%Today's hardware routers are about 20-30 times faster than iPSC/1's channel.

Whoa! You are assuming that all hypercubes are loosely connected,
asynchronous multiprocessor systems of the Intel (or Cosmic Cube) type. This
is not true. Consider, for instance, the Connection Machine. "Hypercube" is
really just a name of a certain interconnection topology with no further
assumptions about the character of the communication.

Bjorn Lisper