10

次の2つのコードスニペットのヒット率とミス率を理解するのに問題があります。

与えられた情報：16バイトのブロックサイズを持つ1024バイトの直接マップされたキャッシュがあります。つまり、64行（この場合はセット）になります。キャッシュが空から始まると仮定します。次のコードを検討してください。

struct pos {
    int x;
    int y;
};

struct pos grid[16][16];
int total_x = 0; int total_y = 0;

void function1() {
    int i, j;
    for (i = 0; i < 16; i++) {
         for (j = 0; j < 16; j++) {
             total_x += grid[j][i].x;
             total_y += grid[j][i].y;
         }
    }
}

void function2() {
    int i, j;
    for (i = 0; i < 16; i++) {
         for (j = 0; j < 16; j++) {
             total_x += grid[i][j].x;
             total_y += grid[i][j].y;
         }
    }
}

いくつかの基本的なルール（つまり、C配列は行優先の順序）から、function2の方が優れている必要があることがわかります。しかし、ヒット/ミスのパーセンテージを計算する方法がわかりません。どうやらfunction1（）は50％の確率で失敗しますが、function2（）は25％の確率で失敗します。

誰かがそれらの計算がどのように機能するかを私に教えてもらえますか？私が実際に見ることができるのは、グリッドの半分以下が一度にキャッシュ内に収まるということです。また、この概念はk-wayアソシアティブキャッシュに簡単に拡張できますか？

ありがとう。

4

2 に答える 2

12

データをメモリに保存する方法
すべての構造posのサイズは8バイトであるため、合計サイズpos[16][16]は2048バイトです。また、配列の順序は次のとおりです
pos[0][0] pos[0][1] pos[0][2]。...... .................。pos[0][15] pos[1]0[]pos[1][15]pos[15][0]pos[15][15]

データと比較したキャッシュ構成
キャッシュの場合、各ブロックは16バイトであり、これは配列の2つの要素と同じサイズです。キャッシュ全体は1024バイトで、これはアレイ全体の半分のサイズです。キャッシュは直接マッピングされるため、キャッシュブロックに0から63のラベルを付けると、マッピングは次のようになると安全に想定できます
------------メモリ------ ----------------------キャッシュ
pos[0][0] pos[0][1] -----------> block 0
pos[0][2] pos[0][3] -----------> block 1
pos[0][4] pos[0][5] --- --------> block 2
pos[0][14] pos[0][15] --------> block 7
.......-----------
pos[1][0] pos[1][1] > block 8
pos[1][2] pos[1][3] -----------> block 9
。 ......
pos[7][14] pos[7][15] --------> block 63
pos[8][0] pos[8][1] -----------> block 0
.......
pos[15][14] pos[15][15] -----> block 63

function1メモリの操作方法
ループは列単位の内部ループに従います。つまり、最初の反復がロードpos[0][0]されpos[0][1]てキャッシュさblock 0れ、2番目の反復がロードpos[1][0]されpos[1][1]てキャッシュされblock 8ます。キャッシュはコールドであるため、最初の列xは常に欠落していますが、y常にヒットしています。2番目の列のデータは、最初の列へのアクセス中にすべてキャッシュにロードされると思われますが、そうではありません。pos[8][0]アクセスはすでに前のページを削除しているのでpos[0][0]（両方とも！にマップされblock 0ます）、以下同様に、ミス率は50％です。

function2メモリの操作方法
2番目の関数には、ストライド1アクセスパターンがあります。つまりpos[0][0].x pos[0][0].y pos[0][1].x pos[0][1].y、最初の1つだけにアクセスする場合は、コールドキャッシュが原因でミスになります。次のパターンはすべて同じです。したがって、ミス率はわずか25％です。

K-wayアソシアティブキャッシュは同じ分析に従いますが、それは面倒かもしれません。キャッシュシステムを最大限に活用するには、たとえばstride-1、適切なアクセスパターンを開始し、メモリからの各ロード中に可能な限りデータを使用するようにしてください。実世界のCPUマイクロアーキテクチャは、効率を高めるために他のインテリジェントな設計とアルゴリズムを採用しています。最良の方法は、常に実世界で時間を測定し、コアコードをダンプして、徹底的な分析を行うことです。

于 2012-07-10T12:13:59.133 に答える
1

さて、私のコンピュータサイエンスの講義は少し遠いですが、私はそれを理解したと思います（あなたがそれについて考えるとき、それは実際には非常に簡単な例です）。

構造体の長さは8バイト（2 x 4）です。キャッシュブロックは16バイトであるため、メモリアクセスは正確に2つの構造体エントリ（および）grid[i][j]をフェッチします。したがって、2番目のインデックスをループすると、4回目のアクセスごとにのみメモリの読み取りが発生します。最初のインデックスをループする場合、フェッチされた2番目のエントリを破棄する可能性があります。これは、内部ループでのフェッチの数と全体的なキャッシュサイズによって異なります。grid[i][j]grid[i][j+1]

ここで、キャッシュサイズについても考慮する必要があります。直接マップされる64行があると言います。関数1では、内部ループは16回のフェッチです。つまり、grid [j] [i+1]に到達する17番目のフェッチです。これは実際にはヒットするはずです。これは、最後の内部ループウォーク以降にキャッシュに保持されている必要があるためです。したがって、1つおきの内部ループはヒットのみで構成されている必要があります。

さて、私の推論が正しければ、あなたに与えられた答えは間違っているはずです。両方の機能は25％のミスで実行されるはずです。誰かがより良い答えを見つけるかもしれませんが、私の推論を理解しているなら、私はそれについてTAに尋ねます。

編集：もう一度考えてみると、最初に、実際にミス/ヒットと見なされるものを定義する必要があります。あなたが見るとき

total_x += grid[j][i].x;
total_y += grid[j][i].y;

これらは2つのメモリアクセスまたは1つのメモリアクセスとして定義されていますか？最適化設定を備えたまともなコンパイラは、これを次のように最適化する必要があります

pos temp = grid[j][i];
total_x += temp.x;
total_y += temp.y;

これは、1回のメモリアクセスとしてカウントできます。したがって、私はすべてのCSの質問に対する普遍的な答えを提案します：「それは依存します」。

于 2012-07-10T06:37:57.807 に答える