--- title: "Set associative mapping" subject: "Computer Organization and Architecture" chapter: 6 key: "semester_5/computer_organization_and_architecture:set-assoc-mapping" source: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/set-assoc-mapping site: BCT Engineering --- # Set associative mapping Computer Organization and Architecture · Chapter 6: Memory System - Asked in: 2073 Shrawan, 5 marks - Video: [Set Associative Mapping](https://www.youtube.com/watch?v=KhAh6thw_TI) — Neso Academy - 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/set-assoc-mapping - Whole chapter: https://www.bctengineer.com/md/semester_5/computer_organization_and_architecture/chapter-6 ## Question Describe how set associative mapping combines the features of direct and associative mapping techniques. ## Short answer Set associative mapping divides cache into sets, each with k lines. A block maps to a fixed set (direct mapping) but can occupy any line within the set (associative mapping); tags of the k lines are compared in parallel. This reduces conflict misses compared to direct mapping while using only k comparators. ## Answer Set associative mapping divides the cache into **sets**, each with k lines (k-way). It combines direct mapping (a block maps to one fixed set, found by index) with associative mapping (inside the set the block may go to any of the k lines). #### How it combines the two | Feature | From direct mapping | From associative mapping | |---|---|---| | Choosing the place | Set number = block mod number of sets (like the line index) | - | | Placement inside the place | - | Any line of the set, tags of the k lines are compared in parallel | | Search cost | Only k comparators, not one per line | Associative search within the set | | Replacement | - | Needed only inside the set (LRU, FIFO) | ```text Address (16 bits) +-----------+---------+--------+ | Tag 11b | Set 3b | Word 2b| +-----------+----+----+--------+ | +---------v---------+ | Set i: way0 way1 | 2-way: compare 2 tags +---------+---------+ v hit / miss ``` Example (2-way): 16 lines in 8 sets of 2. Blocks 0, 8 and 16 all map to set 0, but two of them can be present together; the third needs a replacement (LRU/FIFO) within that set. - **Merits:** fewer conflict misses than direct mapping, cheaper than fully associative (only k comparators). - **Demerits:** more complex than direct mapping, and a replacement algorithm is needed inside each set. Special cases: k = 1 gives direct mapping, and k = number of lines (one set) gives fully associative mapping. A 2-way or 4-way cache gives most of the hit ratio of associative mapping at a cost near direct mapping. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In set associative mapping, which feature is taken from direct mapping? A. A block may go to any line of the cache B. A block maps to one fixed set given by block mod number of sets C. No replacement algorithm is needed D. One comparator per cache line is used Answer: B. The set is chosen like a direct-mapped index: set = block mod number of sets. (Key point: Direct part of set associative) 2. Inside the chosen set, where can the block be placed? A. Only in line 0 of the set B. Only in the line given by the tag C. In any of the k lines of the set D. In any line of the whole cache Answer: C. Within the set the placement is associative, so any of the k lines can hold the block. (Key point: Associative part) 3. What does set associative mapping become when k = 1? A. Fully associative mapping B. Direct mapping C. Write-through mapping D. Random mapping Answer: B. With one line per set each block has one possible line, which is direct mapping; k = all lines gives fully associative. (Key point: Special cases) 4. Why is set associative mapping cheaper than fully associative mapping? A. It needs no tags B. It never needs replacement C. Only k comparators are needed per set instead of one per line D. It stores blocks in main memory Answer: C. Only the k tags of the selected set are compared, and replacement is needed only inside the set. (Key point: Cost and replacement) ## Related in Computer Organization and Architecture - [Associative vs set associative mapping](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Aassoc-vs-setassoc) — 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 - [Cache mapping techniques](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Acache-mapping-techniques) — Computer Organization and Architecture, chapter 6, asked 7× - [Cache management; direct vs associative address structure](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Adirect-vs-assoc-address) — 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 ## Related in other subjects - [Cache memory mapping techniques](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Acache-mapping-techniques) — Embedded System, chapter 4, asked 3× - [Associative cache mapping](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aassociative-cache-mapping) — Embedded System, chapter 4, asked 2× - [Direct, iterative methods; Gauss-Seidel numerical](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Adirect-iterative-gauss-seidel) — Computational Techniques in Civil Engineering, chapter 2