ISI2016-PCB-CS-3

Question

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.

Comments

total elements in matrix = 216 * 216.= 232

as page size is 210 and size of each element is 8 bytes,so we can store only 2^7 elemnts in one frame.

aftr a miss,elements will be loaded in row major order like A[0,0] A[0,1 ,A[0,2]..A[0,127].

but here elements are accessed in column major order i.e A[0,0] then A[1,0] -> A[2,0] ....A[216,0].

sor,for each element accessed,there will be a miss.

now,when A[0,0] will be accessed then there will be a miss and A[0,0] to A[0,127] will be brought to first frame.  // MISS 1

when A[1,0] will be accessed then another miss and A[1,0] to A[1,127] will be loaded to second frame.//MISS 2

similarly we will have 8 misses till 8th frame is filled.and in 8th frame,A[7,0] TO A[7,127] will be there.

now next is A[8,0].as all frames are full,we need to replace and LRU is used.so,8th frame will be replaced and A[8,0 to A[8,127] will be loaded.

similarly,for all the accesses till A[216-1,0],the 8th frame will be replaced.so ,for first iteration,we will get 216  misses.the content of 8th frame will be A[65535,0] to A[65535,127].

for next iteration,A[0,1] will be accessed first but there will be no miss for that as it was already loaded in first frame when A[0,0] was loaded.

similarly for A[1,1] A[2,1] A[3,1] A[4,1] A[5,1] A[6,1]..no miss will occur.but for A[7,1],miss will occur and it will replace 7th frame as it is least recently used.so,wee will load A[7,1 ] to A[7,128].similarly,for all the consecutive accesses for elements A[8,1] to A[65534,1],we will get a miss.,for A[65535,1],no miss will occur as it is already loaded in 8th frame in first iteration.and hence total misses in second iteration will be 216 -8

so,now content of 7th frame will be a[65534,1] to A[65534,128].

in next iteration,from A [0,2] to A[5,2]  ,no miss occurs

for A[65534,2] and A[65535,2] also,no miss occurs as they are already loaded.in last iteration.

but all the elements from A[6,2] to A[65533,2] will be loaded in 6th frame as it is least recently used

hence total misses are 216 - 8 misses.

going on,i guess we will get 216 + 65534 * ( 216 -8) misses.

i know i am wrong somewhere,so pls point out my mistake and help. :)

---

16 is in power of 2

Answer 1

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.

Comments

devashish,in the question it is given that LRU is used..so u have to consider that also.

---

Thank you Akriti for noting that. Actually I have built the procedure always by keeping in mind about LRU, just forgot to mention it. I have updated the answer.

---

actualy i am really getting confused regarding this LRU thing and i had'nt considered accessing B in my solution.

only an expert can help us now with this..

can you pls check my comment above?do you know the answer??

Answer 2

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.

Answer 3

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

Comments

total number of elements are 2^32 ,not 65536 and LRU is used

---

I mean to say there are 65536 elements in 1 column and rite I have nt used LRU and in your answer u  have replaced 8th frame should nt we replace 1frame

Answer 4

https://gateoverflow.in/119710/isi-2016-pcb-c3?show=119710#q119710