Приложение 7 - История изменений

ASA: Полностью удалено содержимое страницы

2015-09-17T08:15:31Z

Полностью удалено содержимое страницы

← Предыдущая версия		Версия от 08:15, 17 сентября 2015
Строка 1:		Строка 1:
	~~= Последовательно-параллельный метод суммирования =~~

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

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

	'''Последовательно-параллельный метод''' используется в качестве эрзаца блочной реализации вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря следующим особенностям: а) реализует приём получения двойных циклов из одинарных; б) в последовательной архитектуре компьютеров позволял для ряда операций уменьшать влияние округления на результат. Здесь будем описывать его версию для суммирования чисел.

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

	~~Исходные данные: одномерный массив <math>N</math> чисел.~~

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

	Формулы метода: число <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>.

	После этого на <math>i</math>-м процессоре (<math>i < p</math>) последовательно вычисляется сумма элементов массива, начиная с <math>(i - 1) k + 1</math>-го, до <math>i k</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>-го.
	~~:<math>S_p = \sum_{j = 1}^q x_{k (p - 1) + j}</math>~~

	По окончании этого процесса процессоры обмениваются данными и на одном из них (либо на всех одновременно, если результат нужен далее на всех процессорах) получившиеся суммы суммируются последовательно друг с другом.
	~~:<math>\sum_{i = 1}^p S_i</math>~~

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

	Вычислительное ядро последовательно-параллельного метода суммирования можно составить из множественных (всего <math>p</math>) вычислений сумм элементов массива:
	~~:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>~~

	~~и ещё одного вычисления суммы элементов частичных сумм~~
	~~:<math>\sum_{i = 1}^p S_i</math>~~

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

	Как уже записано в описании ядра алгоритма, основную часть метода составляют множественные (всего <math>p + 1</math>) вычисления сумм
	~~:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>~~
	~~:<math>\sum_{i = 1}^p S_i</math>~~

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

	Формулы метода описаны выше. Последовательность исполнения суммирования может быть разная — как по возрастанию, так и по убыванию индексов. Обычно без особых причин порядок не меняют, используя естественный (возрастание индексов).

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

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

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

	~~На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 30 элементов массива.~~

	~~[[file:series-parallel summation graph.png\|center\|thumb\|600px\|Рисунок 1. Последовательно-параллельный метод суммирования массива]]~~

	~~=== Описание ресурса параллелизма алгоритма ===~~

	Для суммирования массива порядка <math>n</math> последовательно-параллельным методом в параллельном варианте требуется последовательно выполнить следующие ярусы:
	* <math>k - 1</math> ярусов суммирования по частям массива (<math>p</math> ветвей),
	* <math>p - 1</math> ярусов суммирования (одна последовательная ветвь).

	Таким образом, в параллельном варианте критический путь алгоритма (и соответствующая ему высота ЯПФ) будет зависеть от произведённого разбиения массива на части. В оптимальном случае (<math>p = \sqrt{n}</math>) высота ЯПФ будет равна <math>2 \sqrt{n} - 2</math>.

	При классификации по высоте ЯПФ, таким образом, последовательно-параллельный метод относится к алгоритмам со сложностью ''корень квадратный''. При классификации по ширине ЯПФ его сложность будет такой же — ''корень квадратный''.

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

	~~Входные данные: массив <math>\vec{x}</math> (элементы <math>x_i</math>).~~

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

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

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

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

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

	Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''корнем квадратным'' (отношение линейной к корню квадратному). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм не вполне полностью детерминирован, суммирование может быть проведено в разном порядке. Использование другого порядка выполнения ассоциативных операций может дать, с учётом особенностей входных данных, уменьшение влияния ошибок округления на результат. Дуги информационного графа локальны.

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

ASA в 08:15, 17 сентября 2015

2015-09-17T08:15:03Z

← Предыдущая версия	Версия от 08:15, 17 сентября 2015
Строка 1:	Строка 1:
		= Последовательно-параллельный метод суммирования =

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

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

		'''Последовательно-параллельный метод''' используется в качестве эрзаца блочной реализации вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря следующим особенностям: а) реализует приём получения двойных циклов из одинарных; б) в последовательной архитектуре компьютеров позволял для ряда операций уменьшать влияние округления на результат. Здесь будем описывать его версию для суммирования чисел.

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

		Исходные данные: одномерный массив <math>N</math> чисел.

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

		Формулы метода: число <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>.

		После этого на <math>i</math>-м процессоре (<math>i < p</math>) последовательно вычисляется сумма элементов массива, начиная с <math>(i - 1) k + 1</math>-го, до <math>i k</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>-го.
		:<math>S_p = \sum_{j = 1}^q x_{k (p - 1) + j}</math>

		По окончании этого процесса процессоры обмениваются данными и на одном из них (либо на всех одновременно, если результат нужен далее на всех процессорах) получившиеся суммы суммируются последовательно друг с другом.
		:<math>\sum_{i = 1}^p S_i</math>

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

		Вычислительное ядро последовательно-параллельного метода суммирования можно составить из множественных (всего <math>p</math>) вычислений сумм элементов массива:
		:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>

		и ещё одного вычисления суммы элементов частичных сумм
		:<math>\sum_{i = 1}^p S_i</math>

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

		Как уже записано в описании ядра алгоритма, основную часть метода составляют множественные (всего <math>p + 1</math>) вычисления сумм
		:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>
		:<math>\sum_{i = 1}^p S_i</math>

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

		Формулы метода описаны выше. Последовательность исполнения суммирования может быть разная — как по возрастанию, так и по убыванию индексов. Обычно без особых причин порядок не меняют, используя естественный (возрастание индексов).

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

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

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

		На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 30 элементов массива.

		[[file:series-parallel summation graph.png\|center\|thumb\|600px\|Рисунок 1. Последовательно-параллельный метод суммирования массива]]

		=== Описание ресурса параллелизма алгоритма ===

		Для суммирования массива порядка <math>n</math> последовательно-параллельным методом в параллельном варианте требуется последовательно выполнить следующие ярусы:
		* <math>k - 1</math> ярусов суммирования по частям массива (<math>p</math> ветвей),
		* <math>p - 1</math> ярусов суммирования (одна последовательная ветвь).

		Таким образом, в параллельном варианте критический путь алгоритма (и соответствующая ему высота ЯПФ) будет зависеть от произведённого разбиения массива на части. В оптимальном случае (<math>p = \sqrt{n}</math>) высота ЯПФ будет равна <math>2 \sqrt{n} - 2</math>.

		При классификации по высоте ЯПФ, таким образом, последовательно-параллельный метод относится к алгоритмам со сложностью ''корень квадратный''. При классификации по ширине ЯПФ его сложность будет такой же — ''корень квадратный''.

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

		Входные данные: массив <math>\vec{x}</math> (элементы <math>x_i</math>).

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

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

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

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

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

		Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''корнем квадратным'' (отношение линейной к корню квадратному). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм не вполне полностью детерминирован, суммирование может быть проведено в разном порядке. Использование другого порядка выполнения ассоциативных операций может дать, с учётом особенностей входных данных, уменьшение влияния ошибок округления на результат. Дуги информационного графа локальны.

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

ASA: Полностью удалено содержимое страницы

2015-09-16T14:05:27Z

Полностью удалено содержимое страницы

← Предыдущая версия		Версия от 14:05, 16 сентября 2015
Строка 1:		Строка 1:
	~~= Последовательно-параллельный метод суммирования =~~

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

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

	'''Последовательно-параллельный метод''' используется в качестве эрзаца блочной реализации вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря следующим особенностям: а) реализует приём получения двойных циклов из одинарных; б) в последовательной архитектуре компьютеров позволял для ряда операций уменьшать влияние округления на результат. Здесь будем описывать его версию для суммирования чисел.

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

	~~Исходные данные: одномерный массив <math>N</math> чисел.~~

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

	Формулы метода: число <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>.

	После этого на <math>i</math>-м процессоре (<math>i < p</math>) последовательно вычисляется сумма элементов массива, начиная с <math>(i - 1) k + 1</math>-го, до <math>i k</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>-го.
	~~:<math>S_p = \sum_{j = 1}^q x_{k (p - 1) + j}</math>~~

	По окончании этого процесса процессоры обмениваются данными и на одном из них (либо на всех одновременно, если результат нужен далее на всех процессорах) получившиеся суммы суммируются последовательно друг с другом.
	~~:<math>\sum_{i = 1}^p S_i</math>~~

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

	Вычислительное ядро последовательно-параллельного метода суммирования можно составить из множественных (всего <math>p</math>) вычислений сумм элементов массива:
	~~:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>~~

	~~и ещё одного вычисления суммы элементов частичных сумм~~
	~~:<math>\sum_{i = 1}^p S_i</math>~~

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

	Как уже записано в описании ядра алгоритма, основную часть метода составляют множественные (всего <math>p + 1</math>) вычисления сумм
	~~:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>~~
	~~:<math>\sum_{i = 1}^p S_i</math>~~

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

	Формулы метода описаны выше. Последовательность исполнения суммирования может быть разная — как по возрастанию, так и по убыванию индексов. Обычно без особых причин порядок не меняют, используя естественный (возрастание индексов).

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

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

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

	~~На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 30 элементов массива.~~

	~~[[file:series-parallel summation graph.png\|center\|thumb\|600px\|Рисунок 1. Последовательно-параллельный метод суммирования массива]]~~

	~~=== Описание ресурса параллелизма алгоритма ===~~

	Для суммирования массива порядка <math>n</math> последовательно-параллельным методом в параллельном варианте требуется последовательно выполнить следующие ярусы:
	* <math>k - 1</math> ярусов суммирования по частям массива (<math>p</math> ветвей),
	* <math>p - 1</math> ярусов суммирования (одна последовательная ветвь).

	Таким образом, в параллельном варианте критический путь алгоритма (и соответствующая ему высота ЯПФ) будет зависеть от произведённого разбиения массива на части. В оптимальном случае (<math>p = \sqrt{n}</math>) высота ЯПФ будет равна <math>2 \sqrt{n} - 2</math>.

	При классификации по высоте ЯПФ, таким образом, последовательно-параллельный метод относится к алгоритмам со сложностью ''корень квадратный''. При классификации по ширине ЯПФ его сложность будет такой же — ''корень квадратный''.

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

	~~Входные данные: массив <math>\vec{x}</math> (элементы <math>x_i</math>).~~

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

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

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

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

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

	Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''корнем квадратным'' (отношение линейной к корню квадратному). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм не вполне полностью детерминирован, суммирование может быть проведено в разном порядке. Использование другого порядка выполнения ассоциативных операций может дать, с учётом особенностей входных данных, уменьшение влияния ошибок округления на результат. Дуги информационного графа локальны.

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

ASA в 14:04, 16 сентября 2015

2015-09-16T14:04:49Z

← Предыдущая версия	Версия от 14:04, 16 сентября 2015
Строка 1:	Строка 1:
		= Последовательно-параллельный метод суммирования =

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

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

		'''Последовательно-параллельный метод''' используется в качестве эрзаца блочной реализации вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря следующим особенностям: а) реализует приём получения двойных циклов из одинарных; б) в последовательной архитектуре компьютеров позволял для ряда операций уменьшать влияние округления на результат. Здесь будем описывать его версию для суммирования чисел.

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

		Исходные данные: одномерный массив <math>N</math> чисел.

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

		Формулы метода: число <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>.

		После этого на <math>i</math>-м процессоре (<math>i < p</math>) последовательно вычисляется сумма элементов массива, начиная с <math>(i - 1) k + 1</math>-го, до <math>i k</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>-го.
		:<math>S_p = \sum_{j = 1}^q x_{k (p - 1) + j}</math>

		По окончании этого процесса процессоры обмениваются данными и на одном из них (либо на всех одновременно, если результат нужен далее на всех процессорах) получившиеся суммы суммируются последовательно друг с другом.
		:<math>\sum_{i = 1}^p S_i</math>

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

		Вычислительное ядро последовательно-параллельного метода суммирования можно составить из множественных (всего <math>p</math>) вычислений сумм элементов массива:
		:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>

		и ещё одного вычисления суммы элементов частичных сумм
		:<math>\sum_{i = 1}^p S_i</math>

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

		Как уже записано в описании ядра алгоритма, основную часть метода составляют множественные (всего <math>p + 1</math>) вычисления сумм
		:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>
		:<math>\sum_{i = 1}^p S_i</math>

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

		Формулы метода описаны выше. Последовательность исполнения суммирования может быть разная — как по возрастанию, так и по убыванию индексов. Обычно без особых причин порядок не меняют, используя естественный (возрастание индексов).

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

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

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

		На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 30 элементов массива.

		[[file:series-parallel summation graph.png\|center\|thumb\|600px\|Рисунок 1. Последовательно-параллельный метод суммирования массива]]

		=== Описание ресурса параллелизма алгоритма ===

		Для суммирования массива порядка <math>n</math> последовательно-параллельным методом в параллельном варианте требуется последовательно выполнить следующие ярусы:
		* <math>k - 1</math> ярусов суммирования по частям массива (<math>p</math> ветвей),
		* <math>p - 1</math> ярусов суммирования (одна последовательная ветвь).

		Таким образом, в параллельном варианте критический путь алгоритма (и соответствующая ему высота ЯПФ) будет зависеть от произведённого разбиения массива на части. В оптимальном случае (<math>p = \sqrt{n}</math>) высота ЯПФ будет равна <math>2 \sqrt{n} - 2</math>.

		При классификации по высоте ЯПФ, таким образом, последовательно-параллельный метод относится к алгоритмам со сложностью ''корень квадратный''. При классификации по ширине ЯПФ его сложность будет такой же — ''корень квадратный''.

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

		Входные данные: массив <math>\vec{x}</math> (элементы <math>x_i</math>).

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

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

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

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

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

		Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''корнем квадратным'' (отношение линейной к корню квадратному). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм не вполне полностью детерминирован, суммирование может быть проведено в разном порядке. Использование другого порядка выполнения ассоциативных операций может дать, с учётом особенностей входных данных, уменьшение влияния ошибок округления на результат. Дуги информационного графа локальны.

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

ASA: Полностью удалено содержимое страницы

2015-09-11T08:09:00Z

Полностью удалено содержимое страницы

← Предыдущая версия		Версия от 08:09, 11 сентября 2015
Строка 1:		Строка 1:
	~~= Последовательно-параллельный метод суммирования =~~

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

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

	'''Последовательно-параллельный метод''' используется в качестве эрзаца блочной реализации вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря следующим особенностям: а) реализует приём получения двойных циклов из одинарных; б) в последовательной архитектуре компьютеров позволял для ряда операций уменьшать влияние округления на результат. Здесь будем описывать его версию для суммирования чисел.

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

	~~Исходные данные: одномерный массив <math>N</math> чисел.~~

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

	Формулы метода: число <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>.

	После этого на <math>i</math>-м процессоре (<math>i < p</math>) последовательно вычисляется сумма элементов массива, начиная с <math>(i - 1) k + 1</math>-го, до <math>i k</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>-го.
	~~:<math>S_p = \sum_{j = 1}^q x_{k (p - 1) + j}</math>~~

	По окончании этого процесса процессоры обмениваются данными и на одном из них (либо на всех одновременно, если результат нужен далее на всех процессорах) получившиеся суммы суммируются последовательно друг с другом.
	~~:<math>\sum_{i = 1}^p S_i</math>~~

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

	Вычислительное ядро последовательно-параллельного метода суммирования можно составить из множественных (всего <math>p</math>) вычислений сумм элементов массива:
	~~:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>~~

	~~и ещё одного вычисления суммы элементов частичных сумм~~
	~~:<math>\sum_{i = 1}^p S_i</math>~~

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

	Как уже записано в описании ядра алгоритма, основную часть метода составляют множественные (всего <math>p + 1</math>) вычисления сумм
	~~:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>~~
	~~:<math>\sum_{i = 1}^p S_i</math>~~

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

	Формулы метода описаны выше. Последовательность исполнения суммирования может быть разная — как по возрастанию, так и по убыванию индексов. Обычно без особых причин порядок не меняют, используя естественный (возрастание индексов).

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

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

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

	~~На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 30 элементов массива.~~

	~~[[file:series-parallel summation graph.png\|center\|thumb\|600px\|Рисунок 1. Последовательно-параллельный метод суммирования массива]]~~

	~~=== Описание ресурса параллелизма алгоритма ===~~

	Для суммирования массива порядка <math>n</math> последовательно-параллельным методом в параллельном варианте требуется последовательно выполнить следующие ярусы:
	* <math>k - 1</math> ярусов суммирования по частям массива (<math>p</math> ветвей),
	* <math>p - 1</math> ярусов суммирования (одна последовательная ветвь).

	Таким образом, в параллельном варианте критический путь алгоритма (и соответствующая ему высота ЯПФ) будет зависеть от произведённого разбиения массива на части. В оптимальном случае (<math>p = \sqrt{n}</math>) высота ЯПФ будет равна <math>2 \sqrt{n} - 2</math>.

	При классификации по высоте ЯПФ, таким образом, последовательно-параллельный метод относится к алгоритмам со сложностью ''корень квадратный''. При классификации по ширине ЯПФ его сложность будет такой же — ''корень квадратный''.

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

	~~Входные данные: массив <math>\vec{x}</math> (элементы <math>x_i</math>).~~

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

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

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

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

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

	Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''корнем квадратным'' (отношение линейной к корню квадратному). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм не вполне полностью детерминирован, суммирование может быть проведено в разном порядке. Использование другого порядка выполнения ассоциативных операций может дать, с учётом особенностей входных данных, уменьшение влияния ошибок округления на результат. Дуги информационного графа локальны.

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

ASA: Новая страница: «= Последовательно-параллельный метод суммирования = == Свойства и структура алгоритма ==…»

2015-09-11T08:08:30Z

Новая страница: «= Последовательно-параллельный метод суммирования = == Свойства и структура алгоритма ==…»

Новая страница

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

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

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

'''Последовательно-параллельный метод''' используется в качестве эрзаца блочной реализации вычисления длинных последовательностей ассоциативных операций (например, массового суммирования). Получил распространение благодаря следующим особенностям: а) реализует приём получения двойных циклов из одинарных; б) в последовательной архитектуре компьютеров позволял для ряда операций уменьшать влияние округления на результат. Здесь будем описывать его версию для суммирования чисел.

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

Исходные данные: одномерный массив <math>N</math> чисел.

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

Формулы метода: число <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>.

После этого на <math>i</math>-м процессоре (<math>i < p</math>) последовательно вычисляется сумма элементов массива, начиная с <math>(i - 1) k + 1</math>-го, до <math>i k</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>-го.
:<math>S_p = \sum_{j = 1}^q x_{k (p - 1) + j}</math>

По окончании этого процесса процессоры обмениваются данными и на одном из них (либо на всех одновременно, если результат нужен далее на всех процессорах) получившиеся суммы суммируются последовательно друг с другом.
:<math>\sum_{i = 1}^p S_i</math>

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

Вычислительное ядро последовательно-параллельного метода суммирования можно составить из множественных (всего <math>p</math>) вычислений сумм элементов массива:
:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>

и ещё одного вычисления суммы элементов частичных сумм
:<math>\sum_{i = 1}^p S_i</math>

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

Как уже записано в описании ядра алгоритма, основную часть метода составляют множественные (всего <math>p + 1</math>) вычисления сумм
:<math>S_i = \sum_{j = 1}^k x_{k (i - 1) + j}</math>
:<math>\sum_{i = 1}^p S_i</math>

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

Формулы метода описаны выше. Последовательность исполнения суммирования может быть разная — как по возрастанию, так и по убыванию индексов. Обычно без особых причин порядок не меняют, используя естественный (возрастание индексов).

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

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

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

На рис.1 изображён граф алгоритма. В данном случае выполнено суммирование 30 элементов массива.

[[file:series-parallel summation graph.png|center|thumb|600px|Рисунок 1. Последовательно-параллельный метод суммирования массива]]

=== Описание ресурса параллелизма алгоритма ===

Для суммирования массива порядка <math>n</math> последовательно-параллельным методом в параллельном варианте требуется последовательно выполнить следующие ярусы:
* <math>k - 1</math> ярусов суммирования по частям массива (<math>p</math> ветвей),
* <math>p - 1</math> ярусов суммирования (одна последовательная ветвь).

Таким образом, в параллельном варианте критический путь алгоритма (и соответствующая ему высота ЯПФ) будет зависеть от произведённого разбиения массива на части. В оптимальном случае (<math>p = \sqrt{n}</math>) высота ЯПФ будет равна <math>2 \sqrt{n} - 2</math>.

При классификации по высоте ЯПФ, таким образом, последовательно-параллельный метод относится к алгоритмам со сложностью ''корень квадратный''. При классификации по ширине ЯПФ его сложность будет такой же — ''корень квадратный''.

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

Входные данные: массив <math>\vec{x}</math> (элементы <math>x_i</math>).

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

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

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

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

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''корнем квадратным'' (отношение линейной к корню квадратному). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных столько же, сколько операций)''. При этом алгоритм не вполне полностью детерминирован, суммирование может быть проведено в разном порядке. Использование другого порядка выполнения ассоциативных операций может дать, с учётом особенностей входных данных, уменьшение влияния ошибок округления на результат. Дуги информационного графа локальны.

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