Участник:Vid1525/Дерево отрезков - История изменений

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

2022-10-16T18:22:46Z

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

← Предыдущая версия		Версия от 18:22, 16 октября 2022
Строка 113:		Строка 113:
	[[Файл:TreeBuildingScalability.png\|700px\|центр]]		[[Файл:TreeBuildingScalability.png\|700px\|центр]]
	[[Файл:ArraySizeScalability.png\|700px\|центр]]		[[Файл:ArraySizeScalability.png\|700px\|центр]]
	По графику можно видеть, что время ~~выполнения построения дерева~~ практически не уменьшается при увеличении количества потоков, это говорит о плохой масштабируемости данного алгоритма для приведенных входных данных, это можно объяснить тем, что при построении дерева должна соблюдаться правильная последовательность построения слоев дерева, из-за которой ухудшается качество распараллеливания программы при недостаточно больших размерах входного массива. Однако можно видеть некоторое улучшение качества скорости работы, когда количество элементов во входном массиве достаточно большое (это объясняется тем, что на более низких уровнях дерева, где достаточно много элементов, распараллеливание алгоритма работает эффективно, так как контекст программы переключается не так часто, как на более высоких уровнях дерева).		По графику сильной масштабируемости для алгоритма построения дерева можно видеть, что время работы практически не уменьшается при увеличении количества потоков, это говорит о плохой масштабируемости данного алгоритма для приведенных входных данных, это можно объяснить тем, что при построении дерева должна соблюдаться правильная последовательность построения слоев дерева, из-за которой ухудшается качество распараллеливания программы при недостаточно больших размерах входного массива. Однако можно видеть некоторое улучшение качества скорости работы, когда количество элементов во входном массиве достаточно большое (это объясняется тем, что на более низких уровнях дерева, где достаточно много элементов, распараллеливание алгоритма работает эффективно, так как контекст программы переключается не так часто, как на более высоких уровнях дерева).

	Количество запусков для усреднения в обоих случаях было равно 20.		Количество запусков для усреднения в обоих случаях было равно 20.

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

2022-10-16T17:21:58Z

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

← Предыдущая версия		Версия от 17:21, 16 октября 2022
Строка 103:		Строка 103:
	Количество потоков выполнения: [1, 2, 4, 8, 16, 32, 64]		Количество потоков выполнения: [1, 2, 4, 8, 16, 32, 64]
	[[Файл:QueriesScalability.png\|700px\|центр]]		[[Файл:QueriesScalability.png\|700px\|центр]]
			[[Файл:ScalabilityQueriesPlane.png\|700px\|центр]]

	По графику можно видеть, что время выполнения запросов обратно пропорциональна количеству потоков (до определенного момента). При количестве потоков = 64 можно видеть увеличение времени работы по сравнению с тем значением, которое соответствует количеству потоков = 32, это можно объяснить тем, что максимальное количество потоков выполнения для OpenMP на данной машине = 56, и при большем количестве потоков, чем это число время работы ухудшается, так как больше времени уходит на переключение контекста между потоками, и меньше на полезную работу.		По графику можно видеть, что время выполнения запросов обратно пропорциональна количеству потоков (до определенного момента). При количестве потоков = 64 можно видеть увеличение времени работы по сравнению с тем значением, которое соответствует количеству потоков = 32, это можно объяснить тем, что максимальное количество потоков выполнения для OpenMP на данной машине = 56, и при большем количестве потоков, чем это число время работы ухудшается, так как больше времени уходит на переключение контекста между потоками, и меньше на полезную работу.
Строка 111:		Строка 112:

	[[Файл:TreeBuildingScalability.png\|700px\|центр]]		[[Файл:TreeBuildingScalability.png\|700px\|центр]]
	По графику можно видеть, что время выполнения построения дерева уменьшается при увеличении количества потоков, ~~но зависимость времени не обратно пропорциональна количеству потоков (как в предыдущем примере)~~, ~~так как~~ при построении дерева должна соблюдаться ~~некоторая~~ последовательность ~~действий~~, из-за которой ухудшается качество распараллеливания программы).		[[Файл:ArraySizeScalability.png\|700px\|центр]]
			По графику можно видеть, что время выполнения построения дерева практически не уменьшается при увеличении количества потоков, это говорит о плохой масштабируемости данного алгоритма для приведенных входных данных, это можно объяснить тем, что при построении дерева должна соблюдаться правильная последовательность построения слоев дерева, из-за которой ухудшается качество распараллеливания программы при недостаточно больших размерах входного массива. Однако можно видеть некоторое улучшение качества скорости работы, когда количество элементов во входном массиве достаточно большое (это объясняется тем, что на более низких уровнях дерева, где достаточно много элементов, распараллеливание алгоритма работает эффективно, так как контекст программы переключается не так часто, как на более высоких уровнях дерева).

	Количество запусков для усреднения в обоих случаях было равно 20.		Количество запусков для усреднения в обоих случаях было равно 20.

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

2022-10-16T16:19:01Z

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

← Предыдущая версия		Версия от 16:19, 16 октября 2022
Строка 95:		Строка 95:
	ОС: CentOS Linux release 7.9.2009 (Core)		ОС: CentOS Linux release 7.9.2009 (Core)
	Компилятор: gcc (GCC) 4.8.5 20150623 (Red Hat 4.8.5-44)		Компилятор: gcc (GCC) 4.8.5 20150623 (Red Hat 4.8.5-44)
	Версия OpenMP: ~~openmp -~~ 3.1		Версия OpenMP: 3.1
	Максимальное количество потоков выполнения для OpenMP: 56 ( отображается при вызове функции omp_get_max_threads)		Максимальное количество потоков выполнения для OpenMP: 56 ( отображается при вызове функции omp_get_max_threads)

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

2022-10-16T16:17:53Z

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

@@ Строка 90: / Строка 90: @@
 === Возможные способы и особенности параллельной реализации алгоритма ===
 === Масштабируемость алгоритма и его реализации ===
 === Динамические характеристики и эффективность реализации алгоритма ===
 === Выводы для классов архитектур ===

Vid1525: /* Математическое описание алгоритма */

2022-10-15T15:30:56Z

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

@@ Строка 15: / Строка 15: @@
 === Математическое описание алгоритма ===
 === Вычислительное ядро алгоритма ===
 Зачастую основное время выполнение алгоритма занимают операции получения сумм на отрезках, так как операция построения дерева выполняется один раз, а количество запросов суммы может быть достаточно большим.

Vid1525: /* Схема реализации последовательного алгоритма */

2022-10-15T15:28:54Z

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

← Предыдущая версия		Версия от 15:28, 15 октября 2022
Строка 25:		Строка 25:
	=== Схема реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===
	'''Построение дерева''':		'''Построение дерева''':
	* Cоздать массив <math>tree</math> размера <math>2^{k+1}</math> для хранения дерева отрезков, где <math>2^{k-1} < n <= 2^{k} = m</math>, <math>k</math> - натуральное число, <math>n</math> - длина входного массива <math>a</math> (массив <math>tree</math> для удобства инициализируется нулевыми значениями)		* Cоздать массив <math>tree</math> размера <math>2^{k+1}</math> для хранения дерева отрезков, где <math>2^{k-1} < n \leq 2^{k} = m</math>, <math>k</math> - натуральное число, <math>n</math> - длина входного массива <math>a</math> (массив <math>tree</math> для удобства инициализируется нулевыми значениями)
	* Перенести значения сходного массива <math>a</math> в массив <math>tree</math> следующим образом: <math>tree[m+i] = a[i], i = 0..n-1</math>		* Перенести значения сходного массива <math>a</math> в массив <math>tree</math> следующим образом: <math>tree[m+i] = a[i], i = 0..n-1</math>
	* Произвести операцию инициализации значений на более высоких уровнях дерева:		* Произвести операцию инициализации значений на более высоких уровнях дерева:

Vid1525: /* Общее описание алгоритма */

2022-10-15T14:58:51Z

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

← Предыдущая версия		Версия от 14:58, 15 октября 2022
Строка 11:		Строка 11:

	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
	'''Дерево отрезков''' - это упорядоченная древовидная структура данных для хранения списка точек. Эта структура позволяет эффективно сообщать результаты некоторых запросов на отрезках данного списка точек (сумма / минимум) и обычно используется в двух или более измерениях. Деревья отрезков были введены Джоном Луисом Бентли в 1979 году. Аналогичные структуры данных были обнаружены независимо Лукером, Ли и Вонгом. Дерево отрезков является альтернативой дереву k-d. По сравнению с деревьями k-d, деревья ~~диапазонов~~ обеспечивают более быстрое время запроса (в обозначении Big O) <math>O(log ^ dn)</math>, но худшее хранение <math>O(nlog^{d-1}n)</math>, где n - количество точек, сохраненных в дереве, d - размерность дерева.		'''Дерево отрезков''' - это упорядоченная древовидная структура данных для хранения списка точек. Эта структура позволяет эффективно сообщать результаты некоторых запросов на отрезках данного списка точек (например сумма / минимум) и обычно используется в двух или более измерениях. Деревья отрезков были введены Джоном Луисом Бентли в 1979 году. Аналогичные структуры данных были обнаружены независимо Лукером, Ли и Вонгом. Дерево отрезков является альтернативой дереву k-d. По сравнению с деревьями k-d, деревья отрезков обеспечивают более быстрое время запроса (в обозначении Big O) <math>O(log ^ dn)</math>, но худшее хранение <math>O(nlog^{d-1}n)</math>, где n - количество точек, сохраненных в дереве, d - размерность дерева.
	В данной работе будет рассматриваться одномерное дерево отрезков.		В данной работе будет рассматриваться одномерное дерево отрезков.

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

2022-10-15T14:56:58Z

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

← Предыдущая версия		Версия от 14:56, 15 октября 2022
Строка 51:		Строка 51:
	=== Информационный граф ===		=== Информационный граф ===
	[[Файл:SegmentTreeBuilding.png\|center\|600px]]		[[Файл:SegmentTreeBuilding.png\|center\|600px]]
	Пример построения дерева отрезков для массива длины n = 6, a = [1, 2, 3, 4, 5, 6]		Пример построения дерева отрезков для массива длины n = 6, a = [1, 2, 3, 4, 5, 6] (зеленые вершины - элементы исходного массива в дереве).

	[[Файл:SegmentTreeQuery.png\|center\|600px]]		[[Файл:SegmentTreeQuery.png\|center\|600px]]

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

2022-10-15T14:54:12Z

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

← Предыдущая версия		Версия от 14:54, 15 октября 2022
Строка 50:		Строка 50:

	=== Информационный граф ===		=== Информационный граф ===
			[[Файл:SegmentTreeBuilding.png\|center\|600px]]
			Пример построения дерева отрезков для массива длины n = 6, a = [1, 2, 3, 4, 5, 6]

			[[Файл:SegmentTreeQuery.png\|center\|600px]]
			Пример запроса суммы на отрезке [1..4] для массива из предыдущего примера (красные стрелки показывают, переходы между вершинами при выполнении функции запроса, синие вершины - вершины, из которых были взяты значения для суммирования на отрезке).

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

Vid1525 в 13:31, 15 октября 2022

2022-10-15T13:31:04Z

← Предыдущая версия		Версия от 13:31, 15 октября 2022
Строка 6:		Строка 6:
	}}		}}

	~~Авторы~~: [[Участник:Vid1525\|И.Д. Васенков]]		Автор: [[Участник:Vid1525\|И.Д. Васенков]]

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