Факториал (Потоки)

[BratSinot]

Доброго времени суток!

Надо распаралелить функцию факториала на 4 потока. На 2 потока это легко. Скажем N!, на первый поток идет от 1 до [N/2], на второй от [N/2]+1 до N. А вот на четыре потока вот так просто не получися.
Можно, конечно, проверять, если число делится на 4-ре, то 4-ре потока, если на 3-ри то на 3-ри потока, а все остальные случаи в два потока. Но проверка не вариант, ибо если у нас будет скажем цикл от 1 до 100000, и каждый раз проверять, то сумарная потеря скорости будет заметна.

[Crazy]

Первый поток: 1*5*9*13
Второй поток : 2*6*10*14
Третий поток: 3*7*11*15
Четвертый поток:4*8*12*16

16! =( 1*5*9*13) * (2*6*10*14) * (3*7*11*15) * (4*8*12*16)

[sciko]

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

[BratSinot]

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

Мне, как минимум, просто интересно. А OpenMP как сочетается с GMP?

[NickLion]

Почему не получается?

Код: Выделить всё

if(n>=min_reasonable){
    f1=1st thread: 1*...*[n/4];
    f2=2nd thread: ([n/4]+1)*...*[n/2];
    f3=3rd thread: ([n/2]+1)*...*[3*n/4];
    f4=4th thread: ([3*n/4]+1)*...*n;
    f=f1*f2*f3*f4;
}else{
    f=1*...*n;
}

[sciko]

Например так.

[Crazy]

Если используешь OpenMP, то привязываешься к С, C++, Fortran.

[/dev/random]

Если используешь OpenMP, то привязываешься к С, C++, Fortran.

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

[drBatty]

Надо распаралелить функцию факториала на 4 потока.

ну я-бы создал список M операций, имея N потоков.

первый поток выполняет первую операцию N+1ю операцию, 2N+1ю и т.д.
второй 2ю, N+2, 2N+2 и т.д.

Первый и все остальные потоки пишут результат в тот-же список, потому если например потоков всего два, то второй поток в самом конце обработает Mнное число с M+1м (т.е. с результатом первого потока). Всё это завершается, когда в списке остаётся одно число.

Можно, конечно, проверять, если число делится на 4-ре, то 4-ре потока

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

[drBatty]

кстати, в этом случае (и во многих других) стоимость вычисления следующей операции (n[i+1] = n[i] - 1) сопоставима с самой операцией. Потому первый поток может добавлять 9000, 8999, 8998, 8997... в список, а все остальные - умножать числа. Когда первый процесс добавит N+1 чисел, он начинает запускать потоки умножения, по одному потоку на число, до тех пор, пока не запустит все N-1 потоков. Затем он добавит ост. числа, а потом ему будет достаточно дождаться завершения всех дочерних процессов.

[Grom]

Можно, конечно, проверять, если число делится на 4-ре, то 4-ре потока, если на 3-ри то на 3-ри потока, а все остальные случаи в два потока.

А если число нечётное? Тогда уж может брать S - остаток от деления на N - число потоков, вычитать его из R - исходного числа, параллелить (R-S) на N - потоков и результат умножать на произведение содержимого остатка S.

[drBatty]

Grom
ничего не понял

[Grom]

R - исходное число
N - число потоков /* агрумент функции MPI_Comm_size(MPI_COMM_WORLD, &N) */
S = R%N;
K = (R-S)/N; /* количество чисел в одном потоке */

В каждый поток отправляем два числа :
for( i=0 ; i<N ; i++ ) {
Send_to_Stream( i*K, (i+1)*K -1 );
}

Поток последовательно перемножает всё, что попадает в этот интервал.

Получаемые произведения перемножаем между собой и домножаем на произведение (R-S)*(R-S+1)*...*® . Примерно так. Конечно, алгоритм надо оптимизировать с учётом реалий. Например, если N - число потоков достаточно велико, то и остаток S может оказаться большим, В этом случае возможно, стоит распараллеливать задачу на N-1 потоков, а последний уже будет домножать между собой числа остатка и результаты вычислений других потоков по мере их готовности.

P.S. Так понятнее?

[drBatty]

R - исходное число
N - число потоков /* агрумент функции MPI_Comm_size(MPI_COMM_WORLD, &N) */
S = R%N;
K = (R-S)/N; /* количество чисел в одном потоке */

В каждый поток отправляем два числа :
for( i=0 ; i<N ; i++ ) {
Send_to_Stream( i*K, (i+1)*K -1 );
}

тоже самое, что и мой алгоритм. Только у вас зачем-то остаток и результаты вычисляются отдельно, а я всё вместе считаю. И вы сначала делите на группы, а потом считаете. Я одновременно и считаю и делю на группы. Мой алгоритм будет работать даже в том случае, если вдруг один из потоков надо освободить, либо по середине процесса появится свободный поток. В первом случае главному потоку просто надо раскидать необработанные данные другим потоком, а во втором можно просто необработанные данные отправлять не во все старые, но и в новый поток.

[drBatty]

т.е. у меня остаток S сам получается в конце вычислений, и прямо по мере вычисления этот остаток продолжает пихаться в потоки по очереди. При этом порядок вычисления не определён, и зависит от случайных причин. Но в случае факториала и вообще умножения это не играет никакой роли. На самом деле порядок будет самым быстрым, каким он только может быть - если мы умножаем на число из одних единиц, по одному биту, то это очень долго, и пока один из процессов трудится над этим сложным случаем, другие его не ждут, и множат лёгкие числа и результаты своей работы. У вас порядок жёсткий, и некоторые процессы будут простаивать, ожидая того, кто тормозит. Но за то у вас заданный порядок вычисления, что иногда очень важно (а иногда - нет).

[Grom]

Не то же самое. В вашем алгоритме:
1. Если число R нацело не делится на количество потоков, то нужно вставлять доплнительную проверку, чтобы x*N+y не выходило за пределы заданного числа. В моём варианте это не требуется, поскольку число приводится к виду, когда оно делится нацело.
2. В поток передаются не два граничных числа, а все: {1, N+1, 2N+1,...,xN+1} это дополнительные расходы.
3.

Когда первый процесс добавит N+1 чисел, он начинает запускать потоки умножения,

- ещё дополнительные накладные расходы. Во превых, пассивное ожидание, пока управляющий поток раскидает N чисел, во-вторых, ждут "запуска". В мойм варианте поток просто получает два числа и сразу начинает выполнять процедуру циклического умножения.
4.

Всё это завершается, когда в списке остаётся одно число.

Проверка на количество оставшихся чисел - дополнительные расходы.

[drBatty]

1. Если число R нацело не делится на количество потоков, то нужно вставлять доплнительную проверку, чтобы x*N+y не

не нужно. В списке просто не будет x*N+y. До этого места не дойдёт.

2. В поток передаются не два граничных числа, а все: {1, N+1, 2N+1,...,xN+1} это дополнительные расходы.

нет. если передать в поток диапазон, то сам дочерний процесс будет вынужден брать числа по одному. Нет разницы, кто берёт след. число. Если всё так просто как в этом случае, то главный процесс наоборот быстро всё раскидает, и встанет ждать остальные. Получим замедление. Если на практике так и будет, то главный процесс может ещё и себе числа кидать, и их множить (если заняться нечем).

- ещё дополнительные накладные расходы. Во превых, пассивное ожидание, пока управляющий поток раскидает N чисел

это только для первых N чисел (точнее 2*N ибо множить можно минимум пары). Если N сравнимо с M, то распараллеливать нет никакого смысла.

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

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

Проверка на количество оставшихся чисел - дополнительные расходы

эта проверка в вашем алгоритме в самом начале. У меня проще:
цикл продолжается пока
1) список НЕ пуст
И
2) какие-то процессы ещё работают.

п2 в явном виде не нужно проверять, для этого есть спец-средства.

ЗЫЖ вообще-то подразумевается, что операции занимают МНОГО времени, к примеру мы вычисляем ТОЧНО 100!. Тогда все ваши проверки будут занимать ничтожное время, по сравнению с умножением 100500 значных чисел (у вас хоть памяти для них хватит?)

[drBatty]

Grom
вообще в вашем варианте всё будет как минимум в 2 раза дольше. Первый процесс получит маленькие числа, и мгновенно и перемножит. И встанет. Последний будет работать дольше всех. Время выполнения умножения линейно зависит от логарифма числа, а логарифм растёт быстрее, чем функция обратная факториалу. (и намного). Потому основное время займёт вычисление "хвоста", которое по вашему методу не распараллелено. И распараллелить его не получится, ибо хвост маленький, а числа в нём большие. Но даже если хвоста нет, один из процессов будет работать на много порядков медленнее других, в итоге, через очень короткое время все процессы встанут, и будет работать только один из них.

[Grom]

Согласен, что в моём варианте первый поток будет считаться замтно быстрее, чем последний. Ну это вопрос оптимального выставления границ для деления списка чисел на потоки. Скажем, для вычисления (10^10)! при наличии порядка 200 нодов разница в счёте будет тоже напорядок отличаться, поэтому оптимизация будет заключаться во введении дополнительных множителей установки этих границ. При этом накладные расходы на обработка этих множителей (по сравнению с общим временем счёта) будут незаметны.

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

Нет разницы, кто берёт след. число.

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

п2 в явном виде не нужно проверять, для этого есть спец-средства.

То есть вы хотите сказать, что ожидание и проверка семафора занимает меньше времени, чем программное сравнение двух чисел?

P.S. Если я вас правильно понял, то вы предлагаете нечто вроде:

Код: Выделить всё

for( i=0 ; i<R ; i++) {
for( j=0 ; j<N ; j++) {
Send_to_pipe(j,i);
// j - номер нода
// i - передаваемое число
}
}

Вопрос, как будет организован сбор промежуточных данных с учётом:

А у меня поток получает свои ДВА числа, и их умножает. Затем поток записывает результат в общий список.

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

первый поток выполняет первую операцию N+1ю операцию, 2N+1ю и т.д.
второй 2ю, N+2, 2N+2 и т.д.

Первый и все остальные потоки пишут результат в тот-же список, потому если например потоков всего два, то второй поток в самом конце обработает Mнное число с M+1м (т.е. с результатом первого потока). Всё это завершается, когда в списке остаётся одно число.

[minoru-kun]

Позвольте мне прорекламировать язык для вычисления факториалов - Haskell

[Grom]

Чёрт! Топикстартер неплохо подколол Сейчас начал было экспериментировать со скоростями вычисления факториалов и сразу наткнулся на аппаратное ограничение задачи: 20! < 2^64 < 21! То бишь для манипулирования данными превышающими 64 разряда надо дополнительно поизвращаться. А распараллеливать вычисления факториала в пределах двух десятков не имеет смысла.

[Crazy]

Надо распаралелить функцию факториала на 4 потока.

ну я-бы создал список M операций, имея N потоков.

первый поток выполняет первую операцию N+1ю операцию, 2N+1ю и т.д.
второй 2ю, N+2, 2N+2 и т.д.

Первый и все остальные потоки пишут результат в тот-же список, потому если например потоков всего два, то второй поток в самом конце обработает Mнное число с M+1м (т.е. с результатом первого потока). Всё это завершается, когда в списке остаётся одно число.

Можно, конечно, проверять, если число делится на 4-ре, то 4-ре потока

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

Толсто, неоправданно сложно.

[Lan4]

Чёрт! Топикстартер неплохо подколол Сейчас начал было экспериментировать со скоростями вычисления факториалов и сразу наткнулся на аппаратное ограничение задачи: 20! < 2^64 < 21! То бишь для манипулирования данными превышающими 64 разряда надо дополнительно поизвращаться. А распараллеливать вычисления факториала в пределах двух десятков не имеет смысла.

Ну а фигли - длинная арифметика и все пучком)

[NickLion]

GMP и даёт длинную арифметку.

[BratSinot]

Вообщем постарались вы на славу! Думать будет над чем
А теперь, что лучше самому распаралелить или OpenMP использовать?

[sciko]

А теперь, что лучше самому распаралелить или OpenMP использовать?

Перефразирую вопрос: "Что лучше самому постоить велосипед или использовать готовый?"
Ответ очевиден: если цель понять как это работает -- свой велосипед, если что-то мешает использовать готовый -- свой велосипед, иначе -- готовый.

ЗЫ. Haskell -- тоже неплохой вариант, как и другие функциональные языки.

[eddy]

А как там у CUDA с "длинной арифметикой"? Потому что там распараллеливание вообще элементарно делается. А вот считать что-то очень большое мне никогда не приходилось...

[BratSinot]

Ответ очевиден: если цель понять как это работает -- свой велосипед, если что-то мешает использовать готовый -- свой велосипед, иначе -- готовый.

Готовый велосипед может быть большим и толстым конкретно в моей задаче, ежели я сам сделаю.

ЗЫ. Haskell -- тоже неплохой вариант, как и другие функциональные языки.

Я как-бы его не знаю.

[drBatty]

В своём алгоритме вы не учитываете задежки на передачу данных между процессами. В многопоточном программировании это - одно из самых узких мест

не в этом случае. львиная доля времени будет потрачена на умножения. А не на какие-то "передачи". Указатель на 100500-значные числа передать очень быстро.

P.S. Если я вас правильно понял, то вы предлагаете нечто вроде:
Код
for( i=0 ; i<R ; i++) {
for( j=0 ; j<N ; j++) {
Send_to_pipe(j,i);
// j - номер нода
// i - передаваемое число
}
}

нет. я предлагаю список, в котором будут числа. а процессы будут брать эти числа из списка, и вставлять туда результаты. числа будут громадными, потому время их обработки будет огромным, и всеми накладными расходами можно смело пренебречь. Ессно в списке будут указатели на числа, и процессы будут брать и отдавать указатели, ибо даже 100! не влезет ни в какие типы даных. Вот 100! == 93326215443944152681699238856266700490715968264381621468592963895217599993229915
608941463976156518286253697920827223758251185210916864000000000000000000000000
ы?

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

лениво. это вроде уже 100 раз описано в любом учебнике. Таким извратом ещё Кнут страдал, программируя свой элеватор. Организуется очередь, и сопрограммы ползают по этой очереди. Классика жанра...

Позвольте мне прорекламировать язык

где код?

[drBatty]

Сейчас начал было экспериментировать со скоростями вычисления факториалов и сразу наткнулся на аппаратное ограничение задачи: 20! < 2^64 < 21! То бишь для манипулирования данными превышающими 64 разряда надо дополнительно поизвращаться. А распараллеливать вычисления факториала в пределах двух десятков не имеет смысла.

ну наконец-то!
вот, получите, распишитесь:

Shell

$ bc bc 1.06.95 Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc. This is free software with ABSOLUTELY NO WARRANTY. For details type `warranty'. define f (x) { if (x <= 1) return (1); return (f(x-1) * x); } f(5) 120 f(50) 30414093201713378043612608166064768844377641568960512000000000000 f(100) 93326215443944152681699238856266700490715968264381621468592963895217\ 59999322991560894146397615651828625369792082722375825118521091686400\ 0000000000000000000000

(пример из мана)
теперь можете писать свои проги прямо в шелле :)

Толсто, неоправданно сложно.

нет там ничего сложного. я такое уже реализовывал.

А теперь, что лучше самому распаралелить или OpenMP использовать?

1) почитать учебник
2) сделать самому
3) перечитать учебник
4) выкинуть свой велосипед, и юзать OpenMP

Если начать с п4, получится быдлокод, который тупит... Примеров 100500.

Haskell -- тоже неплохой вариант, как и другие функциональные языки.

не думаю, что реализация длинной арифметики там будет более быстрой чем в C++.