4

空間的局所性に関してキャッシュ操作を学んでいます。（これまでの私の参考資料は、LinとSnyderによる並列プログラミングの原則、このチュートリアル、そしてもちろんWikipediaです。）

次の例を見てください。gccでコンパイルされ、Windows 7 Professionalで実行され、Intel Core2 Duo CPU（L7500）を使用しています。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    int *array;
    int length;
    int count;
    int range;
    int i;

    // generate an array of a million integers between 0 and 99
    length = 1000000;
    range = 100;
    array = calloc(length, sizeof(int));
    srand(time(NULL));
    for(i = 0; i < length; i++)
    {
        array[i] = rand() % range;
        // printf("%d\n", array[i]);
    }

    // count the number of occurrences of 3 in the array
    count=0;
    for(i=0; i<length; i++)
    {
        if(array[i]==3)
        {
            count++;
        }
    }
    printf("count = %6d\n", count);

    return 0;
}

ルーチンの後半では、整数の配列全体が読み取られるため、空間的な場所ごとに、CPUは事前に整数をキャッシュにロードする必要があります。しかし、ループ中の任意の時点で、アレイのどのくらいの量をキャッシュにロードできますか/しますか/ロードする必要がありますか？一度に1つのキャッシュライン（64バイト/intあたり4バイト=16整数）、それの大きなブロック、または一挙に配列全体？

また、私が理解していることから、RAMからキャッシュに（または教科書ごとに、非ローカルメモリからローカルメモリに）データをロードすることに伴う遅延は、実際にルーチンを実行するのに必要な時間よりもはるかに重要です。本当ですか？

ここで、このコードをマルチプロセッサ/マルチコアマシンに移動し、コードのカウント部分を4、8、16などの並列スレッド（pthreadを使用）で実行するように変更し、配列の個別の部分をカウントしてから、プライベートは最後に一緒にカウントされます。これにより、RAMからキャッシュへのレイテンシが複数回発生し、パラレルバージョンの実行がシリアルバージョンよりも遅くなる可能性がありますか？

4

1 に答える 1

2

はい、メモリ速度とレイテンシは多くのアルゴリズムを支配しており、これらを高速化するには、メモリ キャッシュをできるだけ効率的に使用する必要があります。

並行して実行するとパフォーマンスが低下する可能性がありますが、通常はそうではありません。これを理解するには、多くのテストと微調整が必​​要です。

たとえば、RAM の 1 つのバンクに接続されたクアッド コア チップを考えてみましょう。アルゴリズムが最大速度のメモリ読み取りを必要とし、計算が RAM 速度よりも常に高速である場合、並列実行しても何も得られず、おそらく速度が低下します。

しかし、デュアル ソケット システムを使用している場合、各 CPU には独自の RAM があり、アルゴリズムは高速化されます。

または、システムが 1 バンクの RAM から 4 バンクにアップグレードし、シングル チャネルからクアッド チャネル RAM 構成に切り替える場合があります。その時点で、RAM 速度が計算速度を超える可能性があり、クアッド コアはより多くのスレッドを実行することでメリットが得られます。

私の意見では、コアごとにスレッドを実行すると、通常はメリットがあり、システムのアップグレードを利用できます。単一のスレッドを実行すると、少量の同期オーバーヘッドを回避できる場合がありますが、将来的には常にプログラムが制限されます。

于 2012-04-26T16:52:53.927 に答える