Уровень алгоритма

Нахождение частных сумм элементов массива сдваиванием: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][досмотренная версия]
(пока временная болванка для изменений)
 
 
(не показана 31 промежуточная версия 4 участников)
Строка 1: Строка 1:
 
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]]
 
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]]
  
== Описание свойств и структуры алгоритма ==
+
{{level-a}}
 +
 
 +
== Свойства и структура алгоритма ==
  
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
  
'''Метод сдваивания''' используется в качестве быстрого варианта вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря как наименьшей из возможных высоте алгортима, так и из-за ряда своих вычислительных характеристик, а также (в среде нечисленных алгоритмов) из-за своей рекурсивности, то есть лёгкости записи.
+
'''Метод сдваивания'''<ref>Фролов А.В. Использование последовательно-параллельного метода для распараллеливания алгоритмов с ассоциативными операциями  // Принята в качестве доклада на первую объединенную международную конференцию "Суперкомпьютерные дни в России", Москва, 28-29 сентября 2015 г.</ref> используется в качестве быстрого варианта вычисления длинных последовательностей ассоциативных операций (например, массового получения частичных сумм). Получил распространение благодаря наименьшей из возможных высоте алгоритма. Данный алгоритм (нахождение частных сумм элементов массива сдваиванием) является только наиболее простой моделью для показа свойств алгоритма сдваивания.
  
=== Математическое описание ===
+
=== Математическое описание алгоритма ===
  
 
Исходные данные: одномерный массив <math>n</math> чисел.
 
Исходные данные: одномерный массив <math>n</math> чисел.
  
Вычисляемые данные: сумма элементов массива.
+
Вычисляемые данные: частичные суммы первых <math>i</math> элементов массива, где <math>i</math> принимает все значения от <math>1</math> до <math>n</math>.
  
Формулы метода: элементы на каждом этапе алгоритма разбиваются на пары. В каждой из пар находится сумма составляющих её элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д.
+
Формулы метода: элементы на первом этапе алгоритма разбиваются на пары. В каждой из пар находится сумма составляющих её соседних элементов.  
 +
На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д.
 +
По нахождению тех частных сумм, где <math>i</math> является степенью двойки, формулы повторяют [[Нахождение суммы элементов массива сдваиванием|алгоритм нахождения суммы элементов массива сдваиванием]].
 +
Однако, кроме этого, для каждой пары (например, для нахождения суммы <math>x_i+...+x_{i+k}</math> и <math>x_{i+k+1} +...+ x_{i+2k}</math>)дополнительно вычисляются все частные суммы от <math>x_i+...+x_{i+k+1}</math> до <math>x_i+...+x_{i+2k-1}</math>.
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
  
Вычислительное ядро последовательно-параллельного метода суммирования можно составить как из элементарных бинарных (всего <math>n - 1</math>) вычислений сумм, так и (рекуррентно) из набора реализаций метода сдваивания меньших размерностей.
+
Вычислительное ядро метода сдваивания суммирования можно составить из элементарных бинарных (всего <math>\frac{n}{2} log_2 n</math>) вычислений сумм.
  
 
=== Макроструктура алгоритма ===
 
=== Макроструктура алгоритма ===
  
Как уже записано в описании ядра алгоритма, основную часть метода составляют рекурсивные вызовы сумм массивов меньшей размерности.
+
Как уже записано в описании ядра алгоритма, основную часть метода составляют элементарные бинарные (всего <math>\frac{n}{2} log_2 n</math>) вычисления сумм.
  
=== Описание схемы реализации последовательного алгоритма ===
+
=== Схема реализации последовательного алгоритма ===
  
В своём чистом виде суммирование сдваиванием редко используют при последовательной реализации, поскольку при этом усложняется общая схема алгоритма и резко растёт потребность в памяти, нужной для хранения промежуточных данных.
+
В описанном виде суммирование сдваиванием не используют при последовательной реализации, поскольку кроме усложнения общей схемы алгоритма и резкого роста потребности в памяти, нужной для хранения промежуточных данных, сам по себе алгоритм содержит подавляющее большинство [[%D0%93%D0%BB%D0%BE%D1%81%D1%81%D0%B0%D1%80%D0%B8%D0%B9#.D0.98.D0.B7.D0.B1.D1.8B.D1.82.D0.BE.D1.87.D0.BD.D1.8B.D0.B5_.D0.B2.D1.8B.D1.87.D0.B8.D1.81.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|избыточных вычислений]]: по сравнению с последовательным алгоритмом нахождения частных сумм количество операций больше в <math>\frac{1}{2} log_2 n</math> раз.
  
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
  
Для вычисления суммы массива, состоящего из <math>N</math> элементов, при любых разложениях <math>N</math> на пары суть алгоритма сводится к простому переставлению скобок в формуле суммирования, и количество операций неизменно и равно <math>N - 1</math>. Поэтому алгоритм должен быть отнесён к алгоритмам ''линейной сложности'' по количеству последовательных операций.
+
Для вычисления суммы массива, состоящего из <math>n</math> элементов, количество операций равно <math>\frac{n}{2} log_2 n</math>. Поэтому алгоритм должен быть отнесён к алгоритмам ''линейно-логарифмической сложности'' по количеству последовательных операций.
  
 
=== Информационный граф ===
 
=== Информационный граф ===
 +
[[File:DoublingPartUniv.png|thumb|center|600px|Рисунок 1. Граф алгоритма при n=8 c отображением входных данных. Синим обозначены входные, красным - выходные данные. Все вершины соответствуют операции сложения]]
  
Опишем граф алгоритма в виде рисунка. В данном случае выполнено суммирование 16 элементов массива.
+
Граф алгоритма изображён на рисунке.
Вершины , соответствующие входным данным - даны синим цветом , выходным данным - красным цветом.
 
  
[[file:binary-tree-based summation graph.png|center|thumb|500px|Суммирование массива методом сдваивания]]
+
=== Ресурс параллелизма алгоритма ===
  
=== Описание ресурса параллелизма алгоритма ===
+
Для вычисления частичных сумм массива порядка <math>n</math> методом сдваивания в параллельном варианте требуется последовательно выполнить <math>\lceil \log_2 n \rceil</math> ярусов с одинаковым (<math>\frac{n}{2}</math>) количеством операций суммирования.
 
 
Для суммирования массива порядка <math>n</math> методом сдваивания в параллельном варианте требуется последовательно выполнить <math>\lceil \log_2 n \rceil</math> ярусов с убывающим (от <math>\frac{n}{2}</math> до <math>1</math>) количеством операций суммирования.
 
 
При классификации по высоте ЯПФ, таким образом, метод сдваивания относится к алгоритмам с ''логарифмической сложностью''. При классификации по ширине ЯПФ его сложность будет ''линейной''.
 
При классификации по высоте ЯПФ, таким образом, метод сдваивания относится к алгоритмам с ''логарифмической сложностью''. При классификации по ширине ЯПФ его сложность будет ''линейной''.
  
=== Описание входных и выходных данных ===
+
=== Входные и выходные данные алгоритма ===
  
 
Входные данные: массив <math>x</math> (элементы <math>x_i</math>).
 
Входные данные: массив <math>x</math> (элементы <math>x_i</math>).
Строка 49: Строка 52:
 
Дополнительные ограничения: отсутствуют.
 
Дополнительные ограничения: отсутствуют.
  
Объём входных данных: <nowiki/><math>N</math>.  
+
Объём входных данных: <nowiki/><math>n</math>.  
  
Выходные данные: сумма элементов массива.
+
Выходные данные: все частичные суммы первых <math>i</math> элементов массива, где <math>i</math> принимает все значения от <math>1</math> до <math>n</math>.
  
Объём выходных данных: один скаляр.
+
Объём выходных данных: <math>n</math>.
  
 
=== Свойства алгоритма ===
 
=== Свойства алгоритма ===
  
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является <math>\frac{n}{\log_2 n}</math> (отношение линейной к логарифмической). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм полностью детерминирован. Дуги информационного графа нелокальны, от яруса к ярусу наблюдается показательный рост их длины, при любом размещении вершин графа.  
+
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является <math>\frac{n}{2}</math> (отношение линейно-логарифмической к логарифмической). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — логарифмическая <math>\frac{1}{2} log_2 n</math>. Это, однако, обусловлено избыточностью вычислений, реальная мощность - константа (1). При этом алгоритм полностью детерминирован. Дуги информационного графа нелокальны, от яруса к ярусу наблюдается показательный рост их длины, при любом размещении вершин графа (кроме дополнительных измерений в случае расположения вершин в гиперкубе).
  
== Программная реализация ==
+
== Программная реализация алгоритма ==
  
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
 
==== Описание локальности реализации алгоритма ====
 
===== Описание структуры обращений в память и качественная оценка локальности =====
 
===== Количественная оценка локальности =====
 
=== Возможные способы и особенности реализации параллельного алгоритма ===
 
=== Масштабируемость алгоритма и его реализации ===
 
==== Описание масштабируемости алгоритма ====
 
==== Описание масштабируемости реализации алгоритма ====
 
  
 +
Сдваивание, из-за сильной избыточности вычислений, вряд ли может быть применено на компьютерах без параллельных устройств.
  
=== Динамические характеристики и эффективность реализации алгоритма ===
+
=== Возможные способы и особенности параллельной реализации алгоритма ===
 +
 
 +
Ввиду малораспространённости задачи нахождения частных сумм в библиотеках программ данный алгоритм обычно не содержится.
 +
 
 +
Как видно по графу алгоритма, ряд дуг длинны как по времени (по различию номеров ярусов операций, являющихся началом и концом дуги), так и по пространству (исключением является только размещение в гиперкубе, физически невозможное). Эта неустранимая нелокальность должна тормозить исполнение всех аналогичных алгоритмов.
 +
 
 +
При оценке масштабируемости этого алгоритма, как и всех алгоритмов с избыточными вычислениями, следует учитывать, что сравнение по быстродействию и эффективности нужно проводить не с однопроцессорным вариантом исполнения самого алгоритма, а с алгоритмом последовательного сложения чисел. 
 +
 
 +
=== Результаты прогонов ===
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
 
  
 +
Из-за своеобразия графа сдваивания лучше всего он отображается на архитектуру типа "гиперкуб". Поэтому для архитектур с массовым параллелизмом представляется неизбежным рост накладных расходов и слабая масштабируемость алгоритма.
 +
 +
== Литература ==
 +
 +
<references />
 +
 +
[[Категория:Законченные_статьи]]
 +
[[Категория:Метод сдваивания]]
 +
[[Категория:Алгоритмы с избыточными вычислениями]]
 +
[[Категория:Векторные операции]]
  
[[Категория:Новые статьи]]
+
[[en:Parallel prefix scan algorithm using pairwise summation]]

Текущая версия на 12:58, 8 июля 2022

Основные авторы описания: А.В.Фролов



1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Метод сдваивания[1] используется в качестве быстрого варианта вычисления длинных последовательностей ассоциативных операций (например, массового получения частичных сумм). Получил распространение благодаря наименьшей из возможных высоте алгоритма. Данный алгоритм (нахождение частных сумм элементов массива сдваиванием) является только наиболее простой моделью для показа свойств алгоритма сдваивания.

1.2 Математическое описание алгоритма

Исходные данные: одномерный массив [math]n[/math] чисел.

Вычисляемые данные: частичные суммы первых [math]i[/math] элементов массива, где [math]i[/math] принимает все значения от [math]1[/math] до [math]n[/math].

Формулы метода: элементы на первом этапе алгоритма разбиваются на пары. В каждой из пар находится сумма составляющих её соседних элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д. По нахождению тех частных сумм, где [math]i[/math] является степенью двойки, формулы повторяют алгоритм нахождения суммы элементов массива сдваиванием. Однако, кроме этого, для каждой пары (например, для нахождения суммы [math]x_i+...+x_{i+k}[/math] и [math]x_{i+k+1} +...+ x_{i+2k}[/math])дополнительно вычисляются все частные суммы от [math]x_i+...+x_{i+k+1}[/math] до [math]x_i+...+x_{i+2k-1}[/math].

1.3 Вычислительное ядро алгоритма

Вычислительное ядро метода сдваивания суммирования можно составить из элементарных бинарных (всего [math]\frac{n}{2} log_2 n[/math]) вычислений сумм.

1.4 Макроструктура алгоритма

Как уже записано в описании ядра алгоритма, основную часть метода составляют элементарные бинарные (всего [math]\frac{n}{2} log_2 n[/math]) вычисления сумм.

1.5 Схема реализации последовательного алгоритма

В описанном виде суммирование сдваиванием не используют при последовательной реализации, поскольку кроме усложнения общей схемы алгоритма и резкого роста потребности в памяти, нужной для хранения промежуточных данных, сам по себе алгоритм содержит подавляющее большинство избыточных вычислений: по сравнению с последовательным алгоритмом нахождения частных сумм количество операций больше в [math]\frac{1}{2} log_2 n[/math] раз.

1.6 Последовательная сложность алгоритма

Для вычисления суммы массива, состоящего из [math]n[/math] элементов, количество операций равно [math]\frac{n}{2} log_2 n[/math]. Поэтому алгоритм должен быть отнесён к алгоритмам линейно-логарифмической сложности по количеству последовательных операций.

1.7 Информационный граф

Рисунок 1. Граф алгоритма при n=8 c отображением входных данных. Синим обозначены входные, красным - выходные данные. Все вершины соответствуют операции сложения

Граф алгоритма изображён на рисунке.

1.8 Ресурс параллелизма алгоритма

Для вычисления частичных сумм массива порядка [math]n[/math] методом сдваивания в параллельном варианте требуется последовательно выполнить [math]\lceil \log_2 n \rceil[/math] ярусов с одинаковым ([math]\frac{n}{2}[/math]) количеством операций суммирования. При классификации по высоте ЯПФ, таким образом, метод сдваивания относится к алгоритмам с логарифмической сложностью. При классификации по ширине ЯПФ его сложность будет линейной.

1.9 Входные и выходные данные алгоритма

Входные данные: массив [math]x[/math] (элементы [math]x_i[/math]).

Дополнительные ограничения: отсутствуют.

Объём входных данных: [math]n[/math].

Выходные данные: все частичные суммы первых [math]i[/math] элементов массива, где [math]i[/math] принимает все значения от [math]1[/math] до [math]n[/math].

Объём выходных данных: [math]n[/math].

1.10 Свойства алгоритма

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является [math]\frac{n}{2}[/math] (отношение линейно-логарифмической к логарифмической). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — логарифмическая [math]\frac{1}{2} log_2 n[/math]. Это, однако, обусловлено избыточностью вычислений, реальная мощность - константа (1). При этом алгоритм полностью детерминирован. Дуги информационного графа нелокальны, от яруса к ярусу наблюдается показательный рост их длины, при любом размещении вершин графа (кроме дополнительных измерений в случае расположения вершин в гиперкубе).

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

Сдваивание, из-за сильной избыточности вычислений, вряд ли может быть применено на компьютерах без параллельных устройств.

2.2 Возможные способы и особенности параллельной реализации алгоритма

Ввиду малораспространённости задачи нахождения частных сумм в библиотеках программ данный алгоритм обычно не содержится.

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

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

2.3 Результаты прогонов

2.4 Выводы для классов архитектур

Из-за своеобразия графа сдваивания лучше всего он отображается на архитектуру типа "гиперкуб". Поэтому для архитектур с массовым параллелизмом представляется неизбежным рост накладных расходов и слабая масштабируемость алгоритма.

3 Литература

  1. Фролов А.В. Использование последовательно-параллельного метода для распараллеливания алгоритмов с ассоциативными операциями // Принята в качестве доклада на первую объединенную международную конференцию "Суперкомпьютерные дни в России", Москва, 28-29 сентября 2015 г.