問題タブ [cache-locality]

空間的または時間的な局所性のためにキャッシュラインが再利用されている (キャッシュミスが回避されている) かどうかを検出する実用的なツールはありますか?

cachegrindで関連する議論が見つかりませんでした。thisおよびthis paperのみを見つけることができましたが、それらで紹介されているツールは見つかりませんでした。

私は、キャッシュの局所性をよりよく認識できるように努めてきました。両方のキャッシュの局所性の特徴をよりよく理解するために、2 つのコード スニペットを作成しました。

対

最初のコードv1では、if ステートメント内で直接更新されています。これにより、更新中に現在のキャッシュ ラインが からのデータの連続したセグメントに置き換えられるため、キャッシュの局所性の問題が発生しますv1[i] to v1[cache_line_size/double_size]か? この分析が正しければ、ループjの反復ごとにjキャッシュ ミスが発生する可能性が高いため、ループの速度が低下しているように見えます。2 番目の実装では、ローカル変数を使用し、ループが完了するv1[i]まで更新しないことで、この問題を軽減しているようです。j

実際には、コンパイラがキャッシュの局所性の問題を最適化する可能性があると思いますか? 議論のために、コンパイラーの最適化がないと仮定してはどうですか。

ソートされた配列のバイナリ検索は、メモリのランダム アクセスのためにキャッシュの局所性が低くなる可能性がありますが、線形検索は大きな配列に対して低速です。ハイブリッドアルゴリズムを設計することは可能ですか? たとえば、長さ 100 の並べ替えられた配列を、それぞれの長さが 10 の 10 個のチャンクに分割できます。各チャンク内で、単純な線形検索を実行しますが、「グローバル」レベルでは、従来の意味でバイナリ検索を実行します。検索された値が 1 番目のチャンクにも 10 番目のチャンクにもない場合、中間、つまり 5 番目のチャンク (5 = floor((1+10)/2) のため) を調べます。5 番目のチャンクに含まれていない場合検索された値が 5 番目のチャンクの数値より小さいか大きいかに応じて、3 番目のチャンクまたは 7 番目のチャンクを調べます。

人々はこの種のアルゴリズムを検討しましたか? 実装に取り​​組む価値はありますか?

教授からこの質問を受けましたが、なぜvector2が より高速でキャッシュ ミスが少ないのかわかりませんvector1。

以下のコードが有効なコンパイル可能な C コードであると仮定します。

ベクトル 2:

ベクトル 1:

注: INT4 は、整数のサイズが 4 バイトであることを意味します。

CPU スペックに関しては、キャッシュ サイズ = 12288KB、ライン サイズ = 64B で、メイン メモリとやり取りするこの単一のキャッシュのみを考慮しています。

質問

vector2の実行時間が よりも速いのはなぜvector1ですか? そして、なぜvector1より多くのキャッシュ ミスが発生するのvector2でしょうか?

私と数人のクラスメートはしばらくこれに取り組みましたが、理解できませんでした。vector2配列は常に内側のループでアクセスされていたのに対し、vector1では一度に 1 つの要素しかアクセスされないため、 の方が空間的場所性が優れているためではないかと考えました。これが正しいかどうかはわかりませんし、これにキャッシュ ラインを取り込む方法もわかりません。