Архитектура компьютерных сетей

Из  приведенных соотношений можно  показать, что в наилучшем случае S_p(n)=p и E_p(n)=1.

При внимательном рассмотрении можно обратить внимание, что попытки повышения качества параллельных вычислений по одному из показателей (ускорению или эффективности) может привести к ухудшению ситуации по другому показателю, ибо показатели качества параллельных вычислений являются противоречивыми. Так, например, повышение ускорения обычно может быть обеспечено за счет увеличения числа процессоров, что приводит, как правило, к падению эффективности. И, обратно, повышение эффективности достигается во многих случаях при уменьшении числа процессоров (в предельном случае идеальная эффективность E_p(n)=1легко обеспечивается при использовании одного процессора). Как результат, разработка методов параллельных вычислений часто предполагает выбор некоторого компромиссного варианта с учетом желаемых показателей ускорения и эффективности.  

При выборе надлежащего параллельного  способа решения задачи может  оказаться полезной оценка стоимости (cost) вычислений, определяемой как произведение времени параллельного решения задачи и числа используемых процессоров.

C_p=pT_p

В этой связи можно определить понятие стоимостно-оптимального (cost-optimal) параллельного алгоритма как метода, стоимость которого является пропорциональной времени выполнения наилучшего параллельного алгоритма. 

Закон Амдала 

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

S_p ≤1/(f+(1-f)/p) ≤S*=1/f

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

Данное  замечание характеризует одну из самых серьезных проблем в  области параллельного программирования (алгоритмов без определенной доли последовательных команд практически  не существует). Однако часто доля последовательных действий характеризует не возможность параллельного решения задач, а последовательные свойства применяемых алгоритмов. Как результат, доля последовательных вычислений может быть существенно снижена при выборе более подходящих для распараллеливания алгоритмов; 

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

Кроме этого, существует понятие «парадокса параллелизма» – достижение ускорения и эффективности параллельного алгоритма, превышающих значения 1/f и 1, соответственно. Говоря другими словами,  «парадокс параллелизма» - это более чем линейный рост производительности параллельной ВС с увеличением числа  её вычислителей.  

«Парадокс параллелизма» по сути не является таковым, а неравенства объясняются  следующими факторами:

1. эффектом памяти,
2. возможностью применения (априори параллельных) методов решения задач, реализация которых затруднительна на последовательной ЭВМ (например, снова из-за оперативной памяти, точнее ее ограниченного объема).

3. Системы с общей магистралью