Algorithm level

Difference between revisions of "Horners method"

From Algowiki
Jump to navigation Jump to search
[unchecked revision][checked revision]
 
(26 intermediate revisions by 4 users not shown)
Line 1: Line 1:
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]])
+
{{algorithm
 +
| name              = Horners method
 +
| serial_complexity = <math>2 n^3</math>
 +
| input_data        = <math>n^2</math>
 +
| output_data      = <math>n^2</math>
 +
| pf_height        = <math>11n-16</math>
 +
| pf_width          = <math>O(n^2)</math>
 +
}}
  
== Properties and structure of Horner’s scheme ==
+
Main authors: [[:ru:Участник:Frolov|Alexey Frolov]].
  
=== Description of the algorithm ===
+
== Properties and structure of the algorithm ==
 +
 
 +
=== General description of the algorithm ===
  
 
==== Formulation of the problem ====
 
==== Formulation of the problem ====
Line 19: Line 28:
 
Actually, Horner’s scheme implements the long division of a polynomial by the binomial <math>x - \alpha</math>. By the Bezout theorem, the remainder of this operation is equal to the value of a polynomial <math>P_n(x)</math> at a point <math>\alpha</math>.
 
Actually, Horner’s scheme implements the long division of a polynomial by the binomial <math>x - \alpha</math>. By the Bezout theorem, the remainder of this operation is equal to the value of a polynomial <math>P_n(x)</math> at a point <math>\alpha</math>.
  
=== Mathematical description ===
+
=== Mathematical description of the algorithm ===
  
 
Input data: a one-dimensional array consisting of <math>n + 1</math> numbers <math>a_k</math> and a scalar <math>\alpha</math>.
 
Input data: a one-dimensional array consisting of <math>n + 1</math> numbers <math>a_k</math> and a scalar <math>\alpha</math>.
Line 38: Line 47:
 
</math>
 
</math>
  
By <math>b_n</math> er denote <math>P_n(\alpha)</math>. Substituting these polynomials in their canonical form into the above relation and equating the coefficients at equal powers of <math>x</math>, we come to the following formulas of Horner’s scheme:
+
By <math>b_n</math> we denote <math>P_n(\alpha)</math>. Substituting these polynomials in their canonical form into the above relation and equating the coefficients at equal powers of <math>x</math>, we come to the following formulas of Horner’s scheme:
  
 
:<math>
 
:<math>
Line 47: Line 56:
 
</math>
 
</math>
  
=== The computational kernel of Horner’s algorithm ===
+
=== Computational kernel of the algorithm ===
  
The computational kernel of Horner’s algorithm in its sequential version can be represented as a sequential set of <math>n</math> «double» operations: the multiplication of elements of the output array by one and the same scalar and the addition of the result to the next element of the input array.
+
The computational kernel of Horner’s algorithm in its serial version can be represented as a sequential set of <math>n</math> «double» operations: the multiplication of elements of the output array by one and the same scalar and the addition of the result to the next element of the input array.
  
=== Macrostructure of the algorithm ===
+
=== Macro structure of the algorithm ===
  
 
From the computational kernel of Horner’s algorithm it follows that its major part consists of the sequential set of the above «double» operations.
 
From the computational kernel of Horner’s algorithm it follows that its major part consists of the sequential set of the above «double» operations.
  
=== Implementation of the sequential algorithm ===
+
=== Implementation scheme of the serial algorithm ===
  
 
The formulas of the algorithm are described above. The operations are performed in increasing order of <math>k</math>.
 
The formulas of the algorithm are described above. The operations are performed in increasing order of <math>k</math>.
  
=== Sequential complexity of the algorithm ===
+
=== Serial complexity of the algorithm ===
  
For a polynomial of degree <math>n</math>, the number of multiplications is equal to <math>n</math> and the number of additions is also equal to <math>n</math>. Hence, Horner’s algorithm is of linear complexity with respect to the number of sequential operations.
+
For a polynomial of degree <math>n</math>, the number of multiplications is equal to <math>n</math> and the number of additions is also equal to <math>n</math>. Hence, Horner’s algorithm is of linear complexity with respect to the number of serial operations.
  
 
=== Information graph ===
 
=== Information graph ===
  
The graph of the algorithm is illustrated in Fig. 1 for <math>n = 9</math>. As can be seen, the graph is sequential.
+
The graph of the algorithm is illustrated in Fig.1 for <math>n = 9</math>. As can be seen, the graph is serial.
  
[[file:Basic sequental algorithm graph.png|center|thumb|800px|Fig. 1. Horner’s scheme: a sequential version.]]
+
[[file:Basic_sequental_algorithm_graph.png|center|thumb|800px|Figure 1. Horner’s scheme: a serial version.]]
  
 
Here the abbreviations In (Input) and Out (Output) are used to denote the first coefficient of the input array and the value of the polynomial at a given point <math>\alpha</math>, respectively. By Op we denote the "double" operation: the multiplication of an input variable by a scalar and the addition of the result to another variable.
 
Here the abbreviations In (Input) and Out (Output) are used to denote the first coefficient of the input array and the value of the polynomial at a given point <math>\alpha</math>, respectively. By Op we denote the "double" operation: the multiplication of an input variable by a scalar and the addition of the result to another variable.
  
=== A parallelization resource of the algorithm ===
+
=== Parallelization resource of the algorithm ===
  
The sequential version of Horner’s algorithm has no parallelization resource. Its parallel form consists of a single layer and is coincident with the sequential algorithm. Thus, the height of the parallel form is equal to <math>n</math> multiplications plus <math>n</math> additions. Hence, this algorithm is of linear complexity with respect to the height of the parallel form. The width of the parallel form is equal to <math>1</math>; hence, this algorithm is of constant complexity with respect to the width of the parallel form.
+
The serial version of Horner’s algorithm has no parallelization resource. Its parallel form consists of a single layer and is coincident with the serial algorithm. Thus, the height of the parallel form is equal to <math>n</math> multiplications plus <math>n</math> additions. Hence, this algorithm is of linear complexity with respect to the height of the parallel form. The width of the parallel form is equal to <math>1</math>; hence, this algorithm is of constant complexity with respect to the width of the parallel form.
  
 
=== Input and output data of the algorithm ===
 
=== Input and output data of the algorithm ===
Line 85: Line 94:
 
Output data: an array <math>b</math> (its elements are denoted by <math>b_k</math>, where <math>k = 0, \dots, n</math>)
 
Output data: an array <math>b</math> (its elements are denoted by <math>b_k</math>, where <math>k = 0, \dots, n</math>)
  
Amount of output data:: <nowiki/><math>n + 1</math>.
+
Amount of output data: <nowiki/><math>n + 1</math>.
  
=== Свойства алгоритма ===
+
=== Properties of the algorithm ===
  
In the case of unlimited computer resources, the ratio of the sequential complexity to the parallel complexity is ''constant''  (1). Computational power of the algorithm considered as the ratio of the number of operations to the total amount of input and output data is equal to 1 (the number of input and output data is even larger by 1 than the number of operations). The algorithm is completely deterministic. The arcs of the information graph are local. The stability of Horner’s scheme is optimal for the calculation of the values of a polynomial with known coefficient.
+
In the case of unlimited computer resources, the ratio of the serial complexity to the parallel complexity is ''constant''  (1). Computational power of the algorithm considered as the ratio of the number of operations to the total amount of input and output data is equal to 1 (the number of input and output data is even larger by 1 than the number of operations). The algorithm is completely deterministic. The arcs of the information graph are local. The stability of Horner’s scheme is optimal for the calculation of the values of a polynomial with known coefficient.
  
== Software implementation ==
+
== Software implementation of the algorithm ==
  
=== Implementation peculiarities of the sequential algorithm ===
+
=== Implementation peculiarities of the serial algorithm ===
  
 
Horner’s scheme can be represented in Fortran as
 
Horner’s scheme can be represented in Fortran as
Line 103: Line 112:
 
</source>
 
</source>
  
=== Описание локальности данных и вычислений ===
+
=== Possible methods and considerations for parallel implementation of the algorithm  ===
==== Описание локальности реализации алгоритма ====
 
===== Описание структуры обращений в память и качественная оценка локальности =====
 
 
 
[[file:Gorner_1.png|thumb|center|500px|Рисунок 12.1. Реализация схемы Горнера. Общий профиль обращений в память]]
 
 
 
На рис. 12.1 представлен профиль обращений в память последовательной вещественной реализации схемы Горнера. Исходя из рисунка 12.1, данный профиль устроен очень просто и состоит из двух последовательных переборов элементов, выполняемых параллельно для двух массивов.
 
 
 
Однако даже в таком простом примере для полного понимания структуры обращений в память нужен более детальный анализ на уровне отдельных обращений. На рис. 12.2 рассмотрим подробнее фрагмент 1, выделенный на рис. 12.1 зеленым. Можно увидеть, что верхний последовательный перебор несколько отличается от нижнего – в первом случае к каждому элементу выполняется по два обращения подряд. Отметим, однако, что данное уточнение строения профиля слабо сказывается на локальности всего профиля.
 
 
 
В целом, общий профиль обладает высокой пространственной локальностью, поскольку перебор элементов массивов осуществляется последовательно, однако очень низкой временно́й локальностью – в одном из массивов к каждому элементу выполняется обращение только дважды, во втором массиве повторные обращения вообще отсутствуют.
 
 
 
[[file:Gorner_2.jpg|thumb|center|500px|Рисунок 12.2. Фрагмент 1 (первые 100 обращений общего профиля)]]
 
 
 
===== Количественная оценка локальности =====
 
 
 
Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [http://git.algowiki-project.org/Voevodin/locality/blob/master/benchmarks/vectors/vectors.h здесь] (функция KernelGorner). Условия запуска описаны [http://git.algowiki-project.org/Voevodin/locality/blob/master/README.md здесь].
 
 
 
Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
 
 
 
На рисунке 12.3 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Согласно данному рисунку, реализация схемы Горнера показывает низкую производительность работы с памятью. Может показаться странным, что значение daps в этом случае значительно меньше, чем для тестов STREAM, несмотря на то, что профиль обращений во всех случаях очень похож – несколько одновременно выполняемых последовательных переборов массивов.
 
 
 
Причина такого поведения связана с особенностями строения подсистемы памяти. В реализации схемы Горнера, как было отмечено выше, к элементам одного из массивов выполняется по два обращения подряд. Однако если посмотреть исходный код реализации, можно увидеть, что на самом деле второе обращение выполняется на следующей итерации – это обращение к предыдущему элементу:
 
<source lang="c">
 
for (int i = 1; i < size; i++) {
 
    c[i] = a[i] + c[i - 1] * x;
 
}
 
</source>
 
В результате из-за зависимости итераций аппаратный префетчер гораздо хуже справляется с подтягиванием требуемых кэш-строк, что приводит к заметному замедлению выполнения программы по сравнению с другими реализациями, основанными на последовательном переборе (например, тесты STREAM).
 
 
 
Подобный пример лишний раз показывает, насколько сложно утроена подсистема памяти – совсем небольшое изменение строения тела цикла приводит к достаточно неожиданному серьезному замедлению программы.
 
 
 
[[file:Gorner_daps_ru.png|thumb|center|700px|Рисунок 12.3. Сравнение значений оценки daps]]
 
 
 
Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.
 
 
 
На рисунке 12.4 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что реализация схема Горнера обладает очень высокой локальностью согласно оценке cvg.
 
 
 
[[file:Gorner_cvg.png|thumb|center|700px|Рисунок 12.4. Сравнение значений оценки cvg]]
 
 
 
Как мы видели ранее, это плохо соотносится с реальной производительностью работы с памятью из-за особенностей строения памяти. Однако здесь необходимо сделать два замечания. Во-первых, подобные случаи, когда производительность работы с памятью настолько сильно зависит от специфичных аппаратных особенностей строения подсистемы памяти, на практике встречаются не так часто. Во-вторых, cvg предназначена для получения машинно-независимой оценки локальности; на данном уровне учесть подобные аппаратные особенности, по крайней мере, без потери доли машинно-независимых свойств, вряд ли представляется возможным.
 
 
 
=== Возможные способы и особенности реализации параллельного алгоритма ===
 
  
Описываемый алгоритм не предполагает параллельной реализации.
+
This algorithm is not designed to be implemented in parallel.
  
=== Масштабируемость алгоритма и его реализации ===
+
In addition to [[#Implementation peculiarities of the serial algorithm|the above simplest implementation]], there exist more primitive codes implementing only a part of Horner’s scheme. This can be explained by the fact that in many cases it is necessary to know the value of a polynomial (the remainder of division), but it is not necessary to know only the quotient polynomial with the remainder dropped. In such cases one and the same scalar should be used instead of all the elements of the array <math>b</math>.
  
Понятие масштабируемости неприменимо, поскольку описываемый алгоритм не предполагает параллельной реализации.
+
=== Run results ===
 +
=== Conclusions for different classes of computer architecture ===
  
=== Динамические характеристики и эффективность реализации алгоритма ===
+
== References ==
=== Выводы для классов архитектур ===
 
=== Существующие реализации алгоритма ===
 
  
Помимо [[#Особенности реализации последовательного алгоритма|выписанной выше простейшей реализации]], существуют более примитивные коды, реализующие часть функционала схемы Горнера. Это объясняется тем, что для многих нужно только значение многочлена (остаток от деления), но не нужен многочлен-частное. В таком случае вместо всех элементов массива <math>b</math> используется один и тот же скаляр.
+
<references />
  
 
[[ru: Схема Горнера, вещественная версия, последовательный вариант]]
 
[[ru: Схема Горнера, вещественная версия, последовательный вариант]]
  
[[Категория:Статьи в работе]]
+
[[Category:Finished articles]]

Latest revision as of 10:15, 8 July 2022


Horners method
Sequential algorithm
Serial complexity [math]2 n^3[/math]
Input data [math]n^2[/math]
Output data [math]n^2[/math]
Parallel algorithm
Parallel form height [math]11n-16[/math]
Parallel form width [math]O(n^2)[/math]


Main authors: Alexey Frolov.

1 Properties and structure of the algorithm

1.1 General description of the algorithm

1.1.1 Formulation of the problem

Horner’s scheme is devoted to the division of a polynomial [math]P_n(x)[/math] with known coefficients by the binomial [math]x - \alpha[/math]. The results of this operation are the coefficients of the polynomial [math]Q_{n - 1}(x)[/math] obtained by the relation

[math]P_n(x) - P_n(\alpha) = (x - \alpha) Q_{n - 1}(x)[/math]

and the value [math]P_n(\alpha)[/math] of the polynomial [math]P_n(x)[/math] at a given point [math]\alpha[/math].

Unfortunately, Horner’s method is often reduced only to the calculation of a polynomial [math]P_n(x)[/math] at the point [math]\alpha[/math].

1.1.2 General scheme

Actually, Horner’s scheme implements the long division of a polynomial by the binomial [math]x - \alpha[/math]. By the Bezout theorem, the remainder of this operation is equal to the value of a polynomial [math]P_n(x)[/math] at a point [math]\alpha[/math].

1.2 Mathematical description of the algorithm

Input data: a one-dimensional array consisting of [math]n + 1[/math] numbers [math]a_k[/math] and a scalar [math]\alpha[/math].

Output data: a one-dimensional array consisting of [math]n + 1[/math] numbers [math]b_k[/math].

The formulas of Horner's method are based on the relation

[math]P_n(x) - P_n(\alpha) = (x - \alpha) Q_{n - 1}(x)[/math].

Now we represent the above polynomials in canonical form:

[math] \begin{align} P_n(x) & = a_0 x^n+ a_1 x^{n - 1} + \dots + a_{n - 1} x + a_n, \\ Q_{n - 1}(x) & = b_0 x^{n - 1} + b_1 x^{n - 2} + \dots + b_{n - 2} x + b_{n - 1}. \end{align} [/math]

By [math]b_n[/math] we denote [math]P_n(\alpha)[/math]. Substituting these polynomials in their canonical form into the above relation and equating the coefficients at equal powers of [math]x[/math], we come to the following formulas of Horner’s scheme:

[math] \begin{align} b_0 & = a_0, \\ b_k & = a_k + \alpha b_{k - 1}, \quad k = 1, \dots, n. \end{align} [/math]

1.3 Computational kernel of the algorithm

The computational kernel of Horner’s algorithm in its serial version can be represented as a sequential set of [math]n[/math] «double» operations: the multiplication of elements of the output array by one and the same scalar and the addition of the result to the next element of the input array.

1.4 Macro structure of the algorithm

From the computational kernel of Horner’s algorithm it follows that its major part consists of the sequential set of the above «double» operations.

1.5 Implementation scheme of the serial algorithm

The formulas of the algorithm are described above. The operations are performed in increasing order of [math]k[/math].

1.6 Serial complexity of the algorithm

For a polynomial of degree [math]n[/math], the number of multiplications is equal to [math]n[/math] and the number of additions is also equal to [math]n[/math]. Hence, Horner’s algorithm is of linear complexity with respect to the number of serial operations.

1.7 Information graph

The graph of the algorithm is illustrated in Fig.1 for [math]n = 9[/math]. As can be seen, the graph is serial.

Figure 1. Horner’s scheme: a serial version.

Here the abbreviations In (Input) and Out (Output) are used to denote the first coefficient of the input array and the value of the polynomial at a given point [math]\alpha[/math], respectively. By Op we denote the "double" operation: the multiplication of an input variable by a scalar and the addition of the result to another variable.

1.8 Parallelization resource of the algorithm

The serial version of Horner’s algorithm has no parallelization resource. Its parallel form consists of a single layer and is coincident with the serial algorithm. Thus, the height of the parallel form is equal to [math]n[/math] multiplications plus [math]n[/math] additions. Hence, this algorithm is of linear complexity with respect to the height of the parallel form. The width of the parallel form is equal to [math]1[/math]; hence, this algorithm is of constant complexity with respect to the width of the parallel form.

1.9 Input and output data of the algorithm

Input data: an array [math]a[/math] (its elements are denoted by [math]a_i[/math], where [math]i = 0, \dots, n[/math]) and a scalar [math]\alpha[/math].

Additional constraints: absent.

Amount of input data: [math]n + 2[/math].

Output data: an array [math]b[/math] (its elements are denoted by [math]b_k[/math], where [math]k = 0, \dots, n[/math])

Amount of output data: [math]n + 1[/math].

1.10 Properties of the algorithm

In the case of unlimited computer resources, the ratio of the serial complexity to the parallel complexity is constant (1). Computational power of the algorithm considered as the ratio of the number of operations to the total amount of input and output data is equal to 1 (the number of input and output data is even larger by 1 than the number of operations). The algorithm is completely deterministic. The arcs of the information graph are local. The stability of Horner’s scheme is optimal for the calculation of the values of a polynomial with known coefficient.

2 Software implementation of the algorithm

2.1 Implementation peculiarities of the serial algorithm

Horner’s scheme can be represented in Fortran as

	b(0) = a(0)
	DO I = 1, N
		b(I) = a(I)+b(I-1)*alpha
	END DO

2.2 Possible methods and considerations for parallel implementation of the algorithm

This algorithm is not designed to be implemented in parallel.

In addition to the above simplest implementation, there exist more primitive codes implementing only a part of Horner’s scheme. This can be explained by the fact that in many cases it is necessary to know the value of a polynomial (the remainder of division), but it is not necessary to know only the quotient polynomial with the remainder dropped. In such cases one and the same scalar should be used instead of all the elements of the array [math]b[/math].

2.3 Run results

2.4 Conclusions for different classes of computer architecture

3 References