Параллельный рекурсивный алгоритм - PullRequest
Новая
       11

Параллельный рекурсивный алгоритм

1 голос
/ 03 мая 2019

Я пытаюсь разработать рекурсивный алгоритм, который я хотел бы запустить параллельно, используя open mp. Мне нужно запустить алгоритм для множественного ввода, поэтому я хочу, чтобы каждый поток запускал 1 вход. Каждый поток независим, но результаты сохраняются в той же глобальной переменной (суммируя их), как показано в коде: 

#include <stdio.h>
#include <omp>

double * resultA;
double * resultB;

void recursiveAlgorithm(double a)
{
    double b = someFunction(a);
    uint c = anotherFunction(a);

    if (b < 0)
    {
         #pragma omp critical
         {
              resultA[c] = resultA[c] + b;
         }
         return;
    }
    if (b > 100)
    {
         #pragma omp critical
         { 
              resultB[c] = resultB[c] + b;     
         } 
         return;
    } 
    recursiveAlgorithm(b);
}


int main( int argc, const char* argv[] )
{
    double input[5] = {0, 1, 2, 3, 4};

    resultA = malloc(1000*1000*3, sizeof(double));
    resultB = malloc(1000*1000*3, sizeof(double));

    #pragma omp parallel for
    for (uint i; i < 5; i++){
         recursiveAlgorithm(input[i]);
    }
}

Я использовал критическую секцию, чтобы гарантировать, что переменные resultA и resultB не доступны одновременно, но я не уверен, что это лучше всего подходит для моего случая. Улучшение скорости намного меньше, чем я ожидал. Есть ли лучший подход для такого кода?

1 Ответ

1 голос
/ 03 мая 2019

Похоже, ваша проблема может быть лучше решена с помощью схемы сокращения. Но очень сложно сказать без дополнительной информации о том, что вы на самом деле вычисляете.

См. этот вопрос о том, как это сделать для двух переменных, и этот вопрос для случая массива.

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

...