Locating a Block in the Cache

---

This slide considers the task of finding a block in the following three caches:

Direct-Mapped Cache

The three portions of an address in a set-associative or direct-mapped cache include

Tag Index Block offset

• the index is used to select the set,
• the tag is used to choose the block by comparison with the blocks in the selected set, and
• the block offset is the address of the desired data in the block.

Set-Associative Cache

The figure shows the implementation of a four-way set-associative cache requires four comparators and a 4-to-1 multiplexor. The comparators determine which element of the selected set (if any) matches the tag.

The output of the comparators is used to select the data from one of the four blocks of the indexed set, using a multiplexor with a decoded select signal.

Fully Associative Cache

There is effectively only one set, and all the blocks must be checked in parallel. Thus, there is no index, and the entire address, excluding the block offset, is compared against the tag of every block. In other words, we search the entire cache without any indexing.