Hamacher pg255 question 520 1024x1024 array of 32bit numbers

(Hamacher, pg.255, question 5.20) 1024x1024 array of 32-bit numbers is to be normalized as follows. For each column the largest element is found and all elements of the column are divided by this maximum value.Assume that each page in the virtual memory consists of 4Kbytes and that 1Mbytes of the main memory are allocated for storing data during this computation. Suppose that it takes 40 ms to load a page from the disk to the main memory when a page fault occurs (assume that when we start, the main memory is empty ). a. How many page faults would occur if the elements of the array are stored in column order in the virtual memory? b. How many page faults would occur if the elements are stored in row order? c. Estimate the total time needed to perform this normalization for both arrangements a & b. Assume that it takes 2 ns to do a comparison, 20 ns to do a divide and 100 ns to do a load/store to memory.

Solution

1024 x 1024 array and each 32-bit number comprises 4 bytes.

So the each page holds 1024 numbers.

256 pages space are given in 1MB size of the memory. This memory was allocated during the execution and computation.

a) Page fault is occurring when the operating system is selected a page from the existing pages and replaced it by the page that the program wants to access which is present on the disk. This could be occur when the page fault.

     Hence in the each column is one page; there will be 1024 page faults.

b ) all the column at a time processing is not good and it impacts the processor and it is not efficient. Also this is could be slow. To avoid this processed the columns in short amount means if only one quarter of each column (for all columns) is processed before the next quarter is brought in from the disk.

In this case each column is loaded into twice because it occurs in previous group as well as next group. So the number of page faults would be 1024 page faults loads twice so 1024x 2= 2048

c) Computation of normalization of numbers is very little when compared to bring the page form the disk to memory.

Given Time to load each page is 40 ms

For question a page faults are 1024

So 1024 x 40 ms =40960ms time is needed

For question b page faults are 2048

So 2048 x 40ms =81920ms time is needed