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