Redirected
recategorized by
890 views
2 votes
2 votes

Consider the following extract from a program, written in a C-like language, that computes the transpose of a matrix.

for (i=0; i<N; i++)
    for (j=0; j<N; j++)
        B[i,j]=A[i,j];

$A$ and $B$ are $N \times N$ matrices with floating point entries  that are stored in memory in row-major order as shown in the example below:

A[0,0] A[0,1] A[0,2] ... A[0,N-1] A[1,0] A[1,1] ... A[N-1,N-1]

This program runs under an OS that uses demand-paging. Considering $\textbf{only}$ memory references to the matrix entries, and using the information given below, compute the page fault rate for the matrix transposition code given above.

  • Page size: $2^{10}$ bytes
  • Number of frames allocated to the program: 8
  • Page replacement policy: LRU
  • $N=2^{16}$
  • Size of each matrix entry: 8 bytes
  • Each of $A$ and $B$ is stored starting from the beginning of a page
  • None of the pages allocated to $A$ and $B$ are initially in memory.
recategorized by

4 Answers

4 votes
4 votes
I think page fault will occur to reference elements from both of matrices B and A.

B is accessed in row major order and A is in column major order. Both are stored in memory in row major order.

As page size is 2^10 and each entry size 2^3, number of pages required for one row is 2^9.

At the beginning of the first iteration on referring B[0,0] there will be 1 miss and next 127 element will be loaded so to access element elements of B matrix upto next 127 reference there will be no miss, again after the 128th element (including b[0, 0]) there will be 1 miss and next 127 element will be loaded. Since one row contains 2^16 element at the first iteration to access elements of B there will be total 2^9 misses and for 2^16 iteration there will be total (2^9)*(2^16) misses.

For accessing elements of A a the beginning of first iteration there will be 1 miss and next 127 elements i.e. A[0,1], A[0,2]...A[0,127] will be loaded but the next reference is A[1, 0] which is again a miss. By proceeding this way at the end of the first iteration out of 8 frame in 1 frame elements of B will be there and in rest 7 frame elements of A will be there and every reference to elements of A will be a miss. So total miss for matrix A is (2^16)*(2^16)

So total number of page fault will be =  (2^9)*(2^16) + (2^16)*(2^16)

As LRU is used the latest B frame will never be replaced by any A's frame because B's frame will be accessed at every go, so at one frame there will be B's elements. At the rest 7 frames there will be A's elements sometimes one frame will be obsoleted B's frame. These 7 frame will get continually replaced.

Please correct me if I am wrong.
edited by
1 votes
1 votes
Because the elements in B are accessed column-wise and the matrix is stored in row-major, every element access will cause a page fault. Meaning, B causes as many page faults as it has elements which is N x N = 2^(16 + 16) = 2^(32).

A is accessed row-wise and hence causes page faults for ever 2^7 elements (since 2^7 elements can be stored per page.). Therefore, A causes (2^32) / (2^7) = 2^25 page faults.

Because the last page frame used by B is always the LRU, there is no overlap in pages replaced by matrices A and B. So number of page faults = 2^25 + 2^32.
0 votes
0 votes
Size of matrix given to be 2^(16)*2^(16) means there are 65536 rows and columns respectively page size given to be 2^(10) bytes and element size to be 8  bytes  therefore in one page there would be 128 elements nw the given code is accessing the matrix column wise and storing it row wise in B matrix in one column we have 65536 elements so 512 pages would be required to access  the 65536 elements in one  column   therefore to access 65536 columns so page fault would be 512 *65536 plz correct if I am wrong
edited by

Related questions