У меня есть следующий код в моей программе, и я хочу ускорить его с помощью OpenMP.
... for(i=curr_index; i < curr_index + rx_size; i+=2){ int64_t tgt = rcvq[i]; int64_t src = rcvq[i+1]; if (!TEST(tgt)) { pred[tgt] = src; newq[newq_count++] = tgt; } } В настоящее время у меня есть версия:
... chunk = rx_sz / omp_nthreads; #pragma omp parallel for num_threads(omp_nthreads) for (ii = 0; ii < omp_nthreads; ii++) { int start = curr_index + ii * chunk; for (index = start; index < start + chunk; index +=2) { int64_t tgt = rcvq[index]; int64_t src = rcvq[index+1]; if (!TEST(tgt)) { pred[tgt] = src; #pragma omp critical newq[newq_count++] = tgt; } } }
Когда я запускаю версию OpenMP, я вижу большую деgradleацию производительности по сравнению с исходной версией. Я думаю, что проблема может быть вызвана «omp critical», которая предотвращает параллельную обработку. Я хочу знать, что может быть улучшено с помощью моего кода, поэтому я могу получить более высокую производительность по сравнению с серийной версией. В коде rx_sz всегда кратно omp_nthreads.
Я уверен, что критический раздел omp ограничивает вашу производительность на этом этапе.
Я бы рекомендовал вам собрать результаты в отдельные буферы / векторы и объединить их после выполнения параллельной обработки (конечно, если заказ не имеет значения для вас)
vector> res; res.resize(num_threads); #pragma omp parallel for for (index = 0; index < rx_sz/2; ++index) { int64_t tgt = rcvq[2*index]; int64_t src = rcvq[2*index+1]; if (!TEST(tgt)) { pred[tgt] = src; res[omp_get_thread_num()].push_back(tgt); } } // Merge all res vectors if needed
Да, критический раздел ограничивает вашу производительность. Вы должны собирать результаты локально для каждого streamа, а затем объединять их.
size_t newq_offset = 0; #pragma omp parallel { // Figure out something clever here... const size_t max_newq_per_thread = max_newq / omp_get_num_threads(); int64_t* local_newq = malloc(max_results_per_thread * sizeof(int64_t)); size_t local_newq_count = 0; #pragma omp parallel for for (i=curr_index; i < curr_index + rx_size; i+=2) int64_t tgt = rcvq[2*index]; int64_t src = rcvq[2*index+1]; if (!TEST(tgt)) { pred[tgt] = src; local_newq_count++; assert(local_newq_count < max_newq_per_thread); local_newq[local_newq_count] = tgt; } } int local_offset; #pragma omp atomic capture { local_offset = offset; offset += local_newq_count; } for (size_t i = 0; i < counter; i++) { res_global[i + local_offset] = res[i]; } }
При таком подходе все streamи работают параллельно при слиянии, и на atomic capture существует только минимальное противоречие. Обратите внимание, что вы также можете сделать простую версию с atomic capture , которая более эффективна, чем критический раздел, но все равно станет узким местом:
size_t newq_count_local; #pragma omp atomic capture newq_count_local = newq_count++; newq[newq_count_local] = tgt;
newq в любой из версий critical -версия, которую вы опубликовали, неверна , потому что index (определенный во внешней области) неявно разделяется между streamами. rcvq нет дубликатов . В противном случае вы получите условие гонки на pred[tgt] = src; , pragma omp for loop. Другой ответ дает правильную идею. Тем не менее, это C ++, а не как tagged, C. Существует также незначительная, но значительная проблема с производительностью при использовании std::vector . Обычно вектор реализуется с тремя указателями, в общей сложности 24 байта. При push_back один из указателей увеличивается. Это означает, что: а) указатели локальных векторов из нескольких streamов находятся в одной и той же строке кэша, а б) при каждом успешном TEST push_back считывает и записывает в строку кэша, которая используется другими streamами (нитями). Эта линия кэша будет постоянно перемещаться между ядрами, что значительно ограничивает масштабируемость этого подхода. Это называется ложным совместным использованием.
Я выполнил небольшой тест, основанный на другом ответе, дающем следующую производительность:
0.99 s - одиночная нить 1.58 s - два streamа на двух соседних ядрах одного гнезда 2.13 s - две резьбы на двух сердечниках разных гнезд 0.99 s - два streamа, разделяющих одно kernel 0.62 s - 24 резьбы на двух гнездах В то время как более высокая версия версии C намного лучше:
0.46 s - одиночная нить (на самом деле не сравнимая C vs C ++) 0.24 s - две резьбы 0.04 s - 24 streamа