Паралелизиране на схемата Хорнер, Информационен и аналитичен център за паралелни изчисления
Постановка на проблема и същността на проблема
Класически пример за рекурсия в алгоритъм е схемата на Хорнер за изчисляване на частното на полином от 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(c)). В този случай имаме желаните коефициенти и остатъците се изчисляват по рекурсивната формула: 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 - не е необходимо).