Page 34 - 6571

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

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

бути вирішені тільки за допомогою послідовних обчислень, а, ві-
дповідно, відсоток підзадач 1 p- може бути ідеально розпарале-
лений (тобто час обчислення буде обернено пропорційним числу

задіяних процесорів n). Тоді прискорення, яке може бути отрима-
не на обчислювальній системі з n процесорів, у порівнянні з од-

нопроцесорним рішенням не буде перевищувати величини:
1
S = ,
n 1 p-
p +
n
де S – зростання продуктивності програми (як відношення до її
n
початкового часу роботи).
Якщо послідовна частина програми виконується 10% всього

часу роботи, то її виконання неможливо прискорити більш ніж в
10 разів, незалежно від того скільки процесорів буде задіяно. Це
визначає верхню межу корисності від збільшення кількості обчи-

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

цим займаються».

4.3 Програмні підходи до розробки паралельних програм

Паралельне програмування представляє додаткові джерела

складності – необхідно явно керувати роботою тисяч процесорів
та координувати мільйони міжпроцесорних взаємодій. Для вирі-
шення задачі на паралельному комп’ютері, необхідно розподіли-
ти обчислення між процесорами системи так, щоб кожен проце-

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

33