🚀 go-pugleaf

In article <293@hubcap.UUCP> ravi@CS.UCLA.EDU writes:
>In article <291@hubcap.UUCP> wen-king@VLSI.CALTECH.EDU (Wen-King Su) writes:
>>In article <285@hubcap.UUCP> ravi@CS.UCLA.EDU writes:
<><>The obvious solution to this problem is to randomly choose the direction
>> <in which the message should be routed, ...
>>
<>If you do this, you may have problems with deadlock due to lack of queue
>>space along the path of the message.
<
>However when one chooses a direction toward the destination I 
<see no reason why it should deadlock.

I will give an example showing a case of deadlock under one situation
for one routing algorithm.  Consider a 4 node cycle in a message
passing multi-computer.

 0 - 1	1) Each node wants to send a message to the node on its diagonal
 |   |	   and they all happen to choose the clockwise path.
 2 - 3	2) At the same time, each node is filled up completely with
	   messages going toward its diagonal (presumably originated
	   from nodes outside of the 4-cycle), all of which choose to
	   go in the clockwise direction.

We now have a deadlock because no message will move in this cycle even
though each message wants to move in a direction toward it destination.

You may say, well we can do this or do we can that etc, but the burden
of proof is on you, however, to formulate a routing algorithm and to
show that it is deadlock free.  If you claim that any algorithm would
be deadlock free on one particular machine, it is also your burden to
show that too. (We are scientists arn't we? :-)  I am not trying to say
that there are no other deadlock free routing algorithms for a binary
n-cube (infact, there are several well known ones), I am only trying to
say that routing is not a trivial issue.  One needs to give the issue
of deadlock some thought when formulating a routing algorithm.  In your
case, the obvious question to ask would be "will the message system
still be deadlock free after changes in the channel assignment algorithm
are made.  If no, how may the rest of the mesage system be modified so
to make it deadlock free."

The problem of deadlock in a message passing network is a well studied
topic, I can post a list of references if there is enough interest.
The availability of a simple deadlock free algorithm is very often the
main guiding force in the design of a machine.  Here in Caltech, we
have designed or participated in the design of several boolean n-cubes
because at the time it is the only topology for which there is a simple
deadlock free algorithm.  We later switched to torus when former grad
student (now PhD) Bill Dally devised a simple routing mechanism for
torus using virtual channels.  I (still a lowly grad student) have
since shown that a rather obvious way of routing messages on a mesh is
also deadlock free.  Our group is now designing meshes.

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