Re: Deadlock free routing

[Denis A Nicole <D.A.Nicole@xxxxxxxxxxxxxxx>]

On 26 Jun 1997, Øyvind 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?

None.  The application code can exchange short messages to establish
availability of buffers at the receiving application and only then
transmit the actual message data.

The number of buffers you need _in_the_network_ depends on:

1. The details of the network routing algorithm, for example hypercube
routing needs no buffers; some algorithms won't work with less than an
infinite amount of buffering. This in turn depends on the network
topology.  Sensible non-adaptive routers typically need about as many
buffers as the diameter of the network, which is typically around log(P)
for P nodes.

2. How fast you want it all to go, as buffers take up the slack in the
message hardware.  Typically, you want about three times as many buffers
as are _required_ for deadlock freedom. 

> 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.

> 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?

Yes, but not because of occam.

> 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.

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

Yes. Deadlock freedom is not what you want.  You usually need throughput
as well.  There are several deadlock free algorithms which only ensure
that a single packet in the _entire_network_ can move at any given time. 


Denis A Nicole                      WWW:   http://www.hpcc.ecs.soton.ac.uk/~dan 
High Performance Computing Centre   Email: dan@xxxxxxxxxxxxxxx                  
University of Southampton           Phone: +44 1703 592703                      
UK.                                 Fax:   +44 1703 593903