Page 54 - Computer_Science_F5

(b) Fully associative mapping
Any block of main memory can be loaded into any line of the cache. If all lines are
occupied, a replacement algorithm like Least Recently Used (LRU) or First Come, Chapter One: Computer architecture
First Serve (FCFS) are used. The physical address is compared with all stored
FOR ONLINE READING ONLY
addresses in the cache. Block number
The physical address Tag
is divided as shown
in Figure 1.44. When
data is requested, the Compare with all stored Block Block / line
Offset
incoming memory addresses in cache memory
address is compared Address found Access main memory if
with all stored addresses block not found in cache
in the cache. If a match Address not found
is found, data is read;
otherwise, it is fetched Access location
from the main memory. Figure 1.44: Fully associative mapping

(c) Set-associative mapping
The cache is divided into sets, each containing a fixed number of lines (k-way set-
associative mapping). Each main memory block maps to a specific set, and within
that set, it can occupy any line.

For, Example: In a 3-way set-associative cache with 12 lines, there are 4 sets (12/3).
A main memory block’s set number is determined by:
Cache set number = (Block Address of the main memory) Modulo (Number of sets in cache)

Block 0
Tag Line 0 Block 1

Set-0 Tag Line 1 Block 2
Tag Line 2

Tag Line n Block m
Set-K Tag Line n+1 Block m+1
Tag Line n+2 Block m+2
Cache Block m+3

Main memory
Figure 1.45: 3-way set associative

45
Student’s Book Form Five

Computer Science Form 5.indd 45 23/07/2024 12:32