Commons license.

Your support will help MIT Open Courseware

continue to offer high quality educational resources for free.

To make a donation or to view additional materials

from hundreds of MIT courses, visit MIT OpenCourseWare

at ocw.mit.edu.

JULIAN SHUN: All right.

So today we're going to talk about cache

oblivious algorithms.

Who remembers what a cache oblivious algorithm is?

So what is a cache oblivious algorithm oblivious to?

Cache size.

So a cache oblivious algorithm is an algorithm

that automatically tunes for the cache size on your machine.

So it achieves good cache efficiency.

And the code doesn't need to have any knowledge of the cache

parameters of your machine.

In contrast, a cache-aware algorithm

would actually know the parameters of the cache sizes

on your machine.

And the code would actually put the size of the cache inside.

So today we're going to talk a lot more about cache oblivious

algorithms.

Last time we talked about one cache oblivious algorithm

that was for matrix multiplication.

And today we're going to talk about some other ones.

So first example I want to talk about

is simulation of heat diffusion.

So here's a famous equation known as the heat equation.

And this equation is in two dimensions.

And we want to simulate this function

u that has three parameters t, x, and y. t is the time step.

X and y are the x, y coordinates of the 2D space.

And we want to know the temperature for each x,

y coordinate for any point in time t.

And the 2D heat equation can be modeled

using a differential equation.

So how many of you have seen differential equations before?

OK.

So good, most of you.

So here I'm showing the equation in two dimensions.

But you can get similarly equations

for higher dimensions.

So here it says the partial derivative of u with respect

to t is equal to alpha.

Alpha is what's called the thermo diffusivity.

It's a constant times the sum of the second partial derivative

of u with respect to x, and the second partial derivative of u

with respect to y.

So this is a pretty famous equation.

And you can see that we have a single derivative

on the left side and a double derivative on the right side.

And how do we actually write code

to simulate this 2D heat process?

So oftentimes in scientific computing,

people will come up with these differential equations just

to describe physical processes.

And then they want to come up with efficient code

to actually simulate the physical process.

OK.

So here's an example of a 2D heat diffusion.

So let's say we started out with a configuration on the left.

And here the color corresponds to a temperature.

So a brighter color means it's hotter.

Yellow is the hottest and blue is the coldest.

In on the left we just have 6172,

which is the course number.

So if you didn't know that, you're

probably in the wrong class.

And then afterwards we're going to run it

for a couple time steps.

And then the heat is going to diffuse to the neighboring

regions of the 2D space.

So after you run it for a couple of steps,

you might get the configuration on the right

where the heat is more spread out now.

And oftentimes, you want to run this simulation

for a number of time steps until the distribution of heat

converges so it becomes stable and that

doesn't change by much anymore.

And then we stop the simulation.

So this is the 1D heat equation.

I showed you a 2D one earlier.

But we're actually going to generate code for the 1D heat

equation since it's simpler.

But all the ideas generalize to higher dimensions.

And here's the range of colors corresponding to temperature,

so the hottest colors on the left

and the coldest colors on the right.

And if you had a heat source that's

on the left hand side of this bar,

then this might possibly be a stable distribution.

So if you keep running the simulation,

you might get a stable distribution of heat

that looks like this.

OK.

So how do we actually write code to simulate this differential

equation?

So one commonly used method is known as finite difference

approximation.

So we're going to approximate the partial derivative of u

with respect to each of its coordinates.

So the partial derivative of u with respect to t

is approximately equal to u of t plus delta t

where delta t is some small value, and x, and then

minus u of tx.

And then that's all divided by delta t.

So how many of you have seen this approximation method

before from your calculus class?

OK, good.

So as you bring the value of delta t down to 0,

then the thing on the right hand side approach

is the true partial derivative.

So that's a partial derivative with respect to t.

We also need to get the partial derivative with respect to x.

And here I'm saying the partial derivative with respect

to x is approximately equal to ut of x plus delta

x over 2 minus ut of x minus delta x

over 2, all divided by delta x.

So notice here that instead of adding delta

x in the first term and not adding anything

in the second term, I'm actually adding delta x over 2

in the first term and subtracting text over 2

in the second term.

And it turns out that I can do this with the approximation

method.

And it still turns out to be valid as long as the two terms

that I'm putting in, their difference is delta x.

So here the difference is delta x.

And I can basically decide how to split up

this delta x term among the two things in the numerator.

And the reason why I chose delta x over 2 here

is because the math is just going to work out nicely.

And it's going to give us cleaner code.

This is just the first partial derivative with respect to x.

Actually need the second partial derivative

since the right hand side of this equation

has the second partial derivative.

So this is what the second partial derivative looks like.

So I just take the partial derivative with respect

to x of each of the terms in my numerator from the equation

above.

And then now I can actually plug in the value

of this partial derivative by applying the equation

above using the arguments t and x plus delta x

over 2, and similarly for the second term.

So for the first term when I plug it

into the equation for the partial derivative with respect

to x, I'm just going to get ut of x plus delta x minus utx.

And then for the second term, I'm

going to get ut of x minus delta x.

And then I subtract another factor of utx.

So that's why I'm subtracting 2 times utx in the numerator

here.

And then the partial derivative of each

of the things in a numerator also

have to divide by this delta x term.

So on the denominator, I get delta x squared.

So now I have the second partial derivative with respect to x.

And I also have the first partial derivative with respect

to t.

So I can just plug them into my equation above.

So on the left hand side I just have this term here.

And I'm multiplying by this alpha constant.

And then on this term just comes from here.

So this is what the 1d heat equation

reduces to using the finite difference approximation

method.

So any questions on this

So how do we actually write code to simulate this equation here?

So we're going to use what's called a stencil computation.

And here I'm going to set delta at x and delta t equal to 1,

just for simplicity.

But in general you can set them to whatever you want.