7.3a Fully-Associative Cache

Fully-Associative Cache

An $N$-byte, $K$-bytes-per-block fully-associative cache of $\frac{N}{K}$ blocks uses both a write policy and a replacement policy to store memory blocks in the order that they are loaded into the cache. Due to this, its index merges with its tag, such that the number of tag bits is equal to
$N_t=N-N_o,$
where $N_o=lo{g}_2(K)$ is the number of bits allocated to the offset, or the length of every block:

\begin{document}
 
\begin{tikzpicture}
   % Draw the inner boxes for Metadata
   \draw[thick, fill=darkgray] (-.5,3) rectangle (1,4);
   \draw[thick, fill=darkgray] (-.5,2) rectangle (1,3);
   \node at (3, 1.5) {$\vdots$};
   \draw[thick, fill=darkgray] (-.5,0) rectangle (1,1);
   
   % Draw the inner boxes for Data
   \draw[thick] (1,3) rectangle (5,4) node[midway] {$K$ bytes};
   \draw[thick] (1,2) rectangle (5,3) node[midway] {$K$ bytes};
   \node at (0.25, 1.5) {$\vdots$};
   \draw[thick] (1,0) rectangle (5,1) node[midway] {$K$ bytes};
   
   % Add text labels
   \node[align=center] at (0.25, 4.5) {Metadata \\ (Tag)};
   \node at (3, 4.75) {Data Offset};
   
   % Add offset numbers
   \node at (1.75, 4.25) {$2^{N_o}-1$};
   \node at (3, 4.25) {$\cdots$};
   \node at (3.75, 4.25) {1};
   \node at (4.75, 4.25) {0};
\end{tikzpicture}
 
\end{document}

Note!

The figure above shows offset data stored in little-endian format.

Examples

Example