Закон Амдала

Предположим, что по каким-либо причинам k операций из N некоторой программы необходимо выполнять последовательно, а (N – k) операций - параллельно. Причины могут быть разными. Например, операции могут быть последовательно связаны информационно, и тогда без изменения алгоритма их нельзя реализовать иначе. Но вполне возможно, что просто не распознан параллелизм, имеющийся в той части алго­ритма, которая описывается этими операциями. Отношение назовем долей последовательных вычислений, а - долей параллельных операций.

Утверждение.

Пусть система состоит из n одинаковых простых универсальных вычислительных модулей. Предположим, что при выполнении параллельной части алгоритма все n вычислительных модулей загружены полностью. Тогда максимально возможное ускорение равно

(2)

Докажем это утверждение.

Обозначим пиковую производительность отдельного i-го вычислительного модуля ВМi через Pi. Пиковая производительность системы

Если всего выполняется N операций, то среди них операций выполняет­ся последовательно и параллельно на n вычислительных модулях по операций на каждом. Не ограничивая общности, можно считать, что все последовательные операции выполняются на первом вычислительном модуле. Весь алгоритм реализуется за время

На параллельной части алгоритма работают как первый вычислительный модуль, так и все остальные вычислительные модули, тратя на это время

для . Поэтому и

Следовательно

Дата добавления: 2014-01-04