Последовательно-параллельный метод суммирования - История изменений

ASA в 10:13, 20 февраля 2025

2025-02-20T10:13:29Z

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

			{{algorithm
			\| name = Последовательно-параллельный метод суммирования
			\| serial_complexity = <math>n-1</math>
			\| pf_height = <math>O(\sqrt{n})</math>
			\| pf_width = <math>O(\sqrt{n})</math>
			\| input_data = <math>n</math>
			\| output_data = <math>1</math>
			}}

	Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]].		Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]].

ASA в 12:10, 8 июля 2022

2022-07-08T12:10:06Z

@@ Строка 1: / Строка 1: @@
 {{level-a}}
-Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|2.4]])
+Основные авторы описания: [[Участник:Frolov|А.В.Фролов]].
 == Свойства и структура алгоритма ==
@@ Строка 116: / Строка 116: @@
 Можно записать и аналогичные схемы, где суммирование будет проводиться в обратном порядке. Подчеркнём, что граф алгоритма обеих схем — [[#Информационный граф|один и тот же]]!
 === Возможные способы и особенности параллельной реализации алгоритма ===
-[https://gitlab.srcc.msu.ru/alex-teplov/Scalability/blob/master/arraysum/arraysum.c Исследованная реализация алгоритма на языке C]
+В чистом виде алгоритм последовательно-параллельного метода для суммирования массива встречается редко, в основном встречаются его модификации, например для случаев вычисления скалярного произведения (вместо элементов массива будут фигурировать произведения элементов двух массивов), равномерной нормы (вместо элементов массива — их модули) и т. п. В случае вычисления скалярного произведения в одном из частных случаев подобный приём применён в библиотеке BLAS (там одна из размерностей равна 5), но, видимо, не для распараллеливания, а для оптимизации работы с регистрами процессора. Между тем, разбиения массивов на группы для вычислений частных сумм могут быть полезны и для лучшего использования кэша на отдельных узлах.
-=== Динамические характеристики и эффективность реализации алгоритма ===
+=== Результаты прогонов ===
 === Выводы для классов архитектур ===
-В чистом виде алгоритм последовательно-параллельного метода для суммирования массива встречается редко, в основном встречаются его модификации, например для случаев вычисления скалярного произведения (вместо элементов массива будут фигурировать произведения элементов двух массивов), равномерной нормы (вместо элементов массива — их модули) и т. п. В случае вычисления скалярного произведения в одном из частных случаев подобный приём применён в библиотеке BLAS (там одна из размерностей равна 5), но, видимо, не для распараллеливания, а для оптимизации работы с регистрами процессора. Между тем, разбиения массивов на группы для вычислений частных сумм могут быть полезны и для лучшего использования кэша на отдельных узлах.
+== Литература ==
 <references />

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

2022-04-28T06:41:00Z

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

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

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

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

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

2022-04-28T06:40:24Z

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

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

	Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [~~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 здесь].		Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [https://gitlab.srcc.msu.ru/vadim/locality/blob/master/benchmarks/vectors_seqpar/vectors_seqpar.h здесь] (функция KernelOpSeqpar). Условия запуска описаны [https://gitlab.srcc.msu.ru/vadim/locality/blob/master/README.md здесь].

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

ASA в 14:27, 6 марта 2018

2018-03-06T14:27:36Z

← Предыдущая версия		Версия от 14:27, 6 марта 2018
Строка 1:		Строка 1:
			{{level-a}}

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

ASA в 10:00, 9 ноября 2017

2017-11-09T10:00:02Z

← Предыдущая версия		Версия от 10:00, 9 ноября 2017
Строка 173:		Строка 173:
	<references />		<references />

	[[Категория:~~Статьи в работе~~]]		[[Категория:Законченные статьи]]
	[[Категория:Последовательно-параллельная группировка операций]]		[[Категория:Последовательно-параллельная группировка операций]]
	[[Категория:Векторные операции]]		[[Категория:Векторные операции]]

	[[En:The serial-parallel summation method]]		[[En:The serial-parallel summation method]]

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

2017-10-27T08:27:42Z

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

← Предыдущая версия		Версия от 08:27, 27 октября 2017
Строка 160:		Строка 160:
	* По числу процессов: -9.432e-07 – при увеличении числа процессов эффективность уменьшается на рассмотренной области изменений параметров запуска, однако, в целом уменьшение не интенсивное. Это объясняется тем, что при увеличении числа процессов сильно возрастает доля накладных расходов на организацию схемы сдваивания сумирования, однако, так как общая эффективность составляет доли процента интенсивность сильная только при переходе от работы процессов в рамках одного физического узла к использованию коммуникационной сети. В остальной области рассмотренных значений параметров запуска эффективность близка к 0 в силу того, что на каждый процесс приходится черезвычайно малая доля вычислений. Больше полезного времени уходит на организацию работы процессов.		* По числу процессов: -9.432e-07 – при увеличении числа процессов эффективность уменьшается на рассмотренной области изменений параметров запуска, однако, в целом уменьшение не интенсивное. Это объясняется тем, что при увеличении числа процессов сильно возрастает доля накладных расходов на организацию схемы сдваивания сумирования, однако, так как общая эффективность составляет доли процента интенсивность сильная только при переходе от работы процессов в рамках одного физического узла к использованию коммуникационной сети. В остальной области рассмотренных значений параметров запуска эффективность близка к 0 в силу того, что на каждый процесс приходится черезвычайно малая доля вычислений. Больше полезного времени уходит на организацию работы процессов.
	* По размеру задачи: 1.881e-06 – при увеличении размера задачи эффективность в целом очень незначительно увеличивается по рассматриваемой области. Это объясняется общим увеличением вычислительной сложности задачи в связи с увеличением размерности. Однако вычислительная сложность алгоритма <math>(N-1)</math>не позволяет существенно увеличить долю времени затрачиваемую на вычисления.		* По размеру задачи: 1.881e-06 – при увеличении размера задачи эффективность в целом очень незначительно увеличивается по рассматриваемой области. Это объясняется общим увеличением вычислительной сложности задачи в связи с увеличением размерности. Однако вычислительная сложность алгоритма <math>(N-1)</math>не позволяет существенно увеличить долю времени затрачиваемую на вычисления.
	* По двум направлениям: -1.423e-07 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, однако интенсивность уменьшения эффективности небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров несущественная говорит о том, что на поверхности присутствуют области с очень интенсивным изменением эффективности на участке 2-16 процессов, но очень малые по площади. На остальной поверхности изменения эффективности незначительны и находятся на приблизительно одном и том же уровне.		* По двум направлениям: -1.423e-07 – при рассмотрении увеличения как вычислительной сложности, так и числа процессов по всей рассмотренной области значений эффективность уменьшается, однако интенсивность уменьшения эффективности небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров несущественная говорит о том, что на поверхности присутствуют области с очень интенсивным изменением эффективности на участке 2-16 процессов, но очень малые по площади. На остальной поверхности изменения эффективности незначительны и находятся на приблизительно одном и том же уровне.

	[http://git.algowiki-project.org/Teplov/Scalability/blob/master/arraysum/arraysum.c Исследованная реализация алгоритма на языке C]		[http://git.algowiki-project.org/Teplov/Scalability/blob/master/arraysum/arraysum.c Исследованная реализация алгоритма на языке C]

ASA: Отмена правки 23586, сделанной участником Ikramov (обс.)

2017-10-27T08:26:25Z

Отмена правки 23586, сделанной участником Ikramov (обс.)

← Предыдущая версия		Версия от 08:26, 27 октября 2017
Строка 150:		Строка 150:
	==== Масштабируемость реализации алгоритма ====		==== Масштабируемость реализации алгоритма ====
	[[file:Масштабируемость производительность ссумирования элементов массива.png\|thumb\|center\|700px\|Рисунок 6. Параллельная реализация Сумирования элементов массива Максимальная производительность. ]]		[[file:Масштабируемость производительность ссумирования элементов массива.png\|thumb\|center\|700px\|Рисунок 6. Параллельная реализация Сумирования элементов массива Максимальная производительность. ]]
	[[file:Масштабируемость суммирования элементов массива Эффективность.png\|thumb\|center\|700px\|Рисунок 7. Параллельная реализация сумирования элементов массива Максимальная эффективность. ]]		[[file:Масштабируемость суммирования элементов массива Эффективность.png\|thumb\|center\|700px\|Рисунок 7. Параллельная реализация сумирования элементов массива Максимальная эффективность. ]]
			Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
	~~Variable parameters for the launch of the algorithm implementation and the limits of parameter variations~~:		* число процессоров [2 : 256]
	* ~~number of processors~~ [2 : 256]		* размер вектора [80000000:320000000]
	* ~~vector size~~ [80000000:320000000]		Эффективность выполнения реализации алгоритма
	~~Efficiency of algorithm implementation execution~~		* Минимальная эффективность 0,00004%
	* ~~Minimum efficiency:~~ 0,00004%		* Максимальная эффективность 0,0037%
	* ~~Maximum efficiency:~~ 0,0037%		Оценка масштабируемости
	~~Scalability assessment~~
	* По числу процессов: -9.432e-07 – при увеличении числа процессов эффективность уменьшается на рассмотренной области изменений параметров запуска, однако, в целом уменьшение не интенсивное. Это объясняется тем, что при увеличении числа процессов сильно возрастает доля накладных расходов на организацию схемы сдваивания сумирования, однако, так как общая эффективность составляет доли процента интенсивность сильная только при переходе от работы процессов в рамках одного физического узла к использованию коммуникационной сети. В остальной области рассмотренных значений параметров запуска эффективность близка к 0 в силу того, что на каждый процесс приходится черезвычайно малая доля вычислений. Больше полезного времени уходит на организацию работы процессов.		* По числу процессов: -9.432e-07 – при увеличении числа процессов эффективность уменьшается на рассмотренной области изменений параметров запуска, однако, в целом уменьшение не интенсивное. Это объясняется тем, что при увеличении числа процессов сильно возрастает доля накладных расходов на организацию схемы сдваивания сумирования, однако, так как общая эффективность составляет доли процента интенсивность сильная только при переходе от работы процессов в рамках одного физического узла к использованию коммуникационной сети. В остальной области рассмотренных значений параметров запуска эффективность близка к 0 в силу того, что на каждый процесс приходится черезвычайно малая доля вычислений. Больше полезного времени уходит на организацию работы процессов.
	* По размеру задачи: 1.881e-06 – при увеличении размера задачи эффективность в целом очень незначительно увеличивается по рассматриваемой области. Это объясняется общим увеличением вычислительной сложности задачи в связи с увеличением размерности. Однако вычислительная сложность алгоритма <math>(N-1)</math>не позволяет существенно увеличить долю времени затрачиваемую на вычисления.		* По размеру задачи: 1.881e-06 – при увеличении размера задачи эффективность в целом очень незначительно увеличивается по рассматриваемой области. Это объясняется общим увеличением вычислительной сложности задачи в связи с увеличением размерности. Однако вычислительная сложность алгоритма <math>(N-1)</math>не позволяет существенно увеличить долю времени затрачиваемую на вычисления.

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

2017-10-25T16:34:00Z

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

← Предыдущая версия		Версия от 16:34, 25 октября 2017
Строка 150:		Строка 150:
	==== Масштабируемость реализации алгоритма ====		==== Масштабируемость реализации алгоритма ====
	[[file:Масштабируемость производительность ссумирования элементов массива.png\|thumb\|center\|700px\|Рисунок 6. Параллельная реализация Сумирования элементов массива Максимальная производительность. ]]		[[file:Масштабируемость производительность ссумирования элементов массива.png\|thumb\|center\|700px\|Рисунок 6. Параллельная реализация Сумирования элементов массива Максимальная производительность. ]]
	[[file:Масштабируемость суммирования элементов массива Эффективность.png\|thumb\|center\|700px\|Рисунок 7. Параллельная реализация сумирования элементов массива Максимальная эффективность. ]]		[[file:Масштабируемость суммирования элементов массива Эффективность.png\|thumb\|center\|700px\|Рисунок 7. Параллельная реализация сумирования элементов массива Максимальная эффективность. ]]
	~~Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма~~:
	* ~~число процессоров~~ [2 : 256]		Variable parameters for the launch of the algorithm implementation and the limits of parameter variations:
	* ~~размер вектора~~ [80000000:320000000]		* number of processors [2 : 256]
	~~Эффективность выполнения реализации алгоритма~~		* vector size [80000000:320000000]
	* ~~Минимальная эффективность~~ 0,00004%		Efficiency of algorithm implementation execution
	* ~~Максимальная эффективность~~ 0,0037%		* Minimum efficiency: 0,00004%
	~~Оценка масштабируемости~~		* Maximum efficiency: 0,0037%
			Scalability assessment
	* По числу процессов: -9.432e-07 – при увеличении числа процессов эффективность уменьшается на рассмотренной области изменений параметров запуска, однако, в целом уменьшение не интенсивное. Это объясняется тем, что при увеличении числа процессов сильно возрастает доля накладных расходов на организацию схемы сдваивания сумирования, однако, так как общая эффективность составляет доли процента интенсивность сильная только при переходе от работы процессов в рамках одного физического узла к использованию коммуникационной сети. В остальной области рассмотренных значений параметров запуска эффективность близка к 0 в силу того, что на каждый процесс приходится черезвычайно малая доля вычислений. Больше полезного времени уходит на организацию работы процессов.		* По числу процессов: -9.432e-07 – при увеличении числа процессов эффективность уменьшается на рассмотренной области изменений параметров запуска, однако, в целом уменьшение не интенсивное. Это объясняется тем, что при увеличении числа процессов сильно возрастает доля накладных расходов на организацию схемы сдваивания сумирования, однако, так как общая эффективность составляет доли процента интенсивность сильная только при переходе от работы процессов в рамках одного физического узла к использованию коммуникационной сети. В остальной области рассмотренных значений параметров запуска эффективность близка к 0 в силу того, что на каждый процесс приходится черезвычайно малая доля вычислений. Больше полезного времени уходит на организацию работы процессов.
	* По размеру задачи: 1.881e-06 – при увеличении размера задачи эффективность в целом очень незначительно увеличивается по рассматриваемой области. Это объясняется общим увеличением вычислительной сложности задачи в связи с увеличением размерности. Однако вычислительная сложность алгоритма <math>(N-1)</math>не позволяет существенно увеличить долю времени затрачиваемую на вычисления.		* По размеру задачи: 1.881e-06 – при увеличении размера задачи эффективность в целом очень незначительно увеличивается по рассматриваемой области. Это объясняется общим увеличением вычислительной сложности задачи в связи с увеличением размерности. Однако вычислительная сложность алгоритма <math>(N-1)</math>не позволяет существенно увеличить долю времени затрачиваемую на вычисления.

ASA в 07:00, 24 октября 2017

2017-10-24T07:00:28Z

← Предыдущая версия		Версия от 07:00, 24 октября 2017
Строка 176:		Строка 176:
	[[Категория:Последовательно-параллельная группировка операций]]		[[Категория:Последовательно-параллельная группировка операций]]
	[[Категория:Векторные операции]]		[[Категория:Векторные операции]]

			[[En:The serial-parallel summation method]]