# Calculation of effective average instruction execution time in a 2-level paging system

• System has a two level paging scheme
• Average CPU time for a instruction = 100ns
• Average number of memory accesses per instruction = 2
• Regular memory access = 150 ns
• Page fault service time = 8ms
• TLB hit ratio = 0.9
• Page fault rate = 0.0001

What is the average instruction time if the time required for address translation is negligible?

I worked out the solution as follows

Average instruction execution time = CPU time + Memory access time

Memory access time = No. of memory accesses by the instruction * average memory access time

Average memory access time =
[probability of a TLB hit * regular memory access time]
+ [probability of a TLB miss * (Time for accessing the 1st level of the paging tables
+ Time for accessing the 2nd level of the paging tables
+ Time for accessing memory which may not be paged in with the translated address)]

Time for accessing the 1st level of the paging tables
= Time for accessing the 2nd level of the paging tables
= Time for accessing memory which may not be paged in with the translated address
= [probability of a page fault * (page fault service time + regular memory access time) ]
+ [probability of no page fault * regular memory access time]
= [0.0001 * (8 ms + 150ns)]  + [0.9999 * 150 ns]
= 950 ns

Thus, average time per memory access = [0.9 * 150ns] + [0.1 * 3 * 950ns] = 420ns

Average instruction execution time = 100ns + (2 * 420ns) = 940ns


However the choices for this question are 645ns, 1050ns, 1215ns and 1230 ns.

I can't seem to be able to see where I have reasoned wrong.

EDIT

Average number of memory accesses per instruction is 2

-

I think the question wants you to assume that only about 30% of instructions involve a data memory access (which is somewhat low even for a RISC, Hennessey & Patterson give 47% for MIPS for 5 SPECint2000 benchmarks). 100ns + (1.3 * 420ns) = 646.

(Unless the average number of memory accesses per instruction was provided elsewhere, this question is technically unanswerable; but guessing that the number is less than two per instruction [e.g., a load-store ISA and not a memory-memory ISA] might be reasonable.)

-
Apologies. I missed adding that information. The average number of memory accesses per instruction is 2. –  Abhijith Nov 26 '12 at 13:13