## Subtitles section Play video

• ANNOUNCER: The following content is provided under a Creative

• Your support will help MIT Open Courseware

• 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

• In contrast, a cache-aware algorithm

• would actually know the parameters of the cache sizes

• 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.

• 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.