GATE CSE 2017 Set 2 | Question: 45

Question

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 _________

Comments

@Arjun Sir

I have a doubt when there is miss should we add previous access times

MAT = L1 Access Time + L1 Miss Rate [ L1 Access Time + L2 Access Time] + L1 Miss Rate * L2 Miss Rate[Memory Access time + L1 Access Time + L2 Access Time]

and

in which case we multiplied with hit rate as given in

https://www.geeksforgeeks.org/multilevel-cache-organisation/

---

@Manu Thakur sorry for pointing out this typo error but sir it should be only two times 0.1 for operand fetch calculation. [Your approach is simple & elegant]

---

why 3 times 0.1 is added in the question? @manu

Answer 1

$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).

Comments

Do we have to know the architecture beforehand? Otherwise, how can we know that L2 is shared?

---

In  science our main motto is reduce the delay as much as possible and get the maximum efficiency

so simultaneous axis is default because here because delay is less. if explicitly mention use level order or hierarchical  then use hierarchical.

---

@saheb sarkar1997 bro you are wrong because default access method is hierarchical access. 

Source:- 

Simultaneous and Hierarchical Cache Accesses - GeeksforGeeks

Answer 2

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

Answer 3

..…...….….....…………………….…

 

Answer 4

• 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