Chapter 6.4, Problem 6.9PP

Explanation of Solution

Cache Addressing:

The primary storage hierarchy contains cache lines that are grouped into sets. If each set contains k lines then we say that the cache is k-way associative.

A data request has an address specifying the location of the requested data. Each cache-line sized chunk of data from the lower level can only be placed into one set. The set that it can be placed into depends on its address.

The number of cache sets is equal to the number of cache blocks divided by the number of ways of associativity.

$\begin{array}{c}\text{Number of tag bits = (}\text{address \_bit \_length ) - (exponent \_of\_ index )}\text{- }\\ \text{ (}\text{exponent \_of \_offset)}\end{array}$

The least significant bits are used to determine the block offset.

For example:

One needs to consider the following set associative (S, E, B, m) = (8, 4, 4, 13). The derived value will be as follows:

The Index (CI):

${\text{s=log}}_{\text{2}}{\text{(S) =log}}_{\text{2}}{\text{(2}}^{\text{3}}{\text{) = 3 log}}_{\text{2}}\text{(2) = 3}$

The block off set (CO):

${\text{s = log}}_{\text{2}}{\text{(B) = log}}_{\text{2}}{\text{(2}}^{\text{2}}{\text{) = 2 log}}_{\text{2}}\text{(2) = 1}$

The tag bit (CT):

$\text{t = m - (s + b) = 13 - (3 + 2) = 13 - 5 = 8}$

Hence, the “2” lower bits are block offsets (CO); followed by 3 sets of bit index (CI) and the remaining bits are tag bits (CT).

The following table gives the parameters for a number of different caches and the number of cache sets(S), tag bits(t), set index bits (s) and block offset bits (b) are defined.

Cache	m	C	B	E	S	t	s	b
1	32	1024	4	1	256	22	8	2
2	32	1024	8	4	32	24	5	3
3	32	1024	32	32	1	27	0	5

The values for the above table are described below:

For cache-1:

It is given that $B=4$,$E=1$, $C=1024$ and $m=32$.

Hence:

$\begin{array}{l}S=(cache\_memory)/(B\times E)\\ =(1024)/(4\times 1)\\ =256\end{array}$

${\text{s=log}}_{\text{2}}{\text{(S) =log}}_2{\text{(256) = log}}_{\text{2}}{\text{(2}}^8{\text{) = 8 log}}_{\text{2}}\text{(2) = 8}$

$\text{b =}{\text{log}}_{\text{2}}{\text{(B)=log}}_{\text{2}}\text{(4)=2}$

$\text{t = m - (s + b) = 32- (8 + 2) = 32-10 = 22}$

For cache-2:

It is given that $B=8$, $E=4$,$C=1024$ and $m=32$