распараллеливание вложенного цикла в потоковых строительных блоках - PullRequest
Новая
       26

распараллеливание вложенного цикла в потоковых строительных блоках

1 голос
/ 02 апреля 2011

Я новичок в многопоточности строительных блоков и пытаюсь закодировать алгоритм FFT в TBB, чтобы получить практический опыт.В случае этого алгоритма я могу распараллелить только самый внутренний цикл.но при этом производительность снизилась до неприемлемой степени (более тысячи раз).Я пытался для размера массива до 2 ^ 20, но тот же результат.Мой код приведен ниже 

for(stage1=0;stage1 < lim;stage1 ++)
{
    butterfly_index1 = butterfly_index2;
    butterfly_index2 = butterfly_index2 + butterfly_index2; 
    k = -1*2*PI/butterfly_index2;
    k_next = 0.0;
    for(stage2 = 0 ; stage2 < butterfly_index1;stage2++)
    {
        sine=sin(k_next);
        cosine = cos(k_next);
        k_next = k_next + k;
        FFT. sine = &sine;
        FFT.cosine = &cosine;
        FFT.n2 = &butterfly_index2;
        FFT.loop_init = &stage2;
        FFT.n1 = &butterfly_index1;
        parallel_for(blocked_range<int>(
                        stage2,SIZE,SIZE/4),FFT,simple_partitioner()); 
    }
}

, а тело для parallel_loop равно 

void operator()(const blocked_range<int> &r)const
{
    for(int k = r.begin(); k != r.end(); k++)
    {   
        if(k != *loop_init)
        {
            if((k - (*loop_init))% (* n2)!= 0)
                continue;
        }           
        temp_real = (*cosine) * X[k + *n1].real - (*sine) * X[k + *n1].img;
        temp_img = (*sine)* X[k + *n1].real + (*cosine) * X[k + *n1].img;
        X[k + *n1].real = X[k].real - temp_real;
        X[k + *n1].img = X[k].img - temp_img;
        X[k].real = X[k].real + temp_real;
        X[k].img = X[k].img + temp_img; 
    }
}

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

Ответы [ 2 ]

1 голос
/ 03 апреля 2011

Для очень коротких рабочих нагрузок может произойти значительное замедление из-за накладных расходов на создание потоков. Я не верю, что для 2 ^ 20 элементов в массиве такое огромное падение производительности.

Другим существенным источником снижения производительности является неспособность компилятора оптимизировать (в частности, векторизовать) код после того, как он был TBBfied. Узнайте, может ли ваш компилятор создать отчет о векторизации, и найдите различия между серийной и TBB-версиями.

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

Другим обычным источником значительных накладных расходов является слишком мелкий параллелизм, то есть множество задач, каждая из которых содержит очень мало работы. Но и здесь это не так, потому что размер зерна SIZE / 4 в 3-м параметре для block_range указывает, что оператор body () () будет вызываться не более 4 раз в соответствии с алгоритмом.

Я бы порекомендовал не указывать simple_partitioner и grainsize для первоначальных экспериментов, а вместо этого позволить TBB динамически распределять работу. При необходимости вы можете настроить его позже.

0 голосов
/ 04 апреля 2011

проблема с моим кодом заключалась в уменьшении рабочей нагрузки с увеличением переменной n2. поэтому, когда цикл out продолжает работу, параллельная нагрузка становится равной половине, а после нескольких итераций она становится слишком маленькой, чтобы повысить производительность с помощью TBB. Таким образом, решение состоит в том, чтобы распараллеливать внутренний цикл только для итераций, когда рабочая нагрузка для внутреннего цикла достаточна, и сериализовать внутренний цикл для остальных итераций. во-вторых, заголовок цикла for, который содержит проверку условия (k! = r.end ()), также снижает производительность. решение состоит в том, чтобы заменить r.end () на локально определенную переменную, которая инициализируется как r.end ()

Спасибо Intel Software Forum за помощь в решении этой проблемы

...