Теоретический вопрос, может быть, это очевидно:
Возможно ли, что алгоритм, реализованный параллельно с N потоками, будет выполняться более чем в N раз быстрее, чем исходный однопоточный алгоритм? Другими словами, может ли коэффициент усиления быть более линейным с количеством потоков?
Это не распространено, но это, безусловно, возможно.
Рассмотрим, например, создание конвейера программного обеспечения, где каждый шаг в конвейере выполняет довольно небольшой объем вычислений, но требует достаточного количества статических данных, чтобы приблизительно заполнить весь кеш данных, но каждый шаг использует разные статические данные.
В таком случае последовательный расчет на одном процессоре обычно будет ограничен главным образом полосой пропускания для основной памяти. Предполагая, что у вас есть (по крайней мере) столько процессоров/ядер (каждый со своим кэшем данных) в качестве этапов конвейера, вы можете загружать каждый кеш данных один раз и обрабатывать один пакет данных за другим, сохраняя одни и те же статические данные для всех них, Теперь ваш расчет может продолжаться со скоростью процессора, а не ограничиваться пропускной способностью до основной памяти, поэтому улучшение скорости может быть в 10 раз больше, чем количество потоков.
Теоретически, вы могли бы сделать то же самое с одним процессором, у которого был действительно огромный кеш. С практической точки зрения, однако, выбор процессоров и размеров кеша довольно ограничен, поэтому, если вы хотите использовать больше кеша, вам нужно использовать больше процессоров - и способ, которым большинство систем обеспечивает выполнение этого, состоит из нескольких потоков.
Да.
Я видел алгоритм для перемещения руки робота через сложные маневры, которые в основном делятся на N потоков, и каждый поток перемещается более или менее случайным образом через пространство решений. (Это был не практический алгоритм.) Статистика ясно показала суперлинейное ускорение по одному потоку. По-видимому, вероятность столкновения решения с течением времени росла довольно быстро, а затем выровнялась, поэтому преимущество заключалось в том, что у него было много начальных попыток.
Закон Амдаля (распараллеливание) говорит, что это невозможно для общего случая. В лучшем случае мы можем отлично разделить работу на N. Причина этого заключается в том, что без последовательной порции формула Амдаля для ускорения становится:
Ускорение = 1/(1/N)
где N - количество процессоров. Это, конечно, сводится только к N.