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 置換戦略
  • すべての 2 次元配列のサイズ (1:1024、1:1024)
  • 各配列要素は 1 ワードを占有します
  • 2 次元配列は行優先順にメイン メモリにマップされます。

私は解決策を与えられました、そして私の質問はそれから生じます：

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

writeA := readA * readB

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] と同じブロックにあります。したがって、内側のループの 1 回の完全な反復、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 に答える