In the last few videos, we've talked about
managing registers. In this video, we're
going take a few moments to talk about
another very important resource, the cache
and what compilers can and can't do to
manage them. Modern computer systems have
quite elaborate memory hierarchies. And
so, if we were to start at the closest
level to the processor itself, we would
find that on the chip there are some
number of registers. And these are very
fast access. So, typically that can be
accessed in a single cycle so at the same
rate as the clock frequency. And the
problem is that it's very expensive to
build such high performance memory. And
so, we don't get to have very much of it,
typically. You know, you might have 256,
say, to 8K bytes of registers total
available to you on a given processor.
Now, a very significant portion of the die
area and the modern processor would be
devoted to the cache. And the cache is
also quite high performance but not quite
as high performance as registers. Maybe on
average, it would take three cycles just
service something from the cache but you
get a lot more of it. And modern
processors would have up to a megabyte of
cache. Then, much further away from the
processor is the main memory, the DRAM,
and this is much more expensive to
allocate to access in time you know,
typical values would be twenty to 100
cycles and I think, you know, it's more on
100 toward the 120 these days in most
processors but you get quite a lot of it.
You get between 32 megabytes. That would
be fairly small machine up to four
gigabytes for maximally provisions
processor. And finally, farthest away is
typically disk. And this takes a very,
very long time to get to hundreds of
thousands or millions of cycles but you
can have enormous amounts of storage out
there, gigabytes to terabytes of storage.
As I said, there are limitations on the
size and speed of registers and caches.
And these are limited as much by power
actually as, as anything e lse these days.
And I, and so it's, you know, very
important people would like to have as
much register and cache as possible but
there are real constraints on how big and
how fast we can make these relative to the
speeds of the processors. Now
unfortunately, the cost of a cache miss is
very high as we saw in the previous slide.
If you, you could get something in a
couple of cycles from the cache. But if
it's not in the cache, then it could take
you a couple of orders of magnitude longer
to get it out of the main memory. And so
for this reason people, you know, try to
build caches in between the processor and
the main memory to hide that latency of
the main memory so that most of the data
is in the cache. And typically, it
requires more than one level of cache
these days to match a fast processor well
with the speed of a very large main
memory. So, you know, very common now to
have two levels of cache and processors
and some processors even have three levels
of cache. So the bottom line is that it's
very important to for high performance to
manage these resources properly.
Particular to manage the registers and the
cache as well if you want your program to
perform well. Compilers have become very
good in managing registers and in fact, I
think today, most people would agree that
for almost all programs, compilers do a
better job at managing registers than
programmers can. And so, it's very
worthwhile to leave the job of allocating
registers or assigning registers to the
compiler. However, compilers are not good
at managing caches. And while there's a
little bit that compilers can do and
that's what we're going to talk about in
this rest of this video for the most part,
if programmers want to get good cache
performance, they have to understand the
behavior of the cache is on the machine
and have to understand what their program
is doing, you have to understand a little
bit about what the compiler is capable of
doing and then they still have to , write
the program in such a way that is going
to, to be cache friendly. So, it's still
very much an open question. How much a
compiler can do to improve cache
performance? Although, there are a few
things that we've found compilers can do
reliably. So, to see one of those things
that compilers can actually do let's take
a look at this example loop. So, what we
have here, we have an outer loop on j and
inner loop on i and then in each iteration
of the inner loop we're reading from ,
some vector you know, performing some
computational net value and storing the
results into the ith element of the A
vector. Now, as it turns out, this
particular program has really, really
terrible cache performance. This is going
to behave very badly. And so, let's think
about what's going to happen. So, let's
imagine our cache, you know, as some block
of memory, okay. And so, what's going to
happen here. I mean, what's, what's the
first iteration going to be? Well, we're
going to, you know load and, store some
function of that into . And so, what's
going to get loaded into the cache is and
. All right, let's assume they just go
into different elements in this just for
the sake of argument, let's say they land
in the first two elements in the cache.
And then we're going to do the second
iteration of this and, we'll, we'll load
and write it into and so and will be
loaded into the cache, all right and so
on. And this will repeat over and over and
over again, loading one element of a and
one element of b the important thing to
notice is that all of these references to
a and to b are misses, okay. Every single
one of these is a cache miss because on
each iteration of the loop we refer to new
elements, okay. So, we're not referring to
the same elements as we were on the
previous ones. So, now let's ignore for
the moment the fact that there may be
multiple elements in the same cache line,
okay. So, some of you probably are aware
already. That when we fetch data from
memory we don't just fetch the one word,
okay. So, typically when we refer to for
example you know, is stored here will
fetch an entire cache line which will be
some block of memory and that may well
have, you know, other elements of b in it.
So, we might get a couple other elements
of b into the cache at the same time but
the important thing here is that on every
iteration of the loop, we're referring to
fresh data, okay. And, and if these data
values are large enough, if they take up
an entire cache line, then each iteration
of the loop is going to be a cache miss
for both elements, and we won't get any
benefit of the cache. And this loop will
run at the rate of at the rate of the main
memory and not at the rate of the cache.
Now, the other thing that's important here
is that this loop bound here is very large
and I picked it to be very large to
suggest that it's much larger than the
size of the cache. So, as we get towards
the end of the loop what's going to happen
is we will have filled up the whole cache,
so this whole cache will be filled with
values from a and b, and then it's going
to start clobbering values that are
already in the cache. And if this loop,
you know, if the size of these vectors,
let's say twice the size of the cache by
the time we come around and complete the
entire execution of the. Inner loop.
What's in the cache is the second half of
the a and b arrays, it's not the first
half of the a and b arrays. And so, then
when we go back around and execute another
iteration of the outer loop, now what's in
the cache is also, going to be not the
data that we're referencing. And so when
we come back around and begin the
execution of the inner loop the second
time. And we refer to and, and, and .
What's in the cache is the values from the
high numbered elements of the a and b
vector and not the low numbered elements.
And so, these references are all misses
again. And so, the, the basic problem with
this loop is, a loop that's structured
like this, is that almost every memory
reference and if, and if the data values
are big enough again that they fill an
entire cache line then it will be every
single memory reference is a cache miss.
Now, instead, let's consider an
alternative structure for the same
program. Here, I've put the i loop at as
the outer loop and the j loop as the inner
loop. And here what we do is we load . And
we write and then we repeat that
computation ten times on the same data
values. And so here we'll get excellent
cash performance. We'll, we'll have a miss
on the first reference, but then on the
subsequent nine references the data will
be in the cache or will completely exhaust
our computation on those particular a and
b values. And then we'll go on to the next
a and b values. We'll finish the inner
loop and go on to the other and do one
more iteration of the outer loop. And so,
the advantage of this structure is that it
brings the data into the cache and then it
uses that data as much as possible, before
going on to the next data. Rather than
doing a little bit on every data item and
then going back, you know, doing one pass
and then going back and sweeping over all
items, items again and doing another
little bit. Alright, so this particular
structure, where we've exchanged the order
of the outer loops sorry, exchanged the
order of the inner and outer loops, it
computes exactly the same thing but it has
much better cache behavior. And it
probably run more than ten times faster.
Now compilers can preform this simple loop
interchange optimization. This particular
kind of optimization is called loop
interchange, where you just switch in the
order of loops. In this particular case,
it's very easy to see that that's legal
and the compiler could actually figure it
out. Not many compilers actually implement
this optimization because in general, it's
not easy to decide whe ther you can
reverse the orders of, of the loops. And
so usually, a programmer would have to
figure out that they wanted to do this, in
order to improve the performance in the