Участник:D.Polykovskiy/Алгоритм Бойера-Ватсона - История изменений

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

2016-11-26T11:50:09Z

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

← Предыдущая версия		Версия от 11:50, 26 ноября 2016
Строка 111:		Строка 111:
	Проведём исследование масштабируемости параллельной реализации алгоритма Бойера-Ватсона. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].		Проведём исследование масштабируемости параллельной реализации алгоритма Бойера-Ватсона. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

	Запустим реализацию на различных наборах точек и различном числе нитей (по логарифмической сетке), запросив 8 ядер Intel Xeon X5570.		Запустим реализацию на различных наборах точек и различном числе нитей (по логарифмической сетке), запросив 16 ядер Intel Xeon X5570.

	Полученный график сильной масштабируемости приведен ниже.		Полученный график сильной масштабируемости приведен ниже.

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

2016-11-26T11:48:30Z

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

← Предыдущая версия		Версия от 11:48, 26 ноября 2016
Строка 109:		Строка 109:
	==Масштабируемость алгоритма и его реализации==		==Масштабируемость алгоритма и его реализации==

	Проведём исследование масштабируемости параллельной реализации алгоритма Бойера-Ватсона ~~согласно [[Scalability methodology\|методике]]~~. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].		Проведём исследование масштабируемости параллельной реализации алгоритма Бойера-Ватсона. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

	Запустим реализацию на различных наборах точек и различном числе нитей (по логарифмической сетке), запросив 8 ядер Intel Xeon X5570.		Запустим реализацию на различных наборах точек и различном числе нитей (по логарифмической сетке), запросив 8 ядер Intel Xeon X5570.

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

2016-11-18T09:13:57Z

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

← Предыдущая версия		Версия от 09:13, 18 ноября 2016
Строка 109:		Строка 109:
	==Масштабируемость алгоритма и его реализации==		==Масштабируемость алгоритма и его реализации==

	Проведём исследование масштабируемости параллельной реализации ~~разложения Холецкого~~ согласно [[Scalability methodology\|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].		Проведём исследование масштабируемости параллельной реализации алгоритма Бойера-Ватсона согласно [[Scalability methodology\|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

	Запустим реализацию на различных наборах точек и различном числе нитей (по логарифмической сетке), запросив 8 ядер Intel Xeon X5570.		Запустим реализацию на различных наборах точек и различном числе нитей (по логарифмической сетке), запросив 8 ядер Intel Xeon X5570.

D.Polykovskiy: /* Последовательная сложность алгоритма */

2016-11-18T09:12:24Z

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

← Предыдущая версия		Версия от 09:12, 18 ноября 2016
Строка 85:		Строка 85:

	==Последовательная сложность алгоритма==		==Последовательная сложность алгоритма==
	В среднем число поврежденных треугольников оказывается малым, поэтому все действия кроме поиска выполняются в среднем за ''O(1)''.		В среднем число поврежденных треугольников оказывается малым, поэтому все действия кроме поиска выполняются в среднем за <math>O(1)</math>.

	В худшем случае вне зависимости от использования структурирования пространства получается сложность ''O(\|S\|~~<sup>~~2</~~sup~~>~~)''~~. Однако средняя оценка при структурировании снижается до ''O(\|S\| log\|S\|)''.		В худшем случае вне зависимости от использования структурирования пространства получается сложность <math>O(\|S\|^2)</math>. Однако средняя оценка при структурировании снижается до <math>O(\|S\| log\|S\|)</math>.

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

D.Polykovskiy: /* Проверка на вхождение в описанную окружность */

2016-11-18T09:11:10Z

Проверка на вхождение в описанную окружность

← Предыдущая версия		Версия от 09:11, 18 ноября 2016
Строка 35:		Строка 35:
	==Макроструктура алгоритма==		==Макроструктура алгоритма==
	===Проверка на вхождение в описанную окружность===		===Проверка на вхождение в описанную окружность===
	Для работы алгоритма требуется уметь проверять точку D на принадлежность описанной окружности треугольника ABC. Для двумерного случая это может быть сделано при помощи перехода в 3D пространство по схеме ''(x, y) -> (x, y, x~~<sup>~~2~~</sup>~~+y~~<sup>~~2</~~sup~~>~~)''~~<ref>Leonidas J. Guibas, Jorge Stolfi Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics </ref>		Для работы алгоритма требуется уметь проверять точку D на принадлежность описанной окружности треугольника ABC. Для двумерного случая это может быть сделано при помощи перехода в 3D пространство по схеме <math>(x, y) \to (x, y, x^2+y^2)</math><ref>Leonidas J. Guibas, Jorge Stolfi Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics </ref>
	В новом пространстве точке расположены на параболоиде. Утверждается, что четыре точки коцикличны в ''(x, y)'' тогда и только тогда, когда они компланарны в пространстве ''(x, y, x~~<sup>~~2~~</sup>~~+y~~<sup>~~2</~~sup~~>~~)''~~. Пользуясь выпуклостью парабалоида, можно сформулировать критерий принадлежности точки описанной окружности: достаточно проверить неотрицательность определителя матрицы (предполагается, что точки расположены против часовой стрелки)		В новом пространстве точке расположены на параболоиде. Утверждается, что четыре точки коцикличны в <math>(x, y)</math> тогда и только тогда, когда они компланарны в пространстве <math>(x, y, x^2+y^2)</math>. Пользуясь выпуклостью парабалоида, можно сформулировать критерий принадлежности точки описанной окружности: достаточно проверить неотрицательность определителя матрицы (предполагается, что точки расположены против часовой стрелки)

	: <math>\begin{vmatrix}		: <math>\begin{vmatrix}

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

2016-11-18T09:09:52Z

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

← Предыдущая версия		Версия от 09:09, 18 ноября 2016
Строка 31:		Строка 31:

	==Вычислительное ядро алгоритма==		==Вычислительное ядро алгоритма==
	Большая часть времени работы алгоритма приходится на поиск поврежденных треугольников. В простейшей реализации это делается за ''O(\|S\|)'', однако эта сложность может быть в среднем уменьшена до ''O(log\|S\|)'' при структурировании пространства (~~нпр.~~, KD-деревом). Тем не менее в худшем случае поиск все равно будет требовать ''O(\|S\|)'' действий.		Большая часть времени работы алгоритма приходится на поиск поврежденных треугольников. В простейшей реализации это делается за <math>O(\|S\|)</math>, однако эта сложность может быть в среднем уменьшена до <math>O(log\|S\|)</math> при структурировании пространства (например, KD-деревом). Тем не менее в худшем случае поиск все равно будет требовать <math>O(\|S\|)</math> действий.

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

D.Polykovskiy в 09:06, 18 ноября 2016

2016-11-18T09:06:11Z

← Предыдущая версия		Версия от 09:06, 18 ноября 2016
Строка 1:		Строка 1:

	Алгоритм '''Бойера–Ватсона''' --- метод, позволяющий построить триангуляцию Делоне конечного множества точек в пространстве любой размерности. Как следствие, алгоритм позволяет получить диаграму Вороного.		Алгоритм '''Бойера–Ватсона''' - метод, позволяющий построить триангуляцию Делоне конечного множества точек в пространстве любой размерности. Как следствие, алгоритм позволяет получить диаграму Вороного.

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

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

2016-11-18T07:59:17Z

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

← Предыдущая версия		Версия от 07:59, 18 ноября 2016
Строка 108:		Строка 108:

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

			Проведём исследование масштабируемости параллельной реализации разложения Холецкого согласно [[Scalability methodology\|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

			Запустим реализацию на различных наборах точек и различном числе нитей (по логарифмической сетке), запросив 8 ядер Intel Xeon X5570.

			Полученный график сильной масштабируемости приведен ниже.

			[[File:BW_run.png]]

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

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

D.Polykovskiy в 22:56, 15 ноября 2016

2016-11-15T22:56:09Z

← Предыдущая версия		Версия от 22:56, 15 ноября 2016
Строка 97:		Строка 97:
	==Входные и выходные данные алгоритма==		==Входные и выходные данные алгоритма==
	Входными данными алгоритма служит вектор точек пространства. Предполагается, что все точки различны. На выходе получается вектор троек координат вершин треугольников, образующих триангуляцию исходного множества.		Входными данными алгоритма служит вектор точек пространства. Предполагается, что все точки различны. На выходе получается вектор троек координат вершин треугольников, образующих триангуляцию исходного множества.

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

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



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

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

			==Выводы для классов архитектур==

	==Существующие реализации алгоритма==		==Существующие реализации алгоритма==
Строка 106:		Строка 118:
	<li>https://github.com/axelboc/voronoi-delaunay</li>		<li>https://github.com/axelboc/voronoi-delaunay</li>
	<li>https://github.com/ayron/delaunay</li>		<li>https://github.com/ayron/delaunay</li>
			<li>https://github.com/Bl4ckb0ne/delaunay-triangulation</li>
	</ul>		</ul>

	=Литература=		=Литература=
	<ref>C.A.Arens The Bowyer-Watson algorithm: An efficient implementation in a database environment</ref>		<ref>C.A.Arens The Bowyer-Watson algorithm: An efficient implementation in a database environment</ref>

D.Polykovskiy: /* Ресурс параллелизма алгоритма */

2016-11-15T21:06:18Z

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

← Предыдущая версия		Версия от 21:06, 15 ноября 2016
Строка 93:		Строка 93:
	[[Файл:BW.png\|thumb\|center\|400px]]		[[Файл:BW.png\|thumb\|center\|400px]]
	==Ресурс параллелизма алгоритма==		==Ресурс параллелизма алгоритма==
	Самая трудоемкая часть ~~---~~ поиск		Самая трудоемкая часть алгоритма поиск поврежденных треугольников. Это действие можно распараллелить, проводя проверку на повреждение параллельно для каждого треугольника. Поиск дублирующихся ребер также можно распараллелить, однако эта часть программы не являются ресурсоемкой: количество поврежденных треугольников редко бывает большим.

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