Select Page

Computer Organization

Memory Organization
Interrupt
DMA Controller

# K-way Set Associative Mapping

It is a mixture of Direct and Fully associative mapping.

• Total No. of Set= Total No. of lines/K
• Here K is K-way Set Associative
• For 2-way set associative (K=2)
• Total No. Of Set = 4/2 = 2 sets (S0, S1)

Which block will be in which line? It Is calculated by the formula K MOD N.  Here “K” is Block Number and “N” is the Total number Set in Cache.

For example

• If the Block No =0 then (0 MOD 2) = 0 It means Block 0 will be in Set 0.
• and If Block No =7 then (7 MOD 2) = 1 It means Block 7 will be in Set 1.
• and If the Block No =10 then (10 MOD 4) = 0 It means Block 10 will be in Set 0.

So,

```The one of the following block will be in set zero (S0) in any line L0 or L1 at a time
B0, B2, B4, B8,……,B28, B30
The one of the following block will be in set one (S1) in any line L2 or L3 at a time
B1, B3, B5, B7,………. ,B29, B31```

When cache have 4 lines and consider 2-way set associative

Searching for a block through Tag (Cache Hit or miss)

Suppose CPU generates an address 0011000 for 128-word main memory.

The first two bits (00) represent Block offset, the next one bit (0) is use to represents set number. And the last four bits (0011) represent the Tag in Cache memory.

As tag bits of CPU address is not matching with tag bits of any line of Set S0. So it is a cache miss case.

## Numerical Problems

Formulas for K-way

• Physical address = Tag + set +block offset
• Comparator value in k-way set associative is = (k-value) – (tag bit). e.g (7-8) means that 7 lines of a set is compared with 8-bits of tag.

Q1. If the cache size is 64KB and Block/line size is 8B then how many bits are required to represent lines of 4-way set associative cache memory?

Total lines = Cache size/ Block size = 64KB/8B = 213B

So 13 bits are require to represent lines in cache.

Total bits for set = Total lines / K-way = 213B/22 = 211

So 11 bits are require to represent sets in cache.

Q2. If we found 10 bits for Set in 4-way set associative and block size is 16 kb. Then Cache size will be.

Cache size in K-set associative = total set * total lines per set * line size

Cache size = 210  *4* 214 B= 64 MB.

Problem 01:

Problem 02: A 4-way set associative cache memory with a capacity of 16KB is build using a block size of 8 words. The word length is 32 bits. The size of physical address space is 4GB. Find the no of bits for the Tag field.

Block size = 8×4 Bytes = 32 B = 25B

No of Sets in Cache = Size of Cache/ Block Size* K-way = 4KB/25B*4 = 27B

Physical Address Space = 4GB = 232 B

So According to Formula

Physical Address space = Tag + Total no. of sets + Block Size

232 B = Tag + 27B + 25B

Tag = 220B

So, 20 Bits are require to represent the tag number

Advantage: Comparison time is reduce as compared to fully associative

Disadvantage: Some Conflict miss factor involves.

Example

A person who has to live in one room is direct mapping. It is very easy to find him. But there is a restriction for him to not move anywhere. Fully associative means a person can live anywhere in Pakistan so searching time is increase but restriction removed and k-way tells us a person can live in one state in the country.

Help Other’s By Sharing…