--- title: "Associative mapping and replacement algorithms" subject: "Computer Organization and Architecture" chapter: 6 key: "semester_5/computer_organization_and_architecture:associative-mapping" source: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/associative-mapping site: BCT Engineering --- # Associative mapping and replacement algorithms Computer Organization and Architecture · Chapter 6: Memory System - Asked in: 2074 Asoj, 8 marks - Video: [Associative Mapping](https://www.youtube.com/watch?v=uwnsMaH-iV0) — 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/associative-mapping - Whole chapter: https://www.bctengineer.com/md/semester_5/computer_organization_and_architecture/chapter-6 ## Question Explain associative mapping technique. Give reasons why a replacement algorithm is required in the associative mapping technique. ## Short answer Fully associative mapping allows a block to be placed in any cache line; the tag is compared with all lines in parallel. It avoids thrashing but requires a replacement algorithm when the cache is full because there is no fixed location for the incoming block. ## Answer #### 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. #### Why a replacement algorithm is required - In associative mapping any block can go to any line, so when a miss occurs and **all lines are full**, the hardware must choose which existing block to remove. There is no fixed line for the new block as in direct mapping. - A good choice keeps blocks that will be used soon. Common algorithms: - **LRU:** replace the block unused for the longest time (best, uses locality). - **FIFO:** replace the oldest block loaded. - **LFU:** replace the block with the fewest references. - **Random:** replace any line. - The algorithm must be implemented in hardware to keep the cache fast. A poor choice reduces the hit ratio. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In the example, what is the tag? A. The full block number (14 bits) B. The line number C. The set number D. The 2-bit word field Answer: A. Address is Tag | Word, tag = block number. (Key point: Tag) 2. How is a hit checked? A. Only one line is checked B. The tag is compared with all line tags in parallel C. Tags are compared one after another from line 0 only D. Only the word field is compared Answer: B. This is content-addressable searching. (Key point: Comparison) 3. Why is a replacement algorithm needed? A. Each block has a fixed line B. To speed up comparison C. To shorten the tag D. Any line can hold the block, so when the cache is full one must be chosen to evict Answer: D. With no fixed line a victim must be chosen. (Key point: Why replacement) 4. What does LRU replace? A. The block unused for the longest time B. The oldest loaded block C. The block with fewest references D. A random block Answer: A. LRU uses locality; FIFO is oldest, LFU fewest references. (Key point: LRU) ## Close variants set in other exams - [Why direct mapping needs no replacement](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Adirect-no-replacement) — Computer Organization and Architecture, chapter 6, asked 2× ## Related in Computer Organization and Architecture - [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 - [Mapping function and replacement algorithm](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Amapping-replacement) — 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 - [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 - [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× - [Reasons for replacement; strategy from AEC table](https://www.bctengineer.com/question.md?key=semester_6%2Fengineering_economics%3Areasons-replacement-aec-table-12) — Engineering Economics, chapter 5, asked 2× - [Cache write policy and replacement algorithm](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Acache-write-policy-replacement) — Embedded System, chapter 4