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

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

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

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

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

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

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


c++ multithreading series infinite
person kirbo    schedule 07.10.2010    source источник
comment
Надеюсь, у вас бесконечные процессоры...   -  person Mark Ransom    schedule 08.10.2010
comment
Сколько терминов вы планируете рассчитать, чтобы их можно было разделить по ядрам? Я бы подумал, что было бы более эффективно, если бы каждое ядро ​​вычисляло разные значения x (при условии, что вы хотите оценить выражение для более чем одного значения).   -  person Oliver Charlesworth    schedule 08.10.2010
comment
Насколько конечен ваш бесконечный ряд?   -  person EboMike    schedule 08.10.2010
comment
Кстати, почему это помечено как C++?   -  person Oliver Charlesworth    schedule 08.10.2010
comment
На что обратить внимание: Радиус сходимости — ваш ряд для арктангенса сходится только для -1‹x‹1 или что-то в этом роде, хотя арктангенс определен для всех x. Вам нужно будет использовать идентификатор или другое расширение, чтобы выйти за пределы этого диапазона. Чтобы увидеть, насколько это сложно, см. mathworld.wolfram.com/InverseTangent.html.   -  person Michael Anderson    schedule 08.10.2010

Ответы (3)


arrow_upward
7
arrow_downward

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

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

person Mark Ransom    schedule 07.10.2010

arrow_upward
2
arrow_downward

Если вы пытаетесь вычислить значение числа пи в миллионах разрядов или что-то в этом роде, вам сначала нужно уделить пристальное внимание выбору ряда, который быстро сходится и поддается распараллеливанию. Затем, если у вас достаточно цифр, в конечном итоге станет рентабельным разделить их на несколько процессоров; вам придется найти или написать библиотеку 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...]

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

person comingstorm    schedule 07.10.2010

arrow_upward
1
arrow_downward

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

(-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 и так далее, и они могут вычислить каждую последующую степень x из Предыдущая. Если вы хотите, чтобы в серии было больше 8x16 элементов, то в первую очередь назначьте больше каждому процессору.

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

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

person High Performance Mark    schedule 07.10.2010