Вопрос по algorithm – Быстрый алгоритм для вычисления Пи параллельно

20

Я начинаю изучать CUDA, и я думаю, что вычисление длинных цифр числа пи было бы хорошим, вводным проектом.

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

Но это, конечно, не самый быстрый алгоритм для вычисления константы. Раньше, когда я делал это упражнение на однопоточном процессоре, я использовалМашиноподобные формулы сделать расчет для гораздо более быстрой сходимости. Для тех, кто заинтересован, это включает в себя выражение pi в виде суммы арктангенсов и использование рядов Тейлора для оценки выражения.

Пример такой формулы:

enter image description here

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

Так что мне интересно,what is the most efficient way to calculate arbitrarily long digits of pi on a GPU?

Я не думаю, что кто-то делает вычисления произвольной точности. tskuzzy
Erlang? Я думаю, что вы могли бы использовать его для параллельной обработки. Не уверен, поможет ли это в реализации алгоритма. Code Droid
Смотрите также:stackoverflow.com/questions/19/fastest-way-to-get-value-of-pi а такжеstackoverflow.com/questions/14283270/… assylias
Вы смотрели на это:sites.google.com/a/nirmauni.ac.in/cudacodes/ongoing-projects/… James Black
@JamesBlack: код, на который вы ссылаетесь, - полная ерунда. Кажется, это невероятно наивный автоматический перевод последовательного фрагмента кода C в последовательный фрагмент кода графического процессора, где многие потоки вычисляют идентичные первые 1000 элементов расширения серии. Буквально 99,99% вычислений, выполняемых кодом, являются избыточными. talonmies

Ваш Ответ

1   ответ
14

Вы должны использоватьBailey & # x2013; Borwein & # x2013; формула Плуфф

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

Кроме того, предпочтительно, чтобы каждый процессор манипулировал значениями малой точности, а не значениями очень высокой точности. Например, если вы хотите один миллиард десятичных знаков, и вы используете некоторые из используемых выраженийВот, словноЧудновский алгоритмкаждый ваш процессор должен будет манипулировать миллиардами длинных чисел. Это просто не подходящий метод для графического процессора.

Итак, в целом, формула BBP позволит вам вычислять цифры числа Пи отдельно (алгоритм очень крутой) и с «низкой точностью». Процессоры! Прочитайте "алгоритм извлечения цифр BBP для & # x3C0;"

Advantages of the BBP algorithm for computing π This algorithm computes π without requiring custom data types having thousands or even millions of digits. The method calculates the nth digit without calculating the first n − 1 digits, and can use small, efficient data types. The algorithm is the fastest way to compute the nth digit (or a few digits in a neighborhood of the nth), but π-computing algorithms using large data types remain faster when the goal is to compute all the digits from 1 to n.

Имейте в виду, что BBP не дает десятичных цифр, только двоичный.
Ну, это "прилично" алгоритм. Он не самый лучший (записи ведутся по другим алгоритмам), но он все еще приличный. И давайте также помним, что ОП не желает побивать рекорды, ноI am starting to learn CUDA and I think calculating long digits of pi would be a nice, introductory project.
Тогда это хорошая схема, чтобы попробовать. (Я видел людей, пытающихся создавать параллельные программы на Python, который является интерпретатором. А что?)
Так что я понимаю идею, что вы вычисляете все цифры, которые вы хотите в (смущающем) параллели. Но это не гарантия того, что этот алгоритмefficient; каждый процессор / графический процессор может быть вычислительной информацией, которой могут поделиться другие. Возможно, этот алгоритм эффективен, и вы просто не сказали нам, как это сделать. Но если нет, вы не хотите распараллеливать неэффективный алгоритм только потому, что можете. (Возможно, более полезной мерой были бы цифры / транзистор или произведенные цифры / ватт).

Похожие вопросы