Закон Амдала

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

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

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

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

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

Примітки

1. Amdahl, G. (April 1967) «The validity of the single processor approach to achieving large-scale computing capabilities». In Proceedings of AFIPS Spring Joint Computer Conference, Atlantic City, N.J., AFIPS Press, pp. 483-85.

Див. також

• Закон Брукса
• Закон Мура
• Закон Густафсона
• Правило дев'яносто на дев'яносто