параллельный расчет бесконечного ряда

Question

У меня просто быстрый вопрос о том, как ускорить вычисления бесконечных рядов.Это только один из примеров: arctan (x) = x - x ^ 3/3 + x ^ 5/5 - x ^ 7/7 + ....

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

Вы также можете предварительно сохранить X^ n так что для каждого следующего элемента вместо вычисления x ^ (n + 2) вы можете выполнить lastX * (x ^ 2)

Но в целом это, кажется, очень последовательная задача, и что вы можете сделать, чтобыиспользовать несколько процессоров (8 +) ??.

Большое спасибо!

РЕДАКТИРОВАТЬ: мне нужно будет рассчитать что-то от 100 000 до 1 м итераций.Это приложение на основе c ++, но я ищу абстрактное решение, поэтому оно не должно иметь значения.Спасибо за ответ.

Answer 1

Вам нужно разбить проблему так, чтобы она соответствовала количеству имеющихся у вас процессоров или потоков.В вашем случае у вас может быть, например, один процессор, работающий на нечетных терминах, а другой, работающий на нечетных.Вместо предварительного вычисления x ^ 2 и использования lastX * (x ^ 2), вы используете lastX * (x ^ 4), чтобы пропустить каждый второй термин.Чтобы использовать 8 процессоров, умножьте предыдущий термин на x ^ 16, чтобы пропустить 8 терминов.

PS В большинстве случаев, когда возникает такая проблема, стоит искать более эффективный способ вычисления результата.,Лучшие алгоритмы бьют большую мощность в большинстве случаев.

Answer 2

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

Обратите внимание, что вы можете выделять переменные различными способами;Например:

atan(x)= x - x^3/3 + x^5/5 - x^7/7 + x^9/9 ...
       = x*(1 - x^2*(1/3 - x^2*(1/5 - x^2*(1/7 - x^2*(1/9 ...

Хотя вторая строка более эффективна, чем наивная реализация первой строки, последний расчет все еще имеет линейную цепочку зависимостей от начала до конца.Вы можете улучшить свой параллелизм, комбинируя термины в парах:

       = x*(1-x^2/3) + x^3*(1/5-x^2/7) + x^5*(1/9 ...
       = x*( (1-x^2/3) + x^2*((1/5-x^2/7) + x^2*(1/9 ...
       = [yet more recursive computation...]

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

Answer 3

Что ж, для этого примера вы можете суммировать ряды (если у меня есть скобки в нужных местах):

(-1)^i * (x^(2i + 1))/(2i + 1)

Затем на процессоре 1 из 8 вычисляем сумму слагаемых для i = 1, 9, 17, 25, ...

Затем на процессоре 2 из 8 вычисляем сумму слагаемых для i = 2, 11, 18, 26, ...

и так далее, в итоге суммируем частичные суммы.

Или, вы можете сделать, как вы (почти) предлагаете, дать i = 1..16 (скажем) процессору 1, i = 17..32 для процессора 2 и т. Д., И они могут вычислить каждую последующую мощность х из предыдущего. Если вы хотите, чтобы в серии было более 8х16 элементов, то сначала назначьте больше для каждого процессора.

Я сомневаюсь, стоит ли вообще для этого примера распараллеливать, я подозреваю, что вы достигнете точности с двойной точностью на 1 процессоре, пока параллельные потоки все еще пробуждаются; но это всего лишь предположение для этого примера, и вы, вероятно, можете найти много серий, для которых распараллеливание стоит усилий.

И, как уже сказал @Mark Ransom, лучший алгоритм должен каждый раз превосходить грубую силу и множество процессоров.