cache3

ECE463/563Fall `18
Basic Cache Operation, cont.: replacement policies, write policies, victim cachesProf. Eric Rotenberg
1
Fall 2018
ECE 463/563, Microprocessor Architecture, Prof. Eric Rotenberg
Generic Cache
The same equations hold for any cache typeEquation for # of blocks in the cache:Equation for # of sets in the cache:Fully-associative: ASSOC = # blocks
Generic Cache (cont.)
way 0
set 0
set 1
set 2
set 3
set 4
set 5
set 6
set 7
way 0
set 0
set 1
set 2
set 3
way 1
way 0
set 0
way 1
way 2
way 3
way 4
way 5
way 6
way 7
Generic Cache (cont.)
What this means for your Project 1 simulatorYou don’t have to treat the three cache types differently in your simulatorSupport a generic N-way set-associative cacheDon’t have to specifically worry about the two extremes (direct-mapped / fully-associative)Also, question: “How do I specify ‘fully-associative’ in the simulator command-line arguments?”You don’t specify this explicitlyInstead, just specify ASSOC to be equal to SIZE/BLOCKSIZE (the number of blocks)
Replacement Policy
Which block in a set should be replaced when a new block has to be allocated?LRU (Least-Recently-Used) is common (or cheaper variants such as pseudo-LRU)Others: FIFO, Random, more advanced policies
LRU Implementation
Small counter per block in set# bits in each counter = log2(ASSOC)Each block’s counter indicatesrecencyof access w.r.t. other blocks’ countersFor example: If a set has four blocks, each block gets a 2-bit counter. The block with “0” (b’00) counter was most-recently referenced, the block with “1” (b’01) was second-most-recently referenced, … and the block with “3” (b’11) was least-recently referenced overall.If access hits in cache:Increment the counters of other blocks whose counters are less than the referenced block’scounter (i.e., shift theseformerly“more-recent” blocks to now be “less-recent” than the referenced block)Set the referenced block’s counter to “0” (now the most-recently-used)If access misses in cache:Replace the LRU block (the block with counter “3”) and set the newly allocated block’s counter to “0” (now the most-recently-used block)Increment the counters of all other blocks
LRU Example
Blocks A, B, C, D, and E all map to the same setTrace: A B C D D D B D E(LRU counters are shown in parentheses)
(0)
(2)
(1)
(3)
(1)
(3)
(2)
A(0)
(2)
B(0)
(3)
A(1)
(3)
B(1)
C(0)
A(2)
D(0)
B(2)
C(1)
A(3)
D(0)
B(2)
C(1)
A(3)
D(0)
B(2)
C(1)
A(3)
D(1)
B(0)
C(2)
A(3)
D(0)
B(1)
C(2)
A(3)
D(1)
B(2)
C(3)
E(0)
Handling Writes
Two questionsThewrite updatequestion:Suppose there is a write request to a memory block that is cached in a given cache C. Is just C’s copy of the block updated with new data, or is the next level of the memory hierarchy updated at the same time?Thewrite allocatequestion:Suppose there is a write request to a memory block that isnotcached in a given cache C. Do we bring the missing block into C (i.e., do we “allocate” the block)?
The Write Update Question (1)
Write-through (WT) policy
cache
next level in memory hierarchy
The Write Update Question (2)
Write-back (WB) policy
cache
next level in memory hierarchy
The Write Update Question (3)
Write-back (WB) policyWhat happens when a block previously written to needs to be replaced?Need to have a “dirty bit” (D) with each block in the cache: set it when block is written toWhen a dirty block is replaced, need to write entire block back to next level of memory (“writeback”)
The Write Update Question (4)
Write-back (WB) policy
cache
next level in memory hierarchy
D
replacement of a dirty block causes writeback
The Write Allocation Question (1)
Write-Allocate (WA)Bring the block into the cache if the write misses (handled just like a read miss)Typically, used with write-back policy: WBWAWrite-No-Allocate (NA)Do not bring the block into the cache if the write missesTypically,used with write-through policy: WTNA
The Write Allocation Question (2)
WTNA (scenario: the write misses)
cache
next level in memory hierarchy
write miss
The Write Allocation Question (3)
WBWA (scenario: the write misses)
cache
next level in memory hierarchy
write miss
D
Victim Cache
Small fully-associative cache that sits alongside main cacheE.g., holds 2-16 cache blocksManagement is slightly “weird” compared to conventional cachesWhen main cache evicts (replaces) a block, the victim cache will take the evicted (replaced) blockThe evicted block is called the “victim block”When the main cache misses, it searches the victim cache for recently evicted blocks. A victim cache hit means the main cache doesn’t have to go to the next level of memory hierarchy for the block.
Victim Cache Example
2-entry victim cacheInitially holds blocks X, YY is the LRU block in the victim cacheMain cache is direct-mappedBlocks A and B map to the same set in main cacheTrace: A B A B A B…
X
Y (LRU)
A
L1 cache
victim cache
X (LRU)
A
B
L1 cache
victim cache (VC)
B misses in L1 and evicts A, A goes to VCand replaces Y (previous LRU), X becomes LRU
X (LRU)
B
A
L1 cache
victim cache (VC)
A misses in L1 but hits in VC, so A and Bswappositions:A is moved from VC to L1, and B (the victim) goes to VC where A waslocated (note – we don’t replace the LRU block, X, in case of VC hit)
Victim Cache – why?
Direct-mapped caches suffer badly from repeated conflictsVictim cache provides illusion of set-associativityA poor-man’s version of set-associativity