Какое самое быстрое время выполнения модульного умножения больших целых чисел на нескольких процессорах?

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

Я знаю, что время выполнения известных в настоящее время алгоритмов умножения целых чисел примерно ограничено по нижней границе o(n * log n). Моему исследованию не удалось выяснить, относится ли это к одноядерной или многоядерной машине. Однако я думаю, что это для одноядерной машины, поскольку алгоритмы, похоже, используют подход «разделяй и властвуй».

Теперь мой вопрос: какова известная в настоящее время нижняя граница временной сложности алгоритма параллельного целочисленного умножения, реализованного на m ядрах? Можно ли достичь временной сложности с нижней границей o(n) или меньше при достаточном количестве ядер? (т.е. если m зависит от n?) Здесь o(n) описывает входной размер имеющихся целых чисел.

До сих пор в своем исследовании я прочитал несколько статей, в которых утверждалось, что ускорение происходит с помощью параллельного умножения БПФ. К сожалению, они заявляют только об эмпирическом ускорении (например, «улучшение скорости на 56% при использовании 6 ядер на таком-то компьютере»), а затем не могут объяснить теоретическое ускорение, выраженное в пределах временной сложности.

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

Обновление №1: пользователь @delnan связался с вики-страницей о Класс сложности ЧПУ. На этой вики-странице упоминается, что целочисленное умножение выполняется в NC, что означает, что существует O((log n)^c) алгоритм на O(n^k) процессорах. Это помогает приблизиться к ответу. На данный момент без ответа остается вопрос: каковы константы c и k для целочисленного умножения и какой параллельный алгоритм подходит для этой цели?

Обновление №2: согласно странице 12 из 15 в этот PDF-файл из курса компьютерных наук в Корнельском университете, целочисленное умножение в классе сложности ЧПУ занимает O(log n) времени на O(n^2) процессорах. Он также объясняет пример алгоритма того, как это сделать. Я скоро напишу правильный ответ на этот вопрос.

Последний вопрос, удовлетворяющий мое любопытство: может ли кто-нибудь что-нибудь знать о известной в настоящее время временной сложности для «только» O(n), O(sqrt(n)) или O(log n) процессоров?


algorithm math multiplication time-complexity modular-arithmetic
person webdevelopersdiary    schedule 01.10.2014    source источник
comment
Возможно, вам повезет больше в информатике, а если это не удастся, Теоретическая информатика (мне сложно судить о степени вопроса, на который я не могу ответить).   -  person    schedule 01.10.2014
comment
Для процессоров O (n): похоже, я не могу найти подходящую цитату, но я сильно ожидаю, что существует метод на основе БПФ со временем работы O (полилог n), поскольку БПФ, естественно, параллельно до n процессоров . Такой метод сократится до меньшего количества процессоров.   -  person David Eisenstat    schedule 02.10.2014
comment
Спасибо @DavidEisenstat. Вы правы, поскольку БПФ - это алгоритм «разделяй и властвуй», его можно запустить за полилогарифмическое время. параллельно. В случае алгоритма O(n * log n) БПФ это становится O(log n) временем на O(n) процессорах (см. Страницы 5-6 в этот PDF). Я не уверен, как это влияет на все известные в настоящее время алгоритмы умножения, но можно с уверенностью сказать, что те, которые используют БПФ, будут придерживаться известной в настоящее время нижней границы БПФ.   -  person webdevelopersdiary    schedule 02.10.2014

Ответы (1)


arrow_upward
1
arrow_downward

Распараллеливание не влияет на вычислительную сложность алгоритмов.

Обязательно возьмите такую ​​задачу, как умножение целых чисел, и вы сможете найти множество алгоритмов для ее решения. Эти алгоритмы будут иметь ряд сложностей. Но с учетом любого алгоритма, работающего на p процессорах, это в лучшем случае теоретически даст ускорение в p раз. С точки зрения вычислительной сложности это похоже на умножение существующей сложности, назовите ее O(f(n)) на константу, чтобы получить O((1/p)*f(n)). Как вы знаете, умножение сложности на константу не влияет на классификацию сложности.

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

Опять же, имейте в виду, что вычислительная сложность - это очень теоретическая мера вычислительных усилий, обычно измеряемая как количество каких-то базовых операций, необходимых для вычисления для данного размера входных данных. Одной из таких основных операций может быть умножение двух чисел (ограниченного размера). Изменение определения базовой операции на умножение двух векторов чисел (каждый ограниченного размера) не изменит сложности алгоритмов.

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

person High Performance Mark    schedule 01.10.2014
comment
См. суперлинейное ускорение - person Sam Harwell; 01.10.2014
comment
@ 280Z28, Марк говорит, что сложность алгоритма измеряется не во времени, а в количестве базовой операции. Ускорение может быть, но в итоге количество операций, выполняемых процессорами, останется прежним. - person Rerito; 01.10.2014
comment
-1 Вы предполагаете, что p является постоянным, но OP также спрашивает о случаях, когда количество процессоров зависит от размера ввода. Это серьезно изучается в компьютерных науках, и то, что вы описываете, является всего лишь самым основным приложением теории сложности, которое вошло в курсы компьютерной грамотности для бакалавриата. См., Например, NC. Кроме того, упор на измерение времени по сравнению с измерением основных операций является безумным, для постоянного числа процессоров это эквивалентно, а в других моделях время, размер или глубина схемы или некоторые другие меры могут быть более полезными. - person ; 01.10.2014
comment
Спасибо за эту ссылку на NC, @delnan. На этой вики-странице упоминается целочисленное умножение в NC, что означает, что существует алгоритм O ((log n) ^ c) на процессорах O (n ^ k). Остается неизвестным, каковы константы c и k для целочисленного умножения и какой параллельный алгоритм подходит для этой цели? Обновлю вопрос. - person webdevelopersdiary; 01.10.2014