Name: 15.キャッシュオブリビジュアブルなアルゴリズム (15. Cache-Oblivious Algorithms)
Uploaded: 2021-01-14T10:26:46.000Z
Duration: 1 h 21 min 47 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

ANNOUNCER: The following content is provided under a Creative

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

Who remembers what a cache oblivious algorithm is?

So what is a cache oblivious algorithm oblivious to?

So a cache oblivious algorithm is an algorithm

that automatically tunes for the cache size on your machine.

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

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

Last time we talked about one cache oblivious algorithm

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

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

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,

So how many of you have seen differential equations before?

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

So here it says the partial derivative of u with respect

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

And you can see that we have a single derivative

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

people will come up with these differential equations just

And then they want to come up with efficient code

to actually simulate the physical process.

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.

Yellow is the hottest and blue is the coldest.

And then afterwards we're going to run it

And then the heat is going to diffuse to the neighboring

So after you run it for a couple of steps,

you might get the configuration on the right

And oftentimes, you want to run this simulation

for a number of time steps until the distribution of heat

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

But all the ideas generalize to higher dimensions.

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

then this might possibly be a stable distribution.

you might get a stable distribution of heat

So how do we actually write code to simulate this differential

So one commonly used method is known as finite difference

字幕リスト動画再生

15.キャッシュオブリビジュアブルなアルゴリズム (15. Cache-Oblivious Algorithms)

sort

constant

term

negative