Какие алгоритмы нельзя распараллелить?

Есть ли какой-нибудь алгоритм, который очень трудно распараллелить, или исследование все еще активно?

Я хотел знать о любом алгоритме или любой области исследований в параллельных вычислениях.

Все, что я искал, имеет «параллельную» реализацию. Просто хочу изучить некоторые неизученные области параллельных вычислений.

algorithms parallel-computing Полиномиальный Протон
источник

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

Рафаэль

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

Полиномиальный протон

Ты не ответил на мой вопрос. Сколько процессоров вы разрешаете (5,

)? Какой тип ускорения и / или эффективности вам нужен (любое ускорение, линейное ускорение по числу процессоров, общее логарифмическое время)?

p

$p$

n

$n$

\infty

$\infty$

Рафаэль

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

Полиномиальный протон

связанные: stackoverflow.com/questions/18773937/…

Сиро Сантилли 新疆改造中心法轮功六四事件

Ответы:

это в основном открытая исследовательская проблема, относящаяся к вопросу NC =? P, где NC рассматривается как класс эффективно распараллеливаемых алгоритмов.

В влиятельном / широкомасштабном обзоре из Беркли «Пейзаж параллельных вычислений» есть классы алгоритмов или паттернов параллелизма, разделенных на «гномов». из первых 1 идентифицированных, похоже, что проблемы тел могут быть относительно трудными для эффективного распараллеливания при увеличении поскольку существует взаимодействий между всеми точками. $n$ $n$ $n^2$ $n$

позже они добавили 6 других в статье и предположили, что последний, называемый «FSM» (p14), где проблема связана с вычислением вычислений, подобных FSM (таких как е состояние FSM), может быть противоположностью «смущающе параллельного» чего-то они предлагают называть «смущающе последовательным». $n$

ВЗН
источник

Гениально, спасибо за ссылки и объяснения!

Полиномиальный протон

В этой статье представлен ряд проблем, которые легко решить последовательно, но трудно распараллелить: http://en.wikipedia.org/wiki/P-complete

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

Юкка Суомела
источник

Это предполагает теоретически сложное определение «параллелизуемости», которое может представлять интерес, а может и не представлять.

Рафаэль

@Raphael: AFAIK, многие классические P-полные задачи трудно распараллелить не только в теории, но и на практике (даже если у вас относительно небольшое количество процессоров).

Юкка Суомела

@JukkaSuomela Есть также случаи, когда теория сложности предполагает твердость, но на практике все работает хорошо. Кроме того, положительные результаты не имеют большого значения на практике .

Рафаэль

Можно добавить, что с теоретической точки зрения сложности не совсем ясно, существуют ли вообще «непарализуемые» проблемы , поскольку неизвестно, является ли

, как это делает vzn в своем ответ

N C = P

$\mathsf{NC} = \mathsf{P}$

Корнелиус Бранд

С практической точки зрения, вы спрашиваете о последовательных алгоритмах. Есть много кандидатов, таких как хэш-цепочка, которая, как полагают, очень трудно распараллелить. Hash-цепочка широко используется в криптографии. Например, схема хэширования паролей bcrypt была разработана, чтобы затруднить ускорение хеширования посредством распараллеливания. Другой пример - повторное возведение в квадрат (опять же, в криптографии).

DW
источник

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

Полиномиальный протон

@TheUknown Ссылки на эти документы приветствуются.

m33lky

@ m33lky Извините, у меня сейчас нет таких бумаг. Это было еще в январе, и я наконец продолжил свои исследования по другой теме. Тем не менее, вы можете посмотреть в Интернете на Google ученый, и я уверен, что вы получите много статей

Полиномиальный Протон

С практической точки зрения также стоит упомянуть, что если алгоритм, например, связан с памятью, то распараллеливание не очень поможет: stackoverflow.com/questions/868568/…

Сиро Сантилли,