edited by
29,715 views
78 votes
78 votes
The read access times and the hit ratios for different caches in a memory hierarchy are as given below:
$$\begin{array}{|l|c|c|} \hline \text {Cache} &  \text{Read access time (in nanoseconds)}& \text{Hit ratio} \\\hline \text{I-cache} & \text{2} & \text{0.8} \\\hline \text{D-cache} & \text{2} & \text{0.9}\\\hline \text{L2-cache} & \text{8} & \text{0.9} \\\hline \end{array}$$
The read access time of main memory in $90\;\text{nanoseconds}$. Assume that the caches use the referred-word-first read policy and the write-back policy. Assume that all the caches are direct mapped caches. Assume that the dirty bit is always $0$ for all the blocks in the caches. In execution of a program, $60\%$ of memory reads are for instruction fetch and $40\%$ are for memory operand fetch. The average read access time in nanoseconds (up to $2$ decimal places) is _________
edited by

5 Answers

Best answer
114 votes
114 votes

$L2$ cache is shared between Instruction and Data (is it always? see below)

So, average read time

$=$ Fraction of Instruction Fetch $\ast $ Average Instruction fetch time $+$ Fraction of Data Fetch $\ast$ Average Data Fetch Time

Average Instruction fetch Time $= L1$ access time $+ L1$ miss rate $\ast \;L2$ access time $+ L1$ miss rate $\ast\; L2$ miss rate $\ast $ Memory access time

$\quad= 2 + 0.2 \times 8 + 0.2 \times 0.1 \times 90$ 

$\quad= 5.4 \;\text{ns}$

Average Data fetch Time $= L1$ access time $+ L1$ miss rate $\ast \;L2$ access time $+ L1$ miss rate $\ast \;L2$ miss rate $\ast $ Memory access time

$\quad = 2 + 0.1 \times 8 + 0.1 \times 0.1 \times 90$ 

$\quad= 3.7\;\text{ns}$

So, average memory access time

$$= 0.6 \times 5.4 + 0.4 \times 3.7 = 4.72\; \text{ns}$$


Now, why $L2$ must be shared? Because we can otherwise use it for either Instruction or Data and it is not logical to use it for only $1.$ Ideally this should have been mentioned in question, but this can be safely assumed also (not enough merit for Marks to All). Some more points in the question:

Assume that the caches use the referred-word-first read policy and the writeback policy

Writeback policy is irrelevant for solving the given question as we do not care for writes. Referred-word-first read policy means there is no extra time required to get the requested word from the fetched cache line.

Assume that all the caches are direct mapped caches.

Not really relevant as average access times are given

Assume that the dirty bit is always 0 for all the blocks in the caches

Dirty bits are for cache replacement- which is not asked in the given question. But this can mean that there is no more delay when there is a read miss in the cache leading to a possible cache line replacement. (In a write-back cache when a cache line is replaced, if it is dirty then it must be written back to main memory).

edited by
8 votes
8 votes

We use hierarchical access

 

Using I cache:

Tavg1= H1T1 + (1-H1)(H2)(T1 + T2) + (1-H1)(1-H2)(T1+T2+T3)

        = (0.8*0.2) + (0.2)(0.9)(10) + (0.2)(0.1)(100)

        = 5.4 ns

 

Using D cache,

Tavg2 = H1T1 + (1-H1)(H2)(T1 + T2) + (1-H1)(1-H2)(T1+T2+T3)

        = (0.9*0.2) + (0.1)(0.9)(10) + (0.1)(0.1)(100)

        = 3.7 ns

 

Now Tavg = (60% of Tavg1) + (40% of Tavg2)

              = 4.72 ns

0 votes
0 votes
  • CPU connected to 2 caches (I cache and D cache) which are further connected to L2 cache and then Main Memory
  • Referred-word-first read policy means there is no extra time required to get the requested word from the fetched cache line
  • Write-back policy is irrelevant for the question as we do not care for writes. In write-back a block is replaced if it is dirty (dirty bit 1) and is written back to main memory and in question dirty bit is 0 for all blocks.
  • Direct mapped caches : Not really relevant as average access times are given

T_avg = 60% x T_Instr +  40% x T_operand

T_Instr = Hit ratio I cache x Time taken to access I cache  + Miss ratio of I cache  x Hit ratio L2 x Time taken to access L2 + Miss ratio of I cache x Miss ratio of L2 x Time taken to access Main memory 

        = (0.8*0.2) + (1-0.8)(0.9)(2+8) + (1-.08)(1-0.9)(2+8+90) = 5.4ns

T_operand  = Hit ratio D cache x Time taken to access D cache  + Miss ratio of D cache  x Hit ratio L2 cache x Time taken to access L2 cache+ Miss ratio of D cache x Miss ratio of L2 cache x Time taken to access Main memory 

        = (0.9*0.2) + (1-0.9)(0.9)(2+8) + (1-0.9)(1-0.9)(2+8+90)  = 3.7 ns

T_avg = (0.6)(5.4) +(0.4)(3.7) => 4.72 ns

Answer:

Related questions

29 votes
29 votes
8 answers
1