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

Question

• 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

Answer 1

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

Answer 2

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!

Answer 3

Adding the exact question as this was asked in GATE2004

Consider a system with a two-level paging scheme in which a regular memory access takes 150 nanoseconds, and servicing a page fault takes 8 milliseconds. An average instruction takes 100 nanoseconds of CPU time, and two memory accesses. The TLB hit ratio is 90%, and the page fault rate is one in every 10,000 instructions. What is the effective average instruction execution time?

Answer:

Average Instruction execution time

= Average CPU execution time + Average time for getting data(instruction operands from memory for each instruction)

= Average CPU execution time + Average address translation time for each instruction + Average memory fetch time for each instruction + Average page fault time for each instruction

= 100 +2(0.9(0)+0.1(2×150)) +2×150 +1/10000×8×10^6

(Page Fault Rate per 10,000 instruction is directly given in question and this is not per memory access.Two memory accesses per instruction and hence we need 2 × address translation time for average instruction execution time)

[ TLB access time assumed as 0, and 2 page tables need to be accessed in case of TLB miss as the system uses two-level paging ]

= 100+60+300+800

= 1260ns

Answer 4

Average Instruction Execution time = Instruction time + 2*(Average Memory Access time) Average memory access time = 0.9(0) + 0.1(2*150) + 150 + 1/10000(8)*10^6 =980ns. Now, Average Instruction Execution time = 100 + 2*980 =2060ns.