Закон Амдала

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

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

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

Де S — прискорення програми (як відношення до її початкового часу роботи), P — частка яку можна виконувати послідовно,а P-1 частина яка виконуєтся паралельно, {n} -кількість процесорів. Якщо послідовна частина програми виконується 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