In the textbook fully associative lookup model, the memory organization used…

Concept

Associative memory, also called content-addressable memory, is searched by matching a supplied tag against stored tags rather than by supplying a storage address. In a fully associative design, comparison hardware checks every stored tag in parallel. A set-associative design first selects one set and then compares the tag with all ways in that set in parallel.

Application

1. Suppose the virtual page number is 42 and the fully associative TLB stores tags 7, 19, 42, and 86; the entry tagged 42 maps to physical page number 105.

2. The comparison hardware checks 42 against all four stored tags at the same time, producing no match, no match, match, and no match respectively.

3. The matching entry returns physical page number 105; the page offset passes through unchanged, so this translation avoids a page-table memory access.

Cross-check and contrast

• “cache memory” with “one-by-one comparison” combines the cache role with a sequential lookup mechanism.

• “cache memory” with “simultaneous comparison” captures parallel lookup but does not name the content-addressable organization requested by the stem.

• “associative memory” with “one-by-one comparison” names the organization but pairs it with a sequential mechanism.

• “associative memory” with “simultaneous comparison” states both the organization and the fully associative lookup mechanism.

Therefore, in the fully associative textbook model, the TLB is an associative memory in which the search item is compared with all stored keys simultaneously. Real processors may instead use set-associative TLBs; there, comparison is simultaneous among the ways of the selected set, so “set-associative” is a specific associative organization rather than a contradiction.