0 
for I := 1 to 1024 do
    for J := 1 to 1024 do
        A[J,I] := A[J,I] * B[I,J]

对于给定的代码，我想根据以下假设计算在磁盘和主内存之间传输了多少页：

  • 页面大小 = 512 字
  • 主内存中不能超过 256 页
  • LRU 替换策略
  • 所有二维数组大小 (1:1024,1:1024)
  • 每个数组元素占 1 个字
  • 二维数组以行优先顺序映射到主存中

我得到了解决方案，我的问题源于：

A[J,I] := A[J,I] * B[I,J]

写A := 读A * 读B

请注意，每个 J 循环有 2 次传输更改，而每个 I 循环仅更改 1 次传输。

1024 * (8 + 1024 * (1 + 1)) = 2105344 次转移

所以每次我们使用它时都会读取 B 的整行，因此我们将整行计算为已传输（8 页）。但是由于我们在传输时只读取了每个 A 行的一部分（1 个值），所以每次只抓取 1 页。

所以我想弄清楚的是，我们如何获得每次读取 B 时传输 8 页但每次读取和写入 A 时仅传输 1 个页面？

4

1 回答 1

1

我对你感到困惑并不感到惊讶，因为我当然是。

部分混淆来自于将数组标记为 1:1024。我不能那样想，我将它们重新标记为 0:1023。

我采用“行主要顺序”表示 A[0,0] 与 A[0,511] 位于同一磁盘块中。下一个块是 A[0,512] 到 A[0,1023]。然后 A[1,0] 到 A[1,511]... 和 B 的排列相同。

当内部循环首先执行时，系统将获取包含 A[0,0] 的块，然后是 B[0,0]。随着 J 的增加，所引用的 A 的每个元素都将来自一个单独的磁盘块。A[1,0] 与 A[0,0] 位于不同的块中。但是只有每个被引用的第 512 个 B 元素将来自不同的块；B[0,0] 与 B[0,511] 位于同一块中。因此，对于内部循环的一次完整迭代，1024 次计算，将从 A 获取 1024 次块，从 A 写入 1024 次脏块，从 B 获取 2 次块。总共 2050 次访问。我不明白为什么您的答案说将从 B 提取 8 次。如果 B 未在 512 字边界上对齐，则每个周期将从 B 提取 3 次；但不是 8。

对于外部循环中的每个 I 值，都会发生相同的模式。假设 B 是 512 字对齐的，这使得读取和写入的总块数为 2050*1024 = 2099200。

我完全准备好让别人指出我明显的大器晚成——他们通常会这样做——但你得到的解释对我来说似乎是错误的。

于 2012-12-15T12:32:01.837 回答