Параллельный режим OpenMP существенно медленнее последовательного
Я запускаю моделирование случайных событий, происходящих в соответствии с заданным набором вероятностей, до тех пор, пока не произойдет n событий, и повторяю столько итераций, сколько необходимо. Когда я запускаю это последовательно, он завершает небольшой набор тестов из 24 итераций за 5 секунд. Когда я устанавливаю большее количество потоков (16), затраченное время становится 55 секундами. Я сделал эти сравнения, используя time bash -c "...".
Извините, что задаю еще один такой вопрос, но я ищу решение уже несколько часов. Я думаю, что проблема должна быть в каком-то состоянии гонки, но я просто не могу понять, в чем именно. Переменные target, n_probabilities и вероятности должны быть частными для потока, и большая часть времени тратится между операторами печати «Начался поток %d» и «Завершенный поток %d». Это наводит на мысль, что mutation_iterations[i] = simulate_iteration(target, n_probabilities, probabilities); тогда должна быть строкой, вызывающей нарушение, аmutation_iterations — это общая переменная, но доступ к ней должен осуществляться только один раз для каждого потока, поэтому я не понимаю, как это может вызвать такое сильное падение скорости.
Однако, глядя на выходные данные gprof, я не вижу необычного количества времени, потраченного на рассматриваемую функцию (хотя 6.15 для main кажется мне странным, поскольку это не фактическое время выполнения):
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
98.86 6.08 6.08 24 253.33 253.33 simulate_iteration
0.98 6.14 0.06 _init
0.16 6.15 0.01 main
Признаюсь, я впервые читаю gprof, поэтому, возможно, я читаю совершенно неправильно. Но, насколько я понимаю, моя программа работает на 49 секунд дольше, чем говорит gprof, и я не могу понять, откуда это взялось.
Нарушающий код:
int **mutation_iterations = malloc(iterations * sizeof(int *));
srand(0); // Set random number seed
#pragma omp parallel shared(mutation_iterations)
{
int target = desired_mutations;
int n_probabilities = simulation_size;
double probabilities[simulation_size];
for (int i = 0; i < simulation_size; i++) {
probabilities[i] = simulation_set[i].probability;
}
#pragma omp for
for (int i = 0; i < iterations; i++) {
mutation_iterations[i] = NULL;
printf("Started thread %d\n", i);
mutation_iterations[i] = simulate_iteration(target, n_probabilities, probabilities);
printf("Finished thread %d\n", i);
}
}
Функция моделирования_итерации(...):
int * simulate_iteration(int target, int n_probabilities, double probabilities[]) {
int *counts = calloc(n_probabilities, sizeof(int));
int total = 0;
while (total < target) {
for (int i = 0; i < n_probabilities; i++) {
double rand_val = (double) rand() / RAND_MAX;
if (rand_val < probabilities[i]) {
counts[i]++;
total++;
}
}
}
return counts;
}
Должно быть, я что-то упускаю из виду, но не могу понять, что именно. Любая помощь будет очень признательна.
Вы звоните rand из нескольких тредов. Обычно эта функция не является потокобезопасной.. Обратите внимание, что отсутствие потокобезопасности приводит к подпрыгиванию строк кэша, что снижает производительность. Неработающий код также часто является медленным кодом.
@RetiredNinja Извините, я забыл об этом. Я соберу одно для ответа.
@Homer512 Homer512 Именно так, семя ранда было условием гонки, большое спасибо.
Возможно, вам понадобится потокобезопасная версия: rand_r. В glibc он использует LCG и работает немного быстрее, чем rand вызывает random. Кроме того, erand48 может быть лучше для чисел с плавающей запятой. См.: pubs.opengroup.org/onlinepubs/007908799/xsh/drand48.html
Ответы 1
Оказывается, я не заметил разногласий в rand(), спасибо @Homer512 за указание на это. В итоге я использовал rand_r, и это исправило ситуацию.
Для тех, кто пытается сделать что-то подобное, вот минимальный воспроизводимый образец модели нулевой мутации, которую я создавал с включенным исправлением:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <csv.h>
#include <omp.h>
#include <pthread.h>
int * simulate_iteration(unsigned int c_iteration, int target, int n_probabilities, double probabilities[]) {;
int *counts = calloc(n_probabilities, sizeof(int));
int total = 0;
while (total < target) {
for (int i = 0; i < n_probabilities; i++) {
double rand_val = (double) rand_r(&c_iteration) / RAND_MAX;
if (rand_val < probabilities[i]) {
counts[i]++;
total++;
}
}
}
return counts;
}
int main(int argc, char *argv[]) {
int iterations = 24;
int **mutation_iterations = malloc(iterations * sizeof(int *));
#pragma omp parallel shared(mutation_iterations)
{
unsigned int gen_seed = 0;
int target = 500;
int n_probabilities = 500;
double probabilities[500];
for (int i = 0; i < n_probabilities; i++) {
probabilities[i] = (double) rand_r(&gen_seed) / RAND_MAX / 10;
}
#pragma omp for
for (int i = 0; i < iterations; i++) {
mutation_iterations[i] = NULL;
mutation_iterations[i] = simulate_iteration(i, target, n_probabilities, probabilities);
}
}
// Print the results
printf("gene");
for (int i = 0; i < 500; i++) {
printf("\titer_%d", i);
}
printf("\n");
for (int j = 0; j < 500; j++) {
printf("%d", j);
for (int i = 0; i < iterations; i++) {
printf("\t%d", mutation_iterations[i][j]);
}
printf("\n");
}
for (int i = 0; i < iterations; i++) free(mutation_iterations[i]);
free(mutation_iterations);
return 0;
}
Вы все еще звоните rand() внутри раздела parallel. Он по-прежнему не работает, просто менее заметен, поскольку общее количество вызовов меньше. Чтобы это исправить, вам понадобится генератор случайных чисел, состояние которого либо локально для потока, либо управляется с помощью явных переменных, например те, что в GSL или семейство функций rand48_r
Извините, я исправил проблему в своем коде, а затем допустил ту же ошибку в примере. Теперь это исправлено, и вывод воспроизводится так, как и должно быть. Спасибо, что указали на это.
Подумайте о том, чтобы собрать минимально воспроизводимый пример .