Cache Hit Rate - math problem.

[jlbovo]

Sorry i didn't see that math forum earlier..

Hello, I am having trobule with a problem and am wondering if anyone could help me understand.

This is for homework in my Computer Archtecture class at college.

I have a cache with access time of 4 nSec, 
compared to a miss time of 60 nSec. 
W/o the cache Mainmem has access time of 50nSec. 
Running a set of benchmarks w and w/o the cache indicated 
a speed up of 80%. What is the hit ratio...?

I have this formula

EAT =  H * AccessC + (1-H)* AccessM

H = hit rate
AccessC = cache access time
AccessM = main mem Access time

Can anyone possible help me ?

Thanks !!

[jemidiah]

Are you sure AccessM is main memory access time? Cache miss time would make a lot more sense. "EAT" = "expected access time" I'd bet.

If AccessM is cache miss time it's just a system of 2 equations... what have you gotten so far?

[jlbovo]

EAT = effective access time

I've tried

h(4nSec) + (1-h)*50 = .80

but I think I set that up wrong because in my book EAT is usally expressed in nanoSeconds.

Now that I think about it, I'm not really sure how that 80% speed up play into the equation ?

80% speed up from what ? And those are the only numbers I have.

Cache access 4nsec
Cache miss time 60nsec
Main Mem access 50nsec
speedup of 80%

I'm perplexed....what do you think ?


There's an example in my book about it...

Suppose that the cache access time is 10nSec
MainMem access time is 200nSec
and the cache hit rate is 99%

EAT = .99(10nSec) + (1-.99)(200nSec)
EAT = .99(10nSec) + .01(200nSec)
EAT = 9.9nSec + 2nSec
EAT = 11.9nSec

How does 80% play into the factor, how does 60nSec miss time play into it too ?

Thanks for helping

[jemidiah]

The example from the book doesn't explicitly include a cache miss time, which the original problem does. If you've taken any probability the following might be helpful. Even if not it's pretty intuitive.

You have some variable, "access time," that changes depending on the specific conditions of your scenario. The "expected value" of that ("random") variable is going to be the value you'd see on average. Here, say you perform 3000 memory accesses. Say 600 hit the cache and the rest miss, giving a hit rate of h=1/5. Let's say this is the hit rate you always get, just for simplicity.

You'd then expect the access time to be P(hit)*time per hit + P(miss)*time per miss where P means probability of. Since you can only hit or miss, this gives

E(AT) = "expected access time" = h*Th + (1-h)*Tm [Th = time per hit, Tm = time per miss].

Using your formula, this is exactly the expected (effective; different word for the same idea) access time. Then EAT = H * AccessC + (1-H)*AccessM, assuming AccessC is the time per hit and AccessM is the time per miss.


Using your second post's example, it appears that a cache miss goes directly to main memory without any extra lag, so that time per miss is just time per mainmem access. Using your first post, though, this isn't the case. A cache miss takes an extra 10ns longer than a mainmem access, probably because it has to figure out it's a miss first. So you use my more general formula above which takes care of the possibility that you don't instantaneously go to mainmem and find

EAT = h*4ns+(1-h)*60ns.

If you knew some ratio h and plugged it in, EAT would of course be a time. Say h=1, i.e. you always hit--then EAT=4ns. If you always miss EAT=60ns. The in between values are blendings of those two possibilities as you'd expect.

The problem setup is telling you that you've tried two memory models. First, one without a cache and only main memory. Second, one with a cache. Because misses take longer than main memory accesses, you might get a slowdown from the cached model if you miss a very large fraction of the time. As above if you miss all the time your expected access time is 60ns, which is higher than the 50ns main memory access time you'd get if you didn't even bother with a cache. But, in this case we get a speedup of 80% if you do bother with a cache, so you must have a decent hit rate. This is the end of the problem conceptually. I'll work out the algebra below, which just involves writing these ideas out in math and forcing them together in the form of equations. I'm including the algebra so you can check yourself (I'm assuming this is due sometime soon) but you should probably do it on your own first.






80% speed up from 50ns access time means what? Well 100% speed up gives 25ns=50/(1+1) access time, 400% gives 10ns=50/(1+4), so 80% should be 1/1.8*50ns = 27.78ns expected access time with cache. From the formula, EAT = h*Th+(1-h)*Tm = h*(Th-Tm)+Tm, so h = (EAT-Tm)/(Th-Tm) = (27.78ns - 60ns)/(4ns-60ns) = -32.22/-56 = 0.575, so h = 57.5% hit rate.

Plugging it back in to EAT to check we get EAT = 0.575*4ns+0.425*60ns = 2.3ns+25.5ns=27.8ns (I rounded a bit here). Working backwards, you can say it takes 80% longer to access things with mainmem alone (no cache), so mainmem access time = 27.8ns*1.8 = 50.04ns, correct up to rounding. Yay.

[jlbovo]

hey thanks - your right it was due in this morn and i had read your reply. I plugged everything in and it work now i see why.

i never got 1/1.8*50 in my prior tries

and i didnt know how to switch eat= h(Th)=(1-h)*Tm to h = (EAT-Tm)/(Th-Tm)

thanks so much i apperciate it.

thanks - j

[jemidiah]

No problem, glad it worked out