2
$\begingroup$

I don't quite understand the concept of spatial locality in cacheing. I understand that on a cache miss, not only the specific address we want is loaded into the cache, but also "nearby addresses" are loaded too.

However, I can't understand WHICH addresses are loaded. I have an assignment with the following question:

The cache consists of 16 words (4 bytes for each word), and is arranged in blocks of 2 words each.
The following addresses are in BYTES in decimal base. The cache is initially empty.
12,8,24,28,36,44,48,52,60,64,68,76,136,140,144,148,152,220,224,228,220,224,228
Determine what are the addresses which are a MISS (determine whether it's a valid or a tag miss).

What is hard for me is to understand which addresses are loaded, when, for example, the address 12 is reached. Is 13 loaded into the cache? 14? 15? or maybe 11? How do I know that?

I think that if understand this fundamental question, I could answer this question with ease.

$\endgroup$
3
$\begingroup$

When inserting an entry in the cache, an entire block of addresses is copied. In your case 2 words (8 bytes) are inserted.

So when address 12 is reached, the block of 8 bytes having address 12 is inserted into cache.

Likewise in case of subsequent misses a maximum of 8 such "blocks" can be inserted into cache, after which eviction process shall start. Further sequence of cache hits/misses shall depend on the eviction policy.

$\endgroup$
  • $\begingroup$ thank you. You're saying that 8 bytes are loaded because there are 2 words in the block? Also, why isn't 11,10,9 and 8 aren't loaded? Does it only go forward with the loading? Thank you! @user1990169 $\endgroup$ – Alan Sep 20 '14 at 12:20
  • $\begingroup$ Hi, sorry to bother you again but I asked this question on electronic exchange and got this answer: electronics.stackexchange.com/questions/130029/… - who's right? $\endgroup$ – Alan Sep 20 '14 at 13:41
  • 1
    $\begingroup$ @Alan yes the other answer is correct. You have to first decide as to which block in main memory matches with which block in cache and accordingly copy it. $\endgroup$ – Abhishek Bansal Sep 20 '14 at 14:14
1
$\begingroup$

Cache works at the granularity called "cache lines" which are loaded to the cache when ever any byte in the line is accessed. For example if the line size is 8 bytes, and you read byte at address 12, then all bytes from 8 to 15 are loaded to the cache.

There is more to the story though called "associativity" that influences the data kept in the cache. In your assignment due to the order the addresses are accessed the associativity doesn't change the answer, but it's good to be aware of this trait to better understand cache behavior. For example if there was byte at address 12 addressed at the end of the sequence then associativity would influence the answer to your assignment.

There is "fully associative" cache where any cache line address in the memory can reside in any location in the cache. This is the most efficient policy regarding the use of cache memory but also the most costly regarding performance. There is also the opposite "direct mapped" caching policy where memory addresses are directly mapped to addresses in the cache (e.g. for cache size of 64 bytes first "address mod 64" is calculated and that's used to determine the location in the cache) and thus each memory address has effectively only one valid location in the cache. This is the most wasteful policy regarding cache space but most efficient performance-wise. Then there is "N-way associative" caching policy that's the compromise between the two and the mostly used caching policy in practice, where each memory address can reside in N locations in the cache. In N-way associative cache the cache is split to N direct mapped caches and search for the line is performed between the N locations in these caches upon memory access.

The associativity plays a role when new data is loaded to the cache and thus some other data must be evicted from the cache. Normally caches use "least recently used" (LRU) eviction policy, i.e. for the valid cache line locations (determined by the associativity) in the cache, the line that was accessed the longest time ago is evicted.

$\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.