parallel-processing - openmp を使用した並列ハッシュ

Question

並列ハッシュ用のコードがあります。挿入コードは次のとおりです。

int main(int argc, char** argv){
     .....
    Entry* table;//hash table
    for(size_t i=0;i<N;i++){
       keys[i]=i;
       values[i] = rand();//random key-value pairs
    }
    int omp_p = omp_get_max_threads();
    #pragma omp parallel for
    for(int p=0;p<omp_p;p++){
       size_t start = p*N/omp_p;
       size_t end = (p+1)*N/omp_p;//each thread gets contiguous chunks of the arrays
       for(size_t i=start;i<end;i++){
          size_t key = keys[i];
          size_t value = values[i];
          if(insert(table,key,value) == 0){
             printf("Failure!\n");
          }
       }
    }
    ....
    return 0;
}

int insert(Entry* table,size_t key, size_t value){
   Entry entry = (((Entry)key) << 32)+value; //Coalesce key and value into an entry
   /*Use cuckoo hashing*/
   size_t location = hash_function_1(key);

   for(size_t its=0;its<MAX_ITERATIONS;its++){
       entry = __sync_lock_test_and_set(&table[location],entry);
       key=get_key(entry);
       if(key == KEY_EMPTY)
          return1;
       }
       /*We have replaced a valid key, try to hash it using next available hash function*/
       size_t location_1 = hash_function_1(key);
       size_t location_2 = hash_function_2(key);
       size_t location_3 = hash_function_3(key);
       if(location == location_1) location = location_2;
       else if(location == location_2) location = location_3;
       else                            location = location_1;
   }
   return 0;
}

挿入コードはまったくスケーリングしません。たとえば 10M キーのシングル スレッドを使用すると、約 170 ミリ秒で完了しますが、16 スレッドを使用すると 500 ミリ秒以上かかります。私の疑いでは、これは、書き込み操作 (__sync_lock_test_and_set(...)) 中にキャッシュ ライン (table[] 配列で構成される) がスレッド間で移動され、無効化によって速度が低下するためであると考えられます。挿入コードを次のように変更します。

int insert(Entry* table,size_t key, size_t value){
   Entry entry = (((Entry)key) << 32)+value; //Coalesce key and value into an entry

   size_t location = hash_function_1(key);
   table[location] = entry;
   return 1;
}

私はまだ同じ悪いパフォーマンスを得ます。これはハッシュであるため、特定の要素がどこにハッシュされるかを制御することはできません。提案はありますか？また、これが正しい理由ではない場合、何が問題になっている可能性があるかについての他の指針はありますか? 1M から 100M キーまで試しましたが、シングル スレッドのパフォーマンスは常に優れています。