Cache and Main Memory

This is a discussion on Cache and Main Memory within the Tech Board forums, part of the Community Boards category; If there is a 3-level cache structure in place with the following characteristics: Code: organized as column 1) Level, column ...

  1. #1
    Registered User
    Join Date
    Sep 2007
    Posts
    119

    Cache and Main Memory

    If there is a 3-level cache structure in place with the following characteristics:

    Code:
    organized as column 1) Level, column 2) access time (nano-secs), column 3) Hit %
    
            L1         2nsec        91%    (level 1)
            L2        14nsec       96%    (level 2)
            L3        38nsec       99%    (level 3)
            Main   120nsec   100%     (main memory)
    Is average effective access time for memory references computed as follows:
    Code:
    TL1 + (1 - hL1) * TL2 + (1-hL2) * TL3 + (1-hL3)
    
    where T=access time, h = hit %
    Also, with this information; how can I figure out the expected data transfer rate into the CPU? Any help would be greatly appreciated.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I'm sure the book tells you that you can calculate it like that, but in reality, that would be a very rough estimate, and in reality, you will have some situations where the data is all comming from main memory, so you get 8.3MB/s, and other times when all data is being read through the cache, and you get 500MB/s.

    It would be a bit like calculating your average speed in your car with one day you are driving on a relatively empty German Autobahn at 150MPH, and another day in central London at 12 MPH. Yes, your average speed will be pretty good (~80MPH), but when driving in London, it won't feel particularly fast.

    Back to your question, what part of that calculation do you find difficult? Or do you simply not have pen and paper/calculator/spreadsheet to do the calculation?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Sep 2007
    Posts
    119
    Sorry for not phrasing properly. My questions are as follows:

    1) Is my formula for "average effective access time for memory references" correct? meaning, will it give me a rough estimate?

    2) I'm not sure at all how to calculate the "expected data transfer rate into the CPU" with the information I gave in my previous post. How do I do that? The above formula I gave was to find the answer for my 1st question.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    The expected data transfer rate is 1s/Ts bytes (multiplied by the width of the bus, so if you have a 32-bit databus, it will transfer 8.3*4 MB/s from your main memory, as 1s/120ns = 1000,000,000/120 = 8,333,333 transfers per second of 4 bytes per transfer) - so you get 33MB/s from your main memory.

    If you then use the formula to calculate the average access time, you can calculate the average transfer rate.

    But like the average of one foot in a bucket of ice at -17'C and the other foot in a bucket of boiling water at 100'C water makes your feet "on average pretty good" at 41.5'C, your feet aren't going to agree!

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Sep 2007
    Posts
    119
    You kind of lost me there. The only data I have available is the table I gave in my first post. I don't know the width of the bus. With what I have, I must calculate:

    a)average effective access time for memory references
    b)expected data transfer rate into the CPU

    1)Can you please tell me if the formula I was using for a) is correct? Yes or No? If this formula is not correct, I need to revise it until it is. I was thinking that I needed to add in the access time for main memory

    Code:
    average access time = TL1 + (1 - hL1)  * TL2 + (1-hL2) * TL3 + (1-hL3) * TMain
                                     = 5.98 nsec
    2)With the information in the table, and the average effective access time for memory references, how do I calculate b)?
    Last edited by John_L; 10-01-2008 at 05:50 PM.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    It is not clear if the hit ratio is accumulutive (it probably is), or if it's the actual hit ratio of the individual caches. If it is, then you would have to add together the percentage numbers to make the overall main memory access, and the accesses down to lower level caches.

    Other than that, you need to add the main memory access to your formula. Yes, it's only 1% of the total transfers, but it's a "big" one percent, because 1% of 120ns is 1.2ns, so it adds half of the 96% L1 cache hits.

    As to "don't know the bus width", that will obviously destroy any hope of comming up with bytes per second or some such. You could, however come up with a "transfers" per second number.

    The transfer rate is calculated as 1/time, where time is the average access duration. Since we don't know how wide the data-bus is, you can't give more than transfers per second.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User
    Join Date
    Sep 2007
    Posts
    119
    But it looks like you were estimating transfer rate strictly from main memory, should i estimate the data transfer rate from main memory, and all levels of cache? Than maybe average them out?

    Code:
    Average effective memory access time is:
    
    		= TL1 + (1 - hL1) * TL2 + (1-hL2) * TL3 + (1-hL3) * TMain
    		= 2 + (1 – 0.91) * 14 + (1 - 0.96) * 38 + (1-0.99) * 120
    		= 2 + 0.09 * 14 + 0.04 * 38 + 0.01 * 120
    		= 5.98 nsec
    
    	Expected data transfer rate into the CPU is:
    
    		       L1 cache = 1s / Ts 
    			          = 1s / 2nsec
    			          = 1, 000, 000, 000 / 2
    			          = 500, 000, 000 transfers per second
    
    		       L2 cache = 1s / Ts 
    			          = 1s / 14nsec
    			          = 1, 000, 000, 000 / 14
    			          = 71, 428, 571 transfers per second
    
    		       L3 cache = 1s / Ts 
    			          = 1s / 38nsec
    		       	          = 1, 000, 000, 000 / 38
    			          = 26, 315, 789 transfers per second
    
    		Main memory = 1s / Ts 
    				= 1s / 120nsec
    				= 1, 000, 000, 000 / 120
    				= 8,333,333 transfers per second
    
    		Overall,
    
    		    = [ (500, 000, 000) + (71, 428, 571) + (26, 315, 789) + (8,333,333) ] / 4 
    		    =  151, 519, 423 transfers per second
    Last edited by John_L; 10-01-2008 at 06:29 PM.

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by John_L View Post
    But it looks like you were estimating transfer rate strictly from main memory, should i estimate the data transfer rate from main memory, and all levels of cache? Than maybe average them out?
    I was giving the main memory as an example. You should calculate some sort of average, yes.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Prefechind data from main memory into cache
    By Kempelen in forum C Programming
    Replies: 5
    Last Post: 02-05-2009, 06:15 AM
  2. difference between a segment and a page
    By cs32 in forum Tech Board
    Replies: 21
    Last Post: 03-05-2008, 02:09 PM
  3. Resource manager tree
    By VirtualAce in forum Game Programming
    Replies: 23
    Last Post: 09-07-2007, 10:27 PM
  4. How to Parallel reading flat file into C ?
    By anwar_pat in forum C Programming
    Replies: 11
    Last Post: 09-16-2006, 09:44 PM
  5. What's the best memory (RAM) type?
    By Unregistered in forum A Brief History of Cprogramming.com
    Replies: 17
    Last Post: 12-14-2001, 11:37 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21