Path: utzoo!attcan!uunet!lll-winken!lll-tis!ames!mailrus!uflorida!gatech!hubcap!andy
From: andy@cayuga.stanford.edu (Andy Freeman)
Newsgroups: comp.parallel
Subject: Re: communication delays (was analysis of parallel algorithms)
Message-ID: <3882@hubcap.UUCP>
Date: 14 Dec 88 13:54:24 GMT
Sender: fpst@hubcap.UUCP
Lines: 30
Approved: parallel@hubcap.clemson.edu


In article <3781@hubcap.UUCP> jones%HERKY.CS.UIOWA.EDU@VM1.NODAK.EDU (Douglas Jones) writes:
>I have long suspected that there is a natural law that communication
delays >in a system with n components are O(log n).  As a proposed
natural law, this >is subject to counterexample and refinement, but
cannot be proven.

[Jones' law is based on fixed fan-out.]

If one assumes that device size is a constant independent of the total
number of devices and that the speed of light really is a limit on
communications speed, one can prove that communication latency must be
Omega(cube-root(n)).  (Omega is the lower bound, Big-O is the upper
bound.)

If one also assumes standard thermodynamics and that the power-
used/device/unit-time is a constant, the latency grows to
Omega(square-root(n)) because an arbitrarily large cube of heaters
can't be cooled (or powered, for that matter, but heat removal is
harder).  Of course, if the power-used/device/unit-time decreases as a
function of n (which might be the case for CMOS), this bound doesn't
apply.

There was an article in Scientific American some time ago on
arbitrarily low-power computers.  Unfortunately, they're arbitrarily
slow as well.

-andy
UUCP:  {arpa gateways, decwrl, uunet, rutgers}!polya.stanford.edu!andy
ARPA:  andy@polya.stanford.edu
(415) 329-1718/723-3088 home/cubicle