25 вересня 2007 р.

Закон Амдала

Умови Закону Амдала

1. Продуктивність комп'ютерних систем, яка складається із зв'язаних між собою пристроїв в загальному випадку визначається як найбільш непродуктивна.

2. Нехай комп'ютерна система створена із S однакових простих універсальних пристроїв. Нехай припустимо, що при виконанні паралельної частини алгоритму всі S пристроїв завантажені повністю. Тоді максимально можливе прискорення
де – коефіцієнт, тобто частка послідовних обчислень.
Припустимо, що з якихось причин n операцій виконано послідовно, N - загальна кількість операцій.

3. Нехай система створена із простих однакових універсальних пристроїв, при будь-якому режимі роботи її прискорення не може перебільшувати зворотньої величини частки послідовних обчислень.

Якщо послідовно виконуються m операцій, то число ярусів будь-якої паралельної форми алгоритму, не може бути менше n.

В дослідженнях по закону Амдала не конкретизується зміст операцій. В загальному випадку вони можуть бути як елементарними так і дуже складними, і являють собою алгоритм розв’язку достатньо складних задач.

Формулювання закону Амдала не враховує тимчасових витрат на забезпечення обміну інформацією між обчислювальними вузлами.

Наслідок із закону Амдала: для того, щоб прискорити виконання програми в q разів необхідно прискорити не менше, ніж в q разів не менше, ніж (1-1/q) -у частину програми.

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

Закон Амдала деякою мірою допомагає відчути складність паралельного програмування: наприклад, для прискорення виконання програми в 100 разів, необхідно, щоб 99,99% операцій в програмі можливо було б виконувати з 100-кратним розпаралеленням.