[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Deadlock free routing
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).
> 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?
> 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