Okay, so that's high level programming 
models. Or our, our second high level programming 
model, which is not, shared memory, and the contrast with shared memory, of 
messaging or message passing. And today we're going to start talking a 
little bit about the gory details on how to build interesting interconnects. 
Before we get started, I wanted to introduce, sort of the agenda that we are 
going to talk about. We are not going to cover all of this 
today. We're, this is, today's lecture and next lecture we will be talking about 
interconnect design. So a couple of different, things that you 
have to worry about in interconnect design. 
First one is what's called switching. So when I say switching, what I'm trying 
to say by that is, there's different ways to organize the communication. 
And you can think about his probably the best example is the old 
telephone system versus the modern day Internet. 
So in the old telephone system, there's switching, the way it worked is, you try 
to make a phone call and the first you did is you picked up the, the receiver on 
the phone, and you sort of turn the crank, and there is some switch board 
operator in your local town who would hear the bell ring, and take the plug, 
plug the wire in and pick up and say hello, where, who you trying to call. 
And you would say I'm trying to call such and such in next town over. 
Well the switchboard operator would say, okay that's good, I'm going to take a 
wire from, the wire that runs from your house to this location, 
plug one wire in there and then we'll go and plug the other wire into a wire which 
runs to the next town over. So then you'd be connected to the next 
town over, and the switchboard operator in the next town over, and you'd say, oh 
I'd like to talk to the same person you're trying to talk to. 
And they would say, okay that's great. I'm going to patch a wire from, my patch 
board from, the out of town wire, to the destination location, and I'll turn a 
little crank to ring the, the ringer on the, on the destination phone. 
Okay, so that's one idea. And that is actually called circuit 
switch networks, because you're building a circuit. 
You're building a wire all the way from one location, all the way to another 
location. Alternatively we can do what we do in the 
network internet today. In the internet today there is, we don't 
generate, we don't have a wire directly from one location patched together the, 
you'd actually patch wires from one place to another place. 
in contrast, in our switching systems you'll actually packetize the data. 
And then we'll hand the packets from different locations, 
and people and resources can be used for other things. 
So, it's much more akin to something like a mail system. 
So, in a mail system, you take the data you want to send. 
You fold it in half, you put it in an envelope. 
You put a stamp on it, and you, you set it going. 
The road that goes from your house to the post office is not reserved, for that one 
piece of mail, until it gets all the way to the destination, like in a circuit 
switched, to apology. Instead in a packet switched, you are 
going to some of the message, and you are to put a stamp on the physical envelope, 
and the, your postal carriers may come pick it up. 
They are going to take that, take it to some place else, and then there is taken 
to some place else, take to some place else, but you can set another piece of 
mail on that same link, or other people can be using the same roads to send 
another packets, or other messages. So switching is the type of network we 
have here, and how we connect together the different networks and how we do the 
switching. And there's a couple other things in the 
middle between circuit switched and packet switched networks. 
Okay, so next thing we are talking about interconnect design is topology. 
So this, how do we physically connect things together, in our world. 
How do we run wires between the different nodes in the system? 
Do we run wire between every person in the classroom, I run a wire between 
myself and every other person, and everyone runs with a wire between 
everyone else. Or do we build a nod in the middle of 
everything to, or do we really connect to our nearest 
neighbours, and then, we have to send it to them in native sens of X people. 
So there's a lot of different apologies for given size graph. 
[COUGH]. Routing, routing is figuring out what 
path to take through the network to get from one point to another. 
So, we can actually build a nearest neighbor network in this classroom, or we 
run wires between all of our neighbours, but not lets say, we all, each, each of 
us connects to three different people, but not to four, and there's going to be 
multiple paths from any one point to another point. 
So we need to come up with a routing decision to figure out how to get from 
that one point to another point, and that affects our interconnect design. 
And then finally flow control, and there's two types of flow control. 
There is local flow control, which is communication from one node, to the next 
the next node over, and making sure that you don't lose data on that local link. 
But its also, how do you rate limit, round trip throughout the entire network. 
and we are going to study that next time in more depth. 
Okay. So let's move on to some fun pictures 
here. High quality pictures. 
So first thing we're going to look at here is the anatomy of a message. 
. A message is our fundamental primitive of 
some piece of data we want to send. At the top here, we show a message which 
has, let's say, some number of bytes in it. 
These delimiting points here do not delimit a byte, they delimit some chunk 
of data. And we're actually going to fragment this 
message into smaller pieces which we're going to call a packet. 
Now I know that I want to make a big difference between a message and a 
packet. A packet is a piece of data that we're 
going to be sending through the network, and the network natively understands this 
packet and the packet is routable through the network, so it has routing 
information. So, a good example of this is, if you are 
trying to use MPI, and you want to send 1000 words, and 
let's say the maximum message you can and, receive, or maximum package you can 
send on a network is 100 bytes. You're going to packetize the data, 
packetize the message into 100 individually roundable packets. 
So let's look inside of one of these packets. 
Typically, because the packet is roundable, it needs to know where its 
going. It might need to know where its coming 
from. So at the beginning of a packet, you will 
typically have something like a source. You might have a destination, or its 
going to be you definitely need to have a destination, you might have a source. 
You might have a length. If your, network allows for variable 
length packets. [COUGH], and we call this the header. 
And we call the rest of the packet the payload. 
[COUGH] And we're going to introduce an interesting term here. 
Flit Now this is a term actually that was coined by, I believe Bill Dally, who is 
now a Stanford professor who, he did a lot of work in message passing and other 
types of parallel computers. A flit is a flow control digit. 
It's kind of like a bit, but it's the, the, flow control ball unit and. 
The reason we bring this up, sometimes a flit is actually equal to the whole 
packet. Sometimes it's a smaller piece of the 
packet, depending on how you build your network. 
[COUGH]. But a flow control digit is what you were 
flow controlling on from one node to the next node. 
So this is what you track the flow control on. 
So, it's very possible that your, you don't actually track, 
sort of send and receiving of messages on the byte level, or on every single cycle, 
but instead you do it in bigger chunks. So a good example of this is, you have a 
network, which is one byte wide, the link is one byte wide, but you are, so, the 
minimum thing you can send is a 32 bit word. 
As the minimum piece of data that is full control, 
then you need to always send let's say, four bytes. 
The full control will be on the order of the flit, which is the four byte unit. 
But the link is narrower than that. So you don't actually, you can't actually 
stop in the middle of the message, and say. 
Oh, I only got or you can't stop in the middle of a flit 
and say stop. you gave me three bytes, and I can't take 
the fourth right now. No. 
It's not allowed. It's, it's flow control based. 
So the flow control says this is the minimal unit for flow control. 
So there's four bytes, that is what you are allowed to send. 
And you need to send in chunks of basically four bytes. 
And that's our flit size. No we can split inside a flit, and we can 
actually call this one a phit, or a physical transfer digit. 
And a phit is what I was talking about with, you had, if you had for instance, 
four bytes that you're trying to transmit, and your flow control on those 
four bytes. Each of those bytes is a phit, 
or the physical transfer that you transfer in one cy-, in one clock. 
cycle. [COUGH]. 
Many times the phit and the flit will be the same, if you have what, if you have 
wide networks, but if you have very narrow networks, sometimes these will not 
be matched. Okay, it's just a nomenclature so far. 
Our first topic we want to discuss is switching, 
how to get from point A to point B. Oh, okay. 
It's not routing, it's it's rather the model of how to 
connect different locations together, and we're going to talk mostly about 
three here. We already talked about circuit switched. 
Circuit switched is like the old telephone network. 
You pick up the phone and somehow there's a wire patched all the way from where you 
pick up the phone to the destination location, 
and you reserve that location the whole time. 
Packet switched networks, or what is sometimes called store and 
forward networks or probably more commonly called store and forward 
networks, are things like the Internet, where 
you'll actually generate a packet, hand that to someone else, and they'll 
store it. And at some point, when the link is free, 
they'll forward it onto the next hop. And when the next link is free, they'll 
store it on to the next hop, and it'll continue until it gets to the 
destination. Thus in contrast to cut through networks, 
which are sometimes called wormhole networks. 
Cut through networks still have packetization, 
but they'll actually worm through the network. 
So instead of having to send the data from one location, 
to the next hop over, and it waits for the entire message to 
receive before it sends it on to the next node. 
A wormhole network will actually allow, or a, a cut-through network will actually 
start to send the beginning portion of a message from one node to the next node 
along the hops before the tail has been received. 
Hence it's actually worms through the network.. 
You can actually have a message sort of streamed through a multiple different 
nodes, and this is where we have as cut-through 
networks. So I just want to introduce those, those 
three ideas, and think about them as we go on to build networks. 
we'll talk about cut-through networks, when we get to, rounding. 
So before we break for today I want to just introduce a couple 
different topology. And just flash and come up with different 
topologies, where we'll pick up next time. 
But in our networks, we talked about buses. 
Multiple entities on one shared medium. You can think about building a segmented 
bus, where you actually have flip flops along the communication path here. 
And this would allow, for instance, this node, maybe, to communicate with that 
node at the same time as three communicating with four. 
sometimes this is called pipeline bus. You can have rings, 
which are like the segmented bus, but they connect the two ends together. 
You could even implement rings in a way that minimizes wire length. 
We'll talk about that next time. You could have crazier things like 2D 
meshes, 2D toruses, if you have cubes and hyper cubes. 
You can have fully connected topologies. You can have things called omega 
networks, which are multi stage networks, where you can basically communicate from 
anyplace to any other little place in multiple stages, in multiple clock 
cycles. You can build, trees, 
or, things called fat trees, where the lengths at the top of the tree get fatter 
or wider. And we'll talk about this next time, but 
the generalized case of this meshes, you end up with things that are called k-ary 
n-cubes where you can very concisely with two numbers, describe a network topology. 
Okay, let's stop here for today.