Results 1 to 6 of 6

Thread: Cache Hit Rate - math problem.

  1. #1

    Thread Starter
    Addicted Member
    Join Date
    Oct 2004
    Location
    youngstown, oh
    Posts
    202

    Cache Hit Rate - math problem.

    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.

    Code:
    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

    Code:
    EAT =  H * AccessC + (1-H)* AccessM
    
    H = hit rate
    AccessC = cache access time
    AccessM = main mem Access time
    Can anyone possible help me ?

    Thanks !!
    --thanks for the help.

  2. #2
    Only Slightly Obsessive jemidiah's Avatar
    Join Date
    Apr 2002
    Posts
    2,431

    Re: Cache Hit Rate - math problem.

    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?
    The time you enjoy wasting is not wasted time.
    Bertrand Russell

    <- Remember to rate posts you find helpful.

  3. #3

    Thread Starter
    Addicted Member
    Join Date
    Oct 2004
    Location
    youngstown, oh
    Posts
    202

    Re: Cache Hit Rate - math problem.

    EAT = effective access time

    I've tried

    Code:
    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...

    Code:
    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
    --thanks for the help.

  4. #4
    Only Slightly Obsessive jemidiah's Avatar
    Join Date
    Apr 2002
    Posts
    2,431

    Re: Cache Hit Rate - math problem.

    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.
    The time you enjoy wasting is not wasted time.
    Bertrand Russell

    <- Remember to rate posts you find helpful.

  5. #5

    Thread Starter
    Addicted Member
    Join Date
    Oct 2004
    Location
    youngstown, oh
    Posts
    202

    Re: Cache Hit Rate - math problem.

    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
    --thanks for the help.

  6. #6
    Only Slightly Obsessive jemidiah's Avatar
    Join Date
    Apr 2002
    Posts
    2,431

    Re: Cache Hit Rate - math problem.

    No problem, glad it worked out
    The time you enjoy wasting is not wasted time.
    Bertrand Russell

    <- Remember to rate posts you find helpful.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width