--- title: "Cache mapping techniques" subject: "Computer Organization and Architecture" chapter: 6 key: "semester_5/computer_organization_and_architecture:cache-mapping-techniques" source: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/cache-mapping-techniques site: BCT Engineering --- # Cache mapping techniques Computer Organization and Architecture · Chapter 6: Memory System - Asked in: 2078 Kartik, 10 marks; 2076 Chaitra, 2 marks; 2075 Asoj, 6 marks; 2071 Chaitra, 6 marks; 2070 Asar, 6 marks; 2069 Chaitra, 2+6 marks; 2068 Baisakh (old course), 2+8 marks (asked 7 times) - Video: [Cache Memory Mapping – A Comparative Study](https://www.youtube.com/watch?v=e8RCnG2ibJk) — 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/cache-mapping-techniques - Whole chapter: https://www.bctengineer.com/md/semester_5/computer_organization_and_architecture/chapter-6 ## Question What is cache memory? Explain the different cache mapping techniques (direct, associative, set associative) with example and differentiate them. ## Short answer Cache memory is a small fast buffer holding recently used blocks, exploiting locality. Direct mapping places a block in one fixed line (simple but may thrash). Associative mapping allows any line (needs parallel tag compare and replacement). Set-associative maps to a set, balancing speed and flexibility. ## Answer Cache memory is a small, very fast memory placed between the CPU and main memory. It holds copies of the most recently used blocks of main memory, so that most CPU accesses are served at cache speed. It works because of locality of reference (temporal and spatial). Example system used below: main memory = 64K words (16-bit address), block size = 4 words, cache = 16 lines (64 words). Main memory has 16384 blocks. #### Direct mapping Each main-memory block can go to exactly one cache line: line number = (block number) mod (number of lines). The address is split into **Tag | Line | Word**. ```text Address (16 bits) +-----------+---------+--------+ | Tag 10b | Line 4b | Word 2b| +-----+-----+----+----+--------+ | | | +-----v------+ | | line 0 | tag | data | | line 1 | tag | data | | ... | | | line 15 | tag | data | +-----+------+ v v +--------------------+ | compare tag = ? |--> hit / miss +--------------------+ ``` Working: the line field selects one line, and the tag stored there is compared with the tag of the address. If the tags are equal (and the valid bit is set), it is a **hit**, and the word field picks the word. Otherwise it is a **miss**: the block is read from memory into that line, and the line's tag is updated. Example: blocks 0, 16, 32 of main memory all map to line 0 (block mod 16); block 5 maps to line 5; block 21 also maps to line 5. - **Merits:** simple and cheap hardware (only one comparator), fast lookup, no replacement algorithm needed. - **Demerits:** fixed location for each block, so two blocks that map to the same line keep replacing each other (thrashing) even when other lines are empty; lower hit ratio. #### Associative (fully associative) mapping A main-memory block can be placed in **any** cache line. The address is split into **Tag | Word**; the tag is the full block number. ```text Address (16 bits) +----------------------+--------+ | Tag 14b | Word 2b| +----------+-----------+--------+ | compare with ALL tags in parallel +------+-----------+------+ | line0| tag0 | data |--= ? | line1| tag1 | data |--= ? | ... | ... | ... |--= ? +------+-----------+------+--> hit / miss ``` Working: the tag is compared with the tags of all lines at the same time (associative or content-addressable memory). A match is a hit. On a miss the block is loaded into any free line; if the cache is full, a **replacement algorithm** (LRU, FIFO, LFU, random) chooses the line to remove. Example: with 16 lines, blocks 0, 16, 32 and 5 can all stay in the cache together, because any line can hold any block. - **Merits:** most flexible, best hit ratio, no thrashing. - **Demerits:** needs one comparator per line (costly, slow, more power), long tag, and a replacement algorithm. #### Set associative mapping The cache lines are grouped into sets. A block maps to one particular **set** (set number = block mod number of sets) but can be placed in **any line of that set**. The address is split into **Tag | Set | Word**. ```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. #### Comparison | Point | Direct | Associative | Set associative | |---|---|---|---| | Placement of a block | One fixed line | Any line | Any line in one fixed set | | Address fields | Tag, line, word | Tag, word | Tag, set, word | | Comparators | 1 | One per line | One per way (k) | | Replacement algorithm | Not needed | Needed | Needed within the set | | Hit ratio | Lowest | Highest | Between the two | | Hardware cost and speed | Cheapest, fastest | Costliest, slowest | Moderate | | Conflict misses | Many | None | Few | ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In direct mapping, to which line does block j go? A. Line = j mod (number of lines) B. Any line C. Any line in a set D. Line = j div number of lines Answer: A. Each block has exactly one possible line. (Key point: Direct mapping) 2. Which address split matches associative mapping? A. Tag | Line | Word B. Tag | Word C. Tag | Set | Word D. Line | Word Answer: B. The tag is the full block number so there is no line or set field. (Key point: Address fields) 3. How many comparators does a k-way set-associative cache use? A. 1 B. One per line in the cache C. k (one per way) D. None Answer: C. Only the k tags of the selected set are compared. (Key point: Comparators) 4. Which statement ranks hit ratio correctly? A. Direct highest, associative lowest B. All equal C. Set associative highest D. Direct lowest, associative highest, set associative between Answer: D. More placement freedom gives a higher hit ratio but higher cost. (Key point: Trade-off) ## Related in Computer Organization and Architecture - [Direct mapping with 32-block memory, 8-block cache](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Adirect-mapping-example) — Computer Organization and Architecture, chapter 6, asked 3× - [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 - [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 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 - [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× - [Cache write techniques](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Acache-write-techniques) — Embedded System, chapter 4