Cache and Main Memory

[John_L]

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

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:

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.

[matsp]

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

[John_L]

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.

[matsp]

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

[John_L]

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

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)?

[matsp]

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

[John_L]

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?

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

[matsp]

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