キャッシュの使用、空間的局所性、および待ち時間

Question

私は空間的局所性に関するキャッシュ操作を学習しています。 （私の参照は、これまでthis tutorial、林とスナイダーによって並列プログラミングの原則であり、もちろん、ウィキペディアの。）

は（インテルCore2のデュオCPUを使用して、Windows 7のProfessionalの上で実行されている、gccでコンパイルされ、以下の例を見てみましょう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つのキャッシュライン（intごとに64バイト/ 4バイト= 16の整数）、その大きなブロック、または1つのアレイ全体が急増しましたか？

また、実際にルーチンを実行するのに必要な時間よりも、RAMからキャッシュに（またはローカル以外のものからテキストに）データを読み込む際のレイテンシは、はるかに重要です。本当ですか？

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

Answer 1

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

並列で実行すると、通常、あなたのパフォーマンスを傷つけることはできませんが。これを理解するには、多くのテストと調整が必要です。例えば

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

しかし、あなたはデュアルソケットシステムを持っている場合は、各CPUは独自のRAMを持つことになりますし、アルゴリズムがスピードアップします。

あるいは、システムはRAMの1つの銀行から4へのアップグレードおよびクワッドチャネルRAM構成に単一チャネルから切り替える可能性があります。その時点では、RAMの速度が計算速度を超え、クアッドコアはより多くのスレッドを実行する利点があります。私の意見で

、コアあたりのスレッドを実行すると、通常はあなたの利益になると、システムのアップグレードを利用します。単一のスレッドを実行すると、同期オーバーヘッドの量が少なくなる可能性がありますが、将来は常にプログラムが制限されます。