Оценка эффективности параллельных вычислений

непроизводительность есть грех перед Святым Духом.
О. Хаксли

масштабируемости параллельного алгоритма

по сравнению с последовательным вариантом выполнения вычислений:

n – параметр вычислительной

сложности решаемой задачи (например, количество входных данных задачи)

качестве T1 берется время выполнения наилучшего последовательного алгоритма.
Величину ускорения

называют относительной, если в качестве T1 берется время выполнения параллельного алгоритма на одном процессоре.

имеет место при Sp=p.
Сверхлинейное (superlinear) ускорение имеет место при Sp>p.
Неравноправность

выполнения последовательной и параллельной программ (например, недостаток оперативной памяти).
Нелинейный характер зависимости сложности решения задачи от объема обрабатываемых данных.
Различие вычислительных схем последовательного и параллельного методов.

течение которого процессоры реально используются для решения задачи.
_

попытки повышения качества параллельных вычислений по одному из показателей может

привести к ухудшению качества по другому показателю.

стоимость которого является пропорциональной времени выполнения наилучшего последовательного алгоритма.

и Ep=1 для эффективности может быть обеспечено не для всех

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

последовательным алгоритмом в предположении, что размер задачи остается постоянным.
Пусть

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

Джин Амдал
(р. 1922)

доски) – 1 мин. РАСПАРАЛЛЕЛИВАЕТСЯ
Уборка – 30 мин. НЕ распараллеливается


доски) – 1 мин. РАСПАРАЛЛЕЛИВАЕТСЯ
Уборка – 30 мин. НЕ распараллеливается


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

части программы независимы, что не совсем верно.
Как правило, задача с

фиксированным объемом данных не запускается на различном количестве процессоров (за исключением академических исследований), а объем данных изменяется в соответствии с количеством процессоров.
Вместо вопроса об ускорении на p процессорах рассмотрим вопрос о замедлении вычислений при переходе на один процессор.

Дж. Густафсон
(р. 1955)

части программы независимы, что не совсем верно.
Как правило, задача с

фиксированным объемом данных не запускается на различном количестве процессоров (за исключением академических исследований), а объем данных изменяется в соответствии с количеством процессоров.
Вместо вопроса об ускорении на p процессорах рассмотрим вопрос о замедлении вычислений при переходе на один процессор.

Дж. Густафсон
(р. 1955)

объема решаемой задачи приводит к увеличению доли параллельной части, т.к.

последовательная часть не изменяется.

процессоров он обеспечивает увеличение ускорения при сохранении постоянного уровня эффективности

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

росте числа процессоров эффективность, как правило, будет убывать за счет

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

Тогда


Данную зависимость n=F(p) между сложностью решаемой задачи и числом процессоров

называют функцией изоэффективности (isoefficiency function).

масштабируемости параллельного алгоритма