1

アプリケーションのホットスポットである以下のスニペットがあります。ベクトル依存のため、forループはベクトル化されません。このループを書き直して高速に実行する方法はありますか。

#define  NUM_KEYS  (1L << 20)
#define  NUM_BUCKETS (1L << 10)    
int i,k;
int shift = (1L << 11);
int key_array[NUM_KEYS],key_buff[NUM_KEYS];
int bucket_ptrs[NUM_BUCKETS];

for( i=0; i<NUM_KEYS; i++ )  
{
    k = key_array[i];
    key_buff[bucket_ptrs[k >> shift]++] = k;
}

私が試した 1 つのアプローチは、 のシフトされた値を保持する一時配列を作成することでしたkey_array。

for( i=0; i<NUM_KEYS; i++ )  
{
        key_arrays[i] = key_array[i] >> shift;
}
for( i=0; i<NUM_KEYS; i++ )  
{
    k = key_array[i];
    j = key_arrays[i];
    key_buff[bucket_ptrs[j]++] = k;
}

ここでは、最初のループがベクトル化されます。しかし、全体としてパフォーマンスの向上は見られません。

4

2 に答える 2

3

ループがベクトル化できないのはなぜですか?

これは、ここで非シーケンシャル メモリ アクセスがあるためです。

key_buff[bucket_ptrs[k >> shift]++] = k;

bucket_ptrsにアクセスするためのインデックスを決定しますkey_buff。これらのインデックスはいたるところにあるため、メモリ アクセスは非シーケンシャルです。

現在、x86 プロセッサは、メモリの連続したチャンクへの SIMD ロード/ストアのみをサポートしています。（理想的には整列も）

ベクトル化する場合は、AVX2 のギャザー/スキャッター命令が必要です。それらは存在しませんが、次世代の Intel プロセッサで登場するはずです。

ここでは、最初のループがベクトル化されます。しかし、全体としてパフォーマンスの向上は見られません。

これは、追加のループ オーバーヘッドを追加しているためです。これで、 を 2 回通過しkey_arrayます。どちらかといえば、遅くないことに驚いています。

このループを書き直して高速に実行する方法はありますか。

私はそれを疑います - 少なくともアルゴリズムを変更することなく。少なくとも、key_buffL1 キャッシュに快適に収まる必要があります。

AVX2 ではベクトル化できますが、問題key_buffは 4MB です。これは、下位レベルのキャッシュには収まりません。したがって、AVX2 でさえあまり役に立たないかもしれません。メモリアクセスによって完全に拘束されます。

于 2012-12-06T20:29:36.793 に答える
2

おそらくあなたを悩ませているのは、key_array へのアクセスはシーケンシャルで、bucket_ptrs は L1 に収まるほど小さいのに、key_buff へのアクセスはいたるところにあるということです。

ただし、あなたがしていることは、基数ソートのステップのように見えます。それが実際に行っていることである場合は、最初にバケットの数を 32 または 64 程度に減らし、最上位の 5 または 6 ビットでソートすることにより、パフォーマンスを向上させることができます。次に、ほとんどがキャッシュに収まる小さな配列がたくさんあり、基数ソートの別のパスを使用してそれぞれをソートできます。

于 2012-12-06T20:24:33.200 に答える