Закон Амдала гласит, что максимальное ускорение вычислений, при которых доля S вычислений должна быть выполняется последовательно, переход от 1-процессорной системы к N-процессорной системе составляет не более
1 / (S + [(1 - S) / N])
Кто-нибудь знает книги или заметки, где выполняется фактический анализ кода для некоторых нетривиальных вычислений для определения дроби S?
Закон Амдала очень хорошо обсуждается в книге Microsoft Patterns and Practices по Параллельное программирование с .NET.
Провести детальный анализ кода будет довольно сложно - каждая ситуация уникальна.
Однако это должно быть что-то, что можно легко аппроксимировать, если у вас есть механизмы для определения степени параллелизма. Изменив используемый параллелизм и профилирование, вы сможете оценить S, решив уравнение в обратном порядке.
Вот несколько ссылок, которые могут вам помочь:
Исследования Microsoft | Обсуждение закона Амдала в эпоху многоядерности
Оценка и анализ законов Амадала (и Густафсона)
Аннотация по оценке множителей скорости | Кратко обсуждает закон Амдала
Надеюсь, они вам помогут.
Используемый принцип не является уникальным для распараллеливания. Если 25% времени программы тратится на выполнение какой-либо конкретной операции, выполнение всего, кроме этих 25%, мгновенно (без влияния на 25%) оставит программу, которая заняла 25% исходного времени и, таким образом, была в четыре раза быстрее.
В случаях, когда алгоритм имеет четкие фазы, которые можно или нельзя распараллеливать, применение приведенной выше формулы будет простым - представьте, что N-стороннее распараллеливание заставит части, которые можно распараллелить, работать в N раз быстрее, а части, которые не выполняются. t parallelizable будет работать с нормальной скоростью. На практике я не думаю, что большинство алгоритмов полностью состоят из частей, которые либо на 100% распараллеливаются, либо на 100% последовательны. В наиболее интересных случаях алгоритмы могут работать в основном параллельно, но имеют различные ограничения порядка; в некоторых случаях точные ограничения порядка могут зависеть от данных. Таким образом, «процент распараллеливания» может варьироваться в зависимости от количества процессоров, среди прочего, и поэтому попытка включить его в формулу не будет очень полезной.
