Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!ncrlnk!ncrcae!hubcap!paulv
From: paulv@piring.cwi.nl (Paul Vitanyi)
Newsgroups: comp.parallel
Subject: Re: scalability of n-cubes, meshes (was: IPSC Communications)
Keywords: iPSC Parallel hypercubes meshes torus scalability
Message-ID: <7226@hubcap.clemson.edu>
Date: 28 Nov 89 21:39:57 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 24
Approved: parallel@hubcap.clemson.edu

In article <7178@hubcap.clemson.edu> wilson@carcoar.Stanford.EDU (Paul Wilson) writes:
>My admittedly naive intuitions would say that only meshes are truly
>scalable, since you have to pack things into real (<= 3D) space.
>Hypercubes end up needing long wires to project a higher-dimensional
>graph into 2- or 3-space.  As processor speeds increase (and the
>speed of light presumably doesn't) these end up being slower
>than other links and destroy the scalability of n-cubes.
>
>It would *seem* to me that a 3D mesh is the only way to go
>because that's the highest dimensionality you can embed into
>a 3D reality.  You get constant time per hop, no problem.
<<<stuff deleted>>>
>Any comments?  I'm also curious about the pros and cons of
>CM-style combinations of mesh and n-cube routing systems.

This type of questions is addressed in my paper
P. Vitanyi, Locality, communication,
and interconnect length in multicomputers, SIAM J. on Computing,
17(1988), pp. 659-672.

E.g., it shows that while networks of small diameter
like trees necessarily have *some* long wires,
symmetric networks with small diameter like n-cubes, CCC,
necessarily have *average* long wires. 


Brought to you by Super Global Mega Corp .com