Пределы для параллельных вычислений

Мне интересно в широком смысле то, что известно о распараллеливании алгоритмов в P. Я нашел следующую статью в Википедии на эту тему:

http://en.wikipedia.org/wiki/NC_%28complexity%29

Статья содержит следующее предложение:

Неизвестно, является ли NC = P, но большинство исследователей подозревают, что это неверно, а это означает, что, вероятно, существуют некоторые проблемы, которые можно решить, которые являются «по своей сути последовательными» и не могут быть значительно ускорены при использовании параллелизма.

Это звучит разумно? Известны ли случаи, когда проблема в P не может быть ускорена с помощью параллелизма?

Даже неизвестно, является ли NC = P, но P-полные проблемы, по-видимому, трудно распараллелить. К ним относятся линейное программирование и Horn-SAT. (Напротив, проблемы в NC кажутся довольно легко распараллеливаемыми.)

См. Вопрос Проблемы между NC и P: сколько было решено из этого списка? для справочного материала (включая ссылки на классический учебник, который теперь доступен для бесплатной загрузки), а также дальнейшее обсуждение проблем, которые в P, но не известны, чтобы быть распараллеливаемыми.

См. Вопрос Обобщенная теорема Ладнера для структуры классов сложности между NC и P. Вкратце, если они различаются, то существует бесконечно много классов сложности строго между NC и P.

Смотрите вопрос NC = P последствия? для хорошей демонстрации Райаном Уильямсом, что можно усилить коллапсы в иерархии классов сложности в P в, возможно, более маловероятные коллапсы, такие как PSPACE = EXP .

Стоит отметить, что одно из следствий того, что Horn-SAT является P-complete, и ссылки выше, это то, что кажется невозможным распараллелить общие запросы SQL в базах данных, если мы не можем также переписать какие-либо крупномасштабные вычисления для использования только разумный объем хранения. Это загадочное несоответствие - я думаю , что это вполне непротиворечивое в состояние существует ограничения на сжатии , но я часто вижу статьи , которые , кажется , построенные на предположении , что можно распараллелить любой запрос к базе данных.

Ну, если бы были известные случаи, то мы бы смогли разделить P и NC. Но есть много проблем, о которых известно, что они P-полные (т. Е. При сокращении логарифмического пространства), и они представляют тот же тип барьеров для отображения P = NC, что и проблемы с NP-полными для P = NP. Среди них линейное программирование и сопоставление (и максимальные потоки в целом).

Кетан Малмулей доказал результат, разделяющий P и слабую форму NC (без битовых операций) еще в 1994 году. В некотором смысле, его текущая программа для P vs NP взлетает с того места, где она остановилась ( очень свободно ).

В книге « Ограничения параллельных вычислений » об этом больше сказано.

Я ответил на аналогичный вопрос. Существуют ли какие-либо известные проблемы / алгоритмы в научных вычислениях, которые нельзя ускорить распараллеливанием на сайте Computational Science . Позвольте мне привести это здесь, потому что это предлагает практический взгляд на конкретный случай такой проблемы:

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

Проблема с уравнением Эйконала состоит в том, что поток информации зависит от самого решения. Грубо говоря, информация течет вдоль характеристик (то есть световых лучей в оптике), но характеристики зависят от самого решения. И поток информации для дискретизированного уравнения Эйконала еще хуже, требующий дополнительных приближений (например, неявно присутствующих в методах быстрого свипирования), если требуется какое-либо параллельное ускорение.

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

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