Okay, so this brings us to the end of interconnection networks. And what I
wanted to talk about was Deadlock. So let's assume that you have three nodes
labeled one, two, and three here. It's on a 1D, or excuse me, yeah, oh 1D tourist,
that is unidirectional. So links only flow in the clockwise direction here. Now, all
of a sudden, you have node one wants to send to node three, node two wants to send
to node one, and node three wants to send to, to two. And we're going to look at a
wormhole routing network. So the wormhole routing network you start to send the
header words and has not, potentially not even been injected into the network at
this point. Let's say they all start at exactly the same time. So one is going to
start sending to three. Two's going to start sending to one. Three's going to
start sending to two. And if you'll notice, is each set of these has one
overlapping link with the previous one. So there's going to be some contention on
that link. So very quickly, you can see that. If we were to all, if we were to
launch these three messages exactly at same time, and the message length was
long. None of them would actually get to the receivers. One would use this link, or
one sending to three would use this link, two sending to one would use this link,
three sending to two would use this wraparound link. But then all of a sudden,
they would try to acquire the next link but it's already been reserved. But they
can't give up the link cuz they've already acquired the link, so all of a sudden you
have a deadlock. So these numbers get pretty tricky. and one way that we go
about trying to see if our routing protocol is deadlock free or actually can
deadlock is we start to do something called Waits-for-analysis or waits-for and
Holds analysis. And waits for, and Waits-for and Holds analysis, the basic
idea is, so this is looking at our example that we saw before where we have three
routers. What's happening here is we're injecting into A and this A is acquiring
this link or this here, and then it needs to acquire the next one. So let's draw
this as a diagram. So A holds TQ2, so A holds TQ2. This one here, this inbound Q
here. And when we draw Waits-for and Hold analysis diagrams. When we are waiting on
something we draw a edge from the thing that is the, the actor to the resource
that we're waiting on, and the holds actually goes in the opposite direction.
So if a holds TQ2 here we actually draw the edge the other direction. all of a
sudden, A is holding TQ2 two, and it's waiting to acquire TQ3, this one here. Cuz
it needs to transit this link to deliver it to TQ3. But at the same time, B has
acquired TQ3, so it's holding that and it's waiting for TQ1. But C currently
holding TQ1 and its waiting on TQ2. This is how we do deadlock analysis from a
proof perspective. We actually write these dependency graphs or Waits-for and Hods
graphs and if you find a cycle in your protocol, your protocol can have a
deadlock. It need a couple of some way to color link your, color, color edge in this
graph or you need to really design your protocol. But this is the sort of
canonical way that you can do this and if you start to look at different routing
protocols some of them could possibly deadlock and some of'em can, you can prove
statically to all possible weights for of whole graphs you can come up with will
never have cycles. So I, I think I mentioned last time, if you look at
dimension order routing with one more routing. All possible inputs and outputs
on that you never actually going to have a deadlock, you never call for cycle in the
graph. And the reason for this is the only ever quire X routers and then Y routers,
will say if you have the dimension that you acquire X and quire Y. But you never
going into have effectively something that is holding Y trying to acquire something
on the X axis. So, you never going to have a, a cycle in that Waits-for and Holds
whole analysis graph. I just briefly wanted to some up here that Deadlock is
actually not an enemy. You can try to use deadlock, to your benefit or, or just live
with deadlock. Just cuz your protocol has deadlock does not mean you can't try to
recover from it. So what I mean by this is deadlock avoidance can be very expensive.
So trying to draw all possible graphs here, you should think about, you know,
where your deadlocks happen in your systems, and plan them out and make sure
they don't happen often. But some of the things you need to do, to try and cut
edges here, might be too restrictive. So for instance, dimensional routing may only
route in the X dimension and then in the Y dimension, could be very expensive
relative to an adaptive routing scheme, or you try to route around congestion in your
network. So this deadlock avoidance, you know, you'll, you'll design the protocol
to never deadlock, this could be quite expensive. So an alternative, and this is
something you should not necessarily be afraid of, but you have to be careful of
this is that you find the deadlock and then you try to recover from it. So what I
mean by this is on-chip network or a, a, multi-chip network you can actually have a
deadlock occur, notice that a deadlock occurred. And either try to roll back the
state and somehow jitter the state so the deadlock won't happen a second time. Or
many times these deadlocks happen because your dependent on one particular buffer in
the system and two people trying to acquire that buffer. So you can try to
virtualize that buffer. Effectively saving the state of that buffer in memory and
adding more, more states. So you, a lot of these protocols, if you were to add more
FIFO entries into the system, it would actually break the deadlock. So, sort of
going back into this picture here, if all of a sudden if I added another, let's say,
FIFO here that the inbound traffic went into and then this other traffic tried to
bypass it, it would actually cut one of these edges, and all of a sudden you would
not be having a deadlock. So you can think about trying to have a deadlock recovery
mechanism that's an example of it. So a good example this is actually in the raw
micro pro cessor from an IT where we I, you can actually have that much on the
on-chip network. Its dimensional routed, but you can still have message depended
deadlocks. So what I mean by that is while the network itself is not going to
deadlock, the traffic flows you have on top of it that from since your memory
coherence protocol on top of that could be potentially deadlock. So how do you
recover from that? Well you can actually have a counter, a timer which goes off
when you determine that the network has not moved for a 1000 cycles. So all the
sudden you're running along and no traffic moves on your network. Well it's a pretty
good indicator that you have a deadlock condition, cuz something should be
flowing. There should be some forward progress guarantees. And if you notice
that, an interrupt will go off. So this timer will go off saying nothing has moved
on my network for 1,000 cycles, this is probably a deadlock. So that, you could
take an interrupt and then software can go look at all this data in the network and
introduce more buffering into the network. So, effectively through software try to
virtualize a particular FIFO entry and that can break the deadlock. So there are
ways to recover from deadlocks. If your network is for instance used for message
passing network, you can just use memory to go do that. So actually on the raw
processor, our memory coherence protocol, we used deadlock avoidance and then our
message passing protocol, our message passing networks use deadlock recovery.
later on in, in Tylera actually we have something depending on which memory
network we have mixtures of these two. And you might say that sounds scary, but if
you walk through the proofs and are very careful about it and you are guaranteed
that you don't need anymore resources to go break the deadlock you may be okay. But
yeah it's, its just some say it's playing with fire. You've got to be a little
careful of these, these sorts of solutions when trying to play with deadlock
recovery. But if you're guaranteed that you're not goi ng to need any more
resources you can just resolve it right then. And oh, so the reason you would want
to, to use the lock recovery is it does not restrict your protocol. And by doing
that, you can have the common case of your protocol be very, very fast. And, you
could make it so that the deadlock almost never happens. Or never, in practical
concerns ever happens. Then, when the deadlock does happen oh, you take a little
bit of performance bump, or a performance hit there. Because you have to virtualize
it in software. But the probability of it happening is so low.