Locality of reference

Locality of reference refers to a phenomenon in which a computer

program tends to access same set of memory locations for a
particular time period. In other words, Locality of Reference refers to
the tendency of the computer program to access instructions whose
addresses are near one another. The property of locality of reference is
mainly shown by loops and subroutine calls in a program.
"In case of loops in program control processing unit repeatedly refers
to the set of instructions that constitute the loop.
" In case of subroutine calls, every time the set of instructions are
fetched from memory.
"References to data items also get localized that means same data item
is referenced again and again.

There are two main types of locality of reference:

SPATIAL LOCALITY

Spatial locality refers to the tendency of a program to access memory locations

that are close to each other.

Example: Consider an array in a program. If the program accesses array element 1,

it is likely to access elements 2, 3, and so on, in close proximity. This is spatial
locality because nearby memory locations are being used togethe.
TEMPORAL LOCALITY

Tenporal locality refers to the tendency of a program to access the same memory
locations repeatedly over a short period of time.
Example: If a program frequently uses a variable in aloop, the variable's memory
location will be accessed multiple times in a short time span. This is temporal
locality because the same memory location is being accessed repeatedly.

Mapping functions
Mapping functions help decide where data from the main memory will
be stored in the cache. This is important because the cache is much
smaller than the main memory, so it needs a strategy to manage the
placement of data efficiently.

Simple Processor Example:

Cache:
" Has 128 blocks (small storage units).
"Each block can store 16 words (a word is a small piece of data).
" Total cache size is 2048 words.

Main memory has a 16-bit address:

"The main memory (like your computer's RAM) is much larger
than the cache.
 Main memory has a 16-bit address:
"The main memory (like your computer's RAM) is much larger
than the cache.
"The main memory is organized in such a way that each piece
of data (word) has an address.
"Since the address is 16 bits long, there are 216 = 65,536
possible addresses in total.
"Main memory has 4K blocks of 16 words each.
"This means the main memory can store 65,536 words of data
(which is 64K words, where 1K(kilo) = 1024).

There are three different types of mapping used for the

purpose of cache memory which is as follows:
"Direct Mapping
"Associative Mapping
"Set-Associative Mapping

Direct mapping Block C

Block

Blocks from main memory are mapped

to specific locations in the cache. tag
Cach Block 127

Block 0 Block 128

Block I
The formula for this is: Block 129

Cache block = Main memory block number

mod Total number of cache blocks ag Block 127 Block 25S
Block 256
Block 257

Example:
Block 0 from memory goes to cache
block 0, block 129 from memory goes Block 4095

to cache block 1, and so on. Tas Block Word

Waru
Main memory address
74
Figure 5.15 Directmapped coche.

Example with the Formula:

[Link] memory block 0:
"Using the formula: 0 mod 128=0
"So, block 0 from the main memory is placed in cache block 0.
2. Main memory block 129:
"Using the formula: 129 mod 128 = 1
"So, block 129 from the main memory goes to cache block 1.
[Link] memory block 256:
"Using the formula: 256 mod 128 = 0
"So, block 256 from the main memory goes to cache block 0,
replacing the previous data from main memory block 0.
 4. Main memory block 130:
"Using the formula: 130mod 128=2
"So, block 130 from the main memory goes to cache block 2.

What's Happening?
Each main memory block has to fit into one of the 128 cache blocks.
The modulo operation (mod 128)ensures that the block number is
wrapped around to fit into one of the available cache blocks.
This means that multiple main memory blocks will map to the same
cache block. For example, blocks 0, 128, and 256 from the main
memory all map to cache block 0.

Memory Address Structure:

The memory address is divided into three fields:
"Word field :Low-order 4 bits select one of the 16 words in the block.
" Block field :Next 7 bits identify the cache block to store the data.
"Tag field: High-order 5 bits are the tag that helps identify which
specific block of memory is stored in the cache block.
Tag Block Word
4
Main memory address

cache.
Figure 5.15 Direct-mapped

Main
memory

Associative mapping Block 0

Block I

In this method, the main memory Cache

tay
block can be placed in any cache Block 0
tag
block position. Block 1

The tag bits of an address Block i

received from the processor are
tas
compared with the tag bits of Block 127

each block of the cache to see if

the desired block is present.
Block 4095
This is called associative
Word
mapping technique. Tag
12 4 Main memory address

Figure 5.16 Associative-mapped cache.

Memory Address Structure:

The memory address is divided into two parts:
"Word field (Low-order 4 bits): This identifies the specific word (data
unit) within a memory block (since each block can store multiple
words).
"Tag field (High-order 12 bits): This helps to identify the memory
block. When data from memory is stored in the cache, the tag helps
keep track of which block from memory is currently in the cache.

Tag Word

12 4 Main memory address

Figure 5.16 Associative-mapped cache.

 How It Works:
"When the processor needs data, it checks the cache first.
"The cache checks allof its blocks to see if the tag of any block
matches the required block from memory.
"If the tag matches, the cache provides the data (this is called
acache hit).
"If the tag doesn't match, the data block must be brought in
from the main memory (this is a cache miss).

Maim
ienary

Set-Associative Block0

Mapping Cache
Block 1

ag
A combination of direct Set Block 0
tag Block 6
Block

associative-mapping techniques can be Set

tag
Block 2
Block 64

Block 65
used. Block

Blocks of cache are grouped into sets, & Block 127

the mapping allows a block of the main Biock 126

Block 127
Block 128
Block 129
memory to reside in any of the specific
set.
Bock 409s

Main memory addres

Foure 5.17 Setassociativemopped coche with two blocks per set,

Memory Address Structure:

The memory address is divided into three fields:
"Word field: ldentifies the word within a block.
"Set field: ldentifies which set the memory block maps to.
"Tag field: ldentifies the memory block once it is in the cache.

Tag Set Word

6 6 4 Main memory address

Fiqure 5.17 Setassociative mapped cache with two blocks per set.

How it works
"When the processor checks the cache, it identifies the set using the
set field of the memory address.
"The tag bits are then compared to see if the desired memory block is
present in any of the blocks within the set.
"If a match is found, it's a cache hit, and the data is accessed.

Replacement Policy:
If all blocks in a set are full and a new memory block needs to be
loaded, one of the existing blocks is replaced using a replacement
algorithm like LRU (Least Recently Used) or FIFO (First-In-First-Out) or
Random Replacement.