疑問点

仮に a1 , b1 , c1 および d1 はヒープメモリを指しており、私の数値コードでは以下のようなコアループになっています。

const int n = 100000;

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
    c1[j] += d1[j];
}

このループは、別の外側を経由して10,000回実行されます。 for ループを使用します。それを高速化するために、コードを変更した。

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
}

for (int j = 0; j < n; j++) {
    c1[j] += d1[j];
}

でコンパイル Microsoft Visual C++ 10.0 完全な最適化と SSE2 を32ビットで有効化。 インテル・コア2 Duo (x64)の場合、最初の例では5.5秒、2重ループの例ではわずか1.9秒しかかかりません。

最初のループの逆アセンブルは基本的に次のようになります（このブロックはプログラム全体で5回ほど繰り返されます）。

movsd       xmm0,mmword ptr [edx+18h]
addsd       xmm0,mmword ptr [ecx+20h]
movsd       mmword ptr [ecx+20h],xmm0
movsd       xmm0,mmword ptr [esi+10h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [edx+20h]
addsd       xmm0,mmword ptr [ecx+28h]
movsd       mmword ptr [ecx+28h],xmm0
movsd       xmm0,mmword ptr [esi+18h]
addsd       xmm0,mmword ptr [eax+38h]

二重ループの例の各ループでは、このようなコードが生成されます（以下のブロックは3回ほど繰り返されます）。

addsd       xmm0,mmword ptr [eax+28h]
movsd       mmword ptr [eax+28h],xmm0
movsd       xmm0,mmword ptr [ecx+20h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [ecx+28h]
addsd       xmm0,mmword ptr [eax+38h]
movsd       mmword ptr [eax+38h],xmm0
movsd       xmm0,mmword ptr [ecx+30h]
addsd       xmm0,mmword ptr [eax+40h]
movsd       mmword ptr [eax+40h],xmm0

動作はアレイのサイズ(n)とCPUキャッシュに大きく依存するため、質問は意味がないことが判明しました。そこで、さらに興味があれば、質問を言い換えます。

• 次のグラフの5つの領域で示されるような、異なるキャッシュの動作につながる詳細について、確実な洞察をお願いします。

• また、CPU/キャッシュアーキテクチャの違いを指摘するために、これらのCPUについて同様のグラフを用意するのも面白いかもしれませんね。

以下はコードの全容です。これは TBB Tick_Count を定義しないことで、高解像度のタイミングを無効にすることができます。 TBB_TIMING マクロを使用します。

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>

//#define TBB_TIMING

#ifdef TBB_TIMING   
#include <tbb/tick_count.h>
using tbb::tick_count;
#else
#include <time.h>
#endif

using namespace std;

//#define preallocate_memory new_cont

enum { new_cont, new_sep };

double *a1, *b1, *c1, *d1;


void allo(int cont, int n)
{
    switch(cont) {
      case new_cont:
        a1 = new double[n*4];
        b1 = a1 + n;
        c1 = b1 + n;
        d1 = c1 + n;
        break;
      case new_sep:
        a1 = new double[n];
        b1 = new double[n];
        c1 = new double[n];
        d1 = new double[n];
        break;
    }

    for (int i = 0; i < n; i++) {
        a1[i] = 1.0;
        d1[i] = 1.0;
        c1[i] = 1.0;
        b1[i] = 1.0;
    }
}

void ff(int cont)
{
    switch(cont){
      case new_sep:
        delete[] b1;
        delete[] c1;
        delete[] d1;
      case new_cont:
        delete[] a1;
    }
}

double plain(int n, int m, int cont, int loops)
{
#ifndef preallocate_memory
    allo(cont,n);
#endif

#ifdef TBB_TIMING   
    tick_count t0 = tick_count::now();
#else
    clock_t start = clock();
#endif
        
    if (loops == 1) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                a1[j] += b1[j];
                c1[j] += d1[j];
            }
        }
    } else {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a1[j] += b1[j];
            }
            for (int j = 0; j < n; j++) {
                c1[j] += d1[j];
            }
        }
    }
    double ret;

#ifdef TBB_TIMING   
    tick_count t1 = tick_count::now();
    ret = 2.0*double(n)*double(m)/(t1-t0).seconds();
#else
    clock_t end = clock();
    ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC);
#endif
    
#ifndef preallocate_memory
    ff(cont);
#endif

    return ret;
}


void main()
{   
    freopen("C:\\test.csv", "w", stdout);

    char *s = " ";

    string na[2] ={"new_cont", "new_sep"};

    cout << "n";

    for (int j = 0; j < 2; j++)
        for (int i = 1; i <= 2; i++)
#ifdef preallocate_memory
            cout << s << i << "_loops_" << na[preallocate_memory];
#else
            cout << s << i << "_loops_" << na[j];
#endif
            
    cout << endl;

    long long nmax = 1000000;

#ifdef preallocate_memory
    allo(preallocate_memory, nmax);
#endif
    
    for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2)))
    {
        const long long m = 10000000/n;
        cout << n;

        for (int j = 0; j < 2; j++)
            for (int i = 1; i <= 2; i++)
                cout << s << plain(n, m, j, i);
        cout << endl;
    }
}

の値を変えたときのFLOP/sを示しています。 n .

解決方法は？

これをさらに分析すると、4ポインタのデータアライメントが（少なくとも部分的に）原因であると考えられます。これは、あるレベルのキャッシュバンク/ウェイの競合を引き起こします。

アレイの割り当て方法を正しく推測すると、それらは は、ページ行に整列している可能性が高いです。 .

つまり、各ループでのアクセスはすべて同じキャッシュウェイに落ちることになります。しかし、Intelプロセッサはしばらく前から8ウェイL1キャッシュの連想性を持っています。しかし現実には、性能は完全に均一ではありません。4ウェイでアクセスすると、2ウェイでアクセスするよりもまだ遅いのです。

編集部：確かに、すべてのアレイを別々に確保しているように見えますね。 通常、このような大きなアロケーションが要求された場合、アロケータはOSに新しいページを要求します。したがって、ページ境界から同じオフセットに大きな割り当てが現れる可能性が高くなります。

以下はテストコードです。

int main(){
    const int n = 100000;

#ifdef ALLOCATE_SEPERATE
    double *a1 = (double*)malloc(n * sizeof(double));
    double *b1 = (double*)malloc(n * sizeof(double));
    double *c1 = (double*)malloc(n * sizeof(double));
    double *d1 = (double*)malloc(n * sizeof(double));
#else
    double *a1 = (double*)malloc(n * sizeof(double) * 4);
    double *b1 = a1 + n;
    double *c1 = b1 + n;
    double *d1 = c1 + n;
#endif

    //  Zero the data to prevent any chance of denormals.
    memset(a1,0,n * sizeof(double));
    memset(b1,0,n * sizeof(double));
    memset(c1,0,n * sizeof(double));
    memset(d1,0,n * sizeof(double));

    //  Print the addresses
    cout << a1 << endl;
    cout << b1 << endl;
    cout << c1 << endl;
    cout << d1 << endl;

    clock_t start = clock();

    int c = 0;
    while (c++ < 10000){

#if ONE_LOOP
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
            c1[j] += d1[j];
        }
#else
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
        }
        for(int j=0;j<n;j++){
            c1[j] += d1[j];
        }
#endif

    }

    clock_t end = clock();
    cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << endl;

    system("pause");
    return 0;
}

ベンチマークの結果

EDIT: 実際 Core 2アーキテクチャのマシン。

2 x Intel Xeon X5482 Harpertown @ 3.2 GHz。

#define ALLOCATE_SEPERATE
#define ONE_LOOP
00600020
006D0020
007A0020
00870020
seconds = 6.206

#define ALLOCATE_SEPERATE
//#define ONE_LOOP
005E0020
006B0020
00780020
00850020
seconds = 2.116

//#define ALLOCATE_SEPERATE
#define ONE_LOOP
00570020
00633520
006F6A20
007B9F20
seconds = 1.894

//#define ALLOCATE_SEPERATE
//#define ONE_LOOP
008C0020
00983520
00A46A20
00B09F20
seconds = 1.993

観察事項

• 6.206秒 を1ループとし 2.116 秒 を2回ループさせたものです。これは、OPの結果を正確に再現しています。

• 最初の2つのテストでは、アレイが別々に割り当てられています。 ページに対する相対的な配置がすべて同じであることにお気づきでしょう。

• 2番目の2つのテストでは、その整列を崩すために配列が詰め込まれています。 ここで、両方のループが高速化されていることに気がつくだろう。さらに、通常予想されるように、2番目の（2重）ループは遅い方になっています。

コメントで @Stephen Cannon が指摘しているように、このアライメントが原因である可能性は非常に高いです。 フォールスエイリアシング ロード/ストアユニットやキャッシュの中で この件についてググってみたところ、Intelは実際にハードウェアカウンタとして 部分的なアドレスエイリアス が出店しています。

http://software.intel.com/sites/products/documentation/doclib/stdxe/2013/~amplifierxe/pmw_dp/events/partial_address_alias.html

5つの地域-解説

リージョン1

これは簡単です。データセットが小さいので、ループや分岐などのオーバーヘッドが性能を支配しています。

領域2

<ストライク ここでは、データサイズが大きくなるにつれて、相対的なオーバーヘッドが減少し、性能が飽和しています。ここでは、ループと分岐のオーバーヘッドが2倍あるため、2ループの方が遅くなります。

正確にはよくわからないのですが...。アグナー・フォグが言っているように、アライメントが影響している可能性もあります。 キャッシュバンクのコンフリクト . (このリンクは Sandy Bridge についてですが、このアイデアは Core 2 にも適用できるはずです)。

地域3

この時点で、データはもはやL1キャッシュに収まらなくなります。そのため、性能はL1 <-> L2キャッシュのバンド幅によって制限されます。

領域4

シングルループでの性能低下が観察されることです。そして、前述の通り、これはアライメントが原因で（最も可能性が高い）。 フォールスエイリアシング プロセッサのロードストアユニットでストールする。

しかし、false aliasingが発生するためには、データセット間に十分なストライドが必要です。このため、リージョン3ではこの現象は見られません。

リージョン5

この時点では、キャッシュに収まるものはありません。つまり、メモリ帯域幅に縛られているわけです。