OpenMP Parallel for-loop показывает небольшое увеличение производительности

Question

Я изучаю, как использовать OpenMP в C, и в качестве упражнения HelloWorld я пишу программу для подсчета простых чисел. Я тогда parallelise это следующим образом:

int numprimes = 0; 
#pragma omp parallel for reduction (+:numprimes) 
for (i = 1; i <= n; i++) 
{ 
    if (is_prime(i) == true) 
     numprimes ++; 
} 

Я скомпилировать этот код, используя gcc -g -Wall -fopenmp -o primes primes.c -lm (-lm для math.h функций я использую). Затем я запускаю этот код на Intel® Core™2 Duo CPU E8400 @ 3.00GHz × 2, и, как и ожидалось, производительность лучше, чем для последовательной программы.

Проблема, однако, возникает, когда я пытаюсь запустить ее на гораздо более мощной машине. (Я также попытался вручную установить количество потоков для использования с num_threads, но это ничего не меняет.) Подсчет всех простых чисел до 10 000 000 дает мне следующее время (с помощью time):

8-жильных машины :

real 0m8.230s 
user 0m50.425s 
sys  0m0.004s 

двухъядерный машина:

real 0m10.846s 
user 0m17.233s 
sys  0m0.004s 

И эта картина продолжается подсчет более простых чисел, машина с большим количеством ядер показывает небольшое увеличение производительности, но не так много, как хотелось бы ожидать Хавин g доступно еще столько ядер. (Я бы ожидать, в 4 раза больше ядер подразумевает почти в 4 раза меньше времени пробега?)

Counting воспламеняет до 50 000 000:

8-ядро машины:

real 1m29.056s 
user 8m11.695s 
sys  0m0.017s 

двухъядерный машина:

real 1m51.119s 
user 2m50.519s 
sys  0m0.060s 

Если кто-нибудь может прояснить это для меня, было бы очень признательно.

EDIT

Это моя функция прайм-проверка.

static int is_prime(int n) 
{ 
    /* handle special cases */ 
    if  (n == 0) return 0; 
    else if (n == 1) return 0; 
    else if (n == 2) return 1; 

    int i; 
    for(i=2;i<=(int)(sqrt((double) n));i++) 
    if (n%i==0) return 0; 

    return 1; 
} 

Answer 1

Эта работа происходит потому, что:

1. is_prime(i) занимает больше времени, чем выше i получает, и
2. Ваша реализация OpenMP использует статическое планирование по умолчанию для parallel for конструкций без оговорки schedule, т.е. отбивных цикл for в равные по размеру смежные куски.

Другими словами, поток с наивысшим номером выполняет все самые сложные операции.

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

Эта версия будет разделить работу лучше:

int numprimes = 0; 
#pragma omp parallel for schedule(dynamic, 1) reduction(+:numprimes) 
for (i = 1; i <= n; i++) 
{ 
    if (is_prime(i) == true) 
     numprimes ++; 
} 

Информация о синтаксисе планирования доступна через MSDN и Wikipedia.

schedule(dynamic, 1) может быть не оптимальным, так как High Performance Mark Примечания в его ответе. В этом OpenMP wihtepaper содержится более подробное обсуждение гранулярности планирования.

Спасибо также Jens Gustedt и Mahmoud Fayez за содействие в ответе.

Answer 2

Я думаю, что ваш код нужно использовать динамический так резьбе каждый может потреблять разное количество итераций, как ваши итерации имеют различную рабочую нагрузку, так что текущий код сбалансирован, который не поможет в вашем случае попробовать это пожалуйста:

int numprimes = 0; 
#pragma omp parallel for reduction (+:numprimes) schedule(dynamic,1) 
for (i = 1; i <= n; i++){ 
    if (is_prime(i) == true) 
    ++numprimes; 
} 

Answer 3

Причина, по-видимому, плохое масштабирование вашей программы, поскольку, по словам @naroom, изменчивость времени выполнения каждого вызова вашей функции is_prime. Время выполнения не просто увеличивается со значением i. Ваш код показывает, что тест завершается, как только будет найден первый коэффициент i, поэтому самое длинное время выполнения будет для чисел с несколькими (и большими) факторами, включая сами простые числа.

Как вы уже сказали, расписание по умолчанию для вашей параллелизации приведет к выделению итераций основной петли на кусок за один раз доступными потоками. Для вашего случая 5*10^7 целых чисел для тестирования и использования 8 ядер, первый поток получит целые числа 1..6250000 для тестирования, второй получит 6250001..12500000 и так далее. Это приведет к сильно несбалансированной нагрузке на потоки, потому что, конечно, простые числа распределены неравномерно.

Вместо того, чтобы использовать планирование по умолчанию, вы должны поэкспериментировать с динамическим планированием. Следующий оператор указывает время выполнения, чтобы разбазаривать итерации вашего главного контура m итераций в то время, к потокам в вашем вычислении:

#pragma omp parallel for schedule(dynamic,m) 

После того, как поток закончил свою m итераций будет дано больше m работать на. Трюк для вас - найти sweet spot для m. Слишком мало, и в ваших вычислениях будет доминировать работа, выполняемая во время выполнения итераций, слишком большая, и ваши вычисления вернутся к несбалансированным нагрузкам, которые вы уже видели.

Примите во внимание, что вы изучите некоторые полезные уроки о затратах и ​​преимуществах параллельных вычислений, проработав все это.