6.1. Закон Амдала. Возможности ускорения и эффективность параллельной обработки.
Ускорение и эффективность Ускорение параллельного алгоритма Sp определяется следующим образом:
где T0 - время работы наилучшего последовательного алгоритма, T1 - время работы параллельного алгоритма на одном процессоре, Tp - время работы параллельного алгоритма на p процессорах. Следует отметить, что в общем случае T0В общем случае редко удается полностью распараллелить вычислительный процесс и получить максимальное ускорение в p раз. Ни один параллельный алгоритм не может обеспечить идеальную балансировку нагрузки процессоров, т.е. в равной степени разделить вычислительную работу между процессорами. Эффективность Ep параллельного алгоритма характеризует степень загрузки процессоров и определяется как отношение ускорения Sp к максимально возможному ускорению p:
Закон Амдала Пусть есть некая доля вычислений, которые выполняются в параллельном режиме, а доля - в последовательном без совмещения этих режимов во времени. Тогда последовательные вычисления занимают время и параллельные -- время и Оба режима занимают время Тогда формулы для ускорения Sp и эффективности Ep принимают вид:
Формула выражает простую и обладающую большой общностью зависимость, известную как закон Амдала. Согласно этому закону в алгоритме, имеющем два не совмещенных во времени режима последовательных и параллельных вычислений, при границу ускорения составляет величина, обратная доле последовательных вычислений:
Для повышения скорости вычислений за счет распараллеливания требуется повышать скорость параллельных вычислений, однако остающиеся последовательные вычисления все в большей степени тормозят ускорение в целом. Даже небольшая доля последовательных вычислений может сильно снизить общую скорость. Особенно сильное влияние на ускорение и эффективность алгоритма последовательные вычисления оказывают в области . Поэтому в алгоритмах с большим объемом параллельных вычислений заметным является уменьшение последовательных вычислений даже на 1% от общего объема вычислений. Закон Амдаля представляет собой приближенную модель ускорения, т.к. не учитывает так называемые накладные расходы и зависимость от p. Однако в общем случае доля параллельных вычислений может меняться с изменением числа используемых процессоров (проблема масштабируемости).
|