НОУ ІНТУІТ, Лекція, Паралельні алгоритми

Обчислення тригонометричних функцій

Ці ряди з'являються в багатьох додатках. Зокрема обчислення багатьох функцій засноване на використанні їх розкладання в ряд, що сходить. Розглянемо задачу обчислення значення безперервної функції, що диференціюється, використовуючи її розкладання в ряд Тейлора.

З програмістської точки зору завдання зводиться до обчислення нескінченної суми ряду, що сходить:

(3.5)

При побудові ефективного послідовного алгоритму, як правило, вдається побудувати рекурентну формулу, яка суттєво знижує трудомісткість обчислень

(3.6)

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

Як розпаралелити обчислення суми? Зрозуміло, що за наявності паралельно працюючих процесорів P, кожен з них може обчислювати свою частину суми:

(3.7)

Якщо під час підсумовування задавати N і вибирати його кратним P (N = k * P) , то кожен із процесорів може обчислювати k членів суми. Наприклад, перший процесор обчислюватиме суму перших k членів, другий - підсумовує наступну групу з k членів і так далі. Цей алгоритм розпаралелювання ми називаємо сегментним алгоритмом. Інший спосіб розпаралелювання обчислень, званий кроковим алгоритмом, полягає в тому, що процесори підсумовують члени ряду, віддалені один від одного на відстані P .

Послідовний алгоритм часто має безперечні переваги, які в тому, що у багатьох практично значущихЗавдання вдається побудувати просту рекурентну формулу для обчислення та просту формулу для обчислення початкового члена суми. Оскільки обчислення може вимагати складних обчислень, застосування простих рекурентних співвідношень дозволяє істотно збільшити ефективність послідовного алгоритму. При застосуванні сегментного алгоритму розпаралелювання вдається зберегти рекурентну формулу, що застосовується у послідовному алгоритмі. Однак для кожного процесора необхідно обчислити початкове значення і це суттєво знижує ефект, що отримується за рахунок розпаралелювання. Для крокового алгоритму початкові значення обчислюються не так складно, але рекурентна формула стає набагато складнішою. Це типова картина – розпаралелювання вимагає жертв – ускладнення алгоритму. В результаті може виявитися, що залучення додаткових процесорів може призводити не до зниження часу обчислень, а до його зростання. У подібних завдань може існувати оптимальне число процесорів p * після досягнення якого час обчислень почне зростати.

Наведемо приклад, який демонструє зазначені проблеми. Як функцію f(x) виберемо функцію ArcSin(x) , для якої справедливо наступне розкладання в ряд Тейлора:

(3.8)

Точне формулювання завдання ось у чому. Дано дійсне число x таке, що . Потрібно знайти із заданою точністю значення функції ArcSin(x) , що обчислюється як сума нескінченного ряду, що сходить (3.8). Неважко отримати такі співвідношення:

(3.9)

Послідовний алгоритм побудовано шаблоні, заданому алгоритмом 3.5. Відмінність полягає в тому, що додається аргумент x і поточний член обчислюється відповідно до рекурентної формули, заданої співвідношенням (3.9):

Кроковий алгоритм можна будувати з урахуванням шаблону, заданого алгоритмом 3.6. Потрібно лише коректно задати початкові значення та застосувати для обчислення загального члена рекурентну формулу, що зв'язує i-й та i+p-й члени ряду. Для функції Arcsin(x) ця формула має вигляд:

(3.10)

Ось код відповідного алгоритму:

Звичайно, формула (3.10) істотно складніша, ніж формула (3.9) для послідовного алгоритму. Це плата за розпаралелювання, яка може виявитися надмірною в ряді випадків. Результати чисельних експериментів для цієї конкретної функції будуть наведені в наступних розділах.

Для сегментного алгоритму рекурентне співвідношення дається формулою (3.9), як послідовного алгоритму. Але обчислення початкового значення для відповідного сегмента вимагатиме серйозних обчислювальних витрат порівняно з послідовним алгоритмом. Тому для завдань, подібних до обчислення функції ArcSin (x), використання p процесорів не дасть виграшу в часі в p разів. Не наводитиму код сегментного алгоритму, вважаючи, що він досить зрозумілий.

---