Determine for the following code how many pages are transferred between disk and

Question

Determine for the following code how many pages are transferred between disk and main memory. Assume each page has 512 words, the active memory set size is (i. e., at any time no more than 1024 pages may be in main memory), and the replacement strategy is LRU (the Least Recently Used page is always replaced): also assume that all 2D arrays are of size (1: 2048, 1: 2048), with each array element occupying one word, for I = 1 to 2048 do for J: = 1 to 2048 do {A[J, I]: = A [J, I] *B[I, J]} provided the arrays are mapped into the main memory space in row-major order.

Explanation / Answer

write to A := read from A * read from B

So the entire row of B is read every time we use it, therefore we count the entire row as transferred (4 pages). But since we only read a portion of each A row (1 value) when we transfer it, we only grab 1 page each time.

2048 * (4 + 2048 * (1 + 1)) = 8396800 transfers

As the inner loop first executes, the system will fetch the block containing A[0,0], then B[0,0]. As J increments, each element of A referenced will come from a separate disk block. A[1,0] is in a different block from A[0,0]. But only every 512th B element referenced will come from a different block; B[0,0] is in the same block as B[0,511]. So for one complete iteration through the inner loop, 2048 calculations, there will be 2048 fetches of blocks from A, 2048 writes of dirty blocks from A, and 4 fetches of blocks from B

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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