Распараллеливание схемы Горнера

• Постановка задачи и суть проблемы
• Схема сдваивания
• Распараллеливание схемы Горнера
  

Постановка задачи и суть проблемы

Классический пример рекурсии в алгоритме - схема Горнера для вычисления частного от деления многочлена n-й степени одной переменной P_n(x) = a₀xⁿ + a₁x^n-1 + ... + a_n-1x + a на двучлен x - c, с получением многочлена n-1-й степени Q_n-1(x) = b₀x^n-1 + b₁x^n-2 + ... + b_n-2x + b_n-1 и остатка от деления b_n (равного P_n(с)). При этом у нас искомые коэффициенты и остаток вычисляются по рекуррентной формуле: b_i = c b_i-1 + a_i.

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

Схема сдваивания

Пусть нам нужно вычислить все частичные суммы элементов y_i от 1 до k, где 1 ≤ k ≤ n. Оказывается, что это возможно сделать по схеме сдваивания примерно за log₂n шагов, выполняя на каждом шаге примерно по n/2 сложений. Приведём пример вычисления всех частных сумм для n=8 за 3 шага.

1-й шаг: вычисляем y₁ + y₂, y₃ + y₄, y₅ + y₆, y₇ + y₈.
2-й шаг: вычисляем (y₁ + y₂) + y₃ , (y₁ + y₂) + (y₃ + y₄), (y₅ + y₆) + y₇, (y₅ + y₆) + (y₇ + y₈).
3-й шаг: вычисляем (y₁ + y₂ + y₃ + y₄) + y₅, (y₁ + y₂ + y₃ + y₄) + (y₅ + y₆), (y₁ + y₂ + y₃ + y₄) + (y₅ + y₆ + y₇), (y₁ + y₂ + y₃ + y₄) + (y₅ + y₆ + y₇ + y₈)

Как видим, все частные суммы вычислены. Отмечаем про себя то, что

• мы воспользовались ассоциативностью сложения и что
• общее количество операций возросло (чего не было бы, если б нам была нужна только полная сумма, но не нужны частичные).

Теперь рассмотрим, как применить схему сдваивания к схеме Горнера.

Распараллеливание схемы Горнера

Перепишем схему Горнера в векторной формулировке. Введём последовательность векторов z_i = ( b_i, 1)^T. Тогда рекуррентные формулы схемы Горнера примут вид: z_i = A_iz_i-1, где A_i - треугольная матрица вида ( (c, 0)^T, (a_i, 1)^T). После подстановки всех формул мы видим, что z_i = A_iA_i-1...A₁z₀, то есть нам нужно вычислить все частные матричные произведения A_iA_i-1...A₁, после чего умножить их на вектор z₀. Но матричное умножение ассоциативно, и к вычислениям частных произведений мы можем применить схему сдваивания, причём с упрощениями - ведь

• нижние строки матриц нам вычислять не нужно - они все равны (0, 1);
• в верхней строке матрицы первый элемент вычисляется за 1 умножение (второе слагаемое равно 0);
• второй элемент первой строки вычисляется за 1 умножение и 1 сложение (второе умножение - на 1 - выполнять не нужно).

Вычисления векторов z_i на последнем этапе тоже можно выполнять не полностью (потому что 1 не нужно вычислять), и, кроме этого, независимо друг от друга. Они тоже займут всего по 1 умножению и 1 сложению. При достаточно большом n схемой Горнера можно загрузить всё имеющееся у нас оборудование ПЛИС в эффективном режиме, без простоев.