Шаг 13.
Параллельные алгоритмы. Моделирование и анализ параллельных вычислений. Оценка максимально достижимого параллелизма

    На этом шаге мы приведем несколько оценок максимально достижимого параллелизма.

    Оценка качества параллельных вычислений предполагает знание наилучших (максимально достижимых) значений показателей ускорения и эффективности, однако получение идеальных величин S_p=p для ускорения и E_p=1 для эффективности может быть обеспечено не для всех вычислительно трудоемких задач. Рассмотрим еще ряд закономерностей, которые могут быть чрезвычайно полезны при построении оценок максимально достижимого параллелизма.

1. Закон Амдаля. Достижению максимального ускорения может препятствовать существование в выполняемых вычислениях последовательных расчетов, которые не могут быть распараллелены. Пусть f есть доля последовательных вычислений в применяемом алгоритме обработки данных, тогда в соответствии с законом Амдаля ускорение процесса вычислений при использовании p процессоров ограничивается величиной

   

       Так, например, при наличии всего 10% последовательных команд в выполняемых вычислениях эффект использования параллелизма не может превышать 10-кратного ускорения обработки данных.

       Закон Амдаля характеризует одну из самых серьезных проблем в области параллельного программирования - алгоритмов без определенной доли последовательных команд практически не существует. Однако часто доля последовательных действий характеризует не возможность параллельного решения задач, а последовательные свойства применяемых алгоритмов. Поэтому доля последовательных вычислений может быть существенно снижена при выборе более подходящих для распараллеливания методов.

       Следует отметить также, что рассмотрение закона Амдаля происходит в предположении, что доля последовательных расчетов f является постоянной величиной и не зависит от параметра n, определяющего вычислительную сложность решаемой задачи. Однако для большого ряда задач доля f=f(n) является убывающей функцией от n, и в этом случае ускорение для фиксированного числа процессоров может быть увеличено за счет увеличения вычислительной сложности решаемой задачи. Данное замечание может быть сформулировано как утверждение, что ускорение S_p=S_p(n) является возрастающей функцией от параметра n (данное утверждение часто именуется эффект Амдаля).

2. Закон Густавсона-Барсиса. Оценим максимально достижимое ускорение исходя из имеющейся доли последовательных расчетов в выполняемых параллельных вычислениях:

   

   где и есть времена последовательной и параллельной частей выполняемых вычислений соответственно, т.е.

   

       С учетом введенной величины g можно получить

   

   что позволяет построить оценку для ускорения

   ,

   которая после упрощения приводится к виду закона Густавсона-Барсиса:

   S_p = g+(1-g)p = p+(1-p)g.

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

    На следующем шаге мы рассмотрим некоторые компоненты анализа масштабируемости параллельных вычислений.

Предыдущий шаг Содержание Следующий шаг