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.



      “These violent delights have violent ends.”    
      ― William Shakespeare, Romeo and Juliet