Для параллельного алгоритма с N потоками может ли увеличение производительности быть больше, чем N?

Question

Теоретический вопрос, может быть, это очевидно:

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

Answer 1

Это не распространено, но это, безусловно, возможно .

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

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

Теоретически, вы можете сделать то же самое содин процессор, который просто имел огромный кэш.Однако с практической точки зрения выбор процессоров и размеров кеша довольно ограничен, поэтому, если вы хотите использовать больше кеша, вам нужно использовать больше процессоров - и способ, который большинство систем предоставляют для достижения этой цели:с несколькими потоками.

Answer 2

Да.

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

Answer 3

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

Ускорение = 1 / (1 / N)

где N - количество процессоров. Это, конечно, сводится только к N.