C++ OpenMP параллель медленнее, чем последовательный

Question

Я реализовал параллельный код в C++ для поиска минимального связующего дерева с использованием алгоритма Prim с использованием OPENMP. Иногда это немного быстрее (7,95 мс), но иногда я получаю ускорение в 12,7 мс, что намного медленнее, чем серийная версия (для которой я получаю 9,69 мс). Здесь есть параллельная версия моего кода:

https://dpaste.de/dUt6

Не могли бы вы помочь в этом?

Кроме того, существует ли действительный метод проверки производительности моего кода? time.h кажется неточным.

Большое спасибо!

Answer 1

У OpenMP есть накладные расходы, которые добавляют постоянный термин к расчету времени. Позвольте мне привести пример.

Предположим, что ваш алгоритм завершен в A*n, где A - некоторая константа, а n - количество элементов, которые вы будете перебирать. Предположим также, что ваш алгоритм идеально распараллеливается, так что если у вас есть k потоков, то распараллеливаемый алгоритм заканчивается в O(n)/k времени. Из-за накладных расходов OpenMP время запуска будет A*n/k + B, где B - накладные расходы. Поэтому для того, чтобы вы могли видеть любую выгоду от OpenMP A*n/k + B < A*n. Для некоторого диапазона значений n [0, threshhold] OpenMP будет фактически медленнее, чем серийный алгоритм из-за накладных расходов B.

Еще один важный момент заключается в том, что OpenMP имеет разные служебные/пороговые значения в зависимости от того, был ли он уже использован в коде. Я называю это холодными и теплыми порогами.

dtime_cold = omp_get_wtime(); 
foo(); //cold - OpenMP has not been called before 
dtime_cold = omp_get_wtime() - dtime_cold; 

dtime_warm = omp_get_wtime(); 
foo(); //warm - OpenMP has already been called once 
dtime_warm = omp_get_wtime() - dtime_warm; 

Если n достаточно велико, то постоянные термины insignficant в этом случае пороги не имеют значения.