c - キャッシュのレベルとサイズを決定するCプログラム

Question

明確にするための完全な書き直し/更新（そしてあなたの正気、その少し長すぎる）...（古い投稿）

割り当てについては、各キャッシュのレベル（L1、L2、...）とサイズを見つける必要があります。ヒントと私がこれまでに見つけたものを考えると、アイデアはさまざまなサイズの配列を作成してそれらを読み取ることだと思います。これらの操作のタイミング：

sizes = [1k, 4k, 256K, ...]
foreach size in sizes 
    create array of `size`

    start timer
    for i = 0 to n // just keep accessing array
        arr[(i * 16) % arr.length]++ // i * 16 supposed to modify every cache line ... see link
    record/print time

更新（9月28日午後6時57分UTC + 8）

完全なソースも参照してください

@mahのアドバイスに従って、SNR比の問題を修正した可能性があります...また、コードのタイミングをとる方法を見つけました（wall_clock_timeラボのサンプルコードから）

ただし、間違った結果が得られているようです。IntelCore i3 2100を使用しています：[仕様]

• L1：2 x 32K
• L2：2 x 256K
• L3：3MB

私が得た結果は、グラフで：

lengthMod：1KBから512K

1番目のピークのベースは32Kです...妥当です...2番目のピークは384Kです...なぜですか？私は256を期待していますか？

lengthMod：512kから4MB

では、なぜこの範囲が混乱しているのでしょうか。

---

他のアプリケーションからのプリフェッチや干渉についても読んだので、スクリプトの実行中にできるだけ多くのものを閉じましたが、1MB以上のデータは常に非常に乱雑であるように見えますか？

Answer 1

Intelの取扱説明書を10分間検索し、さらに10分間コーディングした後、私はこれを思いつきました（Intelベースのプロセッサの場合）。

void i386_cpuid_caches () {
    int i;
    for (i = 0; i < 32; i++) {

        // Variables to hold the contents of the 4 i386 legacy registers
        uint32_t eax, ebx, ecx, edx; 

        eax = 4; // get cache info
        ecx = i; // cache id

        __asm__ (
            "cpuid" // call i386 cpuid instruction
            : "+a" (eax) // contains the cpuid command code, 4 for cache query
            , "=b" (ebx)
            , "+c" (ecx) // contains the cache id
            , "=d" (edx)
        ); // generates output in 4 registers eax, ebx, ecx and edx 

        // See the page 3-191 of the manual.
        int cache_type = eax & 0x1F; 

        if (cache_type == 0) // end of valid cache identifiers
            break;

        char * cache_type_string;
        switch (cache_type) {
            case 1: cache_type_string = "Data Cache"; break;
            case 2: cache_type_string = "Instruction Cache"; break;
            case 3: cache_type_string = "Unified Cache"; break;
            default: cache_type_string = "Unknown Type Cache"; break;
        }

        int cache_level = (eax >>= 5) & 0x7;

        int cache_is_self_initializing = (eax >>= 3) & 0x1; // does not need SW initialization
        int cache_is_fully_associative = (eax >>= 1) & 0x1;

        // See the page 3-192 of the manual.
        // ebx contains 3 integers of 10, 10 and 12 bits respectively
        unsigned int cache_sets = ecx + 1;
        unsigned int cache_coherency_line_size = (ebx & 0xFFF) + 1;
        unsigned int cache_physical_line_partitions = ((ebx >>= 12) & 0x3FF) + 1;
        unsigned int cache_ways_of_associativity = ((ebx >>= 10) & 0x3FF) + 1;

        // Total cache size is the product
        size_t cache_total_size = cache_ways_of_associativity * cache_physical_line_partitions * cache_coherency_line_size * cache_sets;

        printf(
            "Cache ID %d:\n"
            "- Level: %d\n"
            "- Type: %s\n"
            "- Sets: %d\n"
            "- System Coherency Line Size: %d bytes\n"
            "- Physical Line partitions: %d\n"
            "- Ways of associativity: %d\n"
            "- Total Size: %zu bytes (%zu kb)\n"
            "- Is fully associative: %s\n"
            "- Is Self Initializing: %s\n"
            "\n"
            , i
            , cache_level
            , cache_type_string
            , cache_sets
            , cache_coherency_line_size
            , cache_physical_line_partitions
            , cache_ways_of_associativity
            , cache_total_size, cache_total_size >> 10
            , cache_is_fully_associative ? "true" : "false"
            , cache_is_self_initializing ? "true" : "false"
        );
    }
}

参照： インテル®64およびIA-32アーキテクチャー開発者マニュアル：Vol。2A 、3-190ページ、CPUID-CPUID。

最新のプロセッサではキャッシュのプリフェッチをオフにすることはほとんど不可能であるため、これはキャッシュレイテンシを測定するよりもはるかに信頼性が高くなります。別のプロセッサアーキテクチャについて同様の情報が必要な場合は、それぞれのマニュアルを参照する必要があります。

Answer 2

時間の測定にかかる時間（つまり、clock（）関数を呼び出すだけの時間）は、実行にかかる時間よりも何倍も長くなりますarr[(i*16)&lengthMod]++。この非常に低い信号対雑音比（他の可能性のある落とし穴の中でも）は、計画を実行不可能にします。問題の大部分は、ループの1回の反復を測定しようとしていることです。リンクしたサンプルコードは、反復の完全なセットを測定しようとしています（ループを開始する前にクロックを読み取り、ループから出た後に再度読み取ります。ループ内でprintf（）を使用しないでください）。

ループが十分に大きい場合は、信号対雑音比の問題を克服できる可能性があります。

「どの要素がインクリメントされているか」について; arr1MBのバッファのアドレスです。そのアドレスからオフセットを生成しますarr[(i * 16) & lengthMod]++;。(i * 16) * lengthModそのオフセットは、インクリメントされるintのアドレスです。シフト（i*16はi<<4に変わります）、論理積、そしてCPUに応じて、読み取り/追加/書き込みまたは単一の増分のいずれかを実行しています）。

編集：説明したように、メモリアクセス（キャッシュまたはキャッシュなし）の相対速度と時間を測定するためだけに関数を呼び出すため、コードのSNR（信号対ノイズ比）が低下します。現在取得しているタイミングを取得するために、コードを次のように変更したと仮定します。

int main() {
    int steps = 64 * 1024 * 1024;
    int arr[1024 * 1024];
    int lengthMod = (1024 * 1024) - 1;
    int i;
    double timeTaken;
    clock_t start;

    start = clock();
    for (i = 0; i < steps; i++) {
        arr[(i * 16) & lengthMod]++;
    }
    timeTaken = (double)(clock() - start)/CLOCKS_PER_SEC;
    printf("Time for %d: %.12f \n", i, timeTaken);
}

これにより、測定値がループの外側に移動するため、単一のアクセスを測定するのではなく（実際には不可能です）、stepsアクセスを測定します。

必要に応じて自由に増やすことができsteps、これはタイミングに直接影響します。受信する時間が近すぎて、場合によっては反転することもあるため（時間はサイズ間で変動しますが、キャッシュが原因ではない可能性があります）、の値をstepsに256 * 1024 * 1024またはそれ以上に変更してみてください。

注：steps論理積であり、バッファーでラップアラウンドすることを保証するため、signed int（十分な大きさである必要があります）に収まる限り大きくすることができます。

Answer 3

私はこれを知っている！（実際には、プリフェッチのために非常に複雑です）

 for (times = 0; times < Max; time++) /* many times*/
     for (i=0; i < ArraySize; i = i + Stride)
           dummy = A[i]; /* touch an item in the array */

ストライドを変更すると、キャッシュのプロパティをテストできます。グラフを見ることで、あなたはあなたの答えを得るでしょう。

スライド35〜42をご覧くださいhttp://www.it.uu.se/edu/course/homepage/avdark/ht11/slides/11_Memory_and_optimization-1.pdf

Erik Hagerstenは本当に優秀な教師です（そしてまた本当に有能で、ある時点で太陽の主任建築家でした）ので、彼のスライドの残りの部分を見て、より素晴らしい説明を見つけてください！

Answer 4

1MBを超える奇妙な数字についての質問に答えるのは、非常に簡単です。分岐予測に関係するキャッシュエビクションポリシー、およびL3キャッシュがコア間で共有されるという事実。

コアi3は非常に興味深いキャッシュ構造を持っています。実際、最近のプロセッサならどれでもそうです。ウィキペディアでそれらについて読む必要があります。「まあ、おそらくこれは必要ないだろう...」と判断する方法はいろいろあります。そうすれば、「被害者のキャッシュに入れます」などと言うことができます。L1-2-3キャッシュのタイミングは、多数の要因と行われた個々の設計上の決定に基づいて、非常に複雑になる可能性があります。

その上、これらすべての決定とそれ以上（このテーマに関するウィキペディアの記事を参照）は、2つのコアのキャッシュ間で同期する必要があります。共有L3キャッシュを個別のL1およびL2キャッシュと同期する方法は見苦しく、バックトラッキングや計算のやり直しなどの方法が必要になる場合があります。完全に無料のセカンドコアがあり、L3キャッシュスペースをめぐって競合するものがないため、同期がおかしくなる可能性はほとんどありません。

一般に、カーネルを複雑にするなど、データを処理している場合は、データがL1キャッシュ内に収まるようにし、その周りのアルゴリズムを形成する必要があります。L3キャッシュは、実際には、データセットを実際の方法で操作するためのものではありません（メインメモリよりも優れていますが）。

私がキャッシュアルゴリズムを実装しなければならないのなら、私は気が狂ってしまうだろうと誓います。

Answer 5

さまざまな歩幅でのベンチマークについては、オープンソースのlmbenchパッケージからlat_mem_rdを試すことができます：http：//www.bitmover.com/lmbench/lat_mem_rd.8.html

Windows用のポートをhttp://habrahabr.ru/post/111876/に投稿しました。ここにコピーして貼り付けるのは非常に時間がかかります。それは2年前のことで、最近のCPUではテストしていません。

Answer 6

Windowsの場合、GetLogicalProcessorInformationメソッドを使用できます。

Linuxの場合は、を使用できますsysconf()。またはの有効な引数sysconfを見つけることができます/usr/include/unistd.h/usr/include/bits/confname.h