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

Ответ 1

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

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

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

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

Ответ 2

Да.

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

Ответ 3

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

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

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