Wen-King@hubcap.UUCP (07/16/87)
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 | +--------------------------------------------------------------------------+
bradley@M.CS.UIUC.EDU (07/22/87)
I wouldn't mind seeing that list of references if it wouldn't be too much trouble. Sounds interesting. David Bradley bradley@a.cs.uiuc.edu Department of Computer Science University of Illinois at Urbana-Champaign
ravi@cs.ucla.edu (07/28/87)
In article <328@hubcap.UUCP> bradley@M.CS.UIUC.EDU writes: >I wouldn't mind seeing that list of references if it wouldn't be too much >trouble. Sounds interesting. > >David Bradley > >bradley@a.cs.uiuc.edu >Department of Computer Science >University of Illinois at Urbana-Champaign Some references that I can contribute : The problem of deadlock in routing messages in a network is part of the more general problem - Flow Control The objectives of flow control in a network are: 1) Prevent throughput & response degradation due to network overload 2) Avoid deadlock 3) Allocate resources fairly to competing users Store & Forward deadlocks have been studied in great detail in computer n/w's. One commonly accepted solution to the problem of indirect store & forward deadlocks (the situation described in one of the previous messages) is by the use of "structured buffer pools". Some review papers where one can find numerous references to the actual work are "Flow Control : A Comparitive Survey" Mario Gerla & Leonard Kleinrock IEEE Trans. on Computer Communications, April 1980. "Prevention of Deadlocks in Packet-Switched Data Transport Systems" Klaus D. Gunther IEEE Trans. on Comp. Comm, April 1981. {This entire issue is devoted to congestion control} A recent paper which discusses deadlocks when "wormhole" routing (similar to Kleinrock's "virtual cut through") is used is "Deadlock-Free Message Routing in Multiprocessor Interconnection Networks" W. J. Dally & Charles L. Seitz IEEE Trans. on Computers, May 1987. ravi ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ T. M. Ravi UCLA Computer Science Department, 3680 Boelter Hall, UCLA Los Angeles, CA 90024 Phone: (213) 825-2266 ARPA : ravi@CS.UCLA.EDU UUCP : {...sdcrdcf, ihnp4, trwspp, ucbvax}!ucla-cs!ravi ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~