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

ASA в 13:26, 19 февраля 2025

2025-02-19T13:26:24Z

← Предыдущая версия		Версия от 13:26, 19 февраля 2025
Строка 1:		Строка 1:
	{{level-a}}		{{level-a}}

			{{algorithm
			\| name = Нахождение суммы элементов массива сдваиванием
			\| serial_complexity = <math>n-1</math>
			\| pf_height = <math>log2n</math>
			\| pf_width = <math>n/2</math>
			\| input_data = <math>n</math>
			\| output_data = <math>1</math>
			}}

	Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]].		Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]].
Строка 31:		Строка 40:
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

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

	=== Информационный граф ===		=== Информационный граф ===
Строка 51:		Строка 60:
	Дополнительные ограничения: отсутствуют.		Дополнительные ограничения: отсутствуют.

	Объём входных данных: <nowiki/><math>N</math>.		Объём входных данных: <nowiki/><math>n</math>.

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

ASA в 09:51, 8 июля 2022

2022-07-08T09:51:59Z

@@ Строка 1: / Строка 1: @@
 {{level-a}}
-Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|2.4]])
+Основные авторы описания: [[Участник:Frolov|А.В.Фролов]].
 == Свойства и структура алгоритма ==
@@ Строка 64: / Строка 64: @@
 === Особенности реализации последовательного алгоритма ===
 === Возможные способы и особенности параллельной реализации алгоритма ===
-=== Масштабируемость алгоритма и его реализации ===
+=== Результаты прогонов ===
 === Выводы для классов архитектур ===
 == Литература ==
 <references />

ASA: /* Масштабируемость реализации алгоритма */

2022-04-28T06:48:00Z

Масштабируемость реализации алгоритма

← Предыдущая версия		Версия от 06:48, 28 апреля 2022
Строка 105:		Строка 105:
	* По двум направлениям: -8.047e-08 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, однако интенсивность уменьшения эффективности небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров несущественная говорит о том, что на поверхности присутствуют области с очень интенсивным изменением эффективности на участке 2-16 процессов, но очень малые по площади. На остальной поверхности изменения эффективности незначительны и находятся на приблизительно одном и том же уровне.		* По двум направлениям: -8.047e-08 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, однако интенсивность уменьшения эффективности небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров несущественная говорит о том, что на поверхности присутствуют области с очень интенсивным изменением эффективности на участке 2-16 процессов, но очень малые по площади. На остальной поверхности изменения эффективности незначительны и находятся на приблизительно одном и том же уровне.

	[~~http~~://~~git~~.~~algowiki-project~~.~~org~~/~~Teplov~~/Scalability/blob/master/doublesum/doublesum.c Исследованная параллельная реализация на языке C]		[https://gitlab.srcc.msu.ru/alex-teplov/Scalability/blob/master/doublesum/doublesum.c Исследованная параллельная реализация на языке C]

	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===

ASA: /* Количественная оценка локальности */

2022-04-28T06:43:51Z

Количественная оценка локальности

← Предыдущая версия		Версия от 06:43, 28 апреля 2022
Строка 74:		Строка 74:
	===== Количественная оценка локальности =====		===== Количественная оценка локальности =====

	Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [~~http~~://~~git~~.~~algowiki-project~~.~~org~~/~~Voevodin~~/locality/blob/master/benchmarks/vectors/vectors.h здесь] (функция KernelOpD). Условия запуска описаны [~~http~~://~~git~~.~~algowiki-project~~.~~org~~/~~Voevodin~~/locality/blob/master/README.md здесь].		Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [https://gitlab.srcc.msu.ru/vadim/locality/blob/master/benchmarks/vectors/vectors.h здесь] (функция KernelOpD). Условия запуска описаны [https://gitlab.srcc.msu.ru/vadim/locality/blob/master/README.md здесь].

	Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.		Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.

ASA в 11:04, 14 марта 2018

2018-03-14T11:04:46Z

← Предыдущая версия		Версия от 11:04, 14 марта 2018
Строка 118:		Строка 118:
	[[Категория:Векторные операции]]		[[Категория:Векторные операции]]

	[[En:Pairwise summation]]		[[En:Pairwise summation of numbers]]

Frolov в 13:18, 6 ноября 2017

2017-11-06T13:18:40Z

← Предыдущая версия		Версия от 13:18, 6 ноября 2017
Строка 19:		Строка 19:
	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===

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

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

Frolov в 13:17, 6 ноября 2017

2017-11-06T13:17:35Z

← Предыдущая версия		Версия от 13:17, 6 ноября 2017
Строка 1:		Строка 1:
			{{level-a}}

	Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]], [[Участник:VadimVV\|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений\|раздел 2.2]]), [[Участник:Teplov\|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации\|2.4]])		Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]], [[Участник:VadimVV\|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений\|раздел 2.2]]), [[Участник:Teplov\|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации\|2.4]])

AntonChupin в 13:26, 8 июля 2016

2016-07-08T13:26:34Z

← Предыдущая версия		Версия от 13:26, 8 июля 2016
Строка 114:		Строка 114:
	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]
	[[Категория:Метод сдваивания]]		[[Категория:Метод сдваивания]]
			[[Категория:Векторные операции]]

	[[En:Pairwise summation]]		[[En:Pairwise summation]]

ASA в 08:51, 29 июля 2015

2015-07-29T08:51:00Z

ASA в 14:42, 28 июля 2015

2015-07-28T14:42:18Z

← Предыдущая версия		Версия от 14:42, 28 июля 2015
Строка 1:		Строка 1:
	Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]], [[Участник:VadimVV\|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений\|раздел 2.2]]), [[Участник:Teplov\|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации\|2.4]])		Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]], [[Участник:VadimVV\|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений\|раздел 2.2]]), [[Участник:Teplov\|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации\|2.4]])

	== ~~Описание свойств~~ и ~~структуры~~ алгоритма ==		== Свойства и структура алгоритма ==

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

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

	Исходные данные: одномерный массив <math>n</math> чисел.		Исходные данные: одномерный массив <math>n</math> чисел.
Строка 23:		Строка 23:
	Как уже записано в описании ядра алгоритма, основную часть метода составляют рекурсивные вызовы сумм массивов меньшей размерности.		Как уже записано в описании ядра алгоритма, основную часть метода составляют рекурсивные вызовы сумм массивов меньшей размерности.

	=== ~~Описание схемы~~ реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===

	В своём чистом виде суммирование сдваиванием редко используют при последовательной реализации, поскольку при этом усложняется общая схема алгоритма и резко растёт потребность в памяти, нужной для хранения промежуточных данных.		В своём чистом виде суммирование сдваиванием редко используют при последовательной реализации, поскольку при этом усложняется общая схема алгоритма и резко растёт потребность в памяти, нужной для хранения промежуточных данных.
Строка 38:		Строка 38:
	[[file:binary-tree-based summation graph.png\|center\|thumb\|500px\|Суммирование массива методом сдваивания]]		[[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>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>).
Строка 59:		Строка 59:
	Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является <math>\frac{n}{\log_2 n}</math> (отношение линейной к логарифмической). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм полностью детерминирован. Дуги информационного графа нелокальны, от яруса к ярусу наблюдается показательный рост их длины, при любом размещении вершин графа.		Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является <math>\frac{n}{\log_2 n}</math> (отношение линейной к логарифмической). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм полностью детерминирован. Дуги информационного графа нелокальны, от яруса к ярусу наблюдается показательный рост их длины, при любом размещении вершин графа.

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

	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	=== ~~Описание локальности~~ данных и вычислений ===		=== Локальность данных и вычислений ===
	==== ~~Описание локальности~~ реализации алгоритма ====		==== Локальность реализации алгоритма ====
	===== ~~Описание структуры~~ обращений в память и качественная оценка локальности =====		===== Структура обращений в память и качественная оценка локальности =====

	[[file:Sum doub prof.png\|thumb\|center\|700px\|Рисунок 12.1. Суммирование сдваиванием. Общий профиль обращений в память]]		[[file:Sum doub prof.png\|thumb\|center\|700px\|Рисунок 12.1. Суммирование сдваиванием. Общий профиль обращений в память]]
Строка 86:		Строка 86:
	[[file:Sum doub cvg.png\|thumb\|center\|700px\|Рисунок 12.2. Сравнение значений оценки cvg]]		[[file:Sum doub cvg.png\|thumb\|center\|700px\|Рисунок 12.2. Сравнение значений оценки cvg]]

	=== Возможные способы и особенности реализации ~~параллельного~~ алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	==== ~~Описание масштабируемости~~ алгоритма ====		==== Масштабируемость алгоритма ====
	==== ~~Описание масштабируемости~~ реализации алгоритма ====		==== Масштабируемость реализации алгоритма ====
	[[file:Масштабируемость сумирования схемой сдваивания производительность.png\|thumb\|center\|700px\|Рисунок 1. Параллельная реализация Сумирования схемой сдваивания Максимальная производительность. ]]		[[file:Масштабируемость сумирования схемой сдваивания производительность.png\|thumb\|center\|700px\|Рисунок 1. Параллельная реализация Сумирования схемой сдваивания Максимальная производительность. ]]
	[[file:Масштабируемость Сумирования сдваиванием эффективность.png\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация сумирования схемой сдваивания Максимальная эффективность. ]]		[[file:Масштабируемость Сумирования сдваиванием эффективность.png\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация сумирования схемой сдваивания Максимальная эффективность. ]]
Строка 108:		Строка 108:
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===


	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]

← Предыдущая версия		Версия от 08:51, 29 июля 2015
Строка 33:		Строка 33:
	=== Информационный граф ===		=== Информационный граф ===

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

	[[file:binary-tree-based summation graph.png\|center\|thumb\|500px\|Суммирование массива методом сдваивания]]		[[file:binary-tree-based summation graph.png\|center\|thumb\|500px\|Рисунок 1. Суммирование массива методом сдваивания]]

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
Строка 66:		Строка 66:
	===== Структура обращений в память и качественная оценка локальности =====		===== Структура обращений в память и качественная оценка локальности =====

	[[file:Sum doub prof.png\|thumb\|center\|700px\|Рисунок ~~12.1~~. Суммирование сдваиванием. Общий профиль обращений в память]]		[[file:Sum doub prof.png\|thumb\|center\|700px\|Рисунок 2. Суммирование сдваиванием. Общий профиль обращений в память]]

	На рис. ~~12.1~~ представлен профиль обращений в память для реализации суммирования элементов массива методом сдваивания. Данный профиль устроен достаточно просто – он представляет собой набор итераций, на каждой итерации происходит последовательный перебор элементов массива с некоторым шагом, причем с каждой следующей итерацией шаг увеличивается вдвое. Этим обуславливается тот факт, что на рис. ~~12.1~~ каждая следующая прямая расположена под большим углом. Подобный профиль обладает достаточно высокой пространственной локальностью, поскольку большая часть обращений происходит к соседним или близким элементам. Однако при этом временная локальность низка – к половине элементов обращения происходят только однажды, к четверти – дважды и т.д.		На рис.2 представлен профиль обращений в память для реализации суммирования элементов массива методом сдваивания. Данный профиль устроен достаточно просто – он представляет собой набор итераций, на каждой итерации происходит последовательный перебор элементов массива с некоторым шагом, причем с каждой следующей итерацией шаг увеличивается вдвое. Этим обуславливается тот факт, что на рис.2 каждая следующая прямая расположена под большим углом. Подобный профиль обладает достаточно высокой пространственной локальностью, поскольку большая часть обращений происходит к соседним или близким элементам. Однако при этом временная локальность низка – к половине элементов обращения происходят только однажды, к четверти – дважды и т.д.

	===== Количественная оценка локальности =====		===== Количественная оценка локальности =====
Строка 76:		Строка 76:
	Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.		Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.

	На ~~рисунке 12~~.2 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что из-за низкой временной локальности значение daps для данной программы находится на уровне самых неэффективных вариантов реализации перемножения матриц и лишь немногим лучше реализации программы со случайным доступом.		На рис.3 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что из-за низкой временной локальности значение daps для данной программы находится на уровне самых неэффективных вариантов реализации перемножения матриц и лишь немногим лучше реализации программы со случайным доступом.

	[[file:Sum doub daps.png\|thumb\|center\|700px\|Рисунок ~~12.2~~. Сравнение значений оценки daps]]		[[file:Sum doub daps.png\|thumb\|center\|700px\|Рисунок 3. Сравнение значений оценки daps]]

	Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.		Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.

	На ~~рисунке 12~~.3 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, локальность реализации суммирования сдваиванием достаточно низка, что согласуется с результатами по оценке daps и анализом самого профиля обращений.		На рис.4 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что, согласно данной оценке, локальность реализации суммирования сдваиванием достаточно низка, что согласуется с результатами по оценке daps и анализом самого профиля обращений.

	[[file:Sum doub cvg.png\|thumb\|center\|700px\|Рисунок ~~12.2~~. Сравнение значений оценки cvg]]		[[file:Sum doub cvg.png\|thumb\|center\|700px\|Рисунок 4. Сравнение значений оценки cvg]]

	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
Строка 90:		Строка 90:
	==== Масштабируемость алгоритма ====		==== Масштабируемость алгоритма ====
	==== Масштабируемость реализации алгоритма ====		==== Масштабируемость реализации алгоритма ====
	[[file:Масштабируемость сумирования схемой сдваивания производительность.png\|thumb\|center\|700px\|Рисунок 1. Параллельная реализация Сумирования схемой сдваивания Максимальная производительность. ]]		[[file:Масштабируемость сумирования схемой сдваивания производительность.png\|thumb\|center\|700px\|Рисунок 5. Параллельная реализация Сумирования схемой сдваивания Максимальная производительность. ]]
	[[file:Масштабируемость Сумирования сдваиванием эффективность.png\|thumb\|center\|700px\|Рисунок 2. Параллельная реализация сумирования схемой сдваивания Максимальная эффективность. ]]		[[file:Масштабируемость Сумирования сдваиванием эффективность.png\|thumb\|center\|700px\|Рисунок 6. Параллельная реализация сумирования схемой сдваивания Максимальная эффективность. ]]
	Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:		Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
	* число процессоров [2 : 256]		* число процессоров [2 : 256]
Строка 108:		Строка 108:
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

			== Литература ==
			<references />

	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]