Associative Mapped Cache – Problem 1

In this example we analyze a cache memory that uses Associative Mapping. The goal is to determine which RAM frames and which byte numbers are currently stored in the cache.

Given Information

Cache uses Associative Mapping
Cache has 4 lines
Each RAM frame size = 4 bytes
Each cache line therefore stores 4 bytes
The physical address is divided into Tag + Offset
Tag field size = 5 bits

Because the frame size is 4 bytes, the offset must identify one of the four bytes inside the frame. Therefore:


Offset bits = log2(4) = 2 bits

Since the tag contains 5 bits, the RAM contains:


Number of frames = 2^5 = 32 frames

Cache Content (Tags Stored in Cache)

Cache Line	Tag (Binary)	Frame Number (Decimal)
Line 0	01101	13
Line 1	10111	23
Line 2	00011	3
Line 3	01011	11

The frame numbers are obtained by converting the binary tag into decimal.

Bytes Stored in Each Cache Line

Each frame contains 4 bytes, therefore each cache line stores 4 contiguous bytes from RAM.

Cache Line	Frame Number	Bytes Stored
Line 0	13	52, 53, 54, 55
Line 1	23	92, 93, 94, 95
Line 2	3	12, 13, 14, 15
Line 3	11	44, 45, 46, 47

The first byte of each frame is calculated as:


First Byte = Frame Number × Frame Size

Example:


Frame 23

23 × 4 = 92

Bytes stored:
92
93
94
95

Cache Hit Condition

If the CPU generates a physical address whose byte number corresponds to one of the bytes stored in the cache table above, the result is a:


Cache Hit

If the requested byte is not present in any cache line, the result is a:


Cache Miss

Key Learning Points

Associative mapping allows any frame to be stored in any cache line.
The physical address is divided into Tag + Offset.
The tag uniquely identifies the frame stored in a cache line.
Each cache line contains multiple contiguous bytes from RAM.
A cache hit occurs when the requested byte exists in the cache.

Introduction