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

ASA в 08:40, 20 февраля 2025

2025-02-20T08:40:26Z

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

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

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

	~~{{level-a}}~~

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

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

2022-07-08T09:58:17Z

← Предыдущая версия		Версия от 09:58, 8 июля 2022
Строка 68:		Строка 68:
	Сдваивание, из-за сильной избыточности вычислений, вряд ли может быть применено на компьютерах без параллельных устройств.		Сдваивание, из-за сильной избыточности вычислений, вряд ли может быть применено на компьютерах без параллельных устройств.

	=== ~~Локальность данных~~ и ~~вычислений~~ ===		=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

	~~=== Возможные способы и особенности параллельной реализации алгоритма ===~~
	~~=== Масштабируемость алгоритма и его реализации ===~~

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

	===~~= Масштабируемость алгоритма ====~~		=== Результаты прогонов ===
	~~==== Масштабируемость реализации алгоритма ====~~

	~~=== Динамические характеристики и эффективность реализации алгоритма~~ ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===

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

	==~~= Существующие реализации алгоритма =~~==		== Литература ==

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

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


	[[Категория:Законченные_статьи]]		[[Категория:Законченные_статьи]]

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

2018-03-14T11:15:05Z

← Предыдущая версия		Версия от 11:15, 14 марта 2018
Строка 97:		Строка 97:
	[[Категория:Алгоритмы с избыточными вычислениями]]		[[Категория:Алгоритмы с избыточными вычислениями]]
	[[Категория:Векторные операции]]		[[Категория:Векторные операции]]

			[[en:Parallel prefix scan algorithm using pairwise summation]]

Frolov: /* Свойства и структура алгоритма */

2017-11-06T13:20:13Z

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

← Предыдущая версия		Версия от 13:20, 6 ноября 2017
Строка 1:		Строка 1:
	Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]]		Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]]

			{{level-a}}

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

Frolov: /* Вычислительное ядро алгоритма */

2017-11-06T13:19:41Z

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

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

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

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

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

2016-07-08T13:26:41Z

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

VolkovNikita94: /* Информационный граф */

2015-11-17T13:01:16Z

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

← Предыдущая версия		Версия от 13:01, 17 ноября 2015
Строка 35:		Строка 35:

	=== Информационный граф ===		=== Информационный граф ===
	[[File:DoublingPartUniv.png\|thumb\|~~left~~\|600px\|Рисунок 1. Граф алгоритма при n=8 c отображением входных данных. Синим обозначены входные, красным - выходные данные. Все вершины соответствуют операции сложения]]		[[File:DoublingPartUniv.png\|thumb\|center\|600px\|Рисунок 1. Граф алгоритма при n=8 c отображением входных данных. Синим обозначены входные, красным - выходные данные. Все вершины соответствуют операции сложения]]

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

VolkovNikita94: /* Информационный граф */

2015-10-22T08:51:15Z

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

← Предыдущая версия		Версия от 08:51, 22 октября 2015
Строка 35:		Строка 35:

	=== Информационный граф ===		=== Информационный граф ===
	[[File:DoublingPartUniv.png\|thumb\|left\|600px\|Рисунок 1. Граф алгоритма при n=8 c отображением входных данных. ~~Чёрными~~ обозначены ~~операции~~, ~~результаты которых нужны на выходе алгоритма~~. Все вершины соответствуют операции сложения]]		[[File:DoublingPartUniv.png\|thumb\|left\|600px\|Рисунок 1. Граф алгоритма при n=8 c отображением входных данных. Синим обозначены входные, красным - выходные данные. Все вершины соответствуют операции сложения]]

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

VolkovNikita94: /* Информационный граф */

2015-10-22T08:50:27Z

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

← Предыдущая версия		Версия от 08:50, 22 октября 2015
Строка 35:		Строка 35:

	=== Информационный граф ===		=== Информационный граф ===
	[[File:DoublingPartUniv.png\|thumb\|~~right~~\|~~480px~~\|Рисунок 1. Граф алгоритма при n=8 c отображением входных данных. Чёрными обозначены операции, результаты которых нужны на выходе алгоритма. Все вершины соответствуют операции сложения]]		[[File:DoublingPartUniv.png\|thumb\|left\|600px\|Рисунок 1. Граф алгоритма при n=8 c отображением входных данных. Чёрными обозначены операции, результаты которых нужны на выходе алгоритма. Все вершины соответствуют операции сложения]]

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

Frolov: /* Литература */

2015-08-12T12:08:23Z

Литература

← Предыдущая версия		Версия от 12:08, 12 августа 2015
Строка 90:		Строка 90:
	<references />		<references />

	[[Категория:~~Статьи в работе~~]]
			[[Категория:Законченные_статьи]]
	[[Категория:Метод сдваивания]]		[[Категория:Метод сдваивания]]
	[[Категория:Алгоритмы с избыточными вычислениями]]		[[Категория:Алгоритмы с избыточными вычислениями]]