# 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

I see two possible flaws in your reasoning. 1) At least the first level of the page table is typically pinned in memory (so it could never cause a page fault). 2) The page fault rate is presumably independent of the TLB miss rate (i.e., it is page faults per access not page faults per TLB miss).

This still will not provide an answer equal to any of the options. If the page fault rate is per access, then that would add 800ns to each memory access--1600ns in total--, which exceeds the highest value for total execution time! If the page fault rate is--bizarrely--per TLB miss (and the whole page table is pinned in memory), page faults would add 80ns to each memory access and TLB misses would add 30ns to each access; this would total 100ns + 2 * (150ns + 80ns + 30ns) = 620.

My guess is that the person providing the solution made an arithmetic error and only included the TLB miss and page fault overhead for one memory access. I.e., instead of 100ns + 2 * 150ns + 2 * (0.1 * [2 * 150ns]) + 2 * 0.0001 * 800ms--which would equal 2060ns--, they calculated 100ns + 2 * 150ns + ONE * (0.1 * [2 * 150ns]) + ONE * 0.0001 * 800ms--which would equal 1230ns, which is one of the answers provided. (This is assuming the page table is pinned in memory.)

Students should not have to debug questions!

-
By the way, by "whole page table" I mean the first level and those pages of the second level that have at least one valid translation. L2 page table pages that have no valid translations would have the corresponding entry in L1 marked invalid. –  Paul A. Clayton Nov 28 '12 at 7:57