Как уменьшить параллельную сложность результатов до постоянного количества ядер?

У меня были проблемы с принятием теоретического представления о сложности «эффективно решаемого параллельным алгоритмом», которое задается классом NC :

NC - это класс задач, которые могут быть решены параллельным алгоритмом за время на процессорах с .$O(\log^cn)$c , k ∈ $p(n) \in O(n^k)$$c,k \in \mathbb{N}$

Мы можем принять PRAM .

Моя проблема в том, что это, похоже, мало что говорит о «реальных» машинах, то есть машинах с конечным количеством процессоров. Теперь мне сказали, что «известно», что мы можем «эффективно» моделировать алгоритм процессора процессорах .p ∈ $O(n^k)$$p \in \mathbb{N}$

Что значит «эффективно» здесь? Это фольклор или строгая теорема, которая количественно определяет накладные расходы, вызванные симуляцией?

Я боюсь, что это происходит из-за того, что у меня есть проблема, которая имеет последовательный алгоритм , а также «эффективный» параллельный алгоритм, который при моделировании на процессорах также занимает время (которое это все, что можно ожидать на этом уровне детализации анализа, если последовательный алгоритм асимптотически оптимален). В этом случае, насколько мы можем видеть, ускорения не происходит; на самом деле, симулированный параллельный алгоритм может быть медленнее, чем последовательный алгоритм. То есть я действительно ищу утверждения более точные, чем границы (или объявление об отсутствии таких результатов).p O ( n k$O(n^k)$$p$$O(n^k)$$O$

Если вы предполагаете, что число процессоров ограничено константой, то вы правы, что проблема, связанная с NC, на практике не имеет большого значения. Поскольку любой алгоритм в PRAM с k процессорами и t параллельным временем может быть смоделирован с помощью однопроцессорного ОЗУ за время O ( kt ), параллельное время и последовательное время могут отличаться только на постоянный коэффициент, если k является константой.

Однако если вы предполагаете, что по мере увеличения размера ввода вы можете подготовить компьютер с большим количеством процессоров, то проблема с NC означает, что до тех пор, пока вы сможете подготовить больше процессоров, время выполнения будет «очень коротким» или, точнее, полилогарифмический во входном размере. Если вы считаете, что это предположение нереально, сравните его с предположением о неограниченной памяти: у реальных компьютеров есть только конечный объем пространства, но при изучении алгоритмов и сложности мы почти всегда предполагаем, что вычислительное устройство не имеет постоянного верхнего связаны в пространстве. На практике это означает, что мы можем подготовить компьютер с большим объемом памяти по мере увеличения размера ввода, как мы обычно используем компьютеры в реальном мире. NC моделирует аналогичную ситуацию в параллельных вычислениях.

$NC$

$p = 1$$NC$

Но подождите, это еще не все.

$NC$

$P$$O(n^\epsilon), 0 < \epsilon < 1$$NC$$n$$n$$\sqrt n < \lg^3 n$$n \leq 0.5 \times 10^9$$NC$

В одном из ответов было отмечено, что «на практике это означает, что мы можем подготовить компьютер с большим объемом памяти по мере увеличения размера ввода, как мы обычно используем компьютеры в реальном мире. NC моделирует аналогичную ситуацию в параллельные вычисления ".

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

$p$$n$$p$

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

$n^3$$n$