ECM 1413 Cache & Virtual Memory

Question 1

Temporal Locality

Answer 1

Items accessed recently are likely to be accessed again soon (e.g. loops)
If you want to discard data, start with the one that has not been requested in a long time

Question 2

Spatial Locality

Answer 2

Items located near each other in memory are likely to be accessed within a short period of time (Most programs exhibit spatial locality)
Copy additional nearby memory locations into the cache

Question 3

A memory request may be a

Answer 3

• Cache hit - the cache contains the data (faster data return)
• Cache miss - the cache does not contain the requested data - first read from memory

Question 4

Cache designs

Answer 4

• Direct Mapping
• Fully-associative Mapping
• Set-associative Mapping

Question 5

Direct-Mapped Cache

Answer 5

Each block of main memory maps to one unique cache line
+Simple, easy to implement & search
-Inefficient use of the cache space

Question 6

Fully-Associative Cache

Answer 6

Each block of main memory can map to any line of the cache
Replacement Algorithm: LRU
+Flexible
-Takes a long time to search

Question 7

S-Way Set-Associative Cache

Answer 7

The cache is divided into N cache sets
Each cache set consists of S lines
Each block of main memory maps to one unique cache set
Replacement algorithm: LRU

Question 8

A write request may be a:

Answer 8

• Write hit - the address we want to write to is present in the cache
• Write miss - the address we want to write to is not present in the cache

Question 9

For a write hit, there are two options:

Answer 9

Write-back
Write-through

Question 10

Write-back:

Answer 10

initially write only to cache
Write into memory if being replaced
+fast writes
-mechanism for cache coherence

Question 11

Write-through

Answer 11

write into both cache and memory
+consistency between the cache and memory
-slow writes

Question 12

For a write miss, there are two options:

Answer 12

Write around
Write allocate

Question 13

Write around (no-write allocate):

Answer 13

Write into memory only
+Avoids unnecessary cache access and cache pollution
-Does not utilise temporal locality

Question 14

Write allocate:

Answer 14

write into both cache and memory
+exploits spatial and temporal locality
-Potential unnecessary cache access and cache pollution

Question 15

High temporal Locality indicates

Answer 15

Write-Back + Write-Allocate

Question 16

Low Temporal Locality indicates

Answer 16

Write-Through + Write-Around

Question 17

Virtual Memory

Answer 17

Use disk storage as if it was main memory

Analogy: Main memory is the cache of the disk

Question 18

Demand Paging

Answer 18

Only load a page when there is a request for it
+More processes can be loaded into memory
-Thrashing

Question 19

Pre-paging

Answer 19

Guesses which pages will be requested and pre-load them
+Less overhead when page predictions are accurate
-Resources are wasted on loading unused pages