🚀 go-pugleaf

[* If you have been getting duplicates of this posting, it is the fault of
   our system.  Our system maintainer is looking into it.  It is no reason,
   however, for interrupting normal and healthy exchange of information.   **]

In article<310@hubcap.UUCP> ogcvax!pase@seismo.css.gov (Douglas M. Pase) writes:
>                                          110-------------10---------------111
<                                          /|                               /|
>                                         / |                              / |
<                                        1  |                             2  |
>                                       /   |                            /   |
<                                      /    7                           /    6
>                                    010---------------9--------------011    |
<000 -(8)-> 001                       |     |                          |     |
>000 -(4)-> 010                       |     |                          |     |
<000 -(8)-> 001 -(5)-> 011            |     |                          |     |
>000 -(0)-> 100                       4     |                          5     |
<000 -(8)-> 001 -(3)-> 101            |    100-------------11----------|----101
>000 -(4)-> 010 -(9)-> 110            |    /                           |    /
<000 -(8)-> 001 -(5)-> 011 -(2)-> 111 |   /                            |   /
>                                     |  0                             |  3
<                                     | /                              | /
>                                     |/                               |/
<                                    000---------------8--------------001
<Again, assuming uniform message traffic, the previously posted algorithm will
>place the most messages on channels 8, 9, 10 and 11.  The message traffic will
<be twice that of channels 4, 5, 6, and 7, and four times that of channels 0,
>1, 2, and 3.

I can see why you would say that edge #8 is be used four times as
often as edge #0.  (I use edge instead of channel to refer to the
above pictuer because channel is used to refer to the output ports seen
by each node). There are indeed four instance of edge #8 and one
instance of edge #0 in the list of routing paths.  However, there are
four nodes feeding into edge #0 (in the direction of 000->100) as
opposed to just one feeding into edge #8 (in the direction of 000->001).

Let me try to give it another shot.  Assuming we have random but
uniform message flow from all nodes to all other node.  Lets call the
xor of the node numbers of the source and the destination node of each
message the routing tag of the message.  If the n-th bit of the tag is
set, the message has to cross the n-th channel of some node somewhere
on the cube.  Since every node communicates with every other node with
equal probability, every bit in a routing tag of a messages has the
same probability of being 1 (slightly larger than 50% chance, actually
(2**(N-1))/((2**N)-1) ).  That means, the total amounts of messages
crossing the n-th channels, for any valid values of n, in the cube are
the same.  By symetry, one node's n-th channel is no different from any
other node's n-th channel.  Therefore, given the prescribed assumption
on message flow, channels in the cube are used equally.  QED.

+--------------------------------------------------------------------------+
| Wen-King Su  wen-king@vlsi.caltech.edu  Caltech Corp of Cosmic Engineers |
+--------------------------------------------------------------------------+