$5\mathrm{.}11$ This exercise examines the effect of different cache designs, specifically comparing associative caches to the direct$-$mapped caches from Section $5\mathrm{.}4.$ For these exercises, refer to the sequence of word address shown below.

$003,0b4,02b,002,0$xbe,$058,0xbf,0x0e,01f,$

$0b5,0xbf,0ba,0x2e,0$xce

$5\mathrm{.}11\mathrm{.}1[10]$$$5\mathrm{.}4>$ Sketch the organization of a three$-$way set associative cache with two$-$word blocks and a total size of $48$ words. Your sketch should have a style similar to Figure $5\mathrm{.}18,$ but clearly show the width of the tag and data fields.

$5\mathrm{.}11\mathrm{.}2[10]$ $$5\mathrm{.}4>$ Trace the behavior of the cache from Exercise $5\mathrm{.}11\mathrm{.}1.$ Assume a true LRU replacement policy. For each reference, identify

the binary word address,

the tag,

the index,

the offset

whether the reference is a hit or a miss, and

which tags are in each way of the cache after the reference has been handled.

Sketch the organization of a fully associative cache with oneword blocks and a total size of eight words. Your sketch should have a style similar to Figure $5\mathrm{.}18,$ but clearly show the width of the tag and data fields.

$5\mathrm{.}11\mathrm{.}4[10]$$$5\mathrm{.}4>$ Trace the behavior of the cache from Exercise $5\mathrm{.}11\mathrm{.}3.$ Assume a true LRU replacement policy. For each reference, identify

the binary word address,

the tag,

the index,

the offset,

whether the reference is a hit or a miss, and

the contents of the cache after each reference has been handled.

Address

FIGURE $5\mathrm{.}18$ 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. In some implementations, the Output enable signals on the data portions of the cache RAMs can be used to select the entry in the set that drives the output. The Output enable signal comes from the comparators, causing the element that matches to drive the data outputs. This organization eliminates the need for the multiplexor.