Algorithm level

Difference between revisions of "The serial-parallel summation method"

From Algowiki
Jump to navigation Jump to search
[unchecked revision][checked revision]
 
(48 intermediate revisions by 2 users not shown)
Line 1: Line 1:
Primary authors of this description: [[:ru:Участник:Frolov|A.V.Frolov]], [[:ru:Участник:VadimVV|Vad.V.Voevodin]] ([[#Locality of data and computations|Section 2.2]]), [[:ru:Участник:Teplov|A.M.Teplov]] (раздел [[#Scalability of the algorithm and its implementations|Section 2.4]])
+
{{level-a}}
 +
 
 +
Primary authors of this description: [[:ru:Участник:Frolov|A.V.Frolov]].
  
 
== Properties and structure of the algorithm ==
 
== Properties and structure of the algorithm ==
Line 5: Line 7:
 
=== General description of the algorithm ===
 
=== General description of the algorithm ===
  
The '''serial-parallel method''' используется в качестве эрзаца блочной реализации вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря следующим особенностям: а) реализует приём получения двойных циклов из одинарных; б) в последовательной архитектуре компьютеров позволял для ряда операций уменьшать влияние округления на результат. Здесь будем описывать его версию для суммирования чисел.
+
The '''serial-parallel method''' is used as a substitute for the block implementation of calculating long sequences of associative operations (for instance, mass summations). The method became popular due to the following features: a) it realizes the conversion of single cycles into double ones; b) on serial computers and for certain operations, the method was able to reduce the impact of round-off errors at the results. Here, we describe its version for summing numbers.
  
 
=== Mathematical description of the algorithm ===
 
=== Mathematical description of the algorithm ===
  
Исходные данные: одномерный массив <math>N</math> чисел.
+
Input data: one-dimensional array of <math>N</math> numbers.
  
Вычисляемые данные: сумма элементов массива.
+
Output data: sum of the array's elements.  
  
Формулы метода: число <math>N</math> разлагается в выражение типа <math>N = (p - 1) k + q</math>, где <math>p</math> — количество процессоров, <math>k = \lceil \frac{N}{p} \rceil</math>, <math>q = N - k (p - 1)</math>.
+
Formulas of the method: the integer <math>N</math> is represented as <math>N = (p - 1) k + q</math>, where <math>p</math> is the number of processors, <math>k = \lceil \frac{N}{p} \rceil</math>, and <math>q = N - k (p - 1)</math>.
  
После этого на <math>i</math>-м процессоре (<math>i < p</math>) последовательно вычисляется сумма элементов массива, начиная с <math>(i - 1) k + 1</math>-го, до <math>i k</math>-го.
+
Then the <math>i</math>-th processor (where <math>i < p</math>) calculates, in a serial mode, the sum of array elements with the indices ranging from <math>(i - 1) k + 1</math> to <math>i k</math>.
 
:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>
 
:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>
  
На <math>p</math>-м процессоре последовательно вычисляется сумма элементов массива, начиная с <math>(p - 1) k + 1</math>-го до <math>(p - 1) k + q</math>-го.
+
The <math>p</math>-th processor calculates, in a serial mode, the sum of array elements with the indices ranging from <math>(p - 1) k + 1</math> to <math>(p - 1) k + q</math>.
 
:<math>S_p = \sum_{j = 1}^q x_{k (p - 1) + j}</math>
 
:<math>S_p = \sum_{j = 1}^q x_{k (p - 1) + j}</math>
  
По окончании этого процесса процессоры обмениваются данными и на одном из них (либо на всех одновременно, если результат нужен далее на всех процессорах) получившиеся суммы суммируются последовательно друг с другом.
+
When this process is completed, the processors exchange their data, and one of them (or each of them if the result is later needed to all the processors) adds the partial sums in a serial mode.
 
:<math>\sum_{i = 1}^p S_i</math>
 
:<math>\sum_{i = 1}^p S_i</math>
  
 
=== Computational kernel of the algorithm ===
 
=== Computational kernel of the algorithm ===
  
Вычислительное ядро последовательно-параллельного метода суммирования можно составить из множественных (всего <math>p</math>) вычислений сумм элементов массива:
+
The computational kernel of the serial-parallel summation method can be compiled from multiple calculations of partial sums (altogether <math>p</math> calculations)
 
:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>
 
:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>
  
и ещё одного вычисления суммы элементов частичных сумм
+
plus the addition of these partial sums
 
:<math>\sum_{i = 1}^p S_i</math>
 
:<math>\sum_{i = 1}^p S_i</math>
  
 
=== Macro structure of the algorithm ===
 
=== Macro structure of the algorithm ===
  
Как уже записано в описании ядра алгоритма, основную часть метода составляют множественные (всего <math>p + 1</math>) вычисления сумм
+
As already noted in the description of the computational kernel, the basic part of the method is compiled of multiple calculations (altogether <math>p + 1</math> calculations) of the sums
:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>
+
:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math> and
 
:<math>\sum_{i = 1}^p S_i</math>
 
:<math>\sum_{i = 1}^p S_i</math>
  
 
=== Implementation scheme of the serial algorithm ===
 
=== Implementation scheme of the serial algorithm ===
  
Формулы метода описаны выше. Последовательность исполнения суммирования может быть разная — как по возрастанию, так и по убыванию индексов. Обычно без особых причин порядок не меняют, используя естественный (возрастание индексов).
+
The formulas of the method are given above. The summations can be performed in different ways, with indices of the summands either increasing or decreasing. When no special reasons for reordering are present, the natural order (i.e., increasing indices) is usually used.
  
 
=== Serial complexity of the algorithm ===
 
=== Serial complexity of the algorithm ===
  
Для вычисления суммы массива, состоящего из <math>N</math> элементов, при любых разложениях <math>N</math> суть алгоритма сводится к простому переставлению скобок в формуле суммирования, и количество операций неизменно и равно <math>N - 1</math>. Поэтому алгоритм должен быть отнесён к алгоритмам ''линейной'' сложности по количеству последовательных операций.
+
Let an array of <math>N</math> elements must be summed. Various decompositions of <math>N</math> differ from each other merely by arrangements of parentheses in the summation formula. The number of operations is the same for all the arrangements and is equal to <math>N - 1</math>. Therefore, in terms of the number of serial operations, the method should be regarded as a ''linear'' complexity algorithm.
  
 
=== Information graph ===
 
=== Information graph ===
  
На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 24 элементов массива.
+
The algorithm graph is shown in fig.1 in the case where an array of size 24 is summed.  
 
+
[[file:Series-parallel_summation_graph.png|center|thumb|600px|Figure 1. The serial-parallel summation method]]
[[file:Series-parallel_summation_graph.png|center|thumb|600px|Рисунок 1. Последовательно-параллельный метод суммирования массива]]
 
  
 
<center>
 
<center>
Line 60: Line 61:
 
}}
 
}}
 
<br/>
 
<br/>
Интерактивное изображение графа алгоритма без входных и выходных данных для случая суммирования 20 элементов массива
+
Interactive representation of the algorithm graph in the case where an array of size 24 is summed. No input and output data are shown.
</center>
+
[[Media:[[Media:Example.ogg]]]] </center>
  
 
=== Parallelization resource of the algorithm ===
 
=== Parallelization resource of the algorithm ===
  
Для суммирования массива порядка <math>n</math> последовательно-параллельным методом в параллельном варианте требуется последовательно выполнить следующие ярусы:
+
In order to sum an array of size <math>n</math> by using the serial-parallel summation method in a parallel mode, the following layers must be performed:
* <math>k - 1</math> ярусов суммирования по частям массива (<math>p</math> ветвей),
+
* <math>k - 1</math> layers for the summation of parts of the array (<math>p</math> branches),
* <math>p - 1</math> ярусов суммирования (одна последовательная ветвь).
+
* <math>p - 1</math> summation layers (a single serial branch).
 
   
 
   
Таким образом, в параллельном варианте критический путь алгоритма (и соответствующая ему высота ЯПФ) будет зависеть от произведённого разбиения массива на части. В оптимальном случае (<math>p = \sqrt{n}</math>) высота ЯПФ будет равна <math>2 \sqrt{n} - 2</math>.
+
Thus, in the parallel version, the critical path of the algorithm (and the corresponding height of the parallel form) depends on the chosen splitting of the array. In the optimal case (<math>p = \sqrt{n}</math>), the height of the parallel form is <math>2 \sqrt{n} - 2</math>.
  
При классификации по высоте ЯПФ, таким образом, последовательно-параллельный метод относится к алгоритмам со сложностью ''корень квадратный''. При классификации по ширине ЯПФ его сложность будет такой же — ''корень квадратный''.
+
Consequently, in terms of the parallel form height, the serial-parallel summation method is qualified as an algorithm of the ''square root'' complexity. In terms of the parallel form width, it also has the ''square root'' complexity.
  
 
=== Input and output data of the algorithm ===
 
=== Input and output data of the algorithm ===
  
Входные данные: массив <math>\vec{x}</math> (элементы <math>x_i</math>).
+
Input data: array <math>\vec{x}</math> (with elements <math>x_i</math>).
  
Дополнительные ограничения: отсутствуют.
+
Further restrictions: none.  
  
Объём входных данных: <nowiki/><math>N</math>.
+
Size of the input data: <nowiki/><math>N</math>.
  
Выходные данные: сумма элементов массива.
+
Output data: sum of the array's elements.  
  
Объём выходных данных: один скаляр.
+
Size of the output data: single scalar.
  
 
=== Properties of the algorithm ===
 
=== Properties of the algorithm ===
  
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''корнем квадратным'' (отношение линейной к корню квадратному). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм не вполне полностью детерминирован, суммирование может быть проведено в разном порядке. Использование другого порядка выполнения ассоциативных операций может дать, с учётом особенностей входных данных, уменьшение влияния ошибок округления на результат. Дуги информационного графа локальны.
+
It is clearly seen that, in the case of unlimited resources, the ratio of the serial to parallel complexity has the ''square root'' order (the ratio of the linear to square root complexity). The computational power of the algorithm, understood as the ratio of the number of operations to the total size of the input and output data, is only ''1 (the size of the input and output data is equal to the number of operations)''. The algorithm is not completely determined because the partial summations can be organized in different ways. Choosing the order of performing associative operations in accordance with the peculiarities of the input data may reduce the impact of round-off errors at the result. The edges of the information graph are local.
  
 
== Software implementation of the algorithm ==
 
== Software implementation of the algorithm ==
Line 93: Line 94:
 
=== Implementation peculiarities of the serial algorithm ===
 
=== Implementation peculiarities of the serial algorithm ===
  
В простейшем (без перестановок суммирования) варианте на Фортране можно записать так:
+
The simplest variant (with no order of summation changed) can be written in Fortran as follows:  
 +
 
 
<source lang="fortran">
 
<source lang="fortran">
 
DO  I = 1, P
 
DO  I = 1, P
Line 113: Line 115:
 
</source>
 
</source>
  
Можно записать и аналогичные схемы, где суммирование будет проводиться в обратном порядке. Подчеркнём, что граф алгоритма обеих схем — [[#Информационный граф|один и тот же]]!
+
One can also write a similar scheme with the summations performed in the reverse order. We emphasize that, for both schemes, the algorithm graph is [[#Information graph|the same]]!
 
 
=== Locality of data and computations ===
 
==== Locality of implementation ====
 
===== Structure of memory access and a qualitative estimation of locality =====
 
 
 
[[file:Seqpar sum 1.PNG|thumb|center|700px|Рисунок 2. Суммирование элементов массива. Общий профиль обращений в память]]
 
 
 
На рис.2 представлен профиль обращений в память для суммирования элементов массива. Данный профиль состоит из обращений к двум массивам, фрагменты для отдельных массивов выделены на рис.2 зеленым цветом. Поскольку мы рассматриваем последовательную реализацию последовательно-параллельного метода суммирования, строение профиля практически никак не зависит от выбранного количества ветвей – будет меняться только число задействованных элементов во фрагменте 1.
 
 
 
Фрагмент 2 устроен очень просто и представляет собой последовательный перебор всех элементов массива. Фрагмент 1 состоит из двух одинаковых переборов элементов массива, что хорошо видно из рис.3, где данный фрагмент рассмотрен отдельно.
 
 
 
[[file:Seqpar sum 2.jpg|thumb|center|400px|Рисунок 3. Фрагмент 1 (профиль обращений к первому массиву)]]
 
 
 
Данные фрагмент характеризуются высокой пространственной локальностью и низкой временной, поскольку практически отсутствуют повторные обращения.
 
 
 
===== Quantitative estimation of locality =====
 
 
 
Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [http://git.algowiki-project.org/Voevodin/locality/blob/master/benchmarks/vectors_seqpar/vectors_seqpar.h здесь] (функция KernelOpSeqpar). Условия запуска описаны [http://git.algowiki-project.org/Voevodin/locality/blob/master/README.md здесь].
 
 
 
Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
 
 
 
На рис.4 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что значение данной оценки достаточно высоко и близко к последовательно-параллельному скалярному произведению двух векторов, что является закономерным вследствие однотипности структуры выполняемых операций.
 
 
 
[[file:Seqpar_sum_daps.PNG|thumb|center|700px|Рисунок 4. Сравнение значений оценки daps]]
 
 
 
Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.
 
 
 
На рис.5 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, локальность профиля достаточно высока, что коррелирует со значением оценки daps.
 
 
 
[[file:Seqpar sum cvg.PNG|thumb|center|700px|Рисунок 5. Сравнение значений оценки cvg]]
 
  
 
=== Possible methods and considerations for parallel implementation of the algorithm ===
 
=== Possible methods and considerations for parallel implementation of the algorithm ===
=== Scalability of the algorithm and its implementations ===
 
==== Scalability of the algorithm ====
 
==== Scalability of of the algorithm implementation ====
 
[[file:Масштабируемость_производительность_ссумирования_элементов_массива.png|thumb|center|700px|Рисунок 6. Параллельная реализация Сумирования элементов массива Максимальная производительность. ]]
 
[[file:Масштабируемость_суммирования_элементов_массива_Эффективность.png|thumb|center|700px|Рисунок 7. Параллельная реализация сумирования элементов массива Максимальная эффективность. ]]
 
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
 
* число процессоров [2 : 256]
 
* размер вектора [80000000:320000000]
 
Эффективность выполнения реализации алгоритма
 
* Минимальная эффективность 0,00004%
 
* Максимальная эффективность 0,0037%
 
Оценка масштабируемости
 
* По числу процессов: -9.432e-07 – при увеличении числа процессов эффективность уменьшается на рассмотренной области изменений параметров запуска, однако, в целом уменьшение не интенсивное. Это объясняется тем, что при увеличении числа процессов  сильно возрастает доля накладных расходов на организацию схемы сдваивания сумирования, однако, так как общая эффективность составляет доли процента интенсивность сильная только при переходе от работы процессов в рамках одного физического узла к использованию коммуникационной сети. В остальной области рассмотренных значений параметров запуска эффективность близка к 0 в силу того, что на каждый процесс приходится черезвычайно малая доля вычислений. Больше полезного времени уходит на организацию работы процессов.
 
* По размеру задачи: 1.881e-06 – при увеличении размера задачи эффективность в целом очень незначительно увеличивается по рассматриваемой области. Это объясняется общим увеличением вычислительной сложности задачи в связи с увеличением размерности. Однако вычислительная сложность алгоритма <math>(N-1)</math>не позволяет существенно увеличить долю времени затрачиваемую на вычисления.
 
* По двум направлениям: -1.423e-07 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, однако интенсивность уменьшения эффективности небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров несущественная говорит о том, что на поверхности присутствуют области с очень интенсивным изменением эффективности на участке 2-16 процессов, но очень малые по площади. На остальной поверхности изменения эффективности незначительны и находятся на приблизительно одном и том же уровне.
 
  
[http://git.algowiki-project.org/Teplov/Scalability/blob/master/arraysum/arraysum.c Исследованная реализация алгоритма на языке C]
+
In its pure form, the serial-parallel method for summation an array is rarely used. Usually, modifications of this method are met in practice. They are designed for calculating the dot product (in which case, products of the elements of two arrays are summed rather than the elements of a single array) or the uniform norm (instead of the elements of an array, their moduli are summed), etc. The method is applied in the BLAS library for calculating the dot product in a particular case (where one of the dimensions is 5); however, the aim apparently was not a parallelization but an optimization of functioning the processor registers. Meanwhile, partitions of an array for calculating partial sums may be useful for better using the cache at individual nodes.
  
=== Dynamic characteristics and efficiency of the algorithm implementation ===
+
=== Run results ===
 
=== Conclusions for different classes of computer architecture ===
 
=== Conclusions for different classes of computer architecture ===
=== Existing implementations of the algorithm ===
 
  
В чистом виде алгоритм последовательно-параллельного метода для суммирования массива встречается редко, в основном встречаются его модификации, например для случаев вычисления скалярного произведения (вместо элементов массива будут фигурировать произведения элементов двух массивов), равномерной нормы (вместо элементов массива — их модули) и т. п. В случае вычисления скалярного произведения в одном из частных случаев подобный приём применён в библиотеке BLAS (там одна из размерностей равна 5), но, видимо, не для распараллеливания, а для оптимизации работы с регистрами процессора. Между тем, разбиения массивов на группы для вычислений частных сумм могут быть полезны и для лучшего использования кэша на отдельных узлах.
+
== References ==
  
== References ==
 
 
<references />
 
<references />
  
[[Category:Started articles]]
+
[[Category:Finished articles]]
  
 
[[Ru:Последовательно-параллельный метод суммирования]]
 
[[Ru:Последовательно-параллельный метод суммирования]]

Latest revision as of 15:12, 8 July 2022


Primary authors of this description: A.V.Frolov.

1 Properties and structure of the algorithm

1.1 General description of the algorithm

The serial-parallel method is used as a substitute for the block implementation of calculating long sequences of associative operations (for instance, mass summations). The method became popular due to the following features: a) it realizes the conversion of single cycles into double ones; b) on serial computers and for certain operations, the method was able to reduce the impact of round-off errors at the results. Here, we describe its version for summing numbers.

1.2 Mathematical description of the algorithm

Input data: one-dimensional array of [math]N[/math] numbers.

Output data: sum of the array's elements.

Formulas of the method: the integer [math]N[/math] is represented as [math]N = (p - 1) k + q[/math], where [math]p[/math] is the number of processors, [math]k = \lceil \frac{N}{p} \rceil[/math], and [math]q = N - k (p - 1)[/math].

Then the [math]i[/math]-th processor (where [math]i \lt p[/math]) calculates, in a serial mode, the sum of array elements with the indices ranging from [math](i - 1) k + 1[/math] to [math]i k[/math].

[math]S_i = \sum_{j = 1}^k x_{k (i - 1) + j}[/math]

The [math]p[/math]-th processor calculates, in a serial mode, the sum of array elements with the indices ranging from [math](p - 1) k + 1[/math] to [math](p - 1) k + q[/math].

[math]S_p = \sum_{j = 1}^q x_{k (p - 1) + j}[/math]

When this process is completed, the processors exchange their data, and one of them (or each of them if the result is later needed to all the processors) adds the partial sums in a serial mode.

[math]\sum_{i = 1}^p S_i[/math]

1.3 Computational kernel of the algorithm

The computational kernel of the serial-parallel summation method can be compiled from multiple calculations of partial sums (altogether [math]p[/math] calculations)

[math]S_i = \sum_{j = 1}^k x_{k (i - 1) + j}[/math]

plus the addition of these partial sums

[math]\sum_{i = 1}^p S_i[/math]

1.4 Macro structure of the algorithm

As already noted in the description of the computational kernel, the basic part of the method is compiled of multiple calculations (altogether [math]p + 1[/math] calculations) of the sums

[math]S_i = \sum_{j = 1}^k x_{k (i - 1) + j}[/math] and
[math]\sum_{i = 1}^p S_i[/math]

1.5 Implementation scheme of the serial algorithm

The formulas of the method are given above. The summations can be performed in different ways, with indices of the summands either increasing or decreasing. When no special reasons for reordering are present, the natural order (i.e., increasing indices) is usually used.

1.6 Serial complexity of the algorithm

Let an array of [math]N[/math] elements must be summed. Various decompositions of [math]N[/math] differ from each other merely by arrangements of parentheses in the summation formula. The number of operations is the same for all the arrangements and is equal to [math]N - 1[/math]. Therefore, in terms of the number of serial operations, the method should be regarded as a linear complexity algorithm.

1.7 Information graph

The algorithm graph is shown in fig.1 in the case where an array of size 24 is summed.

Figure 1. The serial-parallel summation method


Interactive representation of the algorithm graph in the case where an array of size 24 is summed. No input and output data are shown.

[[Media:Media:Example.ogg]]

1.8 Parallelization resource of the algorithm

In order to sum an array of size [math]n[/math] by using the serial-parallel summation method in a parallel mode, the following layers must be performed:

  • [math]k - 1[/math] layers for the summation of parts of the array ([math]p[/math] branches),
  • [math]p - 1[/math] summation layers (a single serial branch).

Thus, in the parallel version, the critical path of the algorithm (and the corresponding height of the parallel form) depends on the chosen splitting of the array. In the optimal case ([math]p = \sqrt{n}[/math]), the height of the parallel form is [math]2 \sqrt{n} - 2[/math].

Consequently, in terms of the parallel form height, the serial-parallel summation method is qualified as an algorithm of the square root complexity. In terms of the parallel form width, it also has the square root complexity.

1.9 Input and output data of the algorithm

Input data: array [math]\vec{x}[/math] (with elements [math]x_i[/math]).

Further restrictions: none.

Size of the input data: [math]N[/math].

Output data: sum of the array's elements.

Size of the output data: single scalar.

1.10 Properties of the algorithm

It is clearly seen that, in the case of unlimited resources, the ratio of the serial to parallel complexity has the square root order (the ratio of the linear to square root complexity). The computational power of the algorithm, understood as the ratio of the number of operations to the total size of the input and output data, is only 1 (the size of the input and output data is equal to the number of operations). The algorithm is not completely determined because the partial summations can be organized in different ways. Choosing the order of performing associative operations in accordance with the peculiarities of the input data may reduce the impact of round-off errors at the result. The edges of the information graph are local.

2 Software implementation of the algorithm

2.1 Implementation peculiarities of the serial algorithm

The simplest variant (with no order of summation changed) can be written in Fortran as follows:

	DO  I = 1, P
		S (I) = X(K*(I-1)+1)
		IF (I.LQ.P) THEN
			DO J = 2,K
				S(I)=S(I)+X(K*(I-1)+J)
		             END DO
		ELSE
			DO J = 2,Q
				S(I)=S(I)+X(K*(I-1)+J)
		             END DO
		END IF
	END DO
	SUM = S(1)
	DO I = 2, P
		SUM = SUM + S(I)
	END DO

One can also write a similar scheme with the summations performed in the reverse order. We emphasize that, for both schemes, the algorithm graph is the same!

2.2 Possible methods and considerations for parallel implementation of the algorithm

In its pure form, the serial-parallel method for summation an array is rarely used. Usually, modifications of this method are met in practice. They are designed for calculating the dot product (in which case, products of the elements of two arrays are summed rather than the elements of a single array) or the uniform norm (instead of the elements of an array, their moduli are summed), etc. The method is applied in the BLAS library for calculating the dot product in a particular case (where one of the dimensions is 5); however, the aim apparently was not a parallelization but an optimization of functioning the processor registers. Meanwhile, partitions of an array for calculating partial sums may be useful for better using the cache at individual nodes.

2.3 Run results

2.4 Conclusions for different classes of computer architecture

3 References