Determine for the following code how many pages are transferred betu\'een disk a

Question

Determine for the following code how many pages are transferred betu'een disk and main rnemory, assuming each page has 512 words, the active memory set size is 256 (i. e., at any time no more than 256 pages miiy be in main memory), and the replacement strategy is LRU (the Least Recently Used page is always replaced); also assume that all two-dimensional arrays are of size (1 :1024, I:1024), with each array element occupying one word,

for I := 1 to 1024 do

for J : =1 to 1024 do

{ A[I;J] = A[I,J] *B[J,I] ]

provided the arrays are mapped into the main memory space in column-major order,

Explanation / Answer

Solution :

Number of pages needed to store matrix B = 1024*1024/ 512 = 2048 pages

Number of pages needed to store matrix A = 1024*1024/ 512 = 2048 pages

here number of operations = 1024*1024

[  A[I;J] = A[I,J] *B[J,I] is performed 1024*1024 times ].

Here matrix B is accessed sequentially. i.e B is accessed in a way it is stored in memory.

So after reading every 512 words new page will be requested.

Hence , 2048 requests are there for matrix B.

Matrix A is used in row order. i.e with each operation, only one word of each block is used.

At a time 255 blocks of matrix A can be there in main memory.

Hence, with each operation, there is one request for one block of A.

and for every 512 operations there is one request for one block of B.

Hence total number of replacements = replacements for matrix B + replacements for matrix A

replacements for matrix B = 2048

replacements for matrix A = 1024*1024

hence total replacements = 2048 + 1024*1024

if you have any doubts then you can ask in comment section.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.