Закон Амдаля гласит, что максимальное повышение производительности, которое может быть достигнуто за счет параллельной реализации алгоритма, ограничивается следующим соотношением
Макс. прирост производительности = 1 / (f + (1- f)/ p),
где f – доля операций, которые должны быть выполнены последовательно; p – количество процессоров.
Данный закон показывает, что увеличение производительности системы происходит не линейно с увеличением числа процессоров, причем с увеличением доли последовательных операций эта проблема обостряется (рис.6).
Рис. 6
Из закона Амдаля вытекают определения следующих понятий:
- повышение производительности = (наилучшее время решения задачи в однопроцессорное системе) / (наилучшее время решения задачи в многопроцессорной системе);
- эффективность = (повышение производительности) / (количество процессоров);
- стоимость = (количество процессоров) / (время выполнения задачи в многопроцессорной системе).
Коэффициент повышения производительности показывает увеличение быстродействия многопроцессорной системы по сравнению с однопроцессорной в единицах времен выполнения задачи. Эффективность позволяет оценить, какой процент вычислительных ресурсов многопроцессорной системы используется для выполнения параллельного алгоритма. Стоимость показывает суммарное время, затрачиваемое всеми процессорами на выполнение алгоритма.
Приведенные в табл. 1-4 данные иллюстрируют случай (задача вычисления суммы 8 элементов), когда увеличение количества процессоров не приводит к повышению производительности и ухудшает показатели системы.
Табл.1
Вычисление суммы при n=1
Такты | … | ||||
Процессор 1 | a+b | (a+b)+c | (a+b+c)+d | … | Результат |
Табл.2
Вычисление суммы при n=2
Такты | ||||
Процессор 1 | a+b | e+f | (a+b)+(e+f) | Результат |
Процессор 2 | c+d | g+h | (c+d)+(g+h) |
Табл.3
Вычисление суммы при n=3
Такты | ||||
Процессор 1 | a+b | g+h | (a+b)+(g+h) | Результат |
Процессор 2 | c+d | (c+d)+(e+f) | - - - - - | |
Процессор 2 | e+f | - - - - - | - - - - - |
Табл.4
Сравнительная оценка многопроцессорных систем при n=2 и n=3
Такты | Повышение производительности | Эффективность | Стоимость |
3 процессора | 7 / 4 = 1,75 | 1,75 / 3 = 0,58 | 3 * 4 = 12 |
2 процессора | 7 / 4 = 1,75 | 1,75 / 2 = 0,88 | 2 * 4 = 8 |