Parallel хеширования с использованием 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 мс. Мое подозрение в том, что это связано с тем, что строка кэша (состоящая из массива table []) перемещается между потоками во время операции записи (__sync_lock_test_and_set (...)), а результат недействительности замедляется Например, если Я изменяю код вставки только:

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 ключей, но однопоточная производительность всегда лучше.

Answer 1

У меня есть несколько предложений. Поскольку время работы вашей функции insert не является постоянным, вы должны использовать schedule(dynamic). Во-вторых, вы должны позволить OpenMP делить задачи и не делать это самостоятельно (одна причина, но не главная причина, заключается в том, что теперь у вас есть это N должно быть кратно omp_p). Если вы хотите иметь некоторый контроль над тем, как он делит задачи, попробуйте изменить chunksize следующим образом: schedule(dynamic,n) где n - размер патрона.

#pragma omp parallel for schedule(dynamic) 
for(size_t i=0;i<N;i++){ 
    size_t key = keys[i]; 
    size_t value = values[i]; 
    if(insert(table,key,value) == 0){ 
     printf("Failure!\n"); 
    } 
} 

Answer 2

Я хотел бы попробовать поэкспериментировать со стратегией, основанной на замках, как этот простой фрагмент кода показывает:

#include<omp.h> 

#define NHASHES 4 
#define NTABLE 1000000 
typedef size_t (hash_f)(size_t); 

int main(int argc, char** argv) { 
    Entry  table [NTABLE ]; 
    hash_f  hashes[NHASHES]; 
    omp_lock_t locks [NTABLE ] 
    /* ... */ 
    for(size_t ii = 0; ii < N; ii++) { 
    keys [ii] = ii; 
    values [ii] = rand(); 
    } 
    for(size_t ii = 0; ii < NTABLE; ii++) { 
    omp_init_lock(&locks[ii]); 
    } 
#pragma omp parallel 
    { 
#pragma omp for schedule(static) 
    for(int ii = 0; ii < N; ii++) { 

    size_t key = keys [ii]; 
    size_t value = values[ii]; 
    Entry entry = (((Entry)key) << 32) + value; 

    for (jj = 0; jj < NHASHES; jj++) { 
     size_t location = hashes[jj]; // I assume this is the computationally demanding part 
     omp_set_lock(&locks[location]); // Locks the hash table location before working on it 
     if (get_key(table[location]) == KEY_EMPTY) { 
     table[location] = entry; 
     break; 
     } 
     omp_unset_lock(&locks[location]); // Unlocks the hash table location 
    } 
    // Handle failures here 
    } 
    } /* pragma omp parallel */ 
    for(size_t ii = 0; ii < NTABLE; ii++) { 
    omp_destroy_lock(&locks[ii]); 
    } 
    /* ... */ 
    return 0; 
} 

С немного больше машин вы можете обрабатывать переменное число замков, начиная от 1 (эквивалент a critical) до NTABLE (что эквивалентно конструкции atomic) и посмотреть, обеспечивает ли различие между детализацией.