GATE CSE 2020 | Question: 21

Question

A direct mapped cache memory of $1$ MB has a block size of $256$ bytes. The cache has an access time of $3$ ns and a hit rate of $94 \%$. During a cache miss, it takes $2$0 ns to bring the first word of a block from the main memory, while each subsequent word takes $5$ ns. The word size is $64$ bits. The average memory access time in ns (round off to $1$ decimal place) is______.

Comments

@Aditya_np1 theres nothing like simulataneous access in cache,

you need to know the difference between miss penality, miss time.

AMAT = hitratio * hittime + missratio *(hittime + misspeanlity)

AMAT = hitratio * hittime + missratio * (miss time)

basically, misstime = hittime + miss penality,

in question they told the cache miss  the time is 20ns then followed by 5ns, so this is the time from MM to cache after cache miss, so this miss penality.

---

so what to use --AMAT = hitratio * hittime + missratio *(hittime + misspeanlity) this ??
 

 

---

The key considered both 13.3 and 13.5 is :

But the conceptually correct answer is 13.5 ONLY

The question is actually copied from "Computer Organization and Embedded Systems 6e - Hamacher", Example 8.1

 

The difference is only in the Numericals.

---

Edit : I am disheartened to realize that, the "miss penalty" defined in this question is different from the definition of "Miss Penalty in Hennessy"

For a Single Level Cache System (L1) 

Here (Hamacher) : They defined Miss Penalty as : Miss Penalty(L1) = Time to Access L1 + Time to Access MM

Hennessy : Miss Penalty(L1) = Time to access MM

But, the underlying formula is same for both the definitions. 

In Hamacher they use :

AMAT = Hit rate(L1) × (Access Time(L1)) + Miss Rate(L1) × (Miss Penalty(L1))

[Note : As, I said before, in this problem Hamacher used : Miss Penalty(L1) = Time to Access L1 + Time to Access MM]

In Hennessy they clearly state :

AMAT = Access Time(L1) + Miss Rate(L1) × (Miss Penalty(L1))

[Note : As, I said before, Hennessy uses : Miss Penalty(L1) = Time to access MM]

Hence, terminology usage Is different. But the underlying concept is same. 

 

It is stuff like this, which led to theories like "Simultaneous Access"

 

For your information : Miss Penalty defined by Hennessy is the Standard

---

Finally I would like to conclude, by explaining how "13.3ns" was also accepted. 

They merged the concepts of Hamacher and Hennessy. 

In Hamacher, We multiply the Access Time(L1) with Hit Rate(L1). To compensate, we also add the Access time(L1) in the Miss penalty as defined by Hamacher.

In Hennessy, we do not multiply Access time(L1) with Hit rate(L1). So, we don't need to compensate. So we don't add Access Time(L1) in the Miss Penalty defined by Hennessy. 

Now 13.3ns comes, if we :

1. Multiply Access Time(L1) with Hit Rate(L1)
2. Do not compensate by adding Access Time(L1) in Miss Penalty as defined by Hamacher. 

This is clearly WRONG. 

Answer 1

Block size is 256 Bytes,word size is 64 bits or 8 bytes. So Block size in words is 8 words.

Number of words per block=32

Time to fetch a word from main-memory to cache is: $20+31 \times 5=175$ns because first word takes 20ns and rest each subsequent words take 5ns each.

So average Memory acces time is

$0.94(3)+0.06(3+175)=13.5$ ns

Comments

@moh_haris Recheck first sentence in question, it says CACHE MEMORY size is 1MB, not main memory size.

---

I think believing in " heirarchical access is optimal" seems to be incorrect. as per my understanding,
simultaneous access takes less time.

in heirarchical, one addiotional access to cache(i.e, first it sees into cache, then memroy)

wrt this :Why hierarchical is default access ?

even if there is parrallel unwanted memeory access, but time is reduced, isnt it?

Also, i want to understand the statments:
ignore search time in L1", or "write-through", or it is explicitly mentioned "hit time is xxx and miss time is yyy". Here the question says "during a cache miss to bring the first word....". You could definitely interpret this as "in addition to L1 access" or "when there is a miss". ...

 

can anyone give explanations?

---

@Aditya_np1

Hierarchical access is not used because it is optimal, it's used because cache memory works only on hierarchical access.

Also for your 2nd question, since in hierarchical access, block can't go directly from main memory to cpu, and can only be transferred from main memory to cache memory, therefore the given time can be interpreted only as time required for block transfer from MM to CM, which is 20+ 31*5

Hope it helped

Answer 2

Considering simultaneous access

Cache m/m = 1 MB

Block = 256 B

Word = 64 b = 8 B

1 Block = 256/8 = 32 words

$T_{access}$ = 3 ns

$T_{mem}$ = 20 ns (first word) + 5 ns (each of the rest 31 words)

T = 0.94 * (3) + 0.06 * (20 + 5 * 31) = 13.3 (ans)

Comments

I think here Hierarchical access.

Answer is 13.5 ns

---

Check out the official key: http://gate.iitd.ac.in/CSKey.php

---

This is the link for official solution key: http://gate.iitd.ac.in/gate2020/CSKey.php

Answer 3

Block size = $256$ B

Word size = $64$ bits = $8$ B

Number of words in a block= $256/8$ = $32$ words i.e whenever a miss occurs a block will be fetched from the memory containing $32$ words in which first word will take $1$ ns and rest $31$ words will take $5$ ns each.

Average m/m access time = $0.94 * 3 + 0.06 * [1*20 + 31 * 5 + 3] = 13.5 ns$

Answer 4

ans is 13.5  consider sequential setup of heirarchy

Explaination : h1*t1 + (1-h1)(t1+t2) = avd access time for the given hierarcy of memeory.

so, 0.94*3 + 0.06(3ns + 20 + 31*5) = 13.5 ns

t2 = first word(20 ns) + 5* remaining words (2pow 5 -1) ; 2 pow 5 = no of words in block.

Answer 5

.94x3+.06x(20+5x31+3) = 13.5

Answer 6

Let me simplify the solution .so tell me you know the formula for average memory access time is Average access time = h1*tcm+(1-h1)(tcm+tmm)

so to calculate average memory time we need hit ratio ,cache memory access time and main memory access  time.

now read question and try  to figure out what are the things we have .so we have hit ratio given ,cache memory time given and some info about main memry access time given but not clear . 

it takes 20 ns to bring the first word of a block from the main memory, while each subsequent word takes 5ns .

Now we have to take care of this line and find main memory access time.As after reading the line you know that it is taking about words in memory so for first work it takes 20ns and for remaning it takes 5ns each .So you have figured out that you need to calculate no of words.

no of words:

Block size is 256 Bytes,word size is 64 bits or 8 bytes. So Block size in words is 8 words.

Number of words per block=32

so tmm=20+31*5=175ns

now simply apply the formula and you will get the answer

tavg= 0.94 * (3) + 0.06 * (20 + 5 * 31) = 13.5(ans)