-1

ヒット率は、キャッシュ内で見つかったデータの割合です。しかし、アルゴリズムのヒットを見つける方法がわかりません。私は、コード 1 の場合、それぞれ 4 つの要素を持つ 11 個のブロックがあり、コード 2 の場合、それぞれ 11 個の要素を持つ 4 つのブロックがあり、4 つの要素が欠落しているのを見るたびに考えていました。それがまったく意味があるかどうかはわかりません。どんなアドバイスも歓迎します

11 行 x 4 列の 2 次元配列 A が次のようにメモリに格納されているとします。[0][0], [0][1], [0][2], [0][3], [1][0], [1][1], …[10][2], [10][3]

また、各メモリ ブロックが 4 バイトを保持する 10 個のメモリ ブロックの完全連想型シングル レベル キャッシュと、FIFO 置換ポリシーを想定します。

各行は正確に 1 つのキャッシュ ブロックに収まりますが、残念なことに配列全体がキャッシュに収まりません。キャッシュが 1 行小さすぎます...

次の 2 つのコードを考えると、1- ヒット率を計算する方法 2- キャッシュ アクセス時間が 5ns でメモリ アクセス時間が 70ns であり、メモリとキャッシュへのオーバーラップ アクセスを想定すると、各コードの EAT を計算する方法?

コード 1:

for (int row = 0; row < 11; row ++)
{
   for (int column = 0; column < 4; column ++)
   {
      myByte = A [ row, column ];
   }
}

コード 2:

for (int column = 0; column < 4; column ++)
   {
   for (int row = 0; row < 11; row ++)
   {
      myByte = A [ row, column ];
   }
}

どんな助けでも大歓迎です。ありがとう

4

1 に答える 1

0

アルゴリズムのヒット率は計算しません。キャッシュの概念を利用するような方法でアルゴリズムを記述します。つまり、最大のヒット率を取得します。あなたの質問は、実際にはコンピュータの組織とアーキテクチャに属しています。

とにかく、あなたの 2D - 配列は行優先順でメモリに格納されます。したがって、コード 1 の場合、最初の内部 for ループでは、4 つの要素を含むブロックがメモリからフェッチされます。これは、キャッシュ内に何も見つからなかったためです (つまり、ミスであるため) (つまり、メモリ アクセス時間は 70ns)。 ][1],[0][2],[0][3] は cahce からフェッチされます (つまり、3*5 = 15ns)。つまり、最初の 4 つの要素にアクセスするための合計時間 = 70+3*5 = 85ns です。

上記のプロセスは、10 個のキャッシュ ブロックに対して配列の 10 行に対して繰り返されます。ただし、FIFO コンセプトを使用する最後のブロックでは、ブロックのスワップが行われますが、時間は同じままです。したがって、合計時間 = 85*11 = 935ns

コード 2 の場合、

内部 for ループの反復ごとに、ブロックがフェッチされます。したがって、メモリにアクセスするたびに、その場合はキャッシュの概念を利用していません。つまり、悪いコードです。コード 2 は、配列がメモリに列優先順に格納されている場合に最適に機能します。

于 2013-03-26T06:55:40.543 に答える