1
00:00:03,680 --> 00:00:11,044
Okay, so that's high level programming
models. Or our, our second high level

2
00:00:11,044 --> 00:00:16,516
programming model, which is not, shared
memory, and the contrast with shared

3
00:00:16,516 --> 00:00:22,451
memory, of messaging or message passing.
And today we're gonna start talking a

4
00:00:22,451 --> 00:00:29,303
little bit about the gory details on how
to build interesting interconnects. Before

5
00:00:29,303 --> 00:00:33,522
we get started, I wanted to introduce,
sort of the agenda that we are going to

6
00:00:33,522 --> 00:00:37,904
talk about. We are not going to cover all
of this today. We're, this is, today's

7
00:00:37,904 --> 00:00:43,221
lecture and next lecture we will be
talking about interconnect design. So a

8
00:00:43,221 --> 00:00:48,300
couple of different, things that you have
to worry about in interconnect design.

9
00:00:49,820 --> 00:00:55,944
First one is what's called switching. So
when I say switching, what I'm trying to

10
00:00:55,944 --> 00:01:02,504
say by that is, there's different ways to
organize the communication. And you can

11
00:01:02,504 --> 00:01:09,221
think about his probably the best example
is the old telephone system versus the

12
00:01:09,221 --> 00:01:14,354
modern day Internet. So in the old
telephone system, there's switching, the

13
00:01:14,354 --> 00:01:20,121
way it worked is, you try to make a phone
call and the first you did is you picked

14
00:01:20,121 --> 00:01:25,888
up the, the receiver on the phone, and you
sort of turn the crank, and there is some

15
00:01:25,888 --> 00:01:31,725
switch board operator in your local town
who would hear the bell ring, and take the

16
00:01:31,725 --> 00:01:37,885
plug, plug the wire in and pick up and say
hello, where, who you trying to call. And

17
00:01:37,885 --> 00:01:45,568
you would say I'm trying to call such and
such in next town over. Well the

18
00:01:45,568 --> 00:01:50,505
switchboard operator would say, okay
that's good, I'm going to take a wire

19
00:01:50,505 --> 00:01:55,916
from, the wire that runs from your house
to this location, plug one wire in there

20
00:01:55,916 --> 00:02:01,461
and then we'll go and plug the other wire
into a wire which runs to the next town

21
00:02:01,461 --> 00:02:06,654
over. So then you'd be connected to the
next town over, and the switchboard

22
00:02:06,654 --> 00:02:10,960
operator in the next town over, and you'd
say, oh I'd like to talk to the same

23
00:02:10,960 --> 00:02:14,890
person you're trying to talk to. And they
would say, okay that's great. I'm going to

24
00:02:15,213 --> 00:02:19,573
patch a wire from, my patch board from,
the out of town wire, to the destination

25
00:02:19,573 --> 00:02:23,611
location, and I'll turn a little crank to
ring the, the ringer on the, on the

26
00:02:23,611 --> 00:02:26,712
destination phone. Okay, so that's one ide
a.

27
00:02:26,712 --> 00:02:32,566
And that is actually called circuit switch
networks, cuz you're building a circuit.

28
00:02:32,566 --> 00:02:37,800
You're building a wire all the way from
one location, all the way to another

29
00:02:37,800 --> 00:02:45,495
location. Alternatively we can do what we
do in the network internet today. In the

30
00:02:45,495 --> 00:02:50,674
internet today there is, we don't
generate, we don't have a wire directly

31
00:02:50,674 --> 00:02:56,501
from one location patched together the,
you'd actually patch wires from one place

32
00:02:56,501 --> 00:03:01,753
to another place. in contrast, in our
switching systems you'll actually

33
00:03:01,753 --> 00:03:06,936
packetize the data. And then we'll hand
the packets from different locations, and

34
00:03:06,936 --> 00:03:11,691
people and resources can be used for other
things. So, it's much more akin to

35
00:03:11,691 --> 00:03:16,133
something like a mail system. So, in a
mail system, you take the data you want to

36
00:03:16,508 --> 00:03:21,326
send. You fold it in half, you put it in
an envelope. You put a stamp on it, and

37
00:03:21,326 --> 00:03:26,004
you, you set it going. The road that goes
from your house to the post office is not

38
00:03:26,004 --> 00:03:29,403
reserved, for that one piece of mail,
until it gets all the way to the

39
00:03:29,403 --> 00:03:33,295
destination, like in a circuit switched,
to apology. Instead in a packet switched,

40
00:03:33,295 --> 00:03:37,236
you are going to some of the message, and
you are to put a stamp on the physical

41
00:03:37,236 --> 00:03:40,536
envelope, and the, your postal carriers
may come pick it up. They are going to

42
00:03:40,832 --> 00:03:44,772
take that, take it to some place else, and
then there is taken to some place else,

43
00:03:44,772 --> 00:03:48,713
take to some place else, but you can set
another piece of mail on that same link,

44
00:03:48,713 --> 00:03:52,506
or other people can be using the same
roads to send another packets, or other

45
00:03:52,506 --> 00:03:57,698
messages. So switching is the type of
network we have here, and how we connect

46
00:03:57,698 --> 00:04:03,284
together the different networks and how we
do the switching. And there's a couple

47
00:04:03,284 --> 00:04:08,940
other things in the middle between circuit
switched and packet switched networks.

48
00:04:09,980 --> 00:04:14,684
Okay, so next thing we are talking about
interconnect design is topology. So this,

49
00:04:14,684 --> 00:04:18,815
how do we physically connect things
together, in our world. How do we run

50
00:04:18,815 --> 00:04:23,290
wires between the different nodes in the
system? Do we run wire between every

51
00:04:23,290 --> 00:04:27,822
person in the classroom, I run a wire
between myself and every other person, and

52
00:04:27,822 --> 00:04:32,584
everyone runs with a wire between everyone
else. Or do we build a nod in the middle

53
00:04:32,584 --> 00:04:37,174
of everything to, or do we really connect
to our nearest neighbours, and then, we

54
00:04:37,174 --> 00:04:41,821
have to send it to them in native sens of
X people. So there's a lot of different

55
00:04:41,821 --> 00:04:51,979
apologies for given size graph. . Routing,
routing is figuring out what path to take

56
00:04:51,979 --> 00:04:56,107
through the network to get from one point
to another. So, we can actually build a

57
00:04:56,107 --> 00:04:59,461
nearest neighbor network in this
classroom, or we run wires between all of

58
00:04:59,616 --> 00:05:03,538
our neighbours, but not lets say, we all,
each, each of us connects to three

59
00:05:03,538 --> 00:05:07,563
different people, but not to four, and
there's gonna be multiple paths from any

60
00:05:07,563 --> 00:05:11,742
one point to another point. So we need to
come up with a routing decision to figure

61
00:05:11,742 --> 00:05:15,509
out how to get from that one point to
another point, and that affects our

62
00:05:15,509 --> 00:05:20,050
interconnect design. And then finally flow
control, and there's two types of flow

63
00:05:19,379 --> 00:05:24,331
control. There is local flow control,
which is communication from one node, to

64
00:05:24,331 --> 00:05:30,656
the next the next node over, and making
sure that you don't lose data on that

65
00:05:30,656 --> 00:05:37,060
local link. But its also, how do you rate
limit, round trip throughout the entire

66
00:05:37,060 --> 00:05:43,860
network. and we are going to study that
next time in more depth. Okay. So let's

67
00:05:43,860 --> 00:05:51,159
move on to some fun pictures here. High
quality pictures. So first thing we're

68
00:05:51,159 --> 00:05:59,710
going to look at here is the anatomy of a
message. . A message is our fundamental

69
00:05:59,710 --> 00:06:07,527
primitive of some piece of data we want to
send. At the top here, we show a message

70
00:06:07,527 --> 00:06:14,136
which has, let's say, some number of bytes
in it. These delimiting points here do not

71
00:06:14,136 --> 00:06:20,824
delimit a byte, they delimit some chunk of
data. And we're actually going to fragment

72
00:06:20,824 --> 00:06:27,082
this message into smaller pieces which
we're going to call a packet. Now I know

73
00:06:27,082 --> 00:06:32,139
that I want to make a big difference
between a message and a packet. A packet

74
00:06:32,139 --> 00:06:37,459
is a piece of data that we're going to be
sending through the network, and the

75
00:06:37,459 --> 00:06:42,844
network natively understands this packet
and the packet is routable through the

76
00:06:42,844 --> 00:06:51,889
network, so it has routing information.
So, a good example of this is, if you are

77
00:06:51,889 --> 00:06:57,615
trying to use MPI, and you want to send
1000 words, and let's say the maxi mum

78
00:06:57,615 --> 00:07:03,332
message you can and, receive, or maximum
package you can send on a network is 100

79
00:07:03,332 --> 00:07:08,678
bytes. You're going to packetize the data,
packetize the message into 100

80
00:07:08,678 --> 00:07:14,320
individually roundable packets. So let's
look inside of one of these packets.

81
00:07:14,700 --> 00:07:18,772
Typically, because the packet is
roundable, it needs to know where its

82
00:07:18,772 --> 00:07:22,726
going. It might need to know where its
coming from. So at the beginning of a

83
00:07:22,726 --> 00:07:27,035
packet, you will typically have something
like a source. You might have a

84
00:07:27,035 --> 00:07:31,579
destination, or its going to be you
definitely need to have a destination, you

85
00:07:31,579 --> 00:07:38,484
might have a source. You might have a
length. If your, network allows for

86
00:07:38,484 --> 00:07:45,192
variable length packets. , and we call
this the header. And we call the rest of

87
00:07:45,192 --> 00:07:54,260
the packet the payload. And we're going to
introduce an interesting term here. Flit

88
00:07:54,980 --> 00:08:01,922
Now this is a term actually that was
coined by, I believe Bill Dally, who is

89
00:08:01,922 --> 00:08:09,755
now a Stanford professor who, he did a lot
of work in message passing and other types

90
00:08:09,755 --> 00:08:16,609
of parallel computers. A flit is a flow
control digit. It's kind of like a bit,

91
00:08:16,609 --> 00:08:25,206
but it's the, the, flow control ball unit
and. The reason we bring this up,

92
00:08:25,206 --> 00:08:29,967
sometimes a flit is actually equal to the
whole packet. Sometimes it's a smaller

93
00:08:29,967 --> 00:08:35,144
piece of the packet, depending on how you
build your network. . But a flow control

94
00:08:35,144 --> 00:08:43,870
digit is what you were flow controlling on
from one node to the next node. So this is

95
00:08:43,870 --> 00:08:51,659
what you track the flow control on. So,
it's very possible that your, you don't

96
00:08:51,659 --> 00:08:58,622
actually track, sort of send and receiving
of messages on the byte level, or on every

97
00:08:58,622 --> 00:09:04,227
single cycle, but instead you do it in
bigger chunks. So a good example of this

98
00:09:04,227 --> 00:09:09,904
is, you have a network, which is one byte
wide, the link is one byte wide, but you

99
00:09:09,904 --> 00:09:17,807
are, so, the minimum thing you can send is
a 32 bit word. As the minimum piece of

100
00:09:17,807 --> 00:09:23,785
data that is full control, then you need
to always send let's say, four bytes. The

101
00:09:23,785 --> 00:09:33,241
full control will be on the order of the
flit, which is the four byte unit. But the

102
00:09:33,241 --> 00:09:38,260
link is narrower than that. So you don't
actually, you can't actually stop in the

103
00:09:38,260 --> 00:09:44,345
middle of the message, and say. Oh, I on
ly got or you can't stop in the middle of

104
00:09:43,592 --> 00:09:48,987
a flit and say stop. you gave me three
bytes, and I can't take the fourth right

105
00:09:48,987 --> 00:09:53,880
now. No. It's not allowed. It's, it's flow
control based. So the flow control says

106
00:09:54,649 --> 00:09:59,218
this is the minimal unit for flow control.
So there's four bytes, that is what you

107
00:09:59,218 --> 00:10:03,675
are allowed to send. And you need to send
in chunks of basically four bytes. And

108
00:10:03,675 --> 00:10:11,175
that's our flit size. No we can split
inside a flit, and we can actually call

109
00:10:11,175 --> 00:10:17,981
this one a phit, or a physical transfer
digit. And a phit is what I was talking

110
00:10:17,981 --> 00:10:24,262
about with, you had, if you had for
instance, four bytes that you're trying to

111
00:10:24,262 --> 00:10:31,040
transmit, and your flow control on those
four bytes. Each of those bytes is a phit,

112
00:10:31,300 --> 00:10:38,459
or the physical transfer that you transfer
in one cy-, in one clock. cycle. . Many

113
00:10:38,459 --> 00:10:43,044
times the phit and the flit will be the
same, if you have what, if you have wide

114
00:10:43,044 --> 00:10:47,823
networks, but if you have very narrow
networks, sometimes these will not be

115
00:10:47,823 --> 00:10:59,450
matched. Okay, it's just a nomenclature so
far. Our first topic we want to discuss is

116
00:10:59,450 --> 00:11:04,569
switching, how to get from point A to
point B. Oh, okay. It's not routing, it's,

117
00:11:04,569 --> 00:11:11,793
it's rather the model of how to connect
different locations together, and we're

118
00:11:11,793 --> 00:11:16,167
going to talk mostly about three here. We
already talked about circuit switched.

119
00:11:16,167 --> 00:11:20,873
Circuit switched is like the old telephone
network. You pick up the phone and somehow

120
00:11:20,873 --> 00:11:25,025
there's a wire patched all the way from
where you pick up the phone to the

121
00:11:25,025 --> 00:11:32,406
destination location, and you reserve that
location the whole time. Packet switched

122
00:11:32,406 --> 00:11:36,844
networks, or what is sometimes called
store and forward networks or probably

123
00:11:36,844 --> 00:11:41,554
more commonly called store and forward
networks, are things like the Internet,

124
00:11:41,554 --> 00:11:45,789
where you'll actually generate a packet,
hand that to someone else, and they'll

125
00:11:45,789 --> 00:11:50,241
store it. And at some point, when the link
is free, they'll forward it onto the next

126
00:11:50,241 --> 00:11:54,313
hop. And when the next link is free,
they'll store it on to the next hop, and

127
00:11:54,313 --> 00:12:04,926
it'll continue until it gets to the
destination. Thus in contrast to cut

128
00:12:04,926 --> 00:12:12,858
through networks, which are sometimes
called wormhole networks. Cut thr ough

129
00:12:12,860 --> 00:12:19,049
networks still have packetization. But
they'll actually. Worm, through the

130
00:12:19,049 --> 00:12:24,417
network. So instead of having to, send the
data from one location. To the next hop

131
00:12:24,417 --> 00:12:29,785
over. An it waits for the entire message
to receive. Before it sends it on to the

132
00:12:29,785 --> 00:12:34,348
next node. A wormhole network. Will
actually allow. Or a, a cut-through

133
00:12:34,348 --> 00:12:39,716
network. Will actually, start to send the
beginning portion of a message. From, one

134
00:12:39,716 --> 00:12:46,069
node to the next node. Along the hops.
Before the tail has been received. Hence

135
00:12:46,069 --> 00:12:50,780
it's actually worms through the networks.
You can actually have a message sort of

136
00:12:50,780 --> 00:12:56,868
streamed through a multiple different
nodes. And this is where we have as cut-3

137
00:12:56,868 --> 00:13:03,351
networks. So I just wanna introduce those,
those three ideas and think about them as

138
00:13:03,351 --> 00:13:09,522
we go onto to build networks. we'll talk
about cut-3 networks, when we get to,

139
00:13:09,756 --> 00:13:22,884
rounding. So before we break for today I
want to just introduce a couple different

140
00:13:22,884 --> 00:13:28,321
topology. And just come up with different
topologies where we'll pick up next time.

141
00:13:28,321 --> 00:13:32,602
But in our networks, we talked about
buses. Multiple entities on one shared

142
00:13:32,602 --> 00:13:36,997
medium. You can think about building a
segmented bus, where you actually have

143
00:13:36,997 --> 00:13:41,567
flip flops along the communication path
here. And this would allow, for instance,

144
00:13:41,567 --> 00:13:45,731
this node, maybe, to communicate with that
node at the same time as three

145
00:13:45,731 --> 00:13:54,720
communicating with four. sometimes this is
called pipeline bus. You can have rings.

146
00:13:55,620 --> 00:14:02,794
Which are like the segmented bus, but they
connect the two ends together. You could

147
00:14:02,794 --> 00:14:08,523
even, implement rings in a way, that
minimizes wire length. We'll talk about

148
00:14:08,523 --> 00:14:15,434
that next time. You could have crazier
things like 2D meshes, 2D toreses. If you

149
00:14:15,434 --> 00:14:23,809
have cubes and hyper cubes. You can have
fully connected topologies. You can have,

150
00:14:24,027 --> 00:14:29,401
things called omega networks, which are
multi stage networks. Where you can

151
00:14:29,401 --> 00:14:35,502
basically communicate from anyplace to any
other little place in multiple stages, in

152
00:14:35,502 --> 00:14:41,385
multiple clock cycles. You can build,
trees. or, things called fat trees, where

153
00:14:41,385 --> 00:14:47,606
the lengths at the top of the tree get
fatter or wider. And we'll talk about this

154
00:14:47,606 --> 00:14:52,548
next time, but the generalized case of
this meshes, you end up with things that

155
00:14:52,548 --> 00:14:57,429
are called k-ary n-cubes where you can
very concisely with two numbers, describe

156
00:14:57,429 --> 00:15:00,480
a network topology. Okay, let's stop here
for today.