Skip to main content
Logo image

Dive Into Systems: Exercises

Suzanne J. Matthews, Tia Newhall, Kevin C. Webb

Section 11.4 Caching

Checkpoint 11.4.1. Cache Block Size.

    Consider the following snippet of C code.
    int scores[100];
int i;
for (i = 0; i < 100; i++) {
    scores[i] = 0;
}
    Which of the following cache block sizes would offer a better cache hit rate (considering only access to the scores array)?
  • 16-byte block
  • Incorrect.
  • 32-byte block
  • Correct!
  • There is no significant difference in performance.
  • Incorrect.
  • It depends on the level of the cache
  • Incorrect.

Checkpoint 11.4.2. Cache Blocks.

    Consider a statically allocated 2D int array in C, declared as int array[3][3] that is initialized by a program in some way, such that its contents in memory are the following:
    Memory address | Data
0x FF00 0BB0   |    1
0x FF00 0BB4   |    2
0x FF00 0BB8   |    3
0x FF00 0BBC   |   10
0x FF00 0BC0   |   20
0x FF00 0BC4   |   30
0x FF00 0BC8   |  100
0x FF00 0BCC   |  200
0x FF00 0BD0   |  300
    During execution, data from consecutive memory addresses are loaded into the CPU cache in 16-byte blocks. Assuming the array is copied into the cache starting from element array[0][0]. Which array values are included in the second block loaded into the cache?
  • 1
  • Incorrect.
  • 2
  • Incorrect.
  • 3
  • Incorrect.
  • 10
  • Incorrect.
  • 20
  • Correct!
  • 30
  • Correct!
  • 100
  • Correct!
  • 200
  • Correct!
  • 300
  • Incorrect

Checkpoint 11.4.3. Cache Reads and Writes.

    For which type of memory access does the data need to be in the CPU cache?
  • Read
  • Incorrect.
  • Write
  • Incorrect.
  • Both Read and Write
  • Correct!
  • It depends on the speicifc memory location.
  • Incorrect.

Checkpoint 11.4.4. Direct Mapped Caches.

    Which of the following defines a direct-mapped cache?
  • It has only one set.
  • Incorrect.
  • It has only one line per set.
  • Correct!
  • It has only one byte per block.
  • Incorrect.
  • None of the above.
  • Incorrect.

Checkpoint 11.4.5. Cache Performance.

    If your program contains a lot of spatial locality, which of the following would likely have the best performance?
  • A cache with a small number of big blocks
  • Correct!
  • A cache with a large number of small blocks
  • Incorrect.
  • A cache with a large amount of metadata
  • Incorrect.

Checkpoint 11.4.6. Set Associative Caches.

    Which of the following is TRUE about CPU caches?
  • One memory address will map to multiple sets
  • Incorrect.
  • Multiple memory addresses will map to a single set
  • Correct!
  • Both A and B
  • Incorrect.
  • Neither A nor B
  • Incorrect.
  • It depends on whether the cache is direct-mapped or set-associative
  • Incorrect.

Checkpoint 11.4.7. Cache Hits.

    Which of the following must be checked in order to determine if there is a cache hit? Select ALL that apply.
  • The set index
  • Correct!
  • The tag
  • Correct!
  • The valid bit
  • Correct!
  • The dirty bit
  • Incorrect.
  • The block offset
  • Incorrect.

Checkpoint 11.4.8. Address Bits.

    Assume that you have memory address X. Which of the following is guaranteed to be true about the memory address X+1?
  • It will have the same set index as X
  • Incorrect. If the byte offset of X contains all 1’s, adding +1 to x will increase the index by one, which will map X+1 to a different set.
  • It will have the same tag as X
  • Incorrect. If the byte offset and index of X contains all 1’s, adding +1 to x will increase the tag by one.
  • Both A and B
  • Incorrect.
  • Neither A nor B
  • Correct!

Checkpoint 11.4.9. Address Bits and Caching.

    Which of the following is a consequence of using the least significant bits of a memory address for the block offset?
  • It’s easier to determine if there is a hit.
  • Incorrect.
  • A single block will contain consecutive memory addresses.
  • Correct!
  • There are fewer bits needed for the tag.
  • Incorrect.
  • More than one of the above.
  • Incorrect.
  • None of the above.
  • Incorrect.

Checkpoint 11.4.10. Cache Access.

    Which of the following must be checked in order to determine if there is a cache hit? Select ALL that apply.
  • The set index
  • Correct!
  • The tag
  • Correct!
  • The valid bit
  • Correct!
  • The dirty bit
  • Incorrect.
  • The block offset
  • Incorrect.

Checkpoint 11.4.11. Cache Access.

    Which of the following would you need to know to determine the number of bits in a CPU cache’s tag field?
  • The size of the cache blocks.
  • Correct!
  • The total number of sets.
  • Correct!
  • The number of bits in a memory address.
  • Correct!

Checkpoint 11.4.12. Write-through vs Write-back.

    Which of the following types of caches requires a dirty bit?
  • Write-back cache
  • Correct!
  • Write-through cache
  • Incorrect.
  • Both A and B
  • Incorrect.
  • Neither A nor B
  • Incorrect.

Checkpoint 11.4.13. Compulsory Misses.

    Which of the following determines whether a cache miss is a compulsory miss?
  • The exact address being accessed has never been accessed before
  • Incorrect.
  • The exact tag being accessed has never been accessed before.
  • Incorrect.
  • The exact tag and index being accessed has never been accessed before.
  • Correct!
  • None of the above.
  • Incorrect.

Checkpoint 11.4.14. Set Associative Caches.

    Set associative caches will tend to have fewer of which types of cache misses? Select ALL that apply.
  • Compulsory
  • Incorrect.
  • Capacity
  • Incorrect.
  • Conflict
  • Correct!

Checkpoint 11.4.15. Set Associative Caches.

    True or False: Set associative caches require more metadata than direct-mapped caches
  • True
  • Correct!
  • False
  • Incorrect.

Checkpoint 11.4.16. Cache Replacement Policy.

    The LRU cache replacement policy says that the block to be evicted should be the one that is...?
  • The oldest one
  • Incorrect.
  • The one accessed the least frequently
  • Incorrect.
  • The one with its dirty bit set
  • Incorrect.
  • The one accessed the longest ago
  • Correct!

Checkpoint 11.4.17. Direct Mapped Caches.

    For a direct mapped cache, which of the following is true of two different memory addresses that have the same value for their index bits:
  • They are adjacent in memory and will be loaded into cache as part of the same block.
  • Incorrect.
  • They map to the same cache line.
  • Correct!
  • They access data at the same relative location within their cache blocks.
  • Incorrect.
  • None of the above.
  • Incorrect.

Checkpoint 11.4.18. Direct Mapped Caches.

    For a direct mapped cache, which of the following is true of two different memory addresses that have the same value for their tag bits:
  • They are adjacent in memory and will be loaded into cache as part of the same block.
  • Incorrect.
  • They map to the same cache line.
  • Incorrect.
  • They access data at the same relative location within their cache blocks.
  • Incorrect.
  • None of the above.
  • Correct!

Checkpoint 11.4.19. Direct Mapped Caches.

    For a direct mapped cache, which of the following is true of two different memory addresses that have the same value for their block offset bits:
  • They are adjacent in memory and will be loaded into cache as part of the same block.
  • Incorrect.
  • They map to the same cache line.
  • Incorrect.
  • They access data at the same relative location within their cache blocks.
  • Correct!
  • None of the above.
  • Incorrect.

Checkpoint 11.4.20. Cache Organization.

For each of the following statements, select the cache organization for which the statement is true.

(a) Part A.

    Reduces cold-start misses
  • Direct-mapped cache
  • Incorrect.
  • Set associative cache
  • Incorrect.
  • Neither
  • Correct!
  • Both
  • Incorrect.

(b) Part B.

    Reduces conflict misses
  • Direct-mapped cahce
  • Incorrect.
  • Set associative cache
  • Correct!
  • Neither
  • Incorrect.
  • Both
  • Incorrect.

(c) Part C.

    Faster to locate data in a cache
  • Direct-mapped cahce
  • Correct!
  • Set associative cahce
  • Incorrect.
  • Neither
  • Incorrect.
  • Both
  • Incorrect.

Checkpoint 11.4.21. Cache Lookup and Address Bits.

(a)

(b)

Part B Order the portions below to reflect how they are used in a memory address to perform a cache lookup:

Checkpoint 11.4.22. Factors that Affect the Tag Size.

    Which of the following are accurate descriptions of the number of tag bits for a direct mapped cache:
  • \(log_2 (x)\) where x is the number of distinct memory regions that map to a given cache line.
  • Correct!
  • The number of bits in the address that are not index or offset bits.
  • Correct!
  • The number of tag bits is equal to the sum of the index bits and the offset bits.
  • Incorrect.
  • The number of tag bits is \(log_2(x)\) where x is the number of bits in the address.
  • Incorrect.
  • The number of tag bits is equal to the number of lines in the cache.
  • Incorrect.

Checkpoint 11.4.23. Fully Associative Cache.

    True or false: The tag of a fully associative cache is the entire memory address.
  • True
  • Incorrect.
  • False
  • Correct! If the block size is larger than 1, then the tag will be smaller than the full memory address.

Checkpoint 11.4.24. Cache Configuration Effects.

(a)

(b)

(c)

Checkpoint 11.4.25. Hits/Misses.

Let A, B, C, D, E, and F be memory addresses that have the same index but different tags.
If these addresses are accessed in this order: ABCDEFABCDEF
What is the number of misses for:
· A direct mapped cache? /12
· A 2-way set associative cache? /12
· A 4-way set associative cache? /12
Assume that the cache is initially empty (all blocks are marked invalid) and associative caches use LRU replacement.

Checkpoint 11.4.26. Hits/Misses.

Let A, B, C, D, be memory addresses that have the same index but different tags.
If these addresses are accessed in this order: ABCDABCD
What is the number of misses for:
· A direct mapped cache? /8
· A 2-way set associative cache? /8
· A 4-way set associative cache? /8
Assume that the cache is initially empty (all blocks are marked invalid) and associative caches use LRU replacement.

Checkpoint 11.4.27. Hits/Misses.

Let A, B, C, D, be memory addresses that have the same index but different tags.
If these addresses are accessed in this order: AABBCCDDAABBCCDD
What is the number of misses for:
· A direct mapped cache? /16
· A 2-way set associative cache? /16
· A 4-way set associative cache? /16
Assume that the cache is initially empty (all blocks are marked invalid) and associative caches use LRU replacement.

Checkpoint 11.4.28. Hits/Misses.

Let A, B, C, D, E, and F be memory addresses that have the same index but different tags.
If these addresses are accessed in this order: EFFEDCBAABCD
What is the number of misses for:
· A direct mapped cache? /12
· A 2-way set associative cache? /12
· A 4-way set associative cache? /12
Assume that the cache is initially empty (all blocks are marked invalid) and associative caches use LRU replacement.
PrevTopNext