1
00:00:02,072 --> 00:00:07,098
In the last few videos, we've talked about
managing registers. In this video, we're

2
00:00:07,098 --> 00:00:13,018
going take a few moments to talk about
another very important resource, the cache

3
00:00:13,018 --> 00:00:18,096
and what compilers can and can't do to
manage them. Modern computer systems have

4
00:00:18,096 --> 00:00:24,024
quite elaborate memory hierarchies. And
so, if we were to start at the closest

5
00:00:24,226 --> 00:00:29,357
level to the processor itself, we would
find that on the chip there are some

6
00:00:29,357 --> 00:00:34,579
number of registers. And these are very
fast access. So, typically that can be

7
00:00:34,579 --> 00:00:40,501
accessed in a single cycle so at the same
rate as the clock frequency. And the

8
00:00:40,501 --> 00:00:45,809
problem is that it's very expensive to
build such high performance memory. And

9
00:00:45,809 --> 00:00:51,760
so, we don't get to have very much of it,
typically. You know, you might have 256,

10
00:00:51,760 --> 00:00:57,700
say, to 8K bytes of registers total
available to you on a given processor.

11
00:00:57,700 --> 00:01:02,932
Now, a very significant portion of the die
area and the modern processor would be

12
00:01:02,932 --> 00:01:06,951
devoted to the cache. And the cache is
also quite high performance but not quite

13
00:01:06,951 --> 00:01:11,538
as high performance as registers. Maybe on
average, it would take three cycles just

14
00:01:11,538 --> 00:01:15,776
service something from the cache but you
get a lot more of it. And modern

15
00:01:15,776 --> 00:01:21,185
processors would have up to a megabyte of
cache. Then, much further away from the

16
00:01:21,185 --> 00:01:26,627
processor is the main memory, the DRAM,
and this is much more expensive to

17
00:01:26,627 --> 00:01:31,868
allocate to access in time you know,
typical values would be twenty to 100

18
00:01:31,868 --> 00:01:38,269
cycles and I think, you know, it's more on
100 toward the 120 these days in most

19
00:01:38,269 --> 00:01:43,878
processors but you get quite a lot of it.
You get between 32 megabytes. That would

20
00:01:43,878 --> 00:01:49,663
be fairly small machine up to four
gigabytes for maximally provisions

21
00:01:49,903 --> 00:01:55,736
processor. And finally, farthest away is
typically disk. And this takes a very,

22
00:01:55,736 --> 00:02:00,493
very long time to get to hundreds of
thousands or millions of cycles but you

23
00:02:00,493 --> 00:02:06,629
can have enormous amounts of storage out
there, gigabytes to terabytes of storage.

24
00:02:06,629 --> 00:02:11,068
As I said, there are limitations on the
size and speed of registers and caches.

25
00:02:11,068 --> 00:02:16,014
And these are limited as much by power
actually as, as anything e lse these days.

26
00:02:16,014 --> 00:02:19,277
And I, and so it's, you know, very
important people would like to have as

27
00:02:19,277 --> 00:02:24,135
much register and cache as possible but
there are real constraints on how big and

28
00:02:24,135 --> 00:02:28,148
how fast we can make these relative to the
speeds of the processors. Now

29
00:02:28,148 --> 00:02:32,698
unfortunately, the cost of a cache miss is
very high as we saw in the previous slide.

30
00:02:32,698 --> 00:02:36,484
If you, you could get something in a
couple of cycles from the cache. But if

31
00:02:36,484 --> 00:02:40,625
it's not in the cache, then it could take
you a couple of orders of magnitude longer

32
00:02:40,767 --> 00:02:45,562
to get it out of the main memory. And so
for this reason people, you know, try to

33
00:02:45,562 --> 00:02:51,749
build caches in between the processor and
the main memory to hide that latency of

34
00:02:51,749 --> 00:02:56,493
the main memory so that most of the data
is in the cache. And typically, it

35
00:02:56,493 --> 00:03:01,779
requires more than one level of cache
these days to match a fast processor well

36
00:03:01,779 --> 00:03:07,332
with the speed of a very large main
memory. So, you know, very common now to

37
00:03:07,332 --> 00:03:12,018
have two levels of cache and processors
and some processors even have three levels

38
00:03:12,018 --> 00:03:19,017
of cache. So the bottom line is that it's
very important to for high performance to

39
00:03:19,017 --> 00:03:24,079
manage these resources properly.
Particular to manage the registers and the

40
00:03:24,079 --> 00:03:31,050
cache as well if you want your program to
perform well. Compilers have become very

41
00:03:31,050 --> 00:03:36,068
good in managing registers and in fact, I
think today, most people would agree that

42
00:03:36,068 --> 00:03:41,074
for almost all programs, compilers do a
better job at managing registers than

43
00:03:41,074 --> 00:03:46,048
programmers can. And so, it's very
worthwhile to leave the job of allocating

44
00:03:46,048 --> 00:03:51,053
registers or assigning registers to the
compiler. However, compilers are not good

45
00:03:51,053 --> 00:03:56,012
at managing caches. And while there's a
little bit that compilers can do and

46
00:03:56,012 --> 00:04:00,387
that's what we're going to talk about in
this rest of this video for the most part,

47
00:04:00,387 --> 00:04:05,047
if programmers want to get good cache
performance, they have to understand the

48
00:04:05,047 --> 00:04:08,952
behavior of the cache is on the machine
and have to understand what their program

49
00:04:08,952 --> 00:04:14,059
is doing, you have to understand a little
bit about what the compiler is capable of

50
00:04:14,059 --> 00:04:18,468
doing and then they still have to , write
the program in such a way that is going

51
00:04:18,468 --> 00:04:23,384
to, to be cache friendly. So, it's still
very much an open question. How much a

52
00:04:23,384 --> 00:04:27,044
compiler can do to improve cache
performance? Although, there are a few

53
00:04:27,044 --> 00:04:32,545
things that we've found compilers can do
reliably. So, to see one of those things

54
00:04:32,545 --> 00:04:38,635
that compilers can actually do let's take
a look at this example loop. So, what we

55
00:04:38,635 --> 00:04:44,947
have here, we have an outer loop on j and
inner loop on i and then in each iteration

56
00:04:44,947 --> 00:04:52,322
of the inner loop we're reading from ,
some vector you know, performing some

57
00:04:52,322 --> 00:04:58,178
computational net value and storing the
results into the ith element of the A

58
00:04:58,178 --> 00:05:03,414
vector. Now, as it turns out, this
particular program has really, really

59
00:05:03,414 --> 00:05:09,001
terrible cache performance. This is going
to behave very badly. And so, let's think

60
00:05:09,001 --> 00:05:14,728
about what's going to happen. So, let's
imagine our cache, you know, as some block

61
00:05:14,728 --> 00:05:19,563
of memory, okay. And so, what's going to
happen here. I mean, what's, what's the

62
00:05:19,563 --> 00:05:25,489
first iteration going to be? Well, we're
going to, you know load and, store some

63
00:05:25,489 --> 00:05:32,946
function of that into . And so, what's
going to get loaded into the cache is and

64
00:05:32,946 --> 00:05:38,916
. All right, let's assume they just go
into different elements in this just for

65
00:05:38,916 --> 00:05:44,771
the sake of argument, let's say they land
in the first two elements in the cache.

66
00:05:44,771 --> 00:05:50,840
And then we're going to do the second
iteration of this and, we'll, we'll load

67
00:05:51,216 --> 00:05:58,650
and write it into and so and will be
loaded into the cache, all right and so

68
00:05:58,650 --> 00:06:04,286
on. And this will repeat over and over and
over again, loading one element of a and

69
00:06:04,286 --> 00:06:09,395
one element of b the important thing to
notice is that all of these references to

70
00:06:09,395 --> 00:06:14,744
a and to b are misses, okay. Every single
one of these is a cache miss because on

71
00:06:14,744 --> 00:06:21,059
each iteration of the loop we refer to new
elements, okay. So, we're not referring to

72
00:06:21,059 --> 00:06:26,760
the same elements as we were on the
previous ones. So, now let's ignore for

73
00:06:26,760 --> 00:06:32,006
the moment the fact that there may be
multiple elements in the same cache line,

74
00:06:32,006 --> 00:06:37,429
okay. So, some of you probably are aware
already. That when we fetch data from

75
00:06:37,429 --> 00:06:43,382
memory we don't just fetch the one word,
okay. So, typically when we refer to for

76
00:06:43,382 --> 00:06:49,707
example you know, is stored here will
fetch an entire cache line which will be

77
00:06:49,707 --> 00:06:54,684
some block of memory and that may well
have, you know, other elements of b in it.

78
00:06:54,684 --> 00:06:59,376
So, we might get a couple other elements
of b into the cache at the same time but

79
00:06:59,376 --> 00:07:04,690
the important thing here is that on every
iteration of the loop, we're referring to

80
00:07:04,690 --> 00:07:09,409
fresh data, okay. And, and if these data
values are large enough, if they take up

81
00:07:09,409 --> 00:07:14,323
an entire cache line, then each iteration
of the loop is going to be a cache miss

82
00:07:14,508 --> 00:07:19,440
for both elements, and we won't get any
benefit of the cache. And this loop will

83
00:07:19,440 --> 00:07:24,037
run at the rate of at the rate of the main
memory and not at the rate of the cache.

84
00:07:24,037 --> 00:07:28,252
Now, the other thing that's important here
is that this loop bound here is very large

85
00:07:28,252 --> 00:07:31,908
and I picked it to be very large to
suggest that it's much larger than the

86
00:07:31,908 --> 00:07:36,478
size of the cache. So, as we get towards
the end of the loop what's going to happen

87
00:07:36,478 --> 00:07:40,844
is we will have filled up the whole cache,
so this whole cache will be filled with

88
00:07:40,844 --> 00:07:44,467
values from a and b, and then it's going
to start clobbering values that are

89
00:07:44,467 --> 00:07:48,105
already in the cache. And if this loop,
you know, if the size of these vectors,

90
00:07:48,105 --> 00:07:52,734
let's say twice the size of the cache by
the time we come around and complete the

91
00:07:52,734 --> 00:07:57,316
entire execution of the. Inner loop.
What's in the cache is the second half of

92
00:07:57,316 --> 00:08:01,012
the a and b arrays, it's not the first
half of the a and b arrays. And so, then

93
00:08:01,012 --> 00:08:05,996
when we go back around and execute another
iteration of the outer loop, now what's in

94
00:08:05,996 --> 00:08:10,401
the cache is also, going to be not the
data that we're referencing. And so when

95
00:08:10,401 --> 00:08:14,158
we come back around and begin the
execution of the inner loop the second

96
00:08:14,158 --> 00:08:21,273
time. And we refer to and, and, and .
What's in the cache is the values from the

97
00:08:21,273 --> 00:08:25,725
high numbered elements of the a and b
vector and not the low numbered elements.

98
00:08:25,725 --> 00:08:30,466
And so, these references are all misses
again. And so, the, the basic problem with

99
00:08:30,466 --> 00:08:34,813
this loop is, a loop that's structured
like this, is that almost every memory

100
00:08:34,813 --> 00:08:39,803
reference and if, and if the data values
are big enough again that they fill an

101
00:08:39,803 --> 00:08:46,043
entire cache line then it will be every
single memory reference is a cache miss.

102
00:08:46,043 --> 00:08:51,206
Now, instead, let's consider an
alternative structure for the same

103
00:08:51,206 --> 00:08:56,963
program. Here, I've put the i loop at as
the outer loop and the j loop as the inner

104
00:08:56,963 --> 00:09:04,116
loop. And here what we do is we load . And
we write and then we repeat that

105
00:09:04,116 --> 00:09:09,572
computation ten times on the same data
values. And so here we'll get excellent

106
00:09:09,572 --> 00:09:14,348
cash performance. We'll, we'll have a miss
on the first reference, but then on the

107
00:09:14,348 --> 00:09:19,829
subsequent nine references the data will
be in the cache or will completely exhaust

108
00:09:19,829 --> 00:09:25,495
our computation on those particular a and
b values. And then we'll go on to the next

109
00:09:25,674 --> 00:09:29,778
a and b values. We'll finish the inner
loop and go on to the other and do one

110
00:09:29,778 --> 00:09:34,030
more iteration of the outer loop. And so,
the advantage of this structure is that it

111
00:09:34,030 --> 00:09:38,368
brings the data into the cache and then it
uses that data as much as possible, before

112
00:09:38,368 --> 00:09:42,404
going on to the next data. Rather than
doing a little bit on every data item and

113
00:09:42,404 --> 00:09:46,541
then going back, you know, doing one pass
and then going back and sweeping over all

114
00:09:46,541 --> 00:09:50,635
items, items again and doing another
little bit. Alright, so this particular

115
00:09:50,635 --> 00:09:55,104
structure, where we've exchanged the order
of the outer loops sorry, exchanged the

116
00:09:55,104 --> 00:10:00,069
order of the inner and outer loops, it
computes exactly the same thing but it has

117
00:10:00,069 --> 00:10:04,972
much better cache behavior. And it
probably run more than ten times faster.

118
00:10:04,972 --> 00:10:09,813
Now compilers can preform this simple loop
interchange optimization. This particular

119
00:10:09,813 --> 00:10:13,586
kind of optimization is called loop
interchange, where you just switch in the

120
00:10:13,586 --> 00:10:17,216
order of loops. In this particular case,
it's very easy to see that that's legal

121
00:10:17,216 --> 00:10:22,213
and the compiler could actually figure it
out. Not many compilers actually implement

122
00:10:22,213 --> 00:10:25,905
this optimization because in general, it's
not easy to decide whe ther you can

123
00:10:25,905 --> 00:10:30,164
reverse the orders of, of the loops. And
so usually, a programmer would have to

124
00:10:30,164 --> 00:10:35,497
figure out that they wanted to do this, in
order to improve the performance in the