Now, we're going to do our last topic in 
our memory and caches section. 
We're going to talk about program 
optimizations that considered cache. 
Okay. 
So the optimization code for the memory 
hierarchy has, you know, essentially 
boils down to write code that has better 
locality. 
Okay. 
That has better locality properties. 
And remember, there are two types of 
locality spatial locality and temporal 
locality. 
Okay . 
And spatial locality, what we want to do 
is symmetrically access data contiguously 
as much as possible. 
Even lays out data in memory in a way 
that increases . 
the spatial locality properties. 
And the second one is temporal locality. 
Make sure the algorithm, the code should 
make sure that if there's a data item 
that's going to be accessed multiple 
times, try to access them closer in time. 
So you can take advantage of temporal 
locality and increase the likelihood that 
the data is going to be in the cache... 
And ways of achieving that, there's 
multiple ways. 
Two basic ones, one is a proper choice of 
algorithm. 
Of course the algorithm itself determines 
a lot of the, how the data is laid out 
and the order of operations in the data. 
And the second one is loop 
transformations. 
How to reorder loops when you're 
traversing data structures. 
So let me give you an example that's 
going to showcase how important this is. 
When we talk about matrix multiplication. 
In matrix multiplication, what happens is 
for example, suppose that i have a matrix 
c that multiplier by multiplication 
between matrix a and matrix b. 
So this element here of c which is 
element i, j is equals. 
First column of the ith row of a 
multiplied by the first row of column j 
in matrix b plus this one times this one 
plus this one times this one, this one 
times this one and so on. 
Okay. 
So that means that the, this loop here, I 
don't want to read the corner detail 
because it's going to be it's going to be 
hard for you. 
So, but, what you need to understand is 
that this code is reading this, reading 
this, and then reading this, then reading 
this, then reading this, then reading 
this. 
And so on. 
It's going to read the entire row of a 
and this entire column of b. 
Just to produce a single element in, in 
c. 
Okay? 
So this is a matrix that's n by n 
elements, okay? 
So we're going to do n squared of these 
operations. 
Okay? 
So it's a lot. 
It could, specially if the matrix as big, 
this could be a lot of operation. 
So now, let's look at Cache Miss Analysis 
of this matrix duplication, okay? 
We are going to assume that matrix 
elements are doubles, o they take 8 
bytes. 
And if our cache block is 64 bytes, each 
cache line, each cache block holds 8 
doubles. 
Let's also say that our cache size c, 
capital c it's much smaller than, than n. 
'Kay, which is the dimension of our, our 
which is our dimension of our matrix. 
The dimension of our matrix n by n. 
So let's see what happens in the first 
situation. 
Remember, in the first situation we're 
going to be arranging entire row of this 
matrix and entire columns of this matrix, 
okay. 
So one thin to keep your mind to, the way 
data's laid out in memory. 
What we're doing is, we are storing an 
entire row in memory, then another row, 
then another row. 
Then another row, and so on. 
So, let's say if this is row zero, row 
one, row two, and row three. 
The way it's laid out in memory here. 
Is we're going to have entire row zero, 
then entire row one, entire row two, 
entire row three. 
And so on. 
'Kay, so the number of misses that we're 
going to have is going to be, what, it's 
going to be n divided by 8. 
Because as we're reading this one line 
here, we know that, since each line here, 
each cache line, each cache block has. 
Eight doubles. 
So like, 1, 2, 3, 4, 5, 6, 7, 8. 
We go back to the first one's going to be 
a miss. 
Then the second one's going to hit, a 
hit, a hit, a hit, a hit, a hit, and then 
the next one here is going to be a miss. 
So that's why it's n divided by 8. 
Okay, that's taking advantage of that, 
because of spacial locality, we're taking 
only n over 8. 
'Kay? 
Now, we're going to add n here because 
for each column here, 'kay? 
So each, each for each column here we're 
going to, so for this column here, for 
each row of this column, we're going to 
have a cache miss, right? 
We're going to mess up this one and then 
this one, this one, this one, this one, 
so forth. 
Like all of them, because. 
Just this is, bigger than a block. 
Remember that if the cache is much 
smaller than n, definitely a blocks much 
smaller than n. 
So, and then when we are done with the 
saturation, only this part and this part 
is going to be in the cache. 
And why is it? 
It is because we just read the first 
element, and everything else, we didn't 
read. 
Okay? 
Great. 
So we're going to have 9n over 8 misses 
for the first iterations. 
Now, if we extend this to all of the 
other iterations, what we're going to do 
is going to have 9n over 8 misses 
multiplied by n squared, which is the 
number of iterations. 
Remember that we're going to do this, 
this is n. 
By n, and we're do this for each one of 
the elements here, so that means there's 
n square elements. 
So this, that means that our final cache 
miss the number of cache misses is 9 over 
8, multiplied by n squared, so it's a lot 
of cache misses. 
'Kay? 
So one way to solve this problem is to do 
what we call a blocked matrix 
multiplication. 
So instead of doing an entire row and 
entire column, were going to do this 
block by block, okay. 
Such that we're going to, when we read a 
part of a here, we're going to read. 
All of these. 
And then for b here, instead of reading 
just, just the first one we're going to 
need, we're going to read multiple rows, 
'kay? 
But smaller, in a subset of the row, such 
that this stays in cache and this stays 
in cache. 
'Kay? 
And then when we need to cycle over this 
multiple time we're not going to have to 
take the miss again. 
Isn't that cool? 
So, now lets, let's do a, cache miss 
analysis of this one, okay? 
So now how many blocks are we going to 
have? 
Well we're going to have n over b blocks, 
because b is the size of the block, okay? 
So, and we know that three blocks fits in 
the cache. 
Kay, so and, and that means that 3b 
squared is smaller than the cache size c. 
So, now, what we're going to have is, 
we're going to have b squared over 8 
misses for each block, right? 
Because we have this repeatedly. 
And then. 
so if we do, when, when we add this up, 
we're going to have 2n over b times b 
squared over 8 which then, which ends up 
being nb over 4 misses. 
So now, in the end, after it went in the 
cache, we're going to have, is we're 
going to have all of this, because we 
access all of these blocks that happen to 
fit in the cache. 
Great. 
So, now this is the first iteration. 
When we do this over all iterations you 
know, all these are going to be the same 
as the first one. 
We are going to do this. 
But now, since we are dividing we do this 
in blocks, now we are doing n over b 
squared. 
That would be, because were going to do 
this one for each block but were going to 
do it a few times were going to do n over 
b times square. 
So in the end what were going to do is 
our caching is going to be n squared 
divided by 4b so there's a huge impact in 
our cache miss. 
So in summary, if we don't do blocking 
we're going to have 9 over 8 n squared 
misses, but if we do blocking it's going 
to be 1 over 4b multiplied by n squared 
misses. 
Okay. 
So if B equals 8, the difference is 36 
times. 
If B is 16, the difference number of 
misses is 72x. 
It's just really, really, really big. 
Okay? 
So, and the reason for dramatic 
difference is that, makes the duplication 
inherently has temporal locality. 
But you have to reorder the operation in 
order to take advantage of that. 
Okay. 
So they put data is 3n squared. 
In the computations 2 and cube, so every 
element is accessed, order and times. 
Okay. 
But the program really has to be written 
properly otherwise the different 
localities are too far apart in time and 
the cache can't capture it. 
Okay. 
So... 
The important thing to re, to keep in 
mind for cash friendly code is that the 
programmer, you, can optimize code for 
case performance. 
But it really depends on how the data 
structures are organized, how data are 
accessed How the loop nest structure 
works is think about blocking. 
Because blocking is a general technique. 
You can always try to reorganize how the 
order that you do things. 
That you try to keep a dully of blocks. 
Only parts of it in memory. 
Okay. 
So and one thing to keep in mind is that 
all systems like cache-friendly code but 
to get absolutely optimum performance 
really depends on the platform. 
Because it depends on knowing the actual 
cache organization cache geometry. 
Things like cache sizes, line sizes, 
associativities and so on. 
'Kay. 
So you can get most of the advantage with 
generic code. 
'Kay. 
So not, when you're writing generic code, 
just keep in mind that keep working set 
size reasonably small so it fits in the 
cache and you take advantage of temporal 
locality. 
Uses small strides so you take advantage 
of spatial locality, right, because it's 
to be close by. 
And focus on inner loop codes because 
those are the ones that are going to be 
accessed close by in time, okay. 
Let's edge our, memory and caches 
section, what we call the Memory 
Mountain. 
Okay, this is, this is very cool. 
Okay, we are, we are, we ran some 
experiments in Intel core I7, okay. 
And what we're showing you here in the 
access in, is read through put, megabytes 
per second. 
So that means, up is good, is better, 
okay. 
And our one cache is 32 kilobytes, so and 
this is the working set size which grows 
this way, and the stride size grows this 
way, okay. 
First thing to notice, as you increase 
the stride size, you see there's a 
general drop in throughput, because 
you're not taking as much advantage of 
temporal locality. 
Now, the other thing is if you go, if you 
increase the working set size, if it fits 
in the L1 cache you'll have really, 
really good high through put... 
But then as the, as this doesn't fit in 
the L1 cache, now we're going to drop to 
the other plateau here which is whatever 
fits in the L2. 
And then the next plateau is whatever 
fits in the L3, whatever doesn't fit here 
in L3, have to go to memory. 
Isn't that cool? 
So, that means if you keep the working 
set size as much higher, as low as small, 
there's much higher chance to stay within 
the L1 which is good. 
Or with the L2, and so on. 
So things to keep in mind is, take 
advantage of spatial locality, so you 
keep the stride low. 
Take advantage of the working set size, 
you can do blocking to keep to focus on 
the working side size for reachable parts 
of your code. 
Okay. 
And if you keep it small, you're going to 
get very high throughput. 
It has a huge impact on performance. 
This concludes out memory and caches 
section, and I'll see you soon.