Многопоточные алгоритмы работают намного медленнее - PullRequest
Новая
       34

Многопоточные алгоритмы работают намного медленнее

1 голос
/ 10 января 2020

Я пробовал с OpenMP и Cilk Plus. Результат тот же, многопоточность работает медленнее. Я не знаю, что я делаю не так. Я сделал то, что парень сделал в этом уроке

Его код работает лучше параллельно, в то время как у меня ситуация такая:

PARALLEL : Число Фибоначчи # 42 равно 267914296
Рассчитано за 33.026 секунд с использованием 8 рабочих

SERIAL: Число Фибоначчи # 42 равно 267914296
Рассчитано за 2,110 секунды с использованием 8 рабочих

Я точно скопировал исходный код руководства.

Я также попробовал его с OpenMP, там тоже самое происходит. Я проверяю использование ядер ЦП во время выполнения. Все они работают, это нормально.

Я попытался изменить количество работников с помощью этой команды: 

export CILK_NWORKERS=4

Похоже, что число работников увеличивается, алгоритм работает 1031 * медленнее *. Но иногда это не так. Я реализовал коды Cilk как на C, так и на C ++. Без разницы.

Это последовательная функция Фибоначчи: 

int fib_s(int n)
{
    if (n < 2)
        return n;
    int x = fib_s(n-1);
    int y = fib_s(n-2);

    return x + y;
}

Это параллельная функция Фибоначчи: 

int fib(int n)
{
    if (n < 2)
        return n;
    int x = cilk_spawn fib(n-1);
    int y = fib(n-2);
    cilk_sync;
    return x + y;
}

И я рассчитываю время работы следующим образом в функции main(): 

clock_t start = clock();
int result = fib(n);
clock_t end = clock();
double duration = (double)(end - start) / CLOCKS_PER_SEC;

Кто-нибудь может мне помочь?

Ответы [ 2 ]

2 голосов
/ 10 января 2020

Правильный ответ на ваш вопрос зависит от оборудования. Многие факторы могут влиять на производительность кода в целом: для ускорения выполнения могут применяться разные программные стратегии. Однако некоторые из них являются более эффективными, чем другие, в зависимости от (1) конкретного выбранного приложения и (2) от конкретной выбранной аппаратной платформы. Я хотел бы рекомендовать профилировать ваше приложение.

Здесь , вы можете найти общее введение в профилирование программного обеспечения, а здесь - список программных инструментов, которые поможет вам в этой задаче.

В этом и этом другом ссылках вы можете найти информацию для профилирования приложения OpenMP (случай вашего вопроса).

Это всегда хорошая практика, чтобы знать и понимать, что происходит под капотом. Это позволит вам найти узкое место в известном приложении / коде / оборудовании Трис.

1 голос
/ 14 января 2020

Q : Кто-нибудь может мне помочь?

Да. Вы увидите, что fib( 42 ) может принимать меньше 25 [us] в интерпретируемом (!) коде для одного работника

Учитывая, что, как сообщалось, приведенный выше код PARALLEL тратит ~33 [s] при обработке скомпилированный код может вычислить fib( ~ 1,700,000 ) в течение того же ~33 [s], если он спроектирован правильно.

Решение:

Любое рекурсивно сформулированное описание проблемы является грехом старого математика:

Хотя на бумаге это может выглядеть довольно круто,
оно масштабируется безобразно в стеке и ужасно блокирует ресурсы для любой более глубокой рекурсии ...
делает все" предыдущий " - уровни ждут большую часть времени ,
до тех пор, пока оба return 2 и return 1 произошло во всех их путях-потомках
, и фаза накопления рекурсивно сформулированного алгоритма начинает расти, поднимаясь к вершине со всех сторон h погружения с глубокой рекурсией.

Это дерево зависимостей равно чистому [SERIAL] (одно за другим) прогрессу вычислений, и любая попытка внедрить { [CONCURENT] | [PARALLEL] } -обработанную оркестровку будет, но увеличим затраты на обработку (добавив все накладные расходы надстройки) без каких-либо улучшений последовательности чисто-[SERIAL] накопления результата на основе зависимостей.

Давайте посмотрите, как ужасно плохо пошло cilk_spawn fib( N ): 

f(42)
   |
   x=--> --> --> --> --> --> --> --> --> --> --> -- --> --> --> --> --> --> --> --> --> --> --> --> --> -->f(41)
   |                                                                                                          |
   y=f(40)                                                                                                    x=--> --> --> --> --> --> --> --> --> -->  f(40)
   ~    |                                                                                                     |                                             |
   ~    x=--> --> --> --> --> --> --> --> --> f(39)                                                           y=f(39)                                       x=--> --> --> --> --> --> --> --> -->  f(39)
   ~    |                                        |                                                            ~    |                                        |                                         |   
   ~    y=f(38)                                  x=--> --> --> --> --> --> f(38)                              ~    x=--> --> --> --> f(38)                  y=f(38)                                   x=--> --> --> --> --> --> f(38)
   ~    ~    |                                   |                            |                               ~    |                    |                   ~    |                                    |                            |
   ~    ~    x=--> --> f(37)                     y=f(37)                      x=--> --> f(37)                 ~    y=f(37)              x=--> --> --> f(37) ~    x=--> --> f(37)                      y=f(37)                      x=--> --> f(37)
   ~    ~    |            |                      ~    |                       |            |                  ~    ~    |               |                |  ~    |            |                       ~    |                       |            |
   ~    ~    y=f(36)      x=--> --> f(36)        ~    x=--> --> f(36)         y=f(36)      x=-->f(36)         ~    ~    x=--> --> f(36) y=f(36)          x= ~    y=f(36)      x=--> --> f(36)         ~    x=--> --> f(36)         y=f(36)      x=--> --> f(36)
   ~    ~    ~    |       |            |         ~    |            |          ~    |       |       |          ~    ~    |            |  ~    |           |  ~    ~    |       |            |          ~    |            |          ~    |       |            |
   ~    ~    ~    x=-->f  y=f(35)      x=-->f    ~    y=f(35)      x=-->f(35) ~    x=-->f  y=f(35) x=-->f     ~    ~    y=f(35)      x= ~    x=-->f(35)  y= ~    ~    x=-->f  y=f(35)      x=-->f(35) ~    y=f(35)      x=-->f(35) ~    x=-->   y=f(35)      x=-->f(35)
   ~    ~    ~    |       ~    |       |         ~    ~    |       |       |  ~    |       ~    |  |          ~    ~    ~    |       |  ~    |       |   ~  ~    ~    |       ~    |       |       |  ~    ~    |       |       |  ~    |       ~    |       |       |
   ~    ~    ~    y=f(34) ~    x=-->f  y=f(34)   ~    ~    x=-->f  y=f(34) x= ~    y=f(34) ~    x= y=f(34)    ~    ~    ~    x=-->f  y= ~    y=f(34) x=  ~  ~    ~    y=f(34) ~    x=-->f  y=f(34) x= ~    ~    x=-->f  y=f(34) x= ~    y=f(34) ~    x=-->f  y=f(34) x=-->f
   ~    ~    ~    ~    |  ~    |       ~    |    ~    ~    |       ~    |  |  ~    ~    |  ~    |  ~    |     ~    ~    ~    |       ~  ~    ~    |  |   ~  ~    ~    ~    |  ~    |       ~    |  |  ~    ~    |       ~    |  |  ~    ~    |  ~    |       ~       |
   ~    ~    ~    ~    x= ~    y=f(33) ~    x=   ~    ~    y=f(33) ~    x= y= ~    ~    x= ~    y= ~    x=    ~    ~    ~    y=f(33) ~  ~    ~    x= y=  ~  ~    ~    ~    x= ~    y=f(33) ~    x= y= ~    ~    y=f(33) ~    x= y= ~    ~    x= ~    y=f(33) ~       y=f(33)
   ~    ~    ~    ~    |  ~    ~    |  ~    |    ~    ~    ~    |  ~    |  ~  ~    ~    |  ~    ~  ~    |     ~    ~    ~    ~    |  ~  ~    ~    |  ~   ~  ~    ~    ~    |  ~    ~    |  ~    |  ~  ~    ~    ~    |  ~    |  ~  ~    ~    |  ~    ~    |  ~       ~    |
   ~    ~    ~    ~    y= ~    ~    x= ~    y=   ~    ~    ~    x= ~    y= ~  ~    ~    y= ~    ~  ~    y=    ~    ~    ~    ~    x= ~  ~    ~    y= ~   ~  ~    ~    ~    y= ~    ~    x= ~    y= ~  ~    ~    ~    x= ~    y= ~  ~    ~    y= ~    ~    x= ~       ~    x=-->f
   ~    ~    ~    ~    ~  ~    ~    |  ~    ~    ~    ~    ~    |  ~    ~  ~  ~    ~    ~  ~    ~  ~    ~     ~    ~    ~    ~    |  ~  ~    ~    ~  ~   ~  ~    ~    ~    ~  ~    ~    |  ~    ~  ~  ~    ~    ~    |  ~    ~  ~  ~    ~    ~  ~    ~    |  ~       ~    |
   :    :    :    :    :
   :    :    :    :     
   :    :    :
   ~    ~  --SYNC-----------f(36)+f(37)
   ~    ~ <--RET x+y // <-- f(38)
   ~  --SYNC----------------f(38)+f(39)
   ~ <--RET x+y      // <-- f(40)
 --SYNC---------------------f(40)+f(41)
<--RET x+y           // <-- f(42)

Всего считать , во сколько раз нисходящий рекурсивный метод Fib( N ) был полностью пересчитан для каждого и соответствующего значения N - да, вы подсчитываете одну и ту же вещь много раз снова и снова и снова, просто к "математическому" - lazines рекурсивного метода: 

fib( N == 42 ) was during recursion calculated .........1x times...
fib( N == 41 ) was during recursion calculated .........1x times...
fib( N == 40 ) was during recursion calculated .........2x times...
fib( N == 39 ) was during recursion calculated .........3x times...
fib( N == 38 ) was during recursion calculated .........5x times...
fib( N == 37 ) was during recursion calculated .........8x times...
fib( N == 36 ) was during recursion calculated ........13x times...
fib( N == 35 ) was during recursion calculated ........21x times...
fib( N == 34 ) was during recursion calculated ........34x times...
fib( N == 33 ) was during recursion calculated ........55x times...
fib( N == 32 ) was during recursion calculated ........89x times...
fib( N == 31 ) was during recursion calculated .......144x times...
fib( N == 30 ) was during recursion calculated .......233x times...
fib( N == 29 ) was during recursion calculated .......377x times...
fib( N == 28 ) was during recursion calculated .......610x times...
fib( N == 27 ) was during recursion calculated .......987x times...
fib( N == 26 ) was during recursion calculated ......1597x times...
fib( N == 25 ) was during recursion calculated ......2584x times...
fib( N == 24 ) was during recursion calculated ......4181x times...
fib( N == 23 ) was during recursion calculated ......6765x times...
fib( N == 22 ) was during recursion calculated .....10946x times...
fib( N == 21 ) was during recursion calculated .....17711x times...
fib( N == 20 ) was during recursion calculated .....28657x times...
fib( N == 19 ) was during recursion calculated .....46368x times...
fib( N == 18 ) was during recursion calculated .....75025x times...
fib( N == 17 ) was during recursion calculated ....121393x times...
fib( N == 16 ) was during recursion calculated ....196418x times...
fib( N == 15 ) was during recursion calculated ....317811x times...
fib( N == 14 ) was during recursion calculated ....514229x times...
fib( N == 13 ) was during recursion calculated ....832040x times...
fib( N == 12 ) was during recursion calculated ...1346269x times...
fib( N == 11 ) was during recursion calculated ...2178309x times...
fib( N == 10 ) was during recursion calculated ...3524578x times...
fib( N ==  9 ) was during recursion calculated ...5702887x times...
fib( N ==  8 ) was during recursion calculated ...9227465x times...
fib( N ==  7 ) was during recursion calculated ..14930352x times...
fib( N ==  6 ) was during recursion calculated ..24157817x times...
fib( N ==  5 ) was during recursion calculated ..39088169x times...
fib( N ==  4 ) was during recursion calculated ..63245986x times...
fib( N ==  3 ) was during recursion calculated .102334155x times...
fib( N ==  2 ) was during recursion calculated .165580141x times...
fib( N ==  1 ) was during recursion calculated .102334155x times...

ЭФФЕКТИВНАЯ ОБРАБОТКА БЫСТРОГО И РЕСУРСНОГО ОБЕСПЕЧЕНИЯ - ВДОХНОВЕНИЕ:

В то время как оригинальное, рекурсивное вычисление называется 535,828,591 ti mes (!!!) тот же тривиальный fib() (очень часто один, который где-то еще уже вычислен
---- некоторые даже сотни миллионов уже много раз ~ 102,334,155x раз ... как fib( 3 )), порождая до 267,914,295 всего - [CONCURRENT] блоков исполнения кода, поставленных в очередь на 8- работники, ожидающие большую часть времени, но за то, что они погрузили своих порожденных детей так глубоко, что достигли return 1 и return 2, чтобы потом ничего не делать, кроме как добавить пару потом возвращенных чисел и вернуться из дорогостоящего собственного процесса, «прямой» метод обработки не подлежит сомнению намного умнее и намного быстрее : 

int fib_direct( int n ) // PSEUDO-CODE
{   assert(  n > 0      && "EXCEPTION: fib_direct() was called with a wrong parameter value" );
    if (  n == 1
       || n == 2
          ) return n;
 // ---------------------------- .ALLOC + .SET 
    int fib_[ max(4,n) ];
        fib_[3] = 3;
        fib_[4] = 5;
 // ---------------------------- .LOOP LESS THAN N-TIMES
    for(           int i = 5; i <= n; i++ )
    {   fib_[i] = fib_[i-2]
                + fib_[i-1];
        }
 // ---------------------------- .RET
    return fib_[n];
    }

Чуть более эффективная реализация (все еще только один поток и все еще только интерпретируемый), управляемый легко вычислить fib_direct( 230000 ) менее чем за 2.1 [s], который был вашим временем выполнения скомпилированного кода всего за fib( 42 ).

...