9

分裂のないコードは次のようになります。

int check(int * res, char * map, int n, int * keys){
    int ret = 0;
    for(int i = 0; i < n; ++i){
        res[ret] = i;
        ret += map[hash(keys[i])]
    }
    return ret;
}

核分裂あり：

int check(int * res, char * map, int n, int * keys){
    int ret = 0;
    for(int i = 0; i < n; ++i){
        tmp[i] = map[hash(keys[i])];
    }
    for(int i = 0; i < n; ++i){
        res[ret] = i;
        ret += tmp[i];
    }
    return ret;
}

ノート：

  • ボトルネックはmap[hash(keys[i])]、ランダムにメモリにアクセスすることです。

  • 通常、if(tmp[i]) res[ret++] = i;私が使用しているifを避けることですret += tmp[i]。

  • map[..]常に 0 または 1 です

通常、核分裂バージョンは大幅に高速であり、その理由を説明しようとしています。私の最善の推測では、ret += map[..]まだいくつかの依存関係が導入されており、投機的実行が妨げられています。

誰かがより良い説明を持っているかどうか聞きたいです。

4

2 に答える 2

8

私のテストでは、融合ループと分割ループの間で約 2 倍の速度差が得られました。この速度の違いは、ループをどのように微調整しても一貫しています。

Fused: 1.096258 seconds
Split: 0.562272 seconds

(完全なテスト コードについては、下部を参照してください。)

100% 確信はありませんが、これは次の 2 つの組み合わせが原因であると思われます。

  1. からのキャッシュ ミスによる、メモリの曖昧性解消のためのロード/ストア バッファの飽和map[gethash(keys[i])]。
  2. 融合ループ バージョンで追加された依存関係。

map[gethash(keys[i])]ほぼ毎回キャッシュミスが発生することは明らかです。実際には、ロードストア バッファ全体を飽和させるにはおそらく十分です。

次に、追加された依存関係を見てみましょう。問題はret変数です：

int check_fused(int * res, char * map, int n, int * keys){
    int ret = 0;
    for(int i = 0; i < n; ++i){
        res[ret] = i;
        ret += map[gethash(keys[i])];
    }
    return ret;
}

このret変数はストアのアドレス解決に必要ですres[ret] = i;。

  • 融合ループでretは、確実なキャッシュ ミスが原因です。
  • 分割ループでretは、来てtmp[i]います - これははるかに高速です。

融合ループの場合のアドレス解決のこの遅延によりres[ret] = i、ストアがロードストア バッファを詰まらせる可能性がありmap[gethash(keys[i])]ます。

ロードストア バッファのサイズは固定されていますが、その中にジャンクが 2 倍ある
ため、キャッシュ ミスを以前の半分だけ重複させることができます。したがって、2倍の速度低下。

融合ループを次のように変更したとします。

int check_fused(int * res, char * map, int n, int * keys){
    int ret = 0;
    for(int i = 0; i < n; ++i){
        res[i] = i;    //  Change "res" to "i"
        ret += map[gethash(keys[i])];
    }
    return ret;
}

これにより、アドレス解決の依存関係が壊れます。

(もはや同じではないことに注意してください。ただし、パフォーマンスの違いを示すだけです。)

次に、同様のタイミングが得られます。

Fused: 0.487477 seconds
Split: 0.574585 seconds

完全なテストコードは次のとおりです。

#define SIZE 67108864

unsigned gethash(int key){
    return key & (SIZE - 1);
}

int check_fused(int * res, char * map, int n, int * keys){
    int ret = 0;
    for(int i = 0; i < n; ++i){
        res[ret] = i;
        ret += map[gethash(keys[i])];
    }
    return ret;
}
int check_split(int * res, char * map, int n, int * keys, int *tmp){
    int ret = 0;
    for(int i = 0; i < n; ++i){
        tmp[i] = map[gethash(keys[i])];
    }
    for(int i = 0; i < n; ++i){
        res[ret] = i;
        ret += tmp[i];
    }
    return ret;
}


int main()
{
    char *map = (char*)calloc(SIZE,sizeof(char));
    int *keys =  (int*)calloc(SIZE,sizeof(int));
    int *res  =  (int*)calloc(SIZE,sizeof(int));
    int *tmp  =  (int*)calloc(SIZE,sizeof(int));
    if (map == NULL || keys == NULL || res == NULL || tmp == NULL){
        printf("Memory allocation failed.\n");
        system("pause");
        return 1;
    }

    //  Generate Random Data
    for (int i = 0; i < SIZE; i++){
        keys[i] = (rand() & 0xff) | ((rand() & 0xff) << 16);
    }

    printf("Start...\n");

    double start = omp_get_wtime();
    int ret;

    ret = check_fused(res,map,SIZE,keys);
//    ret = check_split(res,map,SIZE,keys,tmp);

    double end = omp_get_wtime();

    printf("ret = %d",ret);
    printf("\n\nseconds = %f\n",end - start);

    system("pause");
}
于 2012-06-20T17:47:17.957 に答える
1

配列のインデックス付けではないと思いますが、関数の呼び出しがhash()パイプラインの停止を引き起こし、最適な命令の並べ替えを妨げる可能性があります。

于 2012-06-20T16:13:36.750 に答える