Consider the following program: -#define Size 64 int A[Size; Size], B[Size; Size
ID: 3572173 • Letter: C
Question
Consider the following program:
-#define Size 64
int A[Size; Size], B[Size; Size], C[Size; Size];
int register i, j;
for (j = 0; j< Size; j ++)
for (i = 0; i< Size; i++)
C[i; j] = A[i; j] + B[i; j];
Assume that the program is running on a system using demand paging and the page size is 1 Kilobyte. Each integer is 4 bytes long. It is clear that each array requires a 16-page space. As an example, A[0, 0]-A[0, 63], A[1, 0]-A[1, 63], A[2, 0]-A[2, 63], and A[3, 0]-A[3, 63] will be stored in the first data page. A similar storage pattern can be derived for the rest of array A and for arrays B and C. Assume that the system allocates a 4-page working set for this process. One of the pages will be used by the program and three pages can be used for the data. Also, two index registers are assigned for i and j (so, no memory accesses are needed for references to these two variables).
a. Discuss how frequently the page fault would occur (in terms of number of times C[i, j] = A[i, j] + B[i, j] are executed).
b. Can you modify the program to minimize the page fault frequency?
c. What will be the frequency of page faults after your modification?
Explanation / Answer
We know that :-
for (j = 0; j< Size; j ++)
for (i = 0; i< Size; i++)
C[i; j] = A[i; j] + B[i; j];
Access order according to the above loop is
A[0,0] A[1,0]...A[0,63] , A[1,0],A[1,1]..A[1,63] , A[2,0],A[1,1]..A[1,63] , A[3,0],A[1,1]..A[1,63] ,
A[4,0] .....A[4,63] etc
And for B its similar,
B[0,0] B[1,0]...B[0,63] , B[1,0],B[1,1]..B[1,63] , B[2,0],B[1,1]..B[1,63] , B[3,0],B[1,1]..B[1,63] ,
B[4,0] .....B[4,63] etc
Coming to the Memory part , We have 4 pages where 1 has the program and 3 have the data set
Lets says A, B, C are in three data set and the storage order is given
A[0, 0]-A[0, 63], A[1, 0]-A[1, 63], A[2, 0]-A[2, 63], and A[3, 0]-A[3, 63] , We can see When j = 4 there is Page fault
A[0, 0]-A[0, 63], A[1, 0]-A[1, 63], A[2, 0]-A[2, 63], and A[3, 0]-A[3, 63] --> 256 elements , each is 4 bytes so total 1024 bytes = 1KB
a. Discuss how frequently the page fault would occur (in terms of number of times C[i, j] = A[i, j] + B[i, j] are executed). ---> When j = 4 , we have 3 page faults for A, B, C, So there is three page fault for every 4th execution.
b. Can you modify the program to minimize the page fault frequency?
Yes, We can change the order of execution,i.e
for (i = 0; i< Size; i++)
for (j = 0; j< Size; j ++)
C[i; j] = A[i; j] + B[i; j];
In this way wat will happen is , We will be accessing in A[0,0] A[0,63] ....A[1,0]A[1,63] ... A[63,0],A[63,63] etc
So there will be less page faults
c. What will be the frequency of page faults after your modification?
Since we accessed 256 elements from A[0, 0]-A[0, 63], A[1, 0]-A[1, 63], A[2, 0]-A[2, 63], and A[3, 0]-A[3, 63] , B and C as well So there we only three page faults for 256 executions