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

Оценка эффективности параллельных алгоритмов включает показатели ускорения (speedup) и эффективности (efficiency). Ускорение показывает, насколько быстрее выполняется задача при использовании параллельного алгоритма по сравнению с последовательным вариантом, а эффективность определяет долю времени, в течение которого процессоры реально задействованы для решения задачи.

При оценке эффективности параллельных алгоритмов следует учитывать такие моменты:

• Сверхлинейное ускорение (superlinear speedup) возникает, когда ускорение превышает число процессоров. Это может быть связано с неодинаковостью условий выполнения последовательной и параллельной программ или нелинейным характером зависимости сложности решения задачи от объёма обрабатываемых данных.
• Показатели качества параллельных вычислений часто противоречат друг другу: повышение ускорения обычно достигается за счёт увеличения числа процессоров, но это приводит к падению эффективности. Повышение эффективности достигается при уменьшении числа процессоров.
• Разработка методов параллельных вычислений предполагает выбор компромиссного варианта с учётом желаемых показателей ускорения и эффективности.

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