Анализ масштабируемости параллельных вычислений.

Целью применения параллельных вычислений во многих случаях является не только уменьшение времени выполнения расчетов, но и обеспечение возможности решения более сложных вариантов решаемых задач (таких постановок, решение которых не представляется возможным при использовании однопроцессорных вычислительных систем). Способность параллельного алгоритма эффективно использовать процессоры при повышении сложности вычислений является важной характеристикой выполняемых расчетов. В связи с этим параллельный алгоритм называют масштабируемым (scalable), если при росте числа процессоров он обеспечивает увеличение ускорения при сохранении постоянного уровня эффективности использования процессоров.

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

Используя введенные обозначения, соотношения для времени параллельного решения задачи и соответствующего ускорения можно представить в виде:

,

Соответственно эффективность использования s процессоров:

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

Если число процессоров фиксировано, эффективность их использования, как правило, растет при повышении времени (сложности) решаемой задачи . Связано это с тем, что при росте сложности задачи накладные расходы обычно растут медленнее, чем объем вычислений . Для характеристики свойства сохранения эффективности при увеличении числа процессоров и повышении сложности решаемых задач строят так называемую функцию изоэффективности. Рассмотрим схему ее построения.

Пусть задан желаемый уровень эффективности выполняемых вычислений: =const.

Из выражения для эффективности можно записать так : или

, где K=

Из последнего равенства видно, что эффективность характеризуется коэффициентом K. Следовательно, если построить функцию вида N = F(K, s) , то для заданного фиксированного уровня эффективности K каждому числу процессоров s можно поставить в соответствие требуемый уровень сложности –N и наоборот. При рассмотрении конкретных вычислительных алгоритмов построение функции изоэффективности позволяет выявить пути совершенствования параллельных алгоритмов.

Для построения этих функций удобно использовать закон Густавсона –Барсиса. Эффективность использования s процессоров в соответствии с этим законом выражается в виде : .

При заданном фиксированном = const с использованием этого равенства можно построить аналитическое соотношение для функции изоэффективности в следующем виде: g = F( , s). Такая форма может оказаться более удобной в случае, когда известна доля времени на проведение последовательных расчетов в выполняемых параллельных вычислениях.

Верхняя граница времени выполнения параллельного алгоритма.

Для любого количества используемых процессоров – s справедлива следующая верхняя оценка для времени выполнения параллельного алгоритма:

Действительно, пусть есть расписание для достижения минимально возможного времени выполнения . Для каждой итерации τ, 0<τ<T∞ выполнения расписания обозначим через количество операций, выполняемых в ходе итерации τ. Расписание выполнения алгоритма с использованием s процессоров может быть построено следующим образом. Выполнение алгоритма разделим на шагов; на каждом шаге τ следует выполнить все операций, которые выполнялись на итерации τ расписания . Эти операции могут быть выполнены не более чем за ] /s[ итераций при использовании s процессоров. Как результат, время выполнения алгоритма Ts может быть оценено следующим образом: + ,

где ]* [– означает операцию округления до целого числа в сторону увеличения.

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