НОУ ІНТУЇТ | лекція | паралельні алгоритми

1. підсумовування Почнемо з найпростішої завдання - обчислення суми елементів масиву: Класичний алгоритм...

підсумовування

Почнемо з найпростішої завдання - обчислення суми елементів масиву:

Класичний алгоритм виглядає так:

S = 0; for (int i = 0; i <n; i ++) S = S + x [i]; Лістинг 3.1. Послідовний алгоритм обчислення суми елементів масиву

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

Оскільки в алгоритмі використовується тільки один цикл типу for з кроком, рівним одиниця, то алгоритм має лінійну тимчасову складність:

Коли підсумовування повинен виконувати тільки один процесор, то це оптимальний за часом алгоритм. Але підсумовування можна вести різними способами, якщо до обчислення суми залучити кілька процесорів. В "Паралельні обчислення" ми вже аналізували "пірамідальний" алгоритм підсумовування, що допускає розпаралелювання. Ось можлива запис такого алгоритму на С #:

int [] y = new int [n]; Array.Copy (x, y, n); int m = n; while (m! = 1) {for (int i = 0, j = m - 1; i <j; i ++, j--) y [i] = y [i] + y [j]; m = (m + 1) / 2; } S = y [0]; Лістинг 3.2. Пірамідальний алгоритм обчислення суми елементів масиву

У цьому більш складному варіанті алгоритму з'явилися два циклу. Внутрішній цикл for може бути распараллелен. Неважко бачити, що безлічі змінних, використовуваних на кожній ітерації цього циклу, взаємно не перетинаються. Виконання цієї умови достатньо для розпаралелювання. Зовнішній цикл while распараллелить не можна, оскільки ітерації "склеюються" загальною змінної m.

Для комп'ютера з одним процесором цей алгоритм буде гірше класичного алгоритму по ряду причин:

• Йому потрібна додаткова пам'ять, оскільки проміжні результати необхідно запам'ятовувати. Для цього введено масив y тієї ж розмірності, що і вихідний масив x.
• Алгоритм ускладнений, - замість одного циклу класичного алгоритму, вводяться два цикли. Алгоритм менш зрозумілий і налагодження його може викликати утруднення. Безсумнівно, що програмісту потрібно більше часу на розробку і налагодження такого алгоритму.
• Алгоритм при послідовному виконанні хоча і має ту ж тимчасову складність - O (n), але константа у нього більше, ніж у класичного алгоритму, оскільки у внутрішньому циклі використовуються три змінні з індексами, замість однієї, як у класичному алгоритмі.

У чому ж перевага цього алгоритму? Одне безперечне достоїнство у нього є - він допускає розпаралелювання. Якщо запускати його на ідеальному метакомпьютере з необмеженим числом процесорів, то тоді, використовуючи n / 2 процесорів, все обчислення внутрішнього циклу можна виконувати паралельно.

Складність внутрішнього циклу при розпаралелювання буде дорівнює O (1), а загальна складність визначається зовнішнім циклом і дорівнює O (log n). В "Паралельні обчислення" , Де цей алгоритм вже аналізувався, крім прискорення в розгляд вводилася і така характеристика алгоритму як ефективність. У пірамідального алгоритму ефективність низька, оскільки для досягнення максимального прискорення потрібно n / 2 процесорів - число, пропорційне розмірності масиву. Метакомпьютери і навіть суперкомп'ютери з великим числом процесорів не завжди під рукою, а й при їх наявності доводиться дбати про ефективність.

Давайте розглянемо алгоритми підсумовування, орієнтовані на кінцеве число процесорів - на багатоядерні комп'ютери. Нехай в нашому розпорядженні є комп'ютер з фіксованим числом процесорів - р. Як виконати підсумовування, використовуючи всі можливості такого комп'ютера? Природний алгоритм, що допускає розпаралелювання, зрозумілий, - потрібно провести розпаралелювання за даними, розбивши вихідний масив на р груп, приблизно рівній розмірності. Тоді можна паралельно виконати підсумовування для кожної групи, після чого підсумувати отримані результати. І в цьому випадку знадобиться додаткова пам'ять - масив розмірності р, який зберігає результати проміжних сум.

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

Ось варіант запису сегментного алгоритму, відповідного першої стратегії:

int count_p = Environment.ProcessorCount; int [] y = new int [count_p]; int m = n / count_p + 1; int start = 0, finish = 0; for (int k = 0; k <count_p; k ++) {start = k * m; finish = (k + 1) * m <n? (K + 1) * m: n; for (int i = start; i <finish; i ++) y [k] + = x [i]; } S = y [0]; for (int i = 1; i <count_p; i ++) S + = y [i]; Лістинг 3.3. Сегментний алгоритм обчислення суми p процесорами

Трохи простіше кроковий алгоритм, відповідний другій стратегії:

int [] y = new int [count_p]; for (int k = 0; k <count_p; k ++) {for (int i = k; i <n; i + = count_p) y [k] + = x [i]; } S = y [0]; for (int i = 1; i <count_p; i ++) S + = y [i]; Лістинг 3.4. Кроковий алгоритм обчислення суми p процесорами

Обидва ці варіанти допускають паралельне виконання тіла зовнішнього циклу. У цьому випадку складність алгоритму визначається складністю операторів, що складають тіло цього циклу, фактично, складністю внутрішнього циклу - O (n / count_p). Прискорення для обох варіантів одно count_p - числу процесорів, а ефективність дорівнює одиниці. Такі теоретичні оцінки. У наступних розділах подивимося, що можна отримати на практиці.

Завдання підсумовування вкрай важлива, оскільки зустрічається в самих різних додатках. Вона легко узагальнюється на випадок, коли підсумовуються не елемент масиву, а функції, що залежать від параметра i:

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

підсумовування рядів

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

Необхідною умовою збіжності ряду є прагнення до нуля, коли i прямує до нескінченності. У програмуванні це умова, на відміну від математики, є і достатньою умовою збіжності. У математиці це не так, - прикладом є розходиться гармонійний ряд із загальним членом ряду 1 / i. У світі комп'ютерів все дискретно, немає ірраціональності, немає нескінченності, обчислення не завжди точні і можуть мати деяку похибка. При знаходженні на комп'ютері суми гармонійного ряду, починаючи з деякого i *, значення загального члена стане рівним нулю (так званому машинному нулю) через обмеженість розрядної сітки, що відводиться для зберігання числа.

У програмуванні не ставиться завдання обчислення точного значення S у формулі (3.4), - досить обчислити це значення з деякою точністю. У порівнянні з кінцевими сумами додаткова складність в побудові алгоритму полягає в тому, що заздалегідь невідомо, як багато членів ряду необхідно обчислити, щоб знайти суму ряду з потрібною точністю. Класичний алгоритм заснований на тому, що підсумовування припиняється, як тільки черговий член суми стає по модулю менше заданої точності . При цьому передбачається, що виконується умова збіжності ряду, так що все що не враховуються члени ряду будуть по модулю є меншою ніж .

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

double eps = 1E-15; double i = 1; double a = 1; double S = 0; while (Math.Abs ​​(a)> eps) {// Обчислення загального члена ряду a = 1.0 / ((4 * i + 1) * (4 * i - 1)); // приклад S + = a; i ++; } Лістинг 3.5. Класичний алгоритм обчислення суми сходиться ряду

З програмістської точки зору алгоритми 3.1 і 3.5 багато в чому схожі. Різниця в тому, що в першому випадку використовується цикл for, по-другому - цикл while. Через це відмінності важче оцінити тимчасову складність алгоритму, оскільки немає такого природного параметра як n в алгоритмі 3.1 . Число підсумовування залежить як від формули, що задає загальний член ряду, так і від обраної точності обчислень - .

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

Повернемося до розгляду алгоритму 3.5 . За вже наведених причин він не допускає розпаралелювання. Але, як і для обчислення кінцевих сум, неважко побудувати допускає розпаралелювання версію, орієнтовану на p процесорів. Для кінцевих сум ми розглядали два варіанти - сегментний і кроковий алгоритм.

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

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

double i = 1; double a = 0; double [] y = new double [count_p]; for (int k = 0; k <count_p; k ++) {i = k + 1; a = 1.0 / ((4 * i + 1) * (4 * i - 1)); // початкове значення while (Math.Abs ​​(a)> eps) {y [k] + = a; i + = count_p; a = 1.0 / ((4 * i + 1) * (4 * i - 1)); }} S = y [0]; for (int k = 1; k <count_p; k ++) S + = y [k]; Лістинг 3.6. Кроковий алгоритм обчислення суми сходиться ряду p процесорами