рекурсия, глобальные переменные и OpenMP

Question

У меня проблемы с функцией, которая называет себя правильным способом создания потоков с openmp, мне неясно в этом случае.

long *arrayofindex; 
int length, N;

void gen(long index)
{
    if(index == 0)
    {
        #pragma omp parallel for
        for(int a=0; a<N; ++a)
        {
            #pragma omp critical
            {
            gen(index+1);
            ++arrayofindex[index];
            }
        }
    }
    else
    {
        for(arrayofindex[index]=0; arrayofindex[index]<N; ++arrayofindex[index])
        {
            if(index < length-1)
                gen(index+1);
            else printf("%ld\n", arrayofindex[index]);
        }
    }
}

int main(){
    length = 5, N = 4;
    arrayofindex = (long*) malloc(length * sizeof(long));
    for(int i=0; i<length; ++i)
        arrayofindex[index] = 0;
    gen(0);
}

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

Есть ли способ через это?или это будет беспомощно из-за способа кода.

Полный код https://github.com/e2002e/zhou

Answer 1

Как я понимаю представленный код, общая цель состоит в том, чтобы сгенерировать все слова N, которые могут быть сформированы с помощью алфавита length.Каждый рекурсивный вызов gen() соответствует одной позиции буквы, поэтому каждый раз, когда элемент управления достигает дна рекурсии, первые N элементы arrayofindex представляют буквы одного слова.

Но этодолжно быть очевидно, что несколько параллельных потоков не могут использовать один и тот же arrayofindex.Каждый поток ожидает, когда достигнет нижней части рекурсии, чтобы найти в arrayofindex значения, которые it установил на своем рекурсивном пути.Это фундаментально для подхода.Если другие потоки изменяют arrayofindex в то же время, то все они, вероятно, получают путаницу значений, установленных разными потоками.Более того, вы, вероятно, не получите ничего подобного ускорению, на которое надеетесь, потому что потоки должны синхронизировать свои обращения к arrayofindex.

---

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

---

Существуют различные способы присвоения каждому потоку OMP своего собственного рабочего массива.Если пространство должно продолжать выделяться динамически, то вы должны организовать его внутри параллельной области, чтобы каждый поток выделял свой собственный.Однако, если вы хотите и можете полагаться на массивы переменной длины, то, вероятно, единственное, что вам нужно, это предложение OMP private, присоединенное к вашей конструкции parallel for.

Например,этот вариант в вашем коде работает для меня:

void gen_tail(int length, int num_letters, int arrayofindex[], int position) {
    for (int letter = 0; letter < num_letters; letter++) {
        arrayofindex[position] = letter;
        if (position + 1 < length) {
            gen_tail(length, num_letters, arrayofindex, position + 1);
        } else {
            // this is the bottom ... do something with arrayofindex, such as:
            #pragma omp critical
            {
                for (int i = 0; i < length; i++) {
                    putchar('A' + arrayofindex[i]);
                }
                putchar('\n');
            }
        }
    }
}

void gen(int length, int num_letters) {
    assert(length > 1);
    int arrayofindex[length];  // Note: VLA, _not_ dynamically allocated

    // Marking the array 'private' means each thread gets its own copy.
    // This would not have the needed effect if 'arrayofindex' were a pointer.
    #pragma omp parallel for private(arrayofindex)
    for (int letter = 0; letter < num_letters; letter++) {
        arrayofindex[0] = letter;
        gen_tail(length, num_letters, arrayofindex, 1);
    }
}

int main(void) {
    gen(5, 4);
}

, который выдает ожидаемые 1024 (== 4 ⁵ ) результаты для меня, все разные, так как у меня есть все основания ожидатьэто должно сделать.