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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][досмотренная версия]
м (формулы, разметка)
 
(не показано 25 промежуточных версий 8 участников)
Строка 1: Строка 1:
== Описание свойств и структуры алгоритма ==
+
{{level-a}}
  
=== Словесное описание алгоритма ===
+
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]].
 +
 
 +
== Свойства и структура алгоритма ==
 +
 
 +
=== Общее описание алгоритма ===
  
 
'''Метод сдваивания''' используется в качестве быстрого варианта вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря как наименьшей из возможных высоте алгортима, так и из-за ряда своих вычислительных характеристик, а также (в среде нечисленных алгоритмов) из-за своей рекурсивности, то есть лёгкости записи.
 
'''Метод сдваивания''' используется в качестве быстрого варианта вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря как наименьшей из возможных высоте алгортима, так и из-за ряда своих вычислительных характеристик, а также (в среде нечисленных алгоритмов) из-за своей рекурсивности, то есть лёгкости записи.
  
=== Математическое описание ===
+
=== Математическое описание алгоритма ===
  
 
Исходные данные: одномерный массив <math>n</math> чисел.
 
Исходные данные: одномерный массив <math>n</math> чисел.
Строка 15: Строка 19:
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
  
Вычислительное ядро последовательно-параллельного метода суммирования можно составить как из элементарных бинарных (всего <math>n - 1</math>) вычислений сумм, так и (рекуррентно) из набора реализаций метода сдваивания меньших размерностей.
+
Вычислительное ядро метода сдваивания для суммирования можно составить как из элементарных бинарных (всего <math>n - 1</math>) вычислений сумм, так и (рекуррентно) из набора реализаций метода сдваивания меньших размерностей.
  
 
=== Макроструктура алгоритма ===
 
=== Макроструктура алгоритма ===
Строка 21: Строка 25:
 
Как уже записано в описании ядра алгоритма, основную часть метода составляют рекурсивные вызовы сумм массивов меньшей размерности.
 
Как уже записано в описании ядра алгоритма, основную часть метода составляют рекурсивные вызовы сумм массивов меньшей размерности.
  
=== Описание схемы реализации последовательного алгоритма ===
+
=== Схема реализации последовательного алгоритма ===
  
 
В своём чистом виде суммирование сдваиванием редко используют при последовательной реализации, поскольку при этом усложняется общая схема алгоритма и резко растёт потребность в памяти, нужной для хранения промежуточных данных.
 
В своём чистом виде суммирование сдваиванием редко используют при последовательной реализации, поскольку при этом усложняется общая схема алгоритма и резко растёт потребность в памяти, нужной для хранения промежуточных данных.
Строка 31: Строка 35:
 
=== Информационный граф ===
 
=== Информационный граф ===
  
Опишем граф алгоритма в виде рисунка. В данном случае выполнено суммирование 16 элементов массива.
+
На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 16 элементов массива.
 +
Вершины, соответствующие входным данным, даны синим цветом, выходным данным - красным цветом.
  
[[file:binary-tree-based summation graph.png|center|thumb|500px]]
+
[[file:binary-tree-based summation graph.png|center|thumb|500px|Рисунок 1. Суммирование массива методом сдваивания]]
  
=== Описание ресурса параллелизма алгоритма ===
+
=== Ресурс параллелизма алгоритма ===
  
 
Для суммирования массива порядка <math>n</math> методом сдваивания в параллельном варианте требуется последовательно выполнить <math>\lceil \log_2 n \rceil</math> ярусов с убывающим (от <math>\frac{n}{2}</math> до <math>1</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>).
Строка 56: Строка 61:
 
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является <math>\frac{n}{\log_2 n}</math> (отношение линейной к логарифмической). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм полностью детерминирован. Дуги информационного графа нелокальны, от яруса к ярусу наблюдается показательный рост их длины, при любом размещении вершин графа.  
 
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является <math>\frac{n}{\log_2 n}</math> (отношение линейной к логарифмической). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм полностью детерминирован. Дуги информационного графа нелокальны, от яруса к ярусу наблюдается показательный рост их длины, при любом размещении вершин графа.  
  
== Программная реализация ==
+
== Программная реализация алгоритма ==
  
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
+
 
==== Описание локальности алгоритма ====
+
=== Возможные способы и особенности параллельной реализации алгоритма ===
==== Описание локальности реализации алгоритма ====
+
=== Результаты прогонов ===
===== Описание структуры обращений в память и качественная оценка локальности =====
 
===== Количественная оценка локальности =====
 
===== Анализ на основе теста Apex-Map =====
 
=== Возможные способы и особенности реализации параллельного алгоритма ===
 
=== Масштабируемость алгоритма и его реализации ===
 
==== Описание масштабируемости алгоритма ====
 
==== Описание масштабируемости реализации алгоритма ====
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
+
 
 +
== Литература ==
 +
 
 +
<references />
 +
 
 +
[[Категория:Статьи в работе]]
 +
[[Категория:Метод сдваивания]]
 +
[[Категория:Векторные операции]]
 +
 
 +
[[En:Pairwise summation of numbers]]

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


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

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

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

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

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

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

Вычисляемые данные: сумма элементов массива.

Формулы метода: элементы на каждом этапе алгоритма разбиваются на пары. В каждой из пар находится сумма составляющих её элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д.

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

Вычислительное ядро метода сдваивания для суммирования можно составить как из элементарных бинарных (всего [math]n - 1[/math]) вычислений сумм, так и (рекуррентно) из набора реализаций метода сдваивания меньших размерностей.

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

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

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

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

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

Для вычисления суммы массива, состоящего из [math]N[/math] элементов, при любых разложениях [math]N[/math] на пары суть алгоритма сводится к простому переставлению скобок в формуле суммирования, и количество операций неизменно и равно [math]N - 1[/math]. Поэтому алгоритм должен быть отнесён к алгоритмам линейной сложности по количеству последовательных операций.

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

На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 16 элементов массива. Вершины, соответствующие входным данным, даны синим цветом, выходным данным - красным цветом.

Рисунок 1. Суммирование массива методом сдваивания

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

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

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

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

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

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

Выходные данные: сумма элементов массива.

Объём выходных данных: один скаляр.

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

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

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

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

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

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

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

3 Литература