Почему выполнение задачи в потоках OpenMP на самом деле занимает больше времени, чем в последовательном?

Я написал этот код для оценки значения интеграла.

Прямой и простой параллельный цикл for() с использованием openmp.

Что бы я ни делал, я не могу сократить время работы в параллельном режиме до меньшего, чем в последовательном.

В чем проблема?

lenmuta, tol, cores, seed это 1, 0.01, number_of_threads, 0 соответственно.

Вот код:

// ================= Libraries
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <omp.h>
#include <sys/time.h>

int main( int argc, char* argv[] )
{
    float lenmuta = atof( argv[1] );
    float tol     = atof( argv[2] );
    int   cores   = atoi( argv[3] );
    int   seed    = atoi( argv[4] );

#define M  1 / ( tol*tol*0.01*lenmuta*lenmuta );

    unsigned int N = M;

    printf( "%10.5f \n", tol );
    printf(     "%d \n", N );

    omp_set_num_threads( cores );

    double sum2;
    int    Threadnum;
    float  rvalue;

    Threadnum = omp_get_max_threads();
    rvalue    = lenmuta / ( 1 + lenmuta * lenmuta );

    printf( "the true value is %f \n", rvalue );
    printf( "the number of threads we use is %d \n", Threadnum );

    struct random_data* state;
    double start1 = omp_get_wtime();
    int    k, i;
    double y;
    char   statebuf[32];

    state = malloc( sizeof( struct random_data ) );

    initstate_r( seed, statebuf, 32, state );
    srandom_r(   seed, state );

    // =========Parallel Region=======================

    #pragma omp parallel for private( i, y ) reduction( +:sum2 )
    for( i = 0; i < N; i++ )
    {
         y     = -( 1 / lenmuta ) * log( (double) rand() / ( (double) RAND_MAX ) );
         sum2 +=  cos( y );
    }
    sum2 = sum2 / N;

    printf( "Time: \t %f \n", omp_get_wtime() - start1 );
    printf( "the estimate value is %1.10f \n", sum2 );

    return 0;
    }

Mohsen 19.02.2020 источник

Ответы (1)

arrow_upward
0
arrow_downward

Говоря о производительности?
Код может работать намного быстрее ~ +4x (!) для 1E6 циклов.

Независимо от того, используете вы OpenMP-инструменты или нет, давайте начнем с них. Управление потоками OpenMP (создание экземпляров, распределение задач, сбор результатов — (умное reduction(+:sum2)) ** все это требует дополнительных затрат — см. суммы** (пропорции) инструкций по сборке, затраченные на это ).

Учитывая, что код, украшенный #pragma, оплатил все эти дополнительные расходы (что он и сделал в соответствии с инструкциями), вы почти ничего не получаете взамен в обмен на потраченные расходы, но сумма сокращения 1E6 doubles ( 1E6 такая же крошечная, как почти просто синтаксический сахар, по сравнению с бесплатным выполнением кода в чистом [SERIAL] надстройках, который суммирует то же самое в мгновение ока ~ 18 [ms], если умный (даже меньше, чем ~ 70 [ms], если нет), так как не сжигает дополнительные расходы на управление потоками и накладные расходы на распределение задач/сбор результатов (здесь ~ 400 [ms] для a 2-core sandboxed demo test< /а> ),

   0.01000 
1000000 
the true value is 0.500000      the number of threads we use is 2 

OpenMP as-is    Time:    0.467055     
SERIAL as-is    Time:    0.069820 <~~+            70 [ms] @ 1E6 loops
OpenMP Re-DEF'd Time:    0.328225    |            !!
SERIAL Re-DEF'd Time:    0.017899 <~~+~ 6x FASTER 18 [ms] @ 1E6 loops

_{Ошибка : моя вина - код избегает одного fDIV для нижнего регистра (повторные тесты показывают ~ +10% ускорение - см.}code )

Тестирование такого малого количества циклов, как 1E6 ( @-a-few-GHz-CPU-cores ... ), дает больше шума, чем неопровержимых фактов. В любом случае, мы можем стать быстрее в любой из стратегий:

OpenMP as-is    Time:      0.375825     the estimate value is 0.5000982178 
SERIAL as-is    Time:      0.062920     the estimate value is 0.5004906150
                                |||
                               ~300 [us]FASTER--v
OpenMP Re-DEF'd Time:      0.062613     the estimate value is 0.4992401088
                              ~2    [ms]SLOWER--^
                               ||||
SERIAL Re-DEF'd Time:      0.060253     the estimate value is 0.4995912559

Справедливо отметить, что при более длительном цикле накладные расходы, увеличивающие цикл, будут генерировать больше общего времени вычислений, даже при -O3, поэтому рефакторинговый код будет демонстрировать самые быстрые результаты за все время, но коэффициент ускорения уменьшится до ~ 1.16x. на 25E6 петель

Основной недостаток:
ужасно плохой несбалансированность затрат:эффектов
снижает эффективность любых вычислений.

На самом деле почти нечего вычислять (несколько fADD-s, fMUL, fNEG, fDIV-s, fLOG ) внутри самого дорогого синтаксического конструктора (не говоря уже о random ), что могло бы по крайней мере никогда не оправдать эти затраты, которые были потрачены на создание экосистемы выполнения кода OpenMP (тем не менее, мы покажем, что они могут быть сокращены даже в 6 раз для более БЫСТРОГО запуска).

Зачем когда-либо пересчитывать, тем меньше это МИЛЛИОН+ РАЗ постоянное значение?

Итак, давайте отсеем то, что никогда не должно попадать в разделы мотивированные производительностью :

double C_LogRAND_MAX = log( (double) RAND_MAX ); double C_1divLENMUTA = -1 / lenmuta; double C_2sub = C_LogRAND_MAX * C_1divLENMUTA;

и :

#pragma omp parallel for private( i, y ) reduction( +:sum2 ) for( i = 0; i < N; i++ ) { sum2 += cos( C_1divLENMUTA // fMUL * log( (double) rand() ) // +costs of keeping the seed-state management - C_2sub // fSUB ); }

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

w/o -O3: =:_____________________________________________________________________:[ns] SERIAL NOP Time: 3.867352 DIV( 2000000000 ) ~ 0.000000002 ~ 2 [ns]:||:for(){...}loop-overhead : SERIAL RAND() Time: 10.845900 DIV( 1000000000 ) ~ 0.000000011 ~ +9 [ns]: |||||||||:rand() : SERIAL (double) RAND() Time: 10.923597 DIV( 1000000000 ) ~ 0.000000011 ~ +0 [ns]: :(double) : SERIAL LOG( (double) RAND() ) Time: 37.156017 DIV( 1000000000 ) ~ 0.000000037 ~ +27 [ns]: |||||||||||||||||||||||||||:log() : SERIAL COS( LOG( (double) RAND() ) ) Time: 54.472115 DIV( 800000000 ) ~ 0.000000068 ~ +31 [ns]: |||||||||||||||||||||||||||||||:cos() SERIAL COS( LOG( (double) RAND() ) ) Time: 55.320798 DIV( 800000000 ) ~ 0.000000069 : w/o -O3 : w/-O3: :::( :::( (::::::) ::::() ) ) !!. :::( ::::::::: ) !! =:____________: :! : SERIAL COS( LOG( (double) RAND() ) ) Time: 9.305908 DIV( 800000000 ) ~ 0.000000012 ~ 12 [ns]:|||||||||||| with -O3 : SERIAL COS( LOG( (double) RAND() ) ) Time: 2.135143 DIV( 200000000 ) ~ 0.000000011 : : SERIAL LOG( (double) RAND() ) Time: 2.082406 DIV( 200000000 ) ~ 0.000000010 : : SERIAL (double) RAND() Time: 2.244600 DIV( 200000000 ) ~ 0.000000011 SERIAL RAND() Time: 2.101538 DIV( 200000000 ) ~ 0.000000011 SERIAL NOP Time: 0.000000 DIV( 200000000 ) ~ 0.000000000 ^^ || !|| vvv OpenMP COS( LOG( (double) RAND() ) ) Time: 33.336248 DIV( 100000000 ) ~ 0.000000333 #pragma omp parallel num_threads( 2 ) w/o OpenMP COS( LOG( (double) RAND() ) ) Time: 0.388479 DIV( 1000000 ) ~ 0.000000388 #pragma omp parallel num_threads( 2 ) w/o OpenMP COS( LOG( (double) RAND() ) ) Time: 37.636114 DIV( 100000000 ) ~ 0.000000376 #pragma omp parallel num_threads( 2 ) with -O3 OpenMP COS( LOG( (double) RAND() ) ) Time: 38.876272 DIV( 100000000 ) ~ 0.000000389 #pragma omp parallel num_threads( 2 ) with -O3 OpenMP COS( LOG( (double) RAND() ) ) Time: 44.226391 DIV( 100000000 ) ~ 0.000000442 #pragma omp parallel num_threads( 2 ) with -O3 OpenMP COS( LOG( (double) RAND() ) ) Time: 0.333573 DIV( 1000000 ) ~ 0.000000334 #pragma omp parallel num_threads( 4 ) w/o OpenMP COS( LOG( (double) RAND() ) ) Time: 35.624111 DIV( 100000000 ) ~ 0.000000356 #pragma omp parallel num_threads( 4 ) w/o OpenMP COS( LOG( (double) RAND() ) ) Time: 37.820558 DIV( 100000000 ) ~ 0.000000378 #pragma omp parallel num_threads( 4 ) with -O3 OpenMP COS( LOG( (double) RAND() ) ) Time: 38.625498 DIV( 100000000 ) ~ 0.000000386 #pragma omp parallel num_threads( 4 ) with -O3 OpenMP COS( LOG( (double) RAND() ) ) Time: 39.782386 DIV( 100000000 ) ~ 0.000000398 #pragma omp parallel num_threads( 4 ) with -O3 OpenMP COS( LOG( (double) RAND() ) ) Time: 0.317120 DIV( 1000000 ) ~ 0.000000317 #pragma omp parallel num_threads( 8 ) w/o OpenMP COS( LOG( (double) RAND() ) ) Time: 34.692555 DIV( 100000000 ) ~ 0.000000347 #pragma omp parallel num_threads( 8 ) w/o OpenMP COS( LOG( (double) RAND() ) ) Time: 0.360407 DIV( 1000000 ) ~ 0.000000360 #pragma omp parallel num_threads( 8 ) with -O3 OpenMP COS( LOG( (double) RAND() ) ) Time: 3.737517 DIV( 10000000 ) ~ 0.000000374 #pragma omp parallel num_threads( 8 ) with -O3 OpenMP COS( LOG( (double) RAND() ) ) Time: 0.380087 DIV( 1000000 ) ~ 0.000000380 #pragma omp parallel num_threads( 8 ) with -O3 OpenMP COS( LOG( (double) RAND() ) ) Time: 0.354283 DIV( 1000000 ) ~ 0.000000354 #pragma omp parallel num_threads( 16 ) w/o OpenMP COS( LOG( (double) RAND() ) ) Time: 35.984292 DIV( 100000000 ) ~ 0.000000360 #pragma omp parallel num_threads( 16 ) w/o OpenMP COS( LOG( (double) RAND() ) ) Time: 3.654442 DIV( 10000000 ) ~ 0.000000365 #pragma omp parallel num_threads( 16 ) with -O3 OpenMP COS( LOG( (double) RAND() ) ) Time: 37.233374 DIV( 100000000 ) ~ 0.000000372 #pragma omp parallel num_threads( 16 ) with -O3 OpenMP COS( LOG( (double) RAND() ) ) Time: 4.112637 DIV( 10000000 ) ~ 0.000000411 #pragma omp parallel num_threads( 16 ) with -O3 OpenMP COS( LOG( (double) RAND() ) ) Time: 37.813872 DIV( 100000000 ) ~ 0.000000378 #pragma omp parallel num_threads( 32 ) w/o OpenMP COS( LOG( (double) RAND() ) ) Time: 0.412896 DIV( 1000000 ) ~ 0.000000413 #pragma omp parallel num_threads( 32 ) w/o OpenMP COS( LOG( (double) RAND() ) ) Time: 34.098855 DIV( 100000000 ) ~ 0.000000341 #pragma omp parallel num_threads( 32 ) with -O3 OpenMP COS( LOG( (double) RAND() ) ) Time: 35.372660 DIV( 100000000 ) ~ 0.000000354 #pragma omp parallel num_threads( 32 ) with -O3 OpenMP COS( LOG( (double) RAND() ) ) Time: 39.256430 DIV( 100000000 ) ~ 0.000000393 #pragma omp parallel num_threads( 32 ) with -O3 ///////////////////////////////////////////////////////////////////////////////////////////// // // -O3 // warning: iteration 2147483647 invokes undefined behavior [-Waggressive-loop-optimizations] // for( i = 0; i < N; i++ ) // ^~~ ********************************************************************************************/

user3666197 20.02.2020

comment

Поскольку вы упомянули параллельную генерацию случайных чисел... Я только что ответил на вопрос именно об этом stackoverflow.com/questions/60292324/ - Jim Cownie; 20.02.2020

comment

Приветствую Bristol @JimCownie (глубокий поклонник инновационного поколения британских транспьютеров + аппаратное обеспечение транспьютера поддерживает настоящий язык [PARALLEL] occam здесь) — меня удивило, что предложенный инструмент Intel MKL имеет периодичность всего 2^128, когда существует около четверти века, стабильные, дешевые в вычислительном отношении (читай, не разделяющие + не блокирующие) PRNG, имеющие одинаковые намного выше 2^(318+) т. е. намного выше 1E+57 раз дольше? Каково, по вашему опыту, основное преимущество использования предложенного MKL, которое я, возможно, здесь упустил? - user3666197; 20.02.2020

comment

Спасибо за палец вверх. Основное преимущество алгоритмов из статьи «Параллельная генерация случайных чисел так же просто, как 1, 2, 3» заключается в том, что вы можете явно выбирать сегменты последовательности случайных чисел, которые могут гарантированно находиться на определенном расстоянии друг от друга. Таким образом, вы наверняка знаете, что в вашей параллельной программе, в которой много потоков, генерирующих случайные числа, генерируемые ими последовательности не будут перекрываться. - Jim Cownie; 21.02.2020

comment

(ну, если кто-то не использует эти 2^128 членов пространства состояний и не должен начать повторять их в цикле) - спасибо за замечание, @JimCownie - user3666197; 21.02.2020

comment

Верно, но даже с потоками 1 Ми (220) вы все равно можете сгенерировать 2108 чисел в каждом потоке до того, как это произойдет, что, если вы генерируете их со скоростью один/нс, займет 3,25 e41 секунды или ~ 1e34 года, что кажется достаточно безопасным, учитывая, что ожидаемое оставшееся время жизни Солнца составляет всего 5e9 лет... - Jim Cownie; 24.02.2020

comment

Это заслуживает +1, @JimCownie - спасибо за напоминание об ограниченном промежутке времени, в котором мы живем. Хотя это выходит далеко за рамки этого поста, красота справедливой случайности заключается в том, что она никогда не будет( будь то в пределах ограниченного промежутка времени или нет) приблизиться к исчерпанию основного пространства состояний. Мы развиваем и сохраняем по тому же самому принципу значительно большую выразительность (богатство) математического аппарата с такой же уверенностью, что нет ( известных до сих пор)ресурсов, которые могли бы когда-либо материализовать его выражаемое богатство, которое не ограничивает потребность в этом богатстве :о) - user3666197; 24.02.2020

Почему выполнение задачи в потоках OpenMP на самом деле занимает больше времени, чем в последовательном?

Ответы (1)

Говоря о производительности?Код может работать намного быстрее ~ +4x (!) для 1E6 циклов.

Основной недостаток:ужасно плохой несбалансированность затрат:эффектовснижает эффективность любых вычислений.

Зачем когда-либо пересчитывать, тем меньше это МИЛЛИОН+ РАЗ постоянное значение?

Вопросы по теме

Говоря о производительности?
Код может работать намного быстрее ~ +4x (!) для 1E6 циклов.

Основной недостаток:
ужасно плохой несбалансированность затрат:эффектов
снижает эффективность любых вычислений.