Закон Амдала

Закон Амдала визначає потенційне прискорення алгоритму при збільшенні числа процесорів. Він вперше був сформульований Джином Амдалем у 1967 році^[1]. Закон стверджує, що невелика частина програми, що не піддається розпаралелюванню, обмежить загальне прискорення від розпаралелювання. Будь-яка велика математична чи інженерна задача зазвичай буде складатись з кількох частин, що можуть виконуватись паралельно, та кількох частин що виконуються тільки послідовно. Цей зв'язок задається рівнянням:

${\displaystyle S={\frac {1}{p+{\frac {1-p}{n}}}}}$

Графік залежності прискорення виконання програми залежно від числа процесорів при різних рівнях розпаралелювання програмного коду

де ${\displaystyle S}$ — прискорення програми (як відношення до її початкового часу роботи); ${\displaystyle p}$ — частина яку можна виконувати послідовно; ${\displaystyle 1-p}$ — частина, яка виконується паралельно; ${\displaystyle {n}}$  — кількість процесорів. Якщо послідовна частина програми виконується 10 % всього часу роботи, неможливо прискорити виконання такої програми більше ніж в 10 разів — незалежно від того, скільки процесорів використовує програма.

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