Это очень простой исследовательский вопрос, который меня интересует. Есть ли некоторые примеры алгоритмов или просто какой-то код, который можно реализовать последовательно последовательно, но не поддерживает эффективную распараллеливание?Существуют ли некоторые алгоритмы, которые не поддерживают эффективную параллельную реализацию?
Уверены, что существует множество алгоритмов, которые просто не могут быть распараллелены из-за его последовательного характера. У вас есть несколько хороших примеров в криптографии.
Хорошими примерами являются алгоритм цепочки блоков шифрования (CBC), распространение цепочки блоков шифрования (PCBC), обратная связь с шифрованием и обратная связь с выходом. Посмотрите на страницу wikipedia о режимах блочного шифрования; для каждого режима есть небольшой прямоугольник в правом верхнем углу, говорящий о том, что процесс шифрования и дешифрования является параллелизуемым: http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation
В общем, любой алгоритм, на котором следующий шаг зависит от результата предыдущего шага, нельзя распараллелить, наименее эффективно. У вас всегда может быть много потоков, но это было бы не очень полезно, вам придется подождать, пока предыдущий шаг не закончится, прежде чем двигаться дальше, так что у вас никогда не будет истинного параллелизма.
Существует, конечно, несколько других примеров, криптография - это лишь один из них, и я мог сразу подумать.
Простой алгоритм смены двух чисел не может быть параллельным, на самом деле большинство базовых алгоритмов невозможно сделать параллельными. Следовательно, любой алгоритм, состоящий из последовательности зависимых шагов, сделанных из этих простых алгоритмов, не может быть параллельным.
Непоследовательность в этом рассуждении. Предположим, что алгоритм A "1. Обмен номерами A и B. 2. Обмен номерами C и D". Составлен базовый непараллельный алгоритм (ваш пример), но его можно легко распараллелить. – Voo
@Voo Алгоритм должен быть составлен из последовательности простого алгоритма здесь означает 2. должен зависеть от 1. например 1. swap (A, B) 2. swap (B, C). –
Да, это моя мысль: вы не можете распараллелить последовательность зависимых шагов, но вы, безусловно, можете распараллелить алгоритм, состоящий из нераспараллеливаемых частей. – Voo
Этот вопрос не соответствует теме, поскольку речь идет об алгоритмах вообще, а не о проблеме программирования. –
Неизвестно, является ли NC = P (т. Е. Может быть (или нет) некоторый алгоритм в P, который не находится в NC и, следовательно, неэффективно распараллеливается), если это то, что вы просите (что неясно). – harold