ланс завантаження процесорів. Між точками синхронізації кожен з процесорів повинен бути завантажений однаковим обсягом роботи, інакше частина процесорів буде очікувати, поки решта завершать свої операції. Ця ситуація відома як дисбаланс завантаження. Таким чином, прискорення обмежується найбільш повільним з процесорів. p> - Комунікаційні витрати. Якщо прийняти, що обмін інформацією та обчислення можуть перекриватися, то будь-які комунікації між процесорами знижують прискорення. У плані комунікаційних витрат важливий рівень гранулярності, що визначає об'єм обчислювальної роботи, виконуваної між комунікаційними фазами алгоритму. Для зменшення комунікаційних витрат вигідніше, щоб обчислювальні гранули були досить великими, і частка комунікацій була менша.
Ще одним показником паралельних обчислень служить якість паралельного виконання програм - характеристика, об'єднуюча прискорення, ефективність і надмірність. Якість визначається наступним чином:
В
Оскільки як ефективність, так і величина, зворотна надмірності, являють собою дроби, то Q (n) S (n). Оскільки Е (n) - це завжди дріб, a R (n)-число між 1 і n, якість Q (n) при будь-яких умовах обмежено зверху величиною прискорення S (n) [4].
В
7.2 Закон Амдала
В ідеальному випадку система з n процесорів могла б прискорити обчислення в n разів. У реальності досягти такого показника з ряду причин не вдається. Головна з цих причин полягає в неможливості повного розпаралелювання жодної з завдань. Як правило, в кожній програмі є фрагмент коду, який принципово повинен виконуватися послідовно і тільки одним з процесорів. Це може бути частина програми, що відповідає за запуск завдання та розподілення розпаралелених коду по процесорах, або фрагмент програми, що забезпечує операції введення/виводу. Можна навести й інші приклади, але головне полягає в тому, що про повне розпаралелюванні завдання говорити не доводиться. Відомі проблеми виникають і з тією частиною завдання, яка піддається розпаралелюванню. Тут ідеальним був би варіант, коли паралельні гілки програми постійно завантажували б всі процесори системи, причому так, щоб навантаження на кожен процесор була однакова. На жаль, обидві ці умови на практиці важко реалізувати. Таким чином, орієнтуючись на паралельну ВС, необхідно чітко усвідомлювати, що добитися прямо пропорційного числу процесорів збільшення продуктивності не вдасться, та, природно, постає питання про те, на яке реальне прискорення можна розраховувати. Відповідь на це питання в якійсь мірі дає закон Амдала.
Джин Амдал (Gene Amdahl) - один з розробників всесвітньо відомої системи IBM 360, у своїй роботі, опублікованій в 1967 році, запропонував формулу, відображатиме залежність прискорення обчислень, що досягається на багатопроцесорної Нд, від числа процесорів і співвідношення між послідовної і паралельної частинами програми. Показником скорочення часу обчислень служить така метрика, як В«прискоренняВ». Нагадаємо, що прискорення S-це відношення часу Ts, що витрачається на проведення обчислень на однопроцесорній НД (у варіанті найкращого послідовного алгоритму), до часу Тр рішення тієї ж задачі на паралельній системі (при використанні найкращого паралельного алгоритму):
В
Застереження щодо алгоритмів рішення завдання зроблені, щоб підкреслити той факт, що для послідовного і паралельного рішення кращими можуть виявитися різні реалізації, а при оцінці прискорення необхідно виходити саме з найкращих алгоритмів.
Проблема розглядалася Амдалом в наступній постановці (малюнок 7.1). Передусім обсяг розв'язуваної задачі з зміною кількості процесорів, які беруть участь у її вирішенні, залишається незмінним. Програмний код розв'язуваної задачі складається з двох частин: послідовною та распараллелівать. Позначимо частку операцій, які повинні виконуватися послідовно одним з процесорів, через f, де 0f1 (тут частка розуміється не по числу рядків коду, а за кількістю реально виконуваних операцій). Звідси доля, яка припадає на распараллелівать частина програми, становитиме 1-f. Крайні випадки в значеннях f відповідають повністю паралельним (f = 0) і повністю послідовним (f = 1) програмам. Распараллелівать частина програми рівномірно розподіляється по всіх процесорам.
З урахуванням наведеної формулювання маємо:
В
В результаті отримуємо формулу Амдала, виражає прискорення, яке може бути досягнуто на системі з n процесорів:
В
Формула виражає просту і що володіє великий спільністю залежність. Характер залежності прискорення від числа процесорів і частки послідовної частині програми зображений на малюнку 7.2.
Якщо спрямувати число процесорів до нескінченності, то в межі отримуємо:
В
Це означає, що якщо в програмі 10% послідовних операцій (тобто f = 0,1), то, скільки б процесорів ні використовувалося, прискорення роботи програми більш ніж у десять раз ніяк ні отримати, та й то, 10 - це теоретична верхня оцінка самого кращого випадку, ко...
