7.2k views
The memory access time is $1$ $nanosecond$ for a read operation with a hit in cache, $5$ $nanoseconds$ for a read operation with a miss in cache, $2$ $nanoseconds$ for a write operation with a hit in cache and $10$ $nanoseconds$ for a write operation with a miss in cache. Execution of a sequence of instructions involves $100$ instruction fetch operations, $60$ memory operand read operations and $40$ memory operand write operations. The cache hit-ratio is $0.9$. The average memory access time (in nanoseconds) in executing the sequence of instructions is ______.
edited | 7.2k views
0
what is 5 ns here, isnt it the average access time?? which memory organization is used here??? please resolve my doubt
+9

A very good discussion , which concludes that Default access is Hierarchical ,

But in this question we have to go through the meaning of the lines in the question and this question is solved in Simultaneous way .

For that discussion in Fb group : go though below link, i assure you worth it to read each comment there :)

0

@Bikram sir @Arjun sir

Here in the question they have asked "average memory access time in executing the sequence of instructions ".  They didn't give  "average memory access time of an instruction" or "average memory access time of an operation"... i think they have used the word "average" because hit-ratio of cache is 0.9... Now why are we dividing by 200 ... The answer should be 336 ns right ???

0
336 ns is total time taken for all 200 operations, it is Not average time ..it is total time !

the sequence of instructions is 200 in total.

That's why we have to divide by 200 .
+1
@Bikram sir

Sir here all 200 operations involve memory access ... We know that Average Memory Access Time is nothing but time needed for 1 memory access.

Here for 200 memory accesses it is 336 ns ... so for 1 memory access it is 336 ns / 200 = 1.68 ns

Is the above reason correct on why we are dividing by 200 ???
+1
@Vicky

yes correct.

Average Memory Access Time = Time  for 1 memory access.

Here for 200 memory accesses time is 336 ns .

so for 1 memory access time is 336 ns / 200 = 1.68 ns

Hence Average mem Access Time = 1.68 ns
0

Notice --> If memory organization is considered Hierarchical then 1 ns cache read time and 4ns is main memory read time that is why  total read time in case of miss is 5 ns. Simillarly for write.

Please correct me if i am wrong.
0

whenever there is miss penalty given in question it is simultaneous access.

The question is to find the time taken for,

$\frac{\Large100 \space \text{fetch operations and$60$operand read operations and$40$memory operand write operations}}{\Large\text{total number of instructions}}$.

Total number of instructions $=100+60+40 =200$

Time taken for $100$ fetch operations(fetch = read) $= 100*((0.9*1)+(0.1*5))$

$1$ corresponds to time taken for read when there is cache hit $= 140 \,ns$

$0.9$ is cache hit rate

Time taken for $60$ read operations,

$= 60*((0.9*1)+(0.1*5))$
$= 84\,ns$

Time taken for $40$ write operations

$= 40*((0.9*2)+(0.1*10))$
$= 112\,ns$

Here, $2$ and $10$ are the times taken for write when there is cache hit and no cache hit respectively.

So,the total time taken for $200$ operations is,

$= 140+84+112$
$= 336\,ns$

Average time taken = time taken per operation

$=\dfrac{336}{200}$

$= 1.68\,ns$
edited
0
@Divya Bharti

is it  simultaneous approach ?

we add delay time only in hierarchical access

but here we did not add any delay time so it is simultaneous is not it ?
0
Here we are not having hierarchical access,so no need to add delay time.It is sequential access. Hope it clarifies your doubt.
+3
@Divya

I did not understand what you mean by Sequential ?

Sequential access indirectly says hierarchical is not it ? .... Sequential means one level search after the previous level search completed.

But in case of Simultaneous access we use the term parallel access also  .

need to clear your view, whether you solved this problem Hierarchical way or simultaneous way ?
0

There was difference in terminologies which we were using

So, yes it is simultaneous way only,that's why delay is not added.

Thanks for this question
0
Going with the meaning of the word "memory access time" here we use "Simultaneous access".

Thanks Prasanth and Bikram Ballav..
+12
Suman don't go with simultaneous or hirarical logic blindly . Go with question wording here question not said if miss in cache then read word from main memory to cache then read, but it said read directly from main memory it's simultaneous only.

Question said 1st check cache if hit read , if miss go to main memory read from main memory directly.
+4
I am completely agree [email protected] sir and prashant..

Logic is simple- we are given memory access time in case of cache miss and hit respectively.. so use simultaneous concept with given hit ratio..

One need to be very careful with this concept to get good rank because most of the time we student get confused in exam hall...So need to have clear concept..

Generally, gate team asks this type of question with little twist in the wording..
+25

As the wording says " 5 nanoseconds for a read operation with a miss in cache" and "10 nanoseconds for a write operation with a miss in cache".
Hence, when miss occurs , CPU takes 5 ns or 10 ns total time  in case of miss as the access times are directly given. So, we need not worry about hierarchical/ simultaneous here.

Obviously, we first goto cache and check whether miss is there or not and then goto main memory, but in the question it is not giving MM access time, but instead total time when a miss occurs .Hence, we need not have to worry about H/S access and hence even no need of it .

A very similar question and here, also no need to worry about H/S access :-

https://gateoverflow.in/8119/gate2015-2_24

+6

@suman

see another similar type of problem which solve in Simultaneous policy

https://gateoverflow.in/8119/gate2015-2_24

as @kapil mention here, if  only cache hit time and memory access time given then use Hierarchical approach . But here memory access time is not given .

here it is given cache time in case of hit and miss separately... So it's like parallel formula , we can solve it in simultaneous way .

+4

@suman

Here this formula is used to calculate average  access time .

The formula is = Hit Time X Hit Rate + Miss Penalty * Miss Rate .... ( i )

this formula is used in Simultaneous access .

so for 100 fetch instructions, total access time is :

100*((0.9*1)+(0.1*5))

where 0.9 = cache hit-ratio [ given ]

0.1 = cache miss-ratio  [ we calculate ]

1 ns = The memory access time for a read operation with a Hit in cache

5 ns = The memory access time  for a read operation with a Miss in cache

now put them in the formula (i) ..

That's the reason i want to say it solved in simultaneous way ...

0
@bikram sir, the question says :

'The memory access time is 1 nanosecond for a read operation with a hit in cache, 5 nanoseconds for a read operation with a miss in cache.'

My doubt is how can the memory access time change depending on whether it's a hit or miss? Shouldn't memory access time remain constant irrespective of a hit or miss?
+4

When there is a cache miss , we need to go down in memory hierarchy , like from cache to memory .

so it says " memory access time is 1 nanosecond for a read operation with a hit in cache " this means when data us found in cache it takes 1 ns to fetch that data from cache to cpu.

1 nanoseconds time involved = time for cpu to reach cache + cache search time ( negligible, in real problems we ignore this time ) + time to reach from cache to cpu

This 1 ns time is for cache hit .

" 5 nanoseconds for a read operation with a miss in cache."

this means when a miss happen in cache, we go from cache to memory .

so 5 nanoseconds time involved = time to reach from cache to memory + search in memory ( negligible time ) + time to reach with data ( assume there is a hit in memory ) from memory to cache and copy it into cache + time for cache to reach this data into CPU ,

when there is a cache miss , we have to find that data into lower level, this takes more time than time taken in case of hit .

so that's why memory access time change depending on whether it's a hit or miss .

0
Sir, but in case of hit, main memory is not accessed and only cache is accessed as you say here:

"1 nanoseconds time involved = time for cpu to reach cache + cache search time ( negligible, in real problems we ignore this time ) + time to reach from cache to cpu."

So are we referring to cache access as memory access only?
+1

Yes, cache is a memory itself.

So when we say  memory access , we explicitly mention whether it is cache access or main memory access.

like that " 'The memory access time is 1 nanosecond for a read operation with a hit in cache, 5 nanoseconds for a read operation with a miss in cache. "

hit in cache means it is cache memory  and miss in cache means it is main memory .

0
Got it. Thanks sir. :)
0
It means if the time given for cache just one value(without giving, for hit this much value and miss this much value). then we should go with hierachy right?
0
0

Why do we divide by 200?

I have serious doubt in understanding this question.

Execution of a sequence of instructions involves 100 instruction fetch operations

The average memory access time (in nanoseconds) in executing the sequence of instructions is ________

We perform 200 operations but we only execute 100 instructions and the question asks for avg access time in executing the sequence of instructions. Where am I wrong here?

Any suggestion is highly appreciated.

+1

@gmrishikumar  we are dividing by 200 because to execute the sequence of instruction we require 100 instruction fetch, 60 read and 40 write so in all 200 operations are performed. So for this sequence of instructions avg access time=336/200 and not 336/100 as we are asked for "sequence of instructions".

0
Got it.
Fetch is also a memory read operation.

Avg access time $= \dfrac{160 (0.9 \times 1+0.1 \times 5)+ 40(0.9 \times 2+0.1 \times 10)}{200} \\=\dfrac{160\times 1.4+40 \times 2.8}{200} \\=\dfrac{336}{200} \\=1.68$
edited
0

Why did you divide by 200?
200 is not the total number of instructions.
it is the phase of instructions. so average time PER instruction has to be 336 itself?

+5
@aspi u r thinking in wrong way. as fetch is read  also total read 160,and write 40..now original formula is

freq of read inst * tread + freq of write instr *twrirte = avg access time.

freq is nothing but ratio ..

i think now u wl get clear concept
+1
Why we are not using hierarchial memory organization?
0
How can you say it is not hierarchical method being used?
0
@Arjun sir, if it is a hierarchical method then in cache if it is hit 0.9*1 ns but if it is a miss then as we know we have to ask the main memory for the operand and then we also have to put that operand in cache and access the operand from cache only. then it must be 0.1*5 + 0.1*1
0
arjun sir,what is the difference between hierarchical access and structural one ?? and what minor calculations changes are there between them??lso how will we find out whether to use hierrchical or structural??
0
here i suppose,from the language of the question,we are given the *total read or write time incurred during cache hit and cache miss,this time is inclusive of the time of searching in cache + searching in memory + then again copying it to cache.
0
yes @Akriti sood, I am supposing it too...but I need to confirm
0
There are only 100 instructions- 60 read and 40 write. Since each instruction involves fetching as well, we have 2 memory accesses per instruction. This leads to total time for execution to be 336ns which has to be the answer. The term average seems misleading since all the times provided(1ns cache hit read time, etc) are anyway average times, but there is little doubt by the language of the question that they have asked for execution time of the instructions which happens to be 336 ns.

Anyways the answer is definitely not 1.68 because even if we take average, we consider 100 instructions (and not 200)
0

The average memory access time (in nanoseconds) in executing the sequence of instructions is

This is not the average memory access time spend per instruction.

0
Hi arjun,

Can you please explain the logic in detail why are we dividing this by 200?

the time we calculate by using formula t(Avg)= h x t(cache) + (1-h) x t(memory) gives us the average access time experienced by the processor but here they are asking average memory access time in executing sequence of instructions. What is the difference between two?

Regards,

Harveen
0
Sir why do we divide 336 by 200? Here it is not mentioned to find out Average Access Time per instruction. So answer should be 336 instead of 1.68 .
0
if it were Average Access Time per instruction. then it would be 336/100= 3.36 na??
0

@sushmita i think that is true only in the case of "fixed length instructions".

0
I think ans  should be 3.36

because only 100 instruction that are you counting only as fetching instruction cannot occure  ..some other operation must be included with them

here read and write are the types of operation doe by those 100 instruction .

otherwise memory write operation has to be fetched first also so total number of memory read will become 100(for fetch)+60(for fetching memory read operation)+60(memory read)+40(for fetching memory write operation) = 260 and write will remain 40.

isn't it?? @Bikram sir
+1
@sumit

The answer is 1.68 and it is correct .

see the question, what it says : " Execution of a sequence of instructions involves 100 instruction fetch operations, 60 memory operand read operations and 40 memory operand write operations. "

Now instruction fetch operation is same as Read operations. so  total 100 read operations . And 60 operand read operations and 40 memory operand write operations .

Total number of instructions= 100+60+40 =200
+3

iamhusayn   and @sushmita @bharti

why do we divide 336 by 200? Here it is not mentioned to find out Average Access Time per instruction. So answer should be 3.36 instead of 1.68 .

Average Memory Access Time = Time  for 1 memory access.

Total number of instructions= 100+60+40 =200

Here for 200 memory accesses total time is 336 ns .

so for 1 memory access time is 336 ns / 200 = 1.68 ns

Hence Average mem Access Time = 1.68 ns

+1
i got each and every thing but here the no. of instructions are 100 only and according to me out of 100 fetched instructions 60 are read and 40 are for write operation..? but why is it wrong..?
TavgR = 0.9 * 1 + 0.1 * 5 = 1.4 //TavgR here is avg time needed to one read operation

TavgW=0.9 *2 + 0.1*10 =2.8 //TavgW here is avg time needed to one write operation

Tavg = Total time needed to read/write operations / total no.of operations

Here Write operations are=40

So= (160 * 1.4 + 40 * 2.8 ) / 200

=336/200=1.68ns
+1
if this question comes in exam than sureli i will marked 336 . thing is how we know we have to divide by 200 ?? its because .it said in question avg memory access time.

as i have most question without dividing .200 ???? .i dont know where i am wrong .???
0
@Gabbar

$T_{avg} = H\times CM_{AT} + (1-H)(CM_{AT} + MM_{AT})$ where, $CM_{AT}$ =Cache memory access time and $MM_{AT}$ = Main memory access time isn't?

Can I know why have you not included miss penalty in your calculation?
0
here operation time is given not the cache access or main memory access time.
0
Yeah, I missed it. Thanks.
0
@kunal

Average memory access time In executing sequence of instructions then divide by 200.

Average memory access time for each instuction or average memory acces time only then do not divide by 200.
0
@papesh

T avg  a/c to you is average  time taking of one instruction. But here question is saying  to find out Tavg  of instructions  not of instruction.

The average memory access time (in nanoseconds) in executing the sequence of instructions is ______.

Please clarify this . I am very confused .
0
@bharti

Total number of instructions= 100+60+40 =200

336 ns is total time taken for all 200 operations, it is Not average time ..it is total time !

average memory access time =   time taking for one memory access

That's why we have to divide by 200 .
0
@Bikram sir,

yes sir, now I got it .thank you for explaining me.

Earlier, i was considering the total time 336 ns as 1 memory access time. i had wrongly interpreted the question .Thank you, sir for clarifying this
0
its clearly written that 100 fetch which means 100 instructions, why are u taking 200 instructions??

200 is total of memory references.
0

And in microprocessor load is an instruction.

I think that is why we are calculating w.r.t.200 instructions.

Memory access time means howlong it takes for an element in memory to be transferred to or from the cpu....so its the relation between the cpu and memory(in theory....now this memory can be either cache or main memory(in practical)...so when its given memory access time when cache hit then its means the time related to cache and cpu...and when its given memory access time when cache miss then its means its the time related with cpu and higher level memory (not cache)...
0
Can we do it like -

Total time for 200 instructions =

.9 (100*1 + 60*1 + 40*2) + .1 (100*5 + 60*5 + 40*10)

= 336ns

Time for 1 instruction = 336/200

= 1.68ns

1
2