В идеале решение задачи на P процессорах должно выполняться в P раз быстрее, чем на одном процессоре, или/и должно позволить решить задачу с объемами данных, в P раз большими. На самом деле такое ускорение практически никогда не достигается. Причина этого хорошо иллюстрируется законом Амдала [12]:

(3.1)

где S - ускорение работы программы на P процессорах, а f - доля непараллельного кода в программе.

Эта формула справедлива и при программировании в модели общей памяти, и в модели передачи сообщений. Несколько разный смысл вкладывается в понятие доля непараллельного кода. Для SMP систем (модель общей памяти) эту долю образуют те операторы, которые выполняет только главная нить программы. Для MPP систем (механизм передачи сообщений) непараллельная часть кода образуется за счет операторов, выполнение которых дублируется всеми процессорами. Оценить эту величину из анализа текста программы практически невозможно. Такую оценку могут дать только реальные просчеты на различном числе процессоров. Из формулы (3.1) следует, что P-кратное ускорение может быть достигнуто, только когда доля непараллельного кода равна 0. Очевидно, что добиться этого практически невозможно. Очень наглядно действие закона Амдала демонстрирует таблица 3.1.

Из таблицы хорошо видно, что если, например, доля последовательного кода составляет 2%, то более чем 50-кратное ускорение в принципе получить невозможно. С другой стороны, по-видимому, нецелесообразно запускать такую программу на 2048 процессорах с тем, чтобы получить 49-кратное ускорение. Тем не менее, такая задача достаточно эффективно будет выполняться на 16 процессорах, а в некоторых случаях потеря 37% производительности при выполнении задачи на 32 процессорах может быть вполне приемлемой. В некотором смысле, закон Амдала устанавливает предельное число процессоров, на котором программа будет выполняться с приемлемой эффективностью в зависимости от доли непараллельного кода. Заметим, что эта формула не учитывает накладные расходы на обмены между процессорами, поэтому в реальной жизни ситуация может быть еще хуже.

Не следует забывать, что распараллеливание программы - это лишь одно из средств ускорения ее работы. Не меньший эффект, а иногда и больший, может дать оптимизация однопроцессорной программы. Чрезвычайную актуальность эта проблема приобрела в последнее время из-за большого разрыва в скорости работы кэш-памяти и основной памяти. К сожалению, зачастую этой проблеме не уделяется должного внимания. Это приводит к тому, что тратятся значительные усилия на распараллеливание заведомо неэффективных программ. Эту ситуацию достаточно наглядно проиллюстрирует следующий раздел.