Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site redwood.UUCP
Path: utzoo!utcs!lsuc!pesnta!amd!fortune!redwood!rpw3
From: rpw3@redwood.UUCP (Rob Warnock)
Newsgroups: net.arch
Subject: Re: Cube designs vs. x,y,z bus
Message-ID: <171@redwood.UUCP>
Date: Sat, 23-Feb-85 07:18:11 EST
Article-I.D.: redwood.171
Posted: Sat Feb 23 07:18:11 1985
Date-Received: Sun, 24-Feb-85 10:22:07 EST
References: <48@pbear.UUCP> <268@oliveb.UUCP>
Organization: [Consultant], Foster City, CA
Lines: 67

Jerry Aguirre <oliveb!jerry> writes:
+---------------
| At some point the number of processors on a x,y,z bus is going to
| exceed its capacity.  The limit on the number of processors is inherent
| in the design spec of the bus.  With the hyper-cube the number of
| connections grows with the log-2 of the number of processors.  So 1,000
| processors require 10 connections per processor and 1,000,000(1M)
| require 20.  A x,y,z design for 1M processors would have 100 processors
| sharing each bus.
+---------------

Good points, but...

1. 100 processors per bus is NOT an outrageous number, especially if
   (as you suggest later) several processor share a silicon substrate.
   Standard Ethernet allows 100 taps per cable segment, and 1000 nodes
   per logical cable (set by the backoff algorithm).

2. You may object to "1." on the basis of throughput: All 100 processors
   have to share the bus. On the other hand, each processor of a 1M hyper-cube
   with point-to-point connections has to handle 20 TIMES the throughput of one
   of the links!  An x,y,z system may have to handle 3 times the bandwidth of
   a bus, peak, but hardware address filtering will lower this.  Assume packets
   addressed at random, in a 1M x,y,z bus system a processor has to handle
   "bus * 3 / 100", or 3% of one bus.

So pick whatever speed of point-to-point link you really CAN handle 20 of,
and a similar bus system could simply use a bus 300 times the speed of one
pt-to-pt link. This may also sound "outrageous", but start with the processing
capacity and work outwards. Assuming each processor can handle a megabit/sec
of communications in addition to its "real work" (a figure that is quite
high with current protocols), the pt-pt links of a 1M hyper-cube might
be 50 kilobits/sec, and the busses of an x,y,z bus system might be some
33 megabits/sec each. Neither figure is unreasonable, depending on various
engineering tradeoffs.

The bus arrangement will give lower latency, due to the queueing advantage
of single-queue/multi-server (the bus) over multi-queue/multi-server (the
pt-pt links). The pt-pt links can be sped up to improve latency (assuming
the packet rate doesn't change), but you risk causing "data-lates" or
"overruns" if many of the 20 links happen to contain a packet at once. In
an x,y,z bus system, the maximum peak memory load from I/O is 3 times the
bus rate. Assuming equal memory bandwidths, hyper-cube pt-pt links could
only use 3/20 the bus rate (or 5 Mbit/sec in the above example), which is
not enough to overcome the queueing disadvantage.

Incidently, while I prefer busses for the interconnections, an x,y,z hookup of
the form you mention may not be the best way to exploit the connectivity of a
bus.  Consider a hybrid form which groups processors into smaller "hyper-points"
on a bus (say 10 to 1000 of them) and then interconnectes hyper-points into
"hyper-hyper-cubes" (with "fat" corners) by using one additional bus connection
on each processor of a hyper-point. Each hyper-point thus acts like one
processor of a hyper-cube as far as communications goes, but each processor
of the hyper-point only talks to two busses: the intra-point bus and one of
the inter-point (edge) busses. (Giving each processor a third bus connection
would allow hyper-hyper-hyper-cubes.) The path length would be one hop longer
than for a hyper-cube (due to the intra-point bus), but far fewer I/O ports
would be required per processor, thus lessening the strain on the memory
(and processing) bandwidth.


Rob Warnock
Systems Architecture Consultant

UUCP:	{ihnp4,ucbvax!dual}!fortune!redwood!rpw3
DDD:	(415)572-2607
USPS:	510 Trinidad Lane, Foster City, CA  94404