Name: 14. Caching and Cache-Efficient Algorithms
Uploaded: 2020-03-29T16:17:22.000Z
Duration: 1 h 18 min 23 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

The following content is provided under a Creative

Your support will help MIT OpenCourseWare

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

So we've talked a little bit about caching before,

but today we're going to talk in much more detail about caching

and how to design cache-efficient algorithms.

So first, let's look at the caching hardware

They all have their own private L1 caches

for both the data, as well as the instruction.

And then they share a last level cache, or L3 cache,

They're all connected to a memory controller

And then, oftentimes, you'll have multiple chips

So here we have a bunch of multicore chips

So we can see that there are different levels of memory

And the sizes of each one of these levels of memory

So the sizes tend to go up as you move up

The L1 caches tend to be about 32 kilobytes.

In fact, these are the specifications for the machines

So 32 kilobytes for both the L1 data cache

so the L2 cache tends to be about 8 to 10 times

And then the last level cache, the size is 30 megabytes.

So this is typically on the order of tens of megabytes.

And then DRAM is on the order of gigabytes.

And nowadays, you can actually get machines

So the associativity tends to go up as you move up

The time to access the memory also tends to go up.

So the latency tends to go up as you move up

So the L1 caches are the quickest to access,

about two nanoseconds, just rough numbers.

it's about an order of magnitude slower-- so 50 nanoseconds

And the reason why the memory is further down in the cache

using more expensive materials to manufacture these things.

But since they tend to be more expensive, we can't fit as much

So that's why the faster memories are smaller

But if we're able to take advantage of locality

in our programs, then we can make use of the fast memory

And we'll talk about ways to do that in this lecture today.

There's also the latency across the network, which

tends to be cheaper than going to main memory

but slower than doing a last level cache access.

to get the cache coherence protocols right, as we

So since these processors all have private caches,

So we talked about the MSI cache protocol before.

And there are many other protocols out there,

and you can read more about these things online.

and there's a lot of verification involved

in trying to prove that the cache coherence protocols are

So let's talk about the associativity of a cache.

So here I'm showing you a fully associative cache.

a cache block can reside anywhere in the cache.

And a basic unit of movement here is a cache block.

In this example, the cache block size is 4 bytes,

Subtitles ListPlay Video

14. Caching and Cache-Efficient Algorithms

entire

assume

access

constant