Consider the following program fragment that deals with a table T with 17 rows and 1024 columns, computing an average for each column and printing it to screen, where i is row index and j is column index:
for j = [0.....1023] {
temp = 0;
for i = [0....16]:
temp = temp + T[i][j];
print(temp/17.0);
}
T[i][j] and temp are 32 bit floating point values and memory is word addressable. The temporary variable temp is kept in a processor register so access to temp does not involve a memory reference. The main memory is paged and holds 16 pages of size 1024 words, the page replacement policy is "least recently used", if T is stored in the virtual address space in row major format.
How many page faults will be encountered?
Solution
T has 17 rows and 1024 columns.
Page size = 1024 words
Since memory is word addressable and each element is 1 word, each row contains:
$1024$ words
So, in row major format, each row occupies exactly one page.
Total pages for T:
$17$ pages
Main memory can hold only 16 pages.
The program accesses elements column-wise:
$T[0][j], T[1][j], T[2][j], \ldots, T[16][j]$
So, for each column, it accesses 17 different pages.
Since memory can hold only 16 pages and LRU is used, every access causes a page fault.
Total memory accesses:
$17 \times 1024 = 17408$
Therefore, total page faults:
$17408$