---
title: "Associative vs set associative mapping"
subject: "Computer Organization and Architecture"
chapter: 6
key: "semester_5/computer_organization_and_architecture:assoc-vs-setassoc"
source: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/assoc-vs-setassoc
site: BCT Engineering
---

# Associative vs set associative mapping

Computer Organization and Architecture · Chapter 6: Memory System

- Asked in: 2070 Chaitra, 5 marks
- Video: [Associative and Set-Associative Cache Mappings](https://www.youtube.com/watch?v=OGDEsD3hdbk) — Jacob Schrum
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/assoc-vs-setassoc
- Whole chapter: https://www.bctengineer.com/md/semester_5/computer_organization_and_architecture/chapter-6

## Question

Differentiate between associative mapping and set associative mapping with example.

## Short answer

Associative mapping allows a block in any line, uses full tag and parallel comparison of all tags, highest hit ratio but costly. Set associative divides cache into sets; a block maps to a fixed set (by index) but any line within the set, requiring only k comparators. It reduces cost and conflict misses compared to direct mapping, with near-associative hit ratio for k≥4.

## Answer

| Point | Associative mapping | Set associative mapping |
|---|---|---|
| Placement | A block can go in any cache line | A block goes in one fixed set, any line of the set |
| Address format | Tag, word | Tag, set, word |
| Tag length | Longest | Shorter by the set bits |
| Comparators | One per line, all in parallel | k per set (k-way) |
| Hit ratio | Best | Slightly less, close for k = 4 or 8 |
| Cost and speed | Costly and slowest search | Cheaper and faster |
| Replacement | Over the whole cache | Within the selected set only |
| Conflict misses | None | Few |

#### Example
Main memory of 32 blocks (5-bit block number), cache with 8 lines, 2-way set associative; consider block 21 (10101).

- **Associative:** block 21 may go to any of the 8 lines; the 5-bit tag 10101 is compared with all 8 tags.
- **Set associative (2-way):** sets = 8/2 = 4. Set = 21 mod 4 = 1 (binary 01), tag = 21 div 4 = 5 (101). Block 21 can use either of the two lines of set 1; only 2 tags are compared. Blocks 1, 5, 9, 13, 17, 21, 25 and 29 all compete for the two lines of set 1.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How does block placement differ?
   A. Associative: one set; set associative: any line
   B. Associative: any line; set associative: fixed set, any line within it
   C. Both use one fixed line
   D. Both use any line of the cache
   Answer: B. Set associative restricts a block to one set. (Key point: Placement difference)

2. Which address format is set associative?
   A. Tag, word
   B. Tag, set, word
   C. Tag, line, word
   D. Set, word
   Answer: B. A set field is added, so the tag is shorter. (Key point: Address format)

3. Cache 8 lines, 2-way: for block 21, what is the set number?
   A. 0
   B. 1
   C. 2
   D. 5
   Answer: B. Sets = 4, and 21 mod 4 = 1. (Key point: Example calculation)

4. In 2-way set associative, how many tags are compared and where is replacement done?
   A. All 8 tags; whole cache
   B. 2 tags; within the set
   C. 1 tag; none
   D. 4 tags; whole cache
   Answer: B. Only the two lines of the set are compared and replacement is inside that set. (Key point: Comparators and replacement)

## Related in Computer Organization and Architecture

- [Set associative mapping](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Aset-assoc-mapping) — Computer Organization and Architecture, chapter 6
- [Write policy; direct vs associative mapping](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Awp-direct-vs-assoc) — Computer Organization and Architecture, chapter 6
- [Associative mapping and replacement algorithms](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Aassociative-mapping) — Computer Organization and Architecture, chapter 6, asked 2×
- [Associative cache mapping with example](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Aassoc-cache-example) — Computer Organization and Architecture, chapter 6
- [Replacement algorithm in associative mapping](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Areplacement-assoc) — Computer Organization and Architecture, chapter 6
- [Associative mapping technique](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Aassoc-mapping-explain) — Computer Organization and Architecture, chapter 6

## Related in other subjects

- [Associative cache mapping](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aassociative-cache-mapping) — Embedded System, chapter 4, asked 2×
- [TST vs STS; DTMF set pros and cons](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Atst-sts-compare-dtmf) — Telecommunications, chapter 4
- [Compaction vs coalescing; paging mapping](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Acompaction-coalescing-paging) — Operating System, chapter 4
- [Cache memory mapping techniques](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Acache-mapping-techniques) — Embedded System, chapter 4, asked 3×