Re: Deadlock free routing

[jsunter <J.Sunter@xxxxxxxxxxxxxxxxxxxx>]

Hei pa dei!

Hor stor det til?

Xyvind Teig wrote:
> 
> In order to guarantee deadlock-free routing:
> 
> Q1. What is the relationship between how many buffers we need
>     and the blocking characteristics of application-code?
If you do it right, you implement the routing in such a way that it
doesn't change the synchronization behaviour of the application. I.e.
the routing code neither adds nor removes deadlocks from the
application code. In that case the amount of buffering is independent
of the characteristics of the application code.
> 
> Specifically (same questions elaborated):
> 

> Q2. Can we have deadlock-free routing and blocking communication
>     at application level? (Assuming that application level
>     doesn't deadlock).
Yes, I did that for the code generator of my PhD work, based on
the TRANSNET processes of Peter W. This inserted routing processes
in a program that was written without concern for processors, allowing
it to run on a network of transputers. It was guaranteed not to
introduce
deadlock when the routing processes were inserted. It was also
guaranteed
to deadlock if the application would without them. It is basically the
same thing that the virtual links of the T9000 do in hardware. VCR also
does the same sort of thing, but then with more overhead.

> Q3. VCR under occam is deadlock free. Occam is blocking on communication.
>     Does VCR depend on a certain amount of buffering to achieve
>     the deadlock free properties?
Well, if you want to implement the routing in Occam, you'll have to
include a single buffer (Basically since you cannot do an output ALT).
This assuming that you don't want the change the application code to
the fact that you are now using (or inserting) routing code.
If you manage to do the output ALT sort of thing in assembler, you can
implement the deadlock free routing without buffering.

> Q3. We have a system here that is written in C altogether.
>     Packets are routed, but it is the assumption that sufficient
>     buffers exist that guarantees deadlock free routing.
>     Could this unbounded buffer solution have been swapped
>     with a bounded buffer (or zero buffer) - and blocking communication
>     at application level, and still guaranteed deadlock freedom?
yes, Yes, YES! Another nasty problem with 'sufficient' buffering is that
delays (and bandwidth) tend to get severely limited. By the way, I
(actually Herman Roebbers did) developed an earlier implementation
of routing software that made the same assumption about sufficient
buffering. This quickly led to the development of the aforementioned
synchronous deadlock-free router when it was tested with a real-world
application. The reason was of course that whenever the network traf-
fic got a little bit high, the application would deadlock.

> Q4. Are there any more questions I should have asked?

Now, but simply introducing buffering in an existing application
may be dangerous to your health.


Johan

-- 
Dr. Ir. J.P.E. Sunter      Tel. +31-40-2755288
Origin TASS B.V.	   Fax. +31-40-2755419
Building HCZ-1
P.O. Box 218		   E-mail:
5600 MD Eindhoven	   J.Sunter@xxxxxxxxxxxxxxxxxxxx