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 )
.