Hello, again. 
Now, we are ready to start a new section. 
What we are going to be seeing now is how 
we can use a special type of memory 
called caches to make the process of 
memory interaction faster. 
The process memory is actually very, very 
important for overall computer 
performance. 
So, understanding that is very, very 
important. 
So here's what we're going to see in this 
section. 
We're going to see the basics of caches, 
then we're going to understand why caches 
work. 
we're going to see how to put several 
caches together into a hierarchy. 
We're going to see how we organize caches 
In a way that makes them fast and 
effective. 
And finally, we're going to see how we 
can make software better at using caches. 
So, let's start with a question. 
So, how does execution time of this 
program go, grows with the value of size? 
So, in, in this example we have. 
We have an array with as many elements as 
the value of this size, the size define, 
and we have a variable called a. 
And all this is doing is adding the value 
of several of the array elements into a 
we're accumlating them into a. 
This inner loop here is iterating over 
the array repeatedly. 
Now as so it iterating over the entire 
array. 
And the outer loop is iterating over the 
entire array repeatedly. 
So we have an inner loop and an outer 
loop. 
Okay. 
So how to expect the plot of execution 
time to do with respect to size. 
Certainly this doesn't go down it 
probably goes up because as size goes as 
a value size, goes up this[INAUDIBLE] is 
going to take longer the because the 
inner loop is going to be longer. 
So let's see how it looks, so here's the 
actual data of this experiment. 
Okay. 
So we had was here's time, and here's 
size. 
And there's two interesting things to 
note here. 
First is, there's a knee in this curve, 
here. 
Okay, there's a knee here. 
And then there's too other essentially 
flatlines here. 
And, and they don't have exactly the same 
slope. 
So at some point, there's some threshold 
that makes, that after you go above the 
threshold in size, the execution time 
grows. 
Faster, so something is getting slower as 
we grow the value of size. 
Distance height turns out to be exactly 
the cashes. 
If the array, if the array fits in cash 
entirely we're going to have a slope as 
long as it does not fit in cash any more 
we're going to start to have to go memory 
more often. 
Then your going to have a different 
curve. 
We have a different slope. 
Okay. 
So and the problem here is that, there's 
this processor memory bottle neck that we 
need to address. 
And the reason this bottle neck exist is 
that the CPU it's self had it's 
performance growing every 18 months. 
Okay, growing very, very fast. 
That's why we have super fast computers 
today. 
And as we saw early on in this course, 
you see there was a dramatic increase in 
number of transistors. 
Dramatic increase in performance, and so 
on. 
Memory, although memory also evolved, it 
did not evolve as fast as the processor. 
Not the memory latency. 
Nor the, the bandwidth to move data in 
and out of the processor. 
So the, the problem here is that there's 
a lot of waiting fundamentally, right? 
If the process is getting faster, much 
quicker than memory's getting faster, 
that means the disparity is going up. 
It is also known as a memory wall. 
Okay? 
So, ultimately, the big problem is that 
there will be lots of waiting on memory. 
Processors do not like to wait. 
If they're waiting, they're wasting time, 
it hurts performance. 
But because memory, didn't get as fast, 
can it get fast enough compared to the 
processor that will be waiting? 
So how do we solve this problem? 
Well, what we're going to do is put this 
little bit of memory closer to the 
processor here, okay? 
Called the cache, okay? 
And that's going to hold data that's 
accessed frequently. 
And since the cache is smaller and closer 
to the processor, it's much much faster 
to access data stored in the cache. 
Okay? 
One of the reasons that caches are fast 
is because they are small. 
Right? 
Fundamentally[INAUDIBLE] speed of light, 
so if you make things small, it can make 
them fast. 
The larger you make them, fundamentally 
they're going to be slower. 
Okay? 
So let's think about the word cache for a 
second. 
The English definition is a hidden 
storage, space for, hidden storage space 
for provisions, weapons, or treasures. 
In our case, our treasure is data, okay? 
In Computer Science, the definition is a 
computer memory with short access time 
used for storage of data that's accessed, 
data or codes that's accessed, frequently 
or recently. 
'Kay? 
So and more generally the section used to 
optimize data transfers between system 
elements with different characteristics. 
Okay? 
You could imagine caches, you, you know 
we have a, a caches cache for pages in 
your browser's a form of cache. 
You can cash you know to disk, because 
disks are also not very fast. 
So if you access it repeatedly you can 
put data in a faster memory these, these 
are all forms of caches, okay? 
So let's see now have the general cache 
mechanics works. 
Okay, so we have our cache here. 
And we have memory. 
And memory's going to have a bunch of 
locations or blocks. 
And so, and the, the unit of transfer 
between memory and caches is this block. 
Okay? 
So that means we're now going to move a 
byte at a time. 
And we're going to see that actually 
helps us a lot. 
We're going to that why soon. 
But here see the, let's see the 
mechanics. 
Okay? 
So and one thing that's important to note 
here, by the way, is that the cache 
stores a subset of memory. 
Okay? 
So again, the reason that caches are fast 
is because they're small. 
So they're going to be much smaller than 
memory. 
So it can only hold a subset. 
Of the data stored in in memory. 
So the first concept is what we call a 
hit. 
'Kay. 
A hit means whenever you want to access 
the data. 
'Kay, let's say that the processor that's 
right here, 'kay, that's, that's where 
the CPU is, asks for 14. 
Well, it happens to be in the cache. 
We call a hit. 
It means that the data, the CPU asks for 
the data and then the cash can provide 
the data back. 
So that's much, that's fast, right, 
because we took advantage of, that's a 
good thing, right, we took advantage of 
the fact that caches are fast and 
provided that they're in the cache. 
This is in contrast to what we call a 
miss, so suppose that a data block these 
needed by the CPU here. 
Okay and we happen to need 12, so we're 
going to ask does it, is 12 here. 
Well, the answer is, no it's not. 
Okay so, it's a miss. 
So, what happens now? 
What do you think? 
Well, we're going to have to go to memory 
and get the data. 
So the cache requests 12 from memory, so 
the[INAUDIBLE] 12 is gotten, is obtained 
from memory. 
And then it gets transferred to the cash 
and now it's stored in the cache. 
And note, let me show you, notice 
something else got kicked out. 
What happened? 
Nine has to be kicked out. 
To store 12. 
We're going to see in detail later why 
this is this is important. 
And since the cache is finite I've had to 
kick things out. 
So, the choice of what's going to be 
kicked out is very, very important. 
Okay? 
So, one thing I don't want you to forget 
from this, this first video on caches, is 
that a cache is this little bit of very 
very fast memory in between CPU and lots 
of lower memory. 
'Kay? 
So we can give the CPU the illusion that 
memory is faster by putting a little bit 
of storage closer to it. 
'Kay? 
See you soon.