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

Question

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

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

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

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

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

EDIT: Мне нужно будет вычислить что-то от итераций от 100k до 1m. Это приложение на основе C++, но я ищу абстрактное решение, поэтому это не имеет значения. Спасибо за ответ.

Answer 1

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

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

Answer 2

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

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

Затем на процессор-8 вычислить сумму условий для I = 1, 9, 17, 25, ...

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

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

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

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

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

Answer 3

Если вы пытаетесь вычислить значение 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...] 

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