Пределы параллелизма (вопрос о собеседовании)

Проблема заключалась бы в распределении работы и сборе результатов.

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

Однако собрать результаты было бы непросто. Каждый ЦП может сравнивать со своим (числовым) соседом, а затем этот результат сравнивать с результатом двух ближайших соседей и т. Д. Это будет процесс O (log (n!)). Я не знаю наверняка, но подозреваю, что O (log (n!)) Является гиперполиномиальным, поэтому я не думаю, что это решение.

Нет, N! даже выше NP. Мысль о неограниченном параллелизме может решить проблему NP за полиномиальное время, которое обычно считается «разумной» временной сложностью, N! проблема все же выше полинома на такой установке.

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

Однако установка - это нечто важное, что нужно игнорировать.

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

Это все равно, что спросить, может ли бесконечное число обезьян, печатающих на компьютере с текстовым процессором, устойчивым к уничтожению обезьян, придумать все произведения Шекспира; учитывая бесконечное количество времени. Реалист скажет, что нет, поскольку эти условия физически невозможны. Идеалист скажет: да, теоретически это может произойти. Поскольку программная инженерия (именно программная инженерия, а не информатика) фокусируется на реальных системах, которые мы можем увидеть и потрогать, то ответ - нет. Если вы сомневаетесь во мне, тогда идите и докажите, что я не прав! ИМХО.

Иногда правильный ответ: «Сколько раз это встречается в вашей кодовой базе?» но в этом случае есть реальный ответ.

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

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

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

Поскольку мы доказали, что можем заставить некоторое количество этих бесконечно быстрых, бесконечно многочисленных процессоров ждать (даже если они ждут сами себя), мы знаем, что время выполнения не может быть O (1), и нам нужно только выберите очень большое значение N, чтобы гарантировать «неприемлемое» время выполнения.

Если проблема заключается в проверке перестановок / ответов на задачу сложности O (n!), То, конечно, вы можете эффективно сделать это с бесконечным числом процессоров.

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

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

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

Edit: Исправлено мое сообщение в соответствии с комментариями ниже.

Похоже, что на самом деле вы спрашиваете, может ли проблема сложности O(n!) быть сведена к O(n^a) на недетерминированной машине; другими словами, является ли Not-P = NP. Ответ на этот вопрос - нет, есть некоторые проблемы Not-P, которые не являются NP. Например, ограниченная проблема остановки (спрашивается, останавливается ли программа не более чем за n! шагов).

Вы упомянули поиск как "типичную" задачу, но на самом деле вас спрашивали именно о задаче поиска? Если да, то да, поиск обычно распараллеливается, но, насколько я могу судить, O(n!) в принципе не подразумевает доступную степень параллелизма, не так ли? У вас может быть совершенно серийная задача O(n!), а это значит, что бесконечные компьютеры не помогут. Однажды у меня была необычная проблема O(n^4), которая на самом деле была полностью последовательной.

Итак, доступный параллелизм - это первое, и IMHO вы должны получить очки за упоминание закона Амдала в интервью. Следующий потенциальный подводный камень - межпроцессорное взаимодействие и вообще характер алгоритма. Рассмотрим, например, этот список классов приложений: http://view.eecs.berkeley.edu/wiki/Dwarf_Mine. FWIW код O(n^4), который я упоминал ранее, вроде как попадает в категорию FSM.

Еще один несколько связанный с этим анекдот: Я слышал, как инженер из компании-поставщика суперкомпьютеров утверждал, что если 10% процессорного времени тратится на библиотеки MPI, то они считают распараллеливание солидным успехом (хотя, возможно, это касалось только кодов в области вычислительной химии).