質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.76%

  • キャッシュ

    52questions

    キャッシュはドキュメントやデータを一時的に保管するもので、アクセス処理時間を短くするために使用されます。

配列から配列へ要素をコピーする関数におけるキャッシュミス数とキャッシュヒット数の数え方

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 367

ijuya_yika

score 30

C言語で以下のような2次元配列から2次元配列へ要素をコピーする関数があるとします

typedef int array[2][2];

void copy_arr(array A, array B){
    int i, j;

    for(i=0; i<2; ++i){
        for(j=0; j<2; ++j){
            A[j][i] = B[i][j];
        }
    }
}

もし

  • キャッシュが1ブロックサイズ=8バイトで合計容量16バイトまで
  • sizeof(int)が4バイト
  • キャッシュがダイレクトマップ方式で最初は空
  • Bがアドレス0から始まってAがアドレス16から始まる
    とした場合ですが、
  1. キャッシュにB[i][j]が無い(ミス)ので、Bの配列を全てキャッシュに格納(容量が16バイトまでなのでキャッシュはBの要素で埋まる)した後にB[i][j]を読み込む

  2. キャッシュにA[j][i]が無い(ミス)ので、Aの配列を全てキャッシュに格納(容量が16バイトまでなのでキャッシュはAの要素で埋まる)した後にA[j][i]を読み込む

  3. キャッシュにB[i][j+1]が無い(ミス)ので、Bの配列を全てキャッシュに格納(容量が16バイトまでなのでキャッシュはBの要素で埋まる)した後にB[i][j+1]を読み込む

4.キャッシュにA[j+1][i]が無い(ミス)ので、Aの配列を全てキャッシュに格納(容量が16バイトまでなのでキャッシュはAの要素で埋まる)した後にA[j+1][i]を読み込む

(以下(8)まで同じ要領でミスが続く) 
となりミス率は100% (ヒット率は0%) だと思っていたのですが教科書によるとB[1][1]をコピーする時唯一ヒットとなると書いてありました。これはなぜなのでしょうか…?

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

check解決した方法

+1

ダイレクトマップ方式を完全に誤解していました。

ブロックサイズが8なのでブロックオフセットのビット数は2^b = B より b = 3
セット数はS=2なのでセットインデックスのビット数はS = 2^s より s = 1

よってキャッシュのどのセット(今回の場合だと 0 or 1)に配列がロードされるかはアドレスの第3ビットによって決定されるのでしたね 

BとAのそれぞれの要素をArr[int1][int2]の形式にすると

B[0][0] B[0][1] B[1][0] B[1][1]
0-3バイト目 4-7バイト目 8-11バイト目 12ー15バイト目
A[0][0] A[0][1] A[1][0] A[1][1]
16-19バイト目 20-23バイト目 24-27バイト目 28ー31バイト目

アドレスを見るとそれぞれB[0]0x0000B[1]0x1000A[0]0x10000, そしてA[1]0x11000 ⇛ 第3ビットによりA[0],B[0]はセット0へ,A[1],B[1]はセット1へ格納となるのですね

流れとしては
i=0, j=0
B[0][0]をセット0へ(ミス)⇛ セット0のキャッシュが空の為,新しく格納
A[0][0]をセット0へ(ミス)⇛ B[0]を追出し

i=0, j=1
B[0][1]をセット0へ(ミス)⇛ A[0]を追出し
A[1][0]をセット1へ(ミス)⇛ セット1のキャッシュが空の為,新しく格納

i=1, j=0
B[1][0]をセット1へ(ミス)⇛ A[1]を追出し
A[0][1]をセット0へ(ミス)⇛ B[0]を追出し

i=1, j=1
B[1][1]は既にB[1]がセット1に格納されていた為何もしない(ヒット)
A[1][1]をセット1へ(ミス)⇛ B[1]を追出し

で結局唯一のヒットはB[1][1]の時ということがわかりました。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

キャッシュが1ブロックサイズ=8バイト

ということであれば、B[1][0]を参照した場合、B[1](2個分8バイト)だけがキャッシュに乗ります。それを前提に考え直してみてください。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/10/29 21:17 編集

    ご回答ありがとうございます。
    頂いたコメントを元に考え直したのですが、参照の順番は`B[0]`(ミス) ➝ `A[0]`(ミス) ➝ `B[0]`(ヒット) ➝
    `A[1]`(ミス) ➝ `B[1]`(ミス) ➝ `A[0]`(ミス) ➝ `B[1]`(ヒット) ➝ `A[1]`(ミス)で良いと思うのですが、`B[0][1]`の参照の際にヒットにはならないのでしょうか?

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.76%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 解決済

    (char *)とは...

    (char *)の意味 www9.plala.or.jp/sgwr-t/lib/free.html 様のソースコードを読んでいたらむ??となったので質問させていただきました。

  • 受付中

    ArrayListについて

    ArrayListについて質問です ArrayList<String> array = new ArrayList<String>(); array.add("日本");

  • 受付中

    strcpyのエラーに関して

    ある文字列の配列から大文字だけを抽出してそれを別のchar配列に保存したいのですがエラーになります。どのようにすればよいのでしょうか。 char main_array[50]

  • 解決済

    2次元配列の値を関数の引数として渡したい

    タイトルの通り2次元配列で作ったものを関数の引数として渡したいです。また、2次元配列の大きさは固定ではありません。 私が書いたコードは、以下のようになります。 #inclu

  • 受付中

    配列を与えられて計算する

    メソッドfindRangeを作成しなさい。 実数型の配列が与えられる。 全ての要素の値に対して以下の計算を行い,最大値と最小値を求める。 要素の値をxとするとき,|x|

  • 解決済

    初期化子とプロパティ

     前提・実現したいこと イメージ的には、下記のような書き方をしたいのですが、不可能ですか? 下記だとエラーが出ます。  該当のソースコード public array[] a

  • 解決済

    const修飾子について

     前提・実現したいこと 深さ優先探索によって問題を解くプログラムを作成しました. 問題の大まかな内容は,n個のノードとm本の重み付きの無向辺が与えられたとき,その重みに矛盾があるか

  • 解決済

    [java]配列を昇順、降順にソートする方法

    現在、プログラミングの勉強をしており、配列の要素を昇順、降順に並び替えたプログラムを作成したいと思っているのですが、なかなかうまくいきません... 以下は僕が作成したコードなのです

同じタグがついた質問を見る

  • キャッシュ

    52questions

    キャッシュはドキュメントやデータを一時的に保管するもので、アクセス処理時間を短くするために使用されます。