Caches are important to providing a high$-$performance memory hierarchy to processors. Below is a list of $64-$bit memory address references, given as word addresses.

$0$x$03,0$xb$4,0$x$2$b$,0$x$02,0$xbf$,0$x$58,0$xbe, $0$x$0$e$,0$xb$5,0$x$2$c$,0$xba, $0$xfd

For each of these references, identify the binary word address, the tag, and the index given a direct$-$mapped cache with $16$ one$-$word blocks. Also list whether each reference is a hit or a miss, assuming the cache is initially empty.

For each of these references, identify the binary word address, the tag, the index, and the offset given a direct$-$mapped cache with two$-$word blocks and a total size of eight blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty.

You are asked to optimize a cache design for the given references. There are three direct$-$mapped cache designs possible, all with a total of eight words of data:

C$1$ has $1-$word blocks,C$2$ has $2-$word blocks, andC$3$ has $4-$word blocks.

Problem $2.$

For a direct$-$mapped cache design with a $64-$bit address, the following bits of the address are used to access the cache.

TagIndexOffset$63-109-54-0$

What is the cache block size $($in words$)?$

How many blocks does the cache have?

What is the ratio between total bits required for such a cache implementation over the data storage bits?

Beginning from power on$,$ the following byte$-$addressed cache references are recorded.

AddressHex$00041084$E$8$A$04001$E$8$CC$1$CB$4884$Dec$041613223216010243014031001802180$

For each reference, list $(1)$ its tag, index, and offset, $(2)$ whether it is a hit or a miss, and $(3)$ which bytes were replaced $($if any$).$

What is the hit ratio?

List the final state of the cache, with each valid entry represented as a record of $.$ For example,

$<0,3,$ Mem$[0$xC$00]-$ Mem$[0$xC$1$F$]>$

Problem $3.$

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.

$0$x$03,0$xb$4,0$x$2$b$,0$x$02,0$xbe, $0$x$58,0$xbf$,0$x$0$e$,0$x$1$f$,0$xb$5,0$xbf$,0$xba, $0$x$2$e$,0$xce

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.

Figure $5\mathrm{.}18$ The implementation of a four$-$way set$-$associative cache requires four comparators and a $4-$to$-1$ multiplexor.

Trace the behavior of the cache from part $($a$).$ Assume a true LRU replacement policy. For each reference, identify

the binary word address,the tag,the index,the offsetwhether the reference is a hit or a miss, andwhich tags are in each way of the cache after the reference has been handled.

Sketch the organization of a fully associative cache with one$-$word 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.

Trace the behavior of the cache from part $($c$).$ Assume a true LRU replacement policy. For each reference, identify

the binary word address,the tag,the index,the offsetwhether the reference is a hit or a miss, andthe contents of the cache after each reference has been handled.

Sketch the organization of a fully associative cache with twoword 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.

Trace the behavior of the cache from part $($e$).$ Assume an LRU replacement policy. For each reference, identify

the binary word address,the tag,the index,the offsetwhether the reference is a hit or a miss, andthe contents of the cache after each reference has been handled.

Repeat part $($f$)$ using MRU $($most recently used$)$ replacement.

Repeat part $($f$)$ using the optimal replacement policy $($i$.$e$.,$ the one that gives the lowest miss rate$).$