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

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

1 голос
/ 20 февраля 2020

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

Прямое и простое for() -l oop параллельно, используя 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;
    }

1 Ответ

0 голосов
/ 20 февраля 2020

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

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

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

   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

Ошибка : mea culpa - код, исключенный один fDIV для бота случай тома (повторные тесты показывают ускорение на ~ + 10% - см. код )

Тестирование с таким малым количеством циклов, как 1E6 (@ -a-less-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

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

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

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

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

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

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
                   );
}

И, наконец, параллельный источник случайных последовательностей заслуживает другого Пристальное внимание, поскольку эти инструменты пытаются поддерживать свое внутреннее состояние, которое может создавать проблемы "через" потоки. Хорошей новостью является то, что StackOverflow может многое сделать для решения этой задачи, затрагивающей тему, просто не стесняйтесь искать, читать и повторно использовать собранные знания сообщества. Стоит ли учиться здесь, не так ли? 

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++ )
//     ^~~
********************************************************************************************/
...