Прискорення і ефективність паралельного алгоритму

Прискоренням паралельного алгоритму називається відношення:

(4)

де — час обчислення завдання на p процесорах. Зауважимо, що у визначенні мають на увазі справжній час обчислень. Це робить визначення більш корисним на практиці, але ускладнює його використання в тому випадку, якщо необхідний час виконання алгоритму невідомий. Для ідеальної обчислювальної системи і ідеальної паралельної реалізації алгоритму його прискорення дорівнює середньому ступеню паралелізму.

З прискоренням пов'язана ефективність паралельного алгоритму.

Ефективністю паралельного алгоритму називається величина:

(5)

По визначенню, . Теоретично має бути і . Якщо алгоритм досягає максимального прискорення (), то . На практиці зменшується при збільшенні числа процесорів.

Іноді бувають випадки, коли («суперлінійне прискорення»). Ця аномалія викликана, частіше за все, двома причинами:

• Як послідовний алгоритм був застосований не найшвидший алгоритм з доступних.
• Зі збільшенням кількості обчислювачів зростає сумарний обсяг їх оперативної і кеш пам'яті. Тому все більша частина даних завдання уміщається в оперативній пам'яті і не вимагає підкачки з диска, або (найчастіше) уміщається в кеші. У таких випадках для точного вимірювання ефективності реалізованого алгоритму слід зменшувати об'єм кеш пам'яті кожного обчислювача обернено пропорційно числу обчислювачів.