Почему реализация openMP в g cc не может распараллелить рекурсивную функцию внутри другой рекурсивной функции - PullRequest
Новая
       27

Почему реализация openMP в g cc не может распараллелить рекурсивную функцию внутри другой рекурсивной функции

0 голосов
/ 05 мая 2020

Я пытаюсь распараллелить эти рекурсивные функции с задачами openMP,

при компиляции с g cc он выполняется только в 1 потоке. Когда я компилирую его с помощью clang, он запускается в нескольких потоках.

Вторая функция вызывает первую, которая не генерирует новые задачи, чтобы перестать тратить время.

g cc действительно работает, когда есть это только одна функция, которая вызывает сама себя.

Почему это?

Я что-то не так делаю в коде?

Тогда почему это работает с clang?

Я использую g cc 9.3 на windows с Msys2. Код был скомпилирован с -O3 -fopenmp 

//the program compiled by gcc only runs on one thread
#include<vector>
#include<omp.h>
#include<iostream>
#include<ctime>

using namespace std;

vector<int> vec;
thread_local double steps;

void excalibur(int current_node, int current_depth) {
    #pragma omp simd
    for( int i = 0 ; i < current_node; i++){
        ++steps;
        excalibur(i, current_depth);
    }
    if(current_depth > 0){
        int new_depth = current_depth - 1;
        #pragma omp simd
        for(int i = current_node;i <= vec[current_node];i++){
            ++steps;
            excalibur(i + 1,new_depth);
        }
    } 
}

void mario( int current_node, int current_depth) {
    #pragma omp task firstprivate(current_node,current_depth)
    {
        if(current_depth > 0){
            int new_depth = current_depth - 1;
            for(int i = current_node;i <= vec[current_node];i++){
                ++steps;
                mario(i + 1,new_depth);
            }
        } 
    } 
    #pragma omp simd
    for( int i = 0 ; i < current_node; i++){
        ++steps;
        excalibur(i, current_depth);
    }
}



int main() {
    double total = 0;
    clock_t tim = clock();
    omp_set_dynamic(0);
    int nodes = 10;
    int timesteps = 3;
    omp_set_num_threads(4);
    vec.assign( nodes, nodes - 2 );
    #pragma omp parallel
    {
        steps = 0;
        #pragma omp single
        {
            mario(nodes - 1, timesteps - 1);
        }
        #pragma omp atomic
            total += steps;
    }
    double time_taken = (double)(tim) / CLOCKS_PER_SEC;
    cout <<fixed<<total<<" steps, "<< fixed << time_taken << " seconds"<<endl;
    return 0;
}

, тогда как это работает с g cc

#include<vector>
#include<omp.h>
#include<iostream>
#include<ctime>

using namespace std;

vector<int> vec;
thread_local double steps;

void mario( int current_node, int current_depth) {
    #pragma omp task firstprivate(current_node,current_depth)
    {
        if(current_depth > 0){
            int new_depth = current_depth - 1;
            for(int i = current_node;i <= vec[current_node];i++){
                ++steps;
                mario(i + 1,new_depth);
            }
        } 
    } 
    #pragma omp simd
    for( int i = 0 ; i < current_node; i++){
        ++steps;
        mario(i, current_depth);
    }
}



int main() {
    double total = 0;
    clock_t tim = clock();
    omp_set_dynamic(0);
    int nodes = 10;
    int timesteps = 3;
    omp_set_num_threads(4);
    vec.assign( nodes, nodes - 2 );
    #pragma omp parallel
    {
        steps = 0;
        #pragma omp single
        {
            mario(nodes - 1, timesteps - 1);
        }
        #pragma omp atomic
            total += steps;
    }
    double time_taken = (double)(tim) / CLOCKS_PER_SEC;
    cout <<fixed<<total<<" steps, "<< fixed << time_taken << " seconds"<<endl;
    return 0;
}

1 Ответ

1 голос
/ 06 мая 2020

Ваша программа не запускается параллельно, потому что параллельно запускать просто нечего. При первой записи в mario, current_node равно 9, а vec - это все 8 s, поэтому этот l oop в первой и единственной задаче никогда не выполняется: 

        for(int i = current_node;i <= vec[current_node];i++){
            ++steps;
            mario(i + 1,new_depth);
        }

Следовательно, нет рекурсивного создания новых задач. Как и что работает параллельно, когда вы компилируете его с помощью Clang, я не понимаю, поскольку, когда я компилирую его с помощью Clang 9, исполняемый файл ведет себя точно так же, как и тот, который создается G CC.

Второй код выполняется параллельно из-за рекурсивного вызова в l oop после области task. Но это также неправильная программа OpenMP - спецификация запрещает вложение областей task внутри конструкции simd (см. В разделе Ограничения здесь ):

  • Единственные конструкции OpenMP, которые можно встретить во время выполнения области simd, - это конструкция atomic, конструкция loop, конструкция simd и конструкция ordered с simd clause.

Ни один из двух компиляторов не улавливает эту проблему, когда вложение находится в динамическом c, а не в лексической области конструкции simd.

Редактировать: Я на самом деле внимательно посмотрел на него, и у меня может возникнуть подозрение, что могло вызвать ваше замешательство. Я думаю, вы определяете, работает ли ваша программа параллельно или нет, глядя на загрузку процессора во время ее работы. Это часто приводит к путанице. Среда выполнения Intel OpenMP, которую использует Clang, имеет очень агрессивную политику ожидания. Когда параллельная область в функции main() порождает команду из четырех потоков, один из них выполняет mario(), а три других сталкиваются с неявным барьером в конце области. Там они крутятся, ожидая, когда им в конце концов поставят новые задачи. Они никогда не получают ни одной, но все равно продолжают вращаться, и это то, что вы видите по загрузке процессора. Если вы хотите воспроизвести то же самое с G CC, установите OMP_WAIT_POLICY на ACTIVE, и вы увидите, что загрузка ЦП резко возрастает во время работы программы. Тем не менее, если вы профилируете выполнение программы, вы увидите, что время ЦП тратится внутри вашего кода только в одном потоке.

...