Закон Амдала

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Графік залежності прискорення виконання програми залежно від числа процесорів при різних рівнях розпаралелювання програмного коду

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

де  — прискорення програми (як відношення до її початкового часу роботи);  — частка яку можна виконувати послідовно; — частина, яка виконується паралельно;   — кількість процесорів. Якщо послідовна частина програми виконується 10 % всього часу роботи, неможливо прискорити виконання такої програми більше ніж в 10 разів — незалежно від того, скільки процесорів використовує програма.

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

Примітки[ред.ред. код]

  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.
  2. Фред Брукс Міфічний людино-місяць. Розділ 2 — Міфічний людино-місяць. ISBN 0-201-83595-9

Див. також[ред.ред. код]