Okay. So now, let's briefly touch on routing protocols. There's lots of
different routing protocols, protocols out there. And roughly let's, let's split them
into two different categories. Oblivious routing protocols where the routing path
through the network is independent of the state of the network. And the second one
is adaptive routing. So these are sort of smarter networks. They look for they
somehow look at the state of the network, and make some decisions. And if you build
a good adaptive routing network, what you're going to try and do is look for the
hot spots in the routing network, and route around them. And this is where that
path independence, or multi path networks comm, commit. If you only have one route
from any point to any other given point, the routing is basically deterministic.
You can't, can't go route in the wrong, you can't go route someplace else because
you'll never be able to get to your destination. Where this becomes
interesting is if you, if you look at just the basic mesh network. Our basic mesh
network has made it from points between, or many different routes between any two
points. So, if we have let's say bre, four by four grid you can just sort of go
across the top and then along the side, let's say if you're going from the top to
the bottom or you can sort of zigzag along the middle or go the other way. Go Y and
then X, or X and then Y, just lots of different choices along, along there. So
that's where we start to get to decide about different routing networks. under
oblivious newtorks, there's, there's two sort of sub points here. One is
deterministic which basically says, do the same thing all the time, versus a
non-deterministic design. And, you might say, what is, what is a non-deterministic
oblivious routing algorithm? Well, it's typically a randomized routing algorithm.
And these can actually do slightly better than the deterministic oblivious routing
algorithms. So let's take an example of this non-deterministic, but still doesn't
look at the state of the network. So, let's, an example of this is something
where you, let's say, choose some node in the system at random and you route there
first. And then, once you've routed there, you route X and then Y to the destination.
I would say, why would you want to do this? Well, it's actually sort of scatters
your traffic around the network and actually route in different directions and
potentially could increase the delivered aggregate bandwidth through your network
by doing this randomized choice at the beginning where you choose some other
node. Which might be routing a wrong, the wrong direction first, but then you'll
have more aggregate balance, let's say to a destination. So, you can actually have
non-deterministic oblivious routing. Adaptive routing, I'm going to sort of not
talk about in this class because there's a, it's a very active research area and I
recommend you take 588 if you want to learn more about that because that's,
that's a very broad topic where you try to look for congestions network and route
around the congestion. And if you try to do that, you have to make sure you're
network doesn't deadlock or have other bad conditions that happen. And to some extend
usually these networks trade off let's say ease of analysis at least for performance.
I wanted to talk about one quick deterministic oblivious routing algorithm
on a mesh. So let's, let's draw a mesh here. Okay. So, we have our sixteen node,
four array, two cube here. And we wan to route let's say from A to B. The most
basic, or one of the more basic routing algorithms that we're going to be looking
at here we're going to call dimension ordered routing. , And it's called
dimension ordered routing because there's actually two dimensions here. We'll label
this as let's say X increasing, we'll label this as Y increasing. And, and
dimension order routing says that we order the dimensions in which we route. So, we
always route it in one of the dimensions before we go to route in the other
dimension. So, if we want to get from here to here, and let's say we hav e X then Y
is our routing, we're going to route this way, from A to B first. So, now we've
matched our X location to where B is, and then we're going to route down. So, this
is X and Y. This is oblivious. It doesn't matter about the traffic. And it has some
bad problems that show up if you do this. If we have let's say C and D, and it's
trying to route from C to D, it needs to share this link with traffic going from A
to B. And it can't route around it. It can't like, I don't use those links or
something else. It's just not allowed in our oblivious routing algorithm, and
definitely not allowed in our dimension ordered. Now, dimension ordered, there's
networks that are, let's say, X and then Y and you can also have, let's say, Y and
then X. You can, this also generalizes to three dimensional n-dimensional sort of
spaces. You do, let's say X, then Y, then Z. Or W, then X, then Y and then Z or
something like that in a four dimensional cube. But one of the good properties of
dimension order routing is it's not going to deadlock. And we'll talk about that in
a few slides. But the network itself is never going to deadlock. That doesn't mean
you can't get message dependent deadlock. But if you wormhole through the network
here, you can actually come up with a proof that shows that you will not ever
deadlock this network. And the, the rough sketch of the proof look goes like this.
By only using X links first and then using Y links, you only ever acquire an X link,
and then acquire a Y link, and then release an X link, and then release a Y
link. So, you'll never actually grab a resource that you have needed, you have
needed before. And everyone else is doing that same algorithm so they will never try
to grab a resource in order that is, is, is faulty also. So, if we go back to our
sort of dining philosophers problem here, you're guaranteed that you're going to
acquire resource one and then acquire resource two. And everyone's doing that
same algorithm so they will always acquire resource one or block, waiting to acquir e
resource one and then you acquire resource two. But you'll never see a cycle. So,
because of that, you'll next acquire X, and then Y, and then X in this dimension
order of routing. So, you'll never get a cycle in your dependency graph. That's the
rough sketch. And the, the, the full sketch is a little more complicated.
Usually, you have these two dimensional mesh networks without end around, or
without a taurus. You have to sort of prove it in this direction and in that
direction. And then, sort of it, decomposes into sort of X from west to
east, and X from east to west, and vice versa. But, that's the rough sketch of the
proof. But, I just want to get across that. It's a basic routing algorithm, but
there's lots of other choices here. as I sort of said there was this
non-deterministic one, there's adaptive routing algorithms. So, a good adaptive
one, sometimes called hot potato routing, is that if you, you don't have any
buffering in the network, so you can't buffer along the way. If you get to a node
which has a link which is congested, you just choose randomly some other direction,
and you route that direction. And the, the thinking here is that some point you will
actually be able to choose again and route towards the right direction and slowly
you'll move your, your traffic or your packet will move to the end point. But, it
allows you to sort of go around traffic congestion points. But, I don't want to go
into too much detail on this because this is a whole lecture in itself. Okay. So,
let's talk about flow control. This is a aspect of networking that I really enjoy,
actually. So, flow control is making sure that you don't drop data. Making sure that
you have back pressure in your networks so that you don't lose, lose data in your
network. And, this flow control can either be local on a link by link or hop by hop
basis, or it could be round trip. So a good example of round-trip flow control is
going back to something like TCP/IP. You actually want to rate-limit the round-trip
flow control so you don't fl ood the network if a given link is, is too small.
So there's actually a protocol in there which will rate-limit the round-trip flow
control. Or a good example, actually, on a on-chip network, so something like a
mini-core, is if you're trying to guarantee that you do not overrun a buffer
in the memory controller. But lots of different nodes are trying to route to the
memory controller. You can actually have some sort of counter, which effectively is
a round trip flow control to the far away end point node and say, okay, you are
allowed to have five outstanding memory transactions to the memory controller. But
if you try to send a sixth, you need to wait for the app to come back. So, this is
a end to end or long distance flow control, but each of the hops along
network themselves may have localized full control also. So, you can actually layer
these two things together. And typically, sort of, for on chip networks, we would
like some properties and even in computer system networks, we typically like the
networks to be resilient. so we don't want sort of data to be dropped. But that's
not, not necessarily guaranteed. People have built networks where links can drop,
can drop data. So that's another option is, you can drop the data and try to
retransmit it if you want reliable transmission from one point to another.
Okay. So, let's look at a quick example here of flow control in our networks. This
is not in your handouts. so you just, pay attention. so the first type of flow
control we're going to look at is basically a stall wire, or a big stop
sign. So here or is what we have, is we have a sender, with a Q. So Q sub sender
and Q sub R, or Q sub receiver. And we've named sort of all the points along here.
let's say, in this network we have a register in between the sender and the
receiver and this is in our link. This is sort of our link cost. Takes a cycle and
we pipeline the wire. Okay. So now, data arrives here into D, which is our sort of
receive point into the receiver. And at some point it decides, I can't ta ke any
more data. I can't, can't read that data. I need to go process some of it. So, I
need to stall the network. So it says, stop. So it says stop here. And in a
perfect world, this goes through some combinational logic. Just completely, just
like in your pipeline stalls this point in the pipe stalls. This flip flop stalls
that Q, stalls the, going this way. Stalls A, stalls the sender, tells it not to
actually send any more data. So it's a stall. We stop in D. C stops, B stops, A
stops instantaneously. At some point, D unstalls because it's going to go read
data more again and the network keep flowing again. So, sorry. What this is
showing is, these are packets. These are not FITS. These are complete packets
getting sent, or complete FLITS getting sent. This is our flow control unit. So
we're looking at each one of these A, B's, and C's here, and D's are, are uniquely
flow controllable units. So that's on/off flow control for combinational stall
single. Now, the problem with this is, it took us a cycle to send data this wire
because we had a flip flp going that way, but our stall wire runs all the way back.
well, that's not, that's not good from a cycle time perspective. Cuz if you look at
the combinational sort of path now, you're going to see well, maybe you have an
output of this which says this data available that goes through some logic in
D and that generates a stall signal. And then, has to propagate physically a long
distance away and go into lots of other logic. And after having designed a couple
of these sorts of networks, you're never going to be able to build that. That's, if
you want to have a high performance network, that time is, is, is, is too
long. Cuz if your cycle time is anywhere near the length of wire, of the delay of
length wire you have, you're not going to be able to build them. Okay. So now, we
start to look at, we, we switch to something and say, let's try to solve that
and put a pipeline flop in here on the receive on the return path of the stall
wire, of the stall signal. Okay. S o, what, what happens? Well, if we look at
this for packet zero, one, two, three, at some point d decides to stall. But, that
is not able to stop let's say, R from sending the cycle before. Because we now
have a flip flop in this path. So, it doesn't know about that. Likewise, it
doesn't know, it can't stop B and A from moving forward one cycle either. So, if we
look at the pipeline diagram, what that really means is these arrows here, we
can't stall this on a dime. We have to wait and we actually are not able to stall
until the next packet. Likewise, we're not able to stall B and A until later. And
this can even be worse if you have multiple pipeline registers going
backwards here, which is pretty common. Now, the implication of this is, you were
not able to stall C at all. So, like it or not, the data's coming this direction from
our D, Q sub R. Huh. So, what do you go about doing at this point? So, this is a
tough one. you could either drop the data. That's probably not very advantageous cuz
you're just going to drop random data in your network. Networks like to actually
deliver data. A better thing to do is to have extra buffering in Q sub R, and we'll
call this skid buffering. So that the data, it's called skid buffering cuz it's
kind of like in a car. When you hit the stop pedal or you hit the, hit the, the
brake pedal, you need some runway to, to skid into before you can actually stop.
So, you hit the brake, and you're a sort of skid to a stop and you need that, that
extra area. So, we budget that into this Q here and you can actually build a network
build a flow control system where you have extra space in Q sub R to skid into. And
then when you unstall, you'll see actually that there's basically that should be a D,
sorry. it takes a cycle to unstall also. So that's, that's kind of not good.
Conveniently, you have something to feed at that point because we have that extra
value in Q sub R. But there are cases that you can come up to with, where you stall
and then not stall. And then stall and then not s tall. Where you can actually
accidentally introduce bubbles with this type of flow control. And I don't have a,
a diagram of that here. But that would show up as basically a bubble throughout
the entire pipe and no data being read. But that's, you can construct that with a
sort of on/off flow control pipe line flow control. So, you could also think about
having on/off flow control of partial pipeline stall control. So what I mean by
that is, instead of feeding up into this register here, now we need two skid buffer
entries over there cuz we can't stop B flowing into here or C flowing into there.
So we can't stop any of this stuff and we need two entries now in that skid buffer.
And we're running out of time, but I wanted to try to finish this flow control
notion up here. A good solution to this is called Credit-Based flow control. So, in
credit-based flow control, you put a counter in the center and the counter
counts how many entries there are in the receive FIFO. And what it does is it
starts sending data. And whenever data is removed from this FIFO, a credit gets sent
back. And it can be, if, like it can be pipelines multiple levels deep here on the
return, point. When the credit comes back, you increment the counter. But when you
send a word, you decrement the counter. And if the counter ever reaches zero, you
stop sending. This is actually ends up being superior than this order design
because you don't have funny stutters on the receive side when you go to build a
credit-based flow control system. That's a little bit beyond, showing that proof is a
little beyond this course. But I did want to say here that when you compute this,
you need to compute how large the credit needs to be and how big this receive FIFO
needs to be. And they need to be sized appropriately. If you size one of them
wrong, in this case, if you size one of them wrong in the on/off flow control,
you're actually going to end up losing data. If you skid into your skid buffer
and you need two skid entry slots, and you only have one skid ent ry slot, you're
going to lose data. In the credit-based flow control system, the counter just
reaches zero. So, just impact your bandwidth, but you're not going to lose
data. Now, having said that, you should, if you want high performance through this
network, you should size this and this counter to be the same. And you should
size it big to take into account the entire round trip latency of this, this
communication. lets stop here for today. I'll briefly finish up deadlock next time.
And then, we'll move on to building large mini core systems or large multi-core
systems, and coherence protocols for them next lecture.