Теория и практика параллельных вычислений
Анализ масштабируемости параллельных вычислений
Целью применения параллельных вычислений во многих случаях является не только уменьшение времени выполнения расчетов, но и обеспечение возможности решения более сложных вариантов задач (таких постановок, решение которых не представляется возможным при использовании однопроцессорных вычислительных систем). Способность параллельного алгоритма эффективно использовать процессоры при повышении сложности вычислений является важной характеристикой выполняемых расчетов. Поэтому параллельный алгоритм называют масштабируемым (scalable), если при росте числа процессоров он обеспечивает увеличение ускорения при сохранении постоянного уровня эффективности использования процессоров. Возможный способ характеристики свойств масштабируемости состоит в следующем.
Оценим накладные расходы (total overhead), которые имеют место при выполнении параллельного алгоритма
T0=pTp–T1.
Накладные расходы появляются за счет необходимости организации взаимодействия процессоров, выполнения некоторых дополнительных действий, синхронизации параллельных вычислений и т.п. Используя введенное обозначение, можно получить новые выражения для времени параллельного решения задачи и соответствующего ускорения:
Применяя полученные соотношения, эффективность использования процессоров можно выразить как
Последнее выражение показывает, что если сложность решаемой задачи является фиксированной (T1=const), то при росте числа процессоров эффективность, как правило, будет убывать за счет роста накладных расходов T0. При фиксации числа процессоров эффективность их использования можно улучшить путем повышения сложности решаемой задачи T1 (предполагается, что при росте параметра сложности n накладные расходы T0 увеличиваются медленнее, чем объем вычислений T1). Как результат, при увеличении числа процессоров в большинстве случаев можно обеспечить определенный уровень эффективности при помощи соответствующего повышения сложности решаемых задач. Поэтому важной характеристикой параллельных вычислений становится соотношение необходимых темпов роста сложности расчетов и числа используемых процессоров.
Пусть E=const есть желаемый уровень эффективности выполняемых вычислений. Из выражения для эффективности можно получить
Порождаемую последним соотношением зависимость n=F(p) между сложностью решаемой задачи и числом процессоров обычно называют функцией изоэффективности (isoefficiency function) (см. [51]).
Покажем в качестве иллюстрации вывод функции изоэффективности для учебного примера суммирования числовых значений. В этом случае
и функция изоэффективности принимает вид
Как результат, например, при числе процессоров p=16 для обеспечения уровня эффективности E=0,5 (т.е. K=1) количество суммируемых значений должно быть не менее n=64. Или же, при увеличении числа процессоров с p до q (q>p) для обеспечения пропорционального роста ускорения (Sq/Sp)=(q/p) необходимо увеличить число суммируемых значений n в (qlog2q)/(plog2p) раз.
