A new company has proposed a number of different cache layouts for their system and you’ve
been asked to come in and calculate the overhead for each of the different caches. Their
system uses a cache with 512 B of data storage capable of addressing 4 GB of
byte-addressable memory. Stores will be handled by write-back and allocate-on-write policies.
Please be sure to show the work for your calculations.

A. The first design is a fully associative cache with a block size of 32 bytes, how many bytes of
overhead would the cache keep in total (including any necessary tag bits?, valid bits,? dirty
bits?, or LRU bits?)? [5]

B. Their next design utilizes a direct mapped cache with 16 different cache lines. How many
bytes of overhead would the cache keep in total (including any necessary tag bits?, valid
bits,? dirty bits?, or LRU bits?)? [5]

C. Finally, they’ve suggested a 2-way set associative cache with 4 different sets. How many
bytes of overhead would the cache keep in total (including any necessary tag bits?, valid
bits,? dirty bits?, or LRU bits?)? [5]