Розпаралелювання схеми Горнера, Інформаційно-аналітичний центр з паралельних обчислень
Постановка задачі та суть проблеми
Класичний приклад рекурсії в алгоритмі - схема Горнера для обчислення частки від розподілу многочлена n-го ступеня однієї змінної Pn(x) = a0x n + a1x n-1 + . + an-1x + a двочлен x - c, з отриманням многочлена n-1-го ступеня Qn-1(x) = b0x n-1 + b1x n-2 + . + bn-2x + bn-1 та залишку від розподілу bn (рівного Pn(с)). При цьому у нас шукані коефіцієнти та залишок обчислюються за рекурентною формулою: bi = c bi-1 + ai.
Здавалося б, нам нічого не вдієш із послідовним характером алгоритму. Однак у тому випадку, якщо нам можна скористатися асоціативністю та дистрибутивністю додавання та множення, то ми можемо розпаралелити схему Горнера, скориставшись звичайною схемою здвоювання.
Схема здвоювання
Нехай нам потрібно обчислити всі часткові суми елементів yi від 1 до k, де 1 ≤ k ≤ n. Виявляється, що це можливо зробити за схемою здвоювання приблизно за log2n кроків, виконуючи на кожному кроці приблизно n/2 додавань. Наведемо приклад обчислення всіх приватних сум для n=8 за 3 кроки.
Як бачимо, усі приватні суми обчислені. Зазначаємо про себе те, що
- ми скористалися асоціативністю додавання і що
- загальна кількість операцій зросла (чого не було б, якби нам була потрібна тільки повна сума, але не потрібні часткові).
Розпаралелювання схеми Горнера
Перепишемо схему Горнера у векторному формулюванні. Введемо послідовність векторів zi = (bi, 1) T . Тоді рекурентні формули схеми Горнера набудуть вигляду: zi = Aizi-1, де Ai - трикутна матриця виду ((c, 0) T , (ai, 1) T ). Після встановлення всіх формул ми бачимо,що zi = AiAi-1. A1z0, тобто нам потрібно вирахувати всі приватні матричні твори AiAi-1. A1 після чого помножити їх на вектор z0. Але матричне множення асоціативно, і до обчислень приватних творів ми можемо застосувати схему здвоювання, причому зі спрощеннями - адже
- нижні рядки матриць нам обчислювати не потрібно - всі вони рівні (0, 1);
- у верхньому рядку матриці перший елемент обчислюється за 1 множення (друге доданок дорівнює 0);
- другий елемент першого рядка обчислюється за 1 множення та 1 додавання (друге множення - на 1 - виконувати не потрібно).