--- title: "Associative cache mapping with example" subject: "Computer Organization and Architecture" chapter: 6 key: "semester_5/computer_organization_and_architecture:assoc-cache-example" source: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/assoc-cache-example site: BCT Engineering --- # Associative cache mapping with example Computer Organization and Architecture · Chapter 6: Memory System - Asked in: 2072 Kartik, 6 marks - Video: [Cache Mapping Fully Associative Mapping](https://www.youtube.com/watch?v=vWxtmci1Nko) — TutorialsPoint - 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-cache-example - Whole chapter: https://www.bctengineer.com/md/semester_5/computer_organization_and_architecture/chapter-6 ## Question Explain associative cache mapping with example. ## Short answer In associative mapping, a main-memory block can be placed in any cache line. The address splits into Tag and Word; all tags are compared in parallel. Example: with 4 lines and block sequence 12,7,40,7,25,12, blocks 12 and 40 coexist despite mapping to the same direct-mapped line. Misses occur only when cache is full, requiring replacement. ## Answer In 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. #### Example with numbers Cache has 4 lines; blocks requested in order: 12, 7, 40, 7, 25, 12. ```text Request Result Cache (line0..3 after request) 12 miss 12 - - - 7 miss 12 7 - - 40 miss 12 7 40 - 7 hit 12 7 40 - 25 miss 12 7 40 25 12 hit 12 7 40 25 ``` Every block was loaded in the first free line, and the tags (the block numbers) of all four lines are compared at once for each request. Blocks 12 and 40, which would clash in a direct-mapped cache of 4 lines (both map to line 0), stay together here. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In associative mapping, where can a main-memory block be stored? A. In one fixed line B. In any cache line C. Only in a free set D. Only in line 0 Answer: B. Any block can go in any cache line. (Key point: Associative placement) 2. What are the address fields in associative mapping? A. Tag | Line | Word B. Tag | Set | Word C. Tag | Word D. Line | Word Answer: C. The tag is the full block number, so only Tag and Word fields exist. (Key point: Address format) 3. How is a hit detected? A. Only one line's tag is checked B. The tag is compared with all line tags in parallel C. The tag is compared with main memory D. A counter is searched Answer: B. A content-addressable search compares all tags at once; a match is a hit. (Key point: Tag comparison) 4. Why do blocks 12 and 40 coexist in the 4-line associative cache, although they clash in a direct-mapped cache? A. They both map to line 0 here B. Any line may hold any block, so they use different lines C. The tag is ignored D. Block 40 is never loaded Answer: B. Direct mapping sends both to line 0; associative mapping loads each in a free line. (Key point: Example numbers) ## Related in Computer Organization and Architecture - [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 - [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× - [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× - [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 - [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 ## 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× - [Cache memory mapping techniques](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Acache-mapping-techniques) — Embedded System, chapter 4, asked 3×