"Douglas@hubcap.UUCP (07/16/87)
pase%oregon-grad.csnet@RELAY.CS.NET (Douglas M. Pase (me)) writes: 000 -> 001 000 -> 010 000 -> 001 -> 011 ... etc -The channel between nodes 0 and 1 is used in four different cases, between 0 -and 2 in two cases, and 0 and 4 in only one case. [...] elroy!wen-king%cit-vlsi.Caltech.Edu@seismo.css.gov (Wen-King Su) writes: - 000 -(0)-> 001 - 000 -(1)-> 010 - 000 -(0)-> 001 -(1)-> 011 - 000 -(2)-> 100 - 000 -(0)-> 001 -(2)-> 101 - 000 -(1)-> 010 -(2)-> 110 - 000 -(0)-> 001 -(1)-> 011 -(2)-> 111 - -On the countrary, I counted that channels 0, 1, and 2 are each used -exactly 4 times, though they are not all channels coming out of node -0. [...] I see your point, but I think it doesn't help. 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 The intent of the previous article was to find a solution to the following problem: Assume every node communicates with every other node with equal probability. Minimum response time will be achieved if all channels (0-11) are used equally. Excess contention will occur if one channel receives heavier usage than the others. This, of course, assumes sufficient message traffic. What then would be a static routing algorithm which would uniformly distribute the messages over the channels? 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. Clearly, a dynamic approach which moves the message nearer to its destination and sellects the channel based on traffic at that time will be the big winner. However, I am looking for a static algorithm which will uniformly distribute messages over the channels. The random algorithms are an interesting possibility I had not thought of, but I'm hoping for a deterministic (not random) approach. (I can get it through enumeration, but that approach is very expensive.) -- Doug Pase -- ...ucbvax!tektronix!ogcvax!pase or pase@Oregon-Grad.csnet
Wen-King@hubcap.UUCP (07/17/87)
[* 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 | +--------------------------------------------------------------------------+