Версия нотации Big-O, которая включает параллелизм?

Question

Этот вопрос требует некоторой настройки.

http://igoro.com/archive/big-oh-in-the-parallel-world/

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

У меня следующий вопрос: почему эта запись не используется чаще?

В самом описании метода дано одно объяснение: «Чтобы умножить две матрицы 100 × 100, нам нужномашина с 10000 процессоров ".Похоже, эта цитата предполагает, что 10 000 процессоров совершенно неоправданно ожидаются.

Мое опровержение:

https://en.wikipedia.org/wiki/Manycore_processor

Самый большой суперкомпьютер в мире сейчасТайху Лайт, содержит в общей сложности 40960 * 256 = 10485760 ядер.У всех нас нет доступа к суперкомпьютерам, таким как Taihu Light, но облачные вычисления постоянно набирают популярность, и я не вижу причин, по которым 10000 ядерных процессоров и выше не будут широко доступны для использования в ближайшем будущем.Кроме того, средний GPU уже имеет 1000 ядер.Они более специализированы, чем ядра ЦП, но это не главное.

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

Скажем, у нас идеально сбалансированное дерево с коэффициентом ветвления b.Все узлы, кроме одного, содержат логическое значение false, а последний содержит логическое значение true.Мы хотим найти и вернуть этот истинный узел.

Используя поиск в ширину, среда выполнения Big-O для поиска истинного узла будет O (| V | + | E |) == O (b^ d), где b - коэффициент ветвления, а d - глубина дерева.

Однако, если мы предположим, что у нас бесконечно много единиц обработки, каждая с конечными возможностями обработки, запись больших денег будетследующим образом: $ O (b ^ d -> d).Это говорит о том, что на 1 процессоре алгоритм будет занимать O (b ^ d) времени, но по мере увеличения числа процессоров сложность времени приближается к d, глубине дерева.Это потому, что в каждом ложном узле мы можем порождать b больше процессов для поиска каждого из этих узлов b дочерних.Поскольку у нас бесконечные ядра, все эти процессы могут работать параллельно.Вот почему я называю это нотацией больших денег.Сложность времени уменьшается с увеличением вычислительной мощности, вычислительная мощность возрастает, когда вы тратите больше денег на Amazon / Microsoft / Google / YourFavoriteCloudProvider.

Я еще раз повторю свой вопрос.Почему обозначение, подобное этому, не видит более широкого использования?Спасибо!

Answer 1

Класс сложности NC имеет дело с проблемами, которые могут быть эффективно решены в параллельной настройке. Насколько я знаю, люди, работающие с параллельными алгоритмами, используют традиционные обозначения O (.) и используют выражения типа «алгоритмы ЧПУ», поэтому, когда вы читаете их статьи и видите предложения вроде:

«Мы даем алгоритм O (xxx) NC для НЕКОТОРЫХ ПРОБЛЕМ.»

Вы должны интерпретировать это как:

"Мы даем параллельный алгоритм для SOMEPROBLEM, который решает его за время O (xxx), используя O (yyy) процессоры."

(где xxx и yyy изменяются, конечно).

Я не помню, чтобы видел что-то похожее на ваши обозначения, но я не уверен, что это принесет на стол. Классы сложности часто разделяются в соответствии с некоторым параметром и / или некоторым показателем роста этого параметра (например, у нас есть доступ к O (1) процессорам или O (log n) процессоры, или ...) чтобы классифицировать проблемы с такой степенью точности, которой, по-видимому, не хватает вашей записи, если я правильно ее интерпретирую.