2
$\begingroup$

I've read that, incorporating many words(spatial locality) per cache blocks leads to lower miss rate. Is it the case always? One possibility of such approach is to make a single cache block of size equal to the size of the cache, but that would be meaningless as far as benefits of memory hierarchy are concerned. Isn't it so?

$\endgroup$
2
$\begingroup$

If you use larger blocks in the cache, it will mean having less blocks available (given fixed cache size). If the blocks are too large, part of them isn't used; if they are too small, there is much traffic loading them.

More than very general statements like the above, it is almost impossible to say anything unless considering some specific memory access traces. Real workloads access memory in definite patterns that moreover change in time. Look up the working set model.

$\endgroup$
2
$\begingroup$

Spatial (and temporal) locality are both heuristics. Many (in fact, most) algorithms run on data structures in some sequential manner, which many times means that the memory used is consecutive.

However, there are examples where spatial locality may actually be very bad. Perhaps the most common example is scanning a 2-dimensional array: consider an $n\times n$ array, then in the memory, it is represented as an $n^2$ length array, where the entry $i,j$ is in cell $i+n*j$.

If you scan the array row by row, then spatial locality is excellent, your cache will always prepare the next row. However, if you scan by column, then not only will you always get a miss, but using spatial locality, you will actually retrieve the same rows over and over.

$\endgroup$
  • $\begingroup$ Nice example! But how will you frame it in the context of cache? (I mean considering spatial locality per cache block). $\endgroup$ – Winn Mar 23 '14 at 7:04
  • $\begingroup$ I don't understand what you mean by "per cache block". Are you looking at a second level cache? $\endgroup$ – Shaull Mar 23 '14 at 7:36
  • 1
    $\begingroup$ Another example would be a structure with only one or two elements that are hot. One can use hot/cold separation with slab allocation to fit hot elements from multiple objects in a single cache block, but that can be just a statistical optimization. Array of structures vs. structure of arrays is similar to your 2D array example (e.g., the 179.art "hack"). $\endgroup$ – Paul A. Clayton Mar 23 '14 at 11:20
  • $\begingroup$ @Shaull I simply mean that, if more words(bytes) are placed per block, then we need less no. of blocks to design the cache, so in one sense it will help increase spatial locality, but in another sense wouldn't it create high latency to transfer such large blocks between adjacent levels, consequently producing more misses? $\endgroup$ – Winn Mar 24 '14 at 7:33
  • $\begingroup$ @Winn - indeed, this is the tradeoff when using cache. $\endgroup$ – Shaull Mar 24 '14 at 11:37
1
$\begingroup$

If you increase the size of the data imported into the cache, it obliterates an equal amount of data that is previously a part of the cache- your cache, at the end of the day, can accommodate only a given number of bytes. Considering the column based access of matrix elements example discussed previously by Shaull, if I make the size of data equal to number of columns that reduces the chance of a miss. However if the number of columns are so big that it can't fit in the cache you still have a miss despite increasing the cache-block size. So in a nutshell, not always but does the job most of the times as there are only a few applications with irregular data patterns and only data-intensive applications can fill up the cache so fastly that it needs to invalidate it's contents entirely for fetching new data. Hope that helps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.