Problem $5$: Cache Overhead $(15$ points$)($L$19)$

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 $4$ KB of data storage capable of addressing exactly $16$ GB of

byte$-$addressable memory $($you should assume addresses are only as large as needed to access this amount$).$ Stores will be handled by write$-$back and allocate$-$on$-$write policies. Please be sure to show the work for your calculations.

The first design is a fully associative cache with a block size of $16$ 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]$

Their next design utilizes a direct mapped cache with $64$ 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]$

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]$