Hi,
Kindly guide me with the following problem:

If a cache access requires one clock cycle and handling cache misses stalls the processor for an additional five cycles, what is the cache hit rate that comes closest to achieve an average memory access of 2 cycles?

Zulfi.

 

Reasoning:
cache hit = 1 clock cycle
cache miss = 1 Clock cycle + 5 additional clock cycles = 6 clock cycles

need an average of 2 so i did trial and error

 

Please don't just post your solutions to someone else's homework. This is not the Homework Done For You forum. People need to struggle through problems for themselves in order to gain full comprehension of the material, otherwise lectures and worked examples would be all that are needed. When you just provide the answer you generally are doing little to aid in the OP's comprehension since your post just becomes yet one more worked example for them.

Instead, offer hints or ask leading questions to help the OP take the next step, which is also why most of us are pretty insistent that the OP show at least some work on the problem so that we can see what a reasonable next step might be for them.

 

Hi,
Kindly guide me with the following problem:


Zulfi.

Q1) What is the total amount of time (number of cycles) required if there are H hits and M misses?

Q2) What is the average time per access for the situation above?

Q3) Can you put the answer to Q2 in terms of the Hit Rate?

 

Hi,
Based upon google search, i have found following values for my question. I have put these values in a formula:

2 (avg. mem access time) = Hit time (?) + Miss rate(?) * 5(penalty)

For your Q1., If T is the total time then

T=H+M

For your Q2., if average time is AT & acess time (plz tell me what do you mean by access: Hit access or miss access?) is ACT then

AT= ACT/T

For your Q3,

H= T-M
H/100 = (AT/ACT) -M

Kindly guide me with correct answers. I have tried to answer all your Questions. Thanks for interest in our problems.

Zulfi.

 

Normally I would continue with a few more rounds of question and answer, but in this case I think it might be better to take the lecture and demonstrate approach. It's clear you are making the effort and I think there are a few subtle issues that are tripping you up that may be best addresses directly. Besides, you already have the answer given to you via trial and error. So let's look at a very explicit and detailed approach.

If there are H hits and M misses, is the amount of time it takes going to be the sum? Think about the units here. H amd M have units of "accesses" or perhaps "hit accesses" amd "miss accesses". You want time, T, to have units of "seconds" or "clock cycles" or something comparable.

So something like:

T = H*(T_H) + M*(T_M)

Where T_H has units of "clock cycles per hit access" and T_M has units of "clock cycles per missed access".

The total number of accesses is

N = H + M

"But wait!", some might say, "if you are such a units Nazi, why did you just add 'hit accesses' and 'missed accesses' together to get 'accesses'?"

Good and ffair question. Some units, like radians, can drift in and out of units because they are dimensionless. It is a similar thing here. Technically, there is a proportionality constant for each that have units of "accesses per hit access" and "accesses per missed access". In this case, both are numerically equal to one because we WILL get one access per attempt, whether it is a hit or a miss. But this isn't the case in general. Imagine if this were querrying sensors or something else and 50% of the time that we got a miss we didn't any data at all after going through the miss process because it turns out the sensor is off line? Then we would only get 0.5 accesses per missed accessed. But in a case like ours we can justify being a bit sloppy and absorbing the qualifier when we add them together, as long as we understand why we can do so and that it is valid.

Okay, enough of that aside.

Anyway, the quantity you are interested in is the average time per access, which is simply going to be:

Tavg = (total time for N accesses)/N
= T/N
= [H*(T_H) + M*(T_M)]/(H+M)

We can simplify this up by noting that the access time in the event of a miss is equal to the access time for a hit pluss the time associated with the penalty. Essentially, the penalty is the amount of time it takes to make the data available and, once it is available, we sill have to access it. So

T_M = T_H + T_P

Then, the cache hit rate, R, is the number of hits that occur divided by the total number of accesses.

R = H/N = H/H+M)

Plug these into our equation above

Tavg = [H*(T_H) + M*(T_M)]/(H+M)
Tavg = [H*(T_H) + M*(T_H + T_P)]/(H+M)
Tavg = [(H+M)*(T_H) + M*(T_P)]/(H+M)
Tavg = T_H + M*(T_P)/(H+M)
Tavg = T_H + T_P*[M/(H+M)]

Noting that M = H+M-H

Tavg = T_H + T_P*[(H+M-H)/(H+M)]
Tavg = T_H + T_P*[(H+M)/(H+M) - H/(H+M)]

Tavg = T_H + T_P*(1 - R)

Do the units work out?

Yes, because R is dimensionless and so we can subtract it from a dimensionless quantity, namely 1, and T_H and T_P both have units of "clock cycles per access'.

Next, does the answer make sense?

What is the average access time if we never have a miss? That means R is 1 and the average access time is the access time per hit.

What is the average access time if we never have a hit? That means that R is 0 and the average access time is the access time per hit plus the penalty time for a miss, the sum of which is the access time for a miss.

So, yes, the answer makes sense. Life is god and we can proceed.

You are given evereything but the hit rate, R, so that is what we solve for:

Tavg = T_H + T_P*(1 - R)
Tavg = T_H + T_P - T_P*R
T_P*R = T_H + T_P - Tavg
R = (T_H + T_P - Tavg)/T_P
R = 1 - (Tavg - T_H)/T_P

Now, plug in your values (and notice that I waited until the last moment to take that plunge)

R = 1 - (2cycles - 1cycle)/5cycles

R = 1 - 1/5

R = 80%

 

Hi,
I found that your answer is correct. I have not understood the entire stuff, so plz wait , i wont say that my confusion is removed. Thanks for writing this stuff.

Zulfi.

 

Thanks its clear now.

Thanks for providing me this comprehensive solution.

Zulfi.

 

You are welcome, but it is only useful if you can now throw it away and work the problem from scratch without referring to it.

 

This is right. Derivation is very interesting and very helpful for building my concepts. However i found that we are treating both the ratio and average similarly. Is this true? I would surely do it so that your work will not go waste although derivations wont come in my exams but really your short questios are important and can be asked in the exam. If you have time kindly remove my confusion related to avg and ratio otherwise its fine.

Zulfi.

 

I'm not following what you mean by the claim that we are treating the ratio and the average similarly. We have a ratio of hits to total accesses and we have an average access time. Those are two very different things.

Could you clarify what you see as being treated similarly?

 

Hi,
I have a feeling that the concepts behind the ratio and avg looks same.
For avg

Anyway, the quantity you are interested in is the average time per access, which is simply going to be:

Tavg = (total time for N accesses)/N

i found there is a slight difference. In ratio numerator doesnt represent the total value but we are again dividing by N.

the cache hit rate, R, is the number of hits that occur divided by the total number of accesses.

R = H/N = H/H+M)

Thanks for your help on this.

Zulfi.

 

The two quantities are fundamentally difference. It's like counting up how much water you consumed in outdoor watering over the course of several months and dividing the total water used by the number of days to get the average amount used per day. And then counting how many days it snowed over the same period of time and dividing that by the number of days to get the "snowy day rate". Just because you're dividing by the total number of days in each case does not mean that there is only a "slight" difference between the two -- they are fundamentally different.

Now, if the amount of water used each day was determined by whether or not it snowed that day, then there is a relationship between them that can be used to tie them together, but it is THAT relationship that established the tie.