Ускорение параллельных программ

Ускоре́ние паралле́льных програ́мм, критерий качества параллельных программ, отношение времени выполнения последовательной реализации ${\displaystyle T_{1}}$ ко времени выполнения параллельной программы с использованием ${\displaystyle p}$ процессов ${\displaystyle T_{p}:}$

${\displaystyle S={\frac {T_{1}}{T_{p}}}}$.

Если в качестве времени ${\displaystyle T_{1}}$ берётся наилучшая последовательная реализация, то иногда ускорение называют абсолютным, если же в качестве времени ${\displaystyle T_{1}}$ берётся время выполнения самой параллельной программы, запущенной с использованием одного процесса, то ускорение называют относительным.

Ускорение – величина безразмерная, большее её значение обычно соответствует лучшему качеству параллельной программы. Если ускорение ${\displaystyle S}$ близко к числу процессов ${\displaystyle p}$ (что соответствует незначительному количеству накладных расходов), говорят о линейном ускорении.

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

В отдельных случаях ускорение при использовании ${\displaystyle p}$ процессов может превосходить ${\displaystyle p}$, что соответствует суперлинейному, или сверхлинейному, ускорению программы (англ. super linear speedup). Чаще всего это объясняется более эффективным использованием иерархии памяти компьютера (в частности, кэш-памяти): чем больше процессов используется, тем больше общий объём высокоскоростной памяти доступен и тем меньше объём данных, приходящихся на каждый процесс. Это означает увеличение вероятности, что обращения к данным будут происходить в более быстрые области памяти, что и даёт дополнительное ускорение. На рисунке суперлинейному ускорению соответствует красная линия.