Участник:Allocator/Метод рекурсивной координатной бисекции - История изменений

ASA в 11:57, 7 февраля 2017

2017-02-07T11:57:29Z

← Предыдущая версия		Версия от 11:57, 7 февраля 2017
Строка 1:		Строка 1:
			{{Assignment\|ASA}}

	Авторы: Долгов Борис (624), Галуза Дмитрий (624)		Авторы: Долгов Борис (624), Галуза Дмитрий (624)
	= Свойства и структура алгоритмов =		= Свойства и структура алгоритмов =

Allocator в 11:17, 7 февраля 2017

2017-02-07T11:17:27Z

← Предыдущая версия		Версия от 11:17, 7 февраля 2017
Строка 120:		Строка 120:
	Результаты запуска при разбиении на 16 доменов показаны ниже.		Результаты запуска при разбиении на 16 доменов показаны ниже.

	[[Файл:Allocator_split16.png]]		[[Файл:Allocator_split16.png\|thumb\|center\|800px]]

Allocator в 11:14, 7 февраля 2017

2017-02-07T11:14:28Z

← Предыдущая версия		Версия от 11:14, 7 февраля 2017
Строка 102:		Строка 102:

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

			Оценка масштабируемости метода рекурсивной координатной бисекции проводилась на основе существующей реализации. Из существующих реализаций была выбрана наиболее широко используемая на данный момент реализация из программной библиотеки для распределения нагрузки Zoltan.

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

			Запуск производился на суперкомпьютере ВМК МГУ BlueGene/P и осуществлялся следующей программой на языке BASH

			<source lang="bash">
			#!/bin/bash
			for size in 1024 2048 4096; do
			for procs in 1 2 16 64 128 256 512; do
			mpisubmit.bg -n $procs -w 3:00 -m smp --stdin /dev/null --stderr ~/output2/$size-$procs.log --stdout /dev/null ./simpleRCB.exe -- $size
			done
			done
			</source>

			Результаты запуска при разбиении на 16 доменов показаны ниже.

			[[Файл:Allocator_split16.png]]


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

Allocator в 15:15, 6 февраля 2017

2017-02-06T15:15:35Z

← Предыдущая версия		Версия от 15:15, 6 февраля 2017
Строка 78:		Строка 78:
	Ярусно-параллельная форма алгоритма имеет высоту в <math>log_2 k</math> уровней, где k – требуемое значение конечных доменов. Соответственно ширина яруса i будет равна <math>2^i</math>. Так как ширина i-го яруса равна <math>2^i</math>, а общее количество вершин примем за n – то в кажом домене на i-м ярусе будет по <math>n / 2^i</math> вершин. Если на каждом шаге использовать параллельную сортировку c хорошей сложностью <math>(n/p)(log_2(n/p)+log_2^2(p))</math> (где n - количество сортируемых элементов, p - количество процессоров), то получаем итоговую сложность алгоритма как сумму всех ярусов, на которых параллельно запускается сортировка.		Ярусно-параллельная форма алгоритма имеет высоту в <math>log_2 k</math> уровней, где k – требуемое значение конечных доменов. Соответственно ширина яруса i будет равна <math>2^i</math>. Так как ширина i-го яруса равна <math>2^i</math>, а общее количество вершин примем за n – то в кажом домене на i-м ярусе будет по <math>n / 2^i</math> вершин. Если на каждом шаге использовать параллельную сортировку c хорошей сложностью <math>(n/p)(log_2(n/p)+log_2^2(p))</math> (где n - количество сортируемых элементов, p - количество процессоров), то получаем итоговую сложность алгоритма как сумму всех ярусов, на которых параллельно запускается сортировка.
	А именно:		А именно:
	<math>\sum_{i=0}^{log_2 k} ((n / 2^i) / (p / 2^i)) (log_2((n / 2^i) / (p / 2^i)) + log_2^2(p / 2^i)) = O((n/p) * (log_2 (n/p) + log_2^2(p)) * log_2 k)</math>		<math>\sum_{i=0}^{log_2 k} ((n / 2^i) / (p / 2^i)) (log_2((n / 2^i) / (p / 2^i)) + log_2^2(p / 2^i)) = O((n/p) * (log_2 (n/p) + log_2^2(p)) * log_2(k))</math>
	== Входные и выходные данные алгоритма ==		== Входные и выходные данные алгоритма ==
	'''Входные данные''': требуемое количество доменов в разбиении, вершины графа. Каждой вершине соответствуют некоторые многомерные числовые координаты. Вершины могут быть произвольно разбиты по вычислительным узлам. Таким образом, '''объём входных данных''' пропорционален размеру графа V и количеству измерений N: \|V\|*N.		'''Входные данные''': требуемое количество доменов в разбиении, вершины графа. Каждой вершине соответствуют некоторые многомерные числовые координаты. Вершины могут быть произвольно разбиты по вычислительным узлам. Таким образом, '''объём входных данных''' пропорционален размеру графа V и количеству измерений N: <math>\|V\|*N+\|E\|</math>.

	'''Выходные данные''': p доменов, разбивающих граф; при этом вершины этих доменов хранятся последовательно в исходном массиве. При количестве узлов, используемых для декомпозиции, совпадающим с количеством узлов, используемых для дальнейших вычислений, это автоматически размещает всю информацию о вершинах на вычислительных узлах, которые будут обрабатывать эти вершины. Таким образом, '''объём выходных данных''' пропорционален количеству вершин в исходном графе: \|V\|.		'''Выходные данные''': p доменов, разбивающих граф; при этом вершины этих доменов хранятся последовательно в исходном массиве. При количестве узлов, используемых для декомпозиции, совпадающим с количеством узлов, используемых для дальнейших вычислений, это автоматически размещает всю информацию о вершинах на вычислительных узлах, которые будут обрабатывать эти вершины. Таким образом, '''объём выходных данных''' пропорционален количеству вершин в исходном графе: \|V\|.
Строка 91:		Строка 91:
	Так как процессы обрабатывают примерно равное количество вершин, полученный алгоритм является '''сбалансированным''' по числу операций на каждом процессе.		Так как процессы обрабатывают примерно равное количество вершин, полученный алгоритм является '''сбалансированным''' по числу операций на каждом процессе.

	Вычислительная мощность алгоритма, равная отношению количества операций к количеству входных и выходных данных равна <math>(\|V\|/P+P) * log_2(\|V\|/P + P) * log_2(K) / (\|V\|N~~) = O(P * log_2(~~\|V\|~~/P + P~~) * log_2(K)) / N</math>. Если принять количество вычислительных узлов P и количество измерений N за константы, вычислительная мощность будет равна <math>O(log_2(\|V\|) * log_2(K))</math>		Вычислительная мощность алгоритма, равная отношению количества операций к количеству входных и выходных данных равна <math>((\|V\|/P) * (log_2 (\|V\|/P) + log_2^2(P)) * log_2(K) / (\|V\|N+\|E\|) = </math>. Если принять количество вычислительных узлов P и количество измерений N за константы, а количество ребёр пропорциональным количеству вершин (что верно для координатных сеток), вычислительная мощность будет равна <math>O(log_2(\|V\|) * log_2(K))</math>

	= Программная реализация алгоритма =		= Программная реализация алгоритма =

Allocator в 15:08, 6 февраля 2017

2017-02-06T15:08:38Z

Allocator в 12:42, 6 февраля 2017

2017-02-06T12:42:03Z

Внесённые изменения

ASA в 08:08, 6 февраля 2017

2017-02-06T08:08:32Z

← Предыдущая версия		Версия от 08:08, 6 февраля 2017
Строка 1:		Строка 1:
	~~{{Assignment}}~~
	Авторы: Долгов Борис (624), Галуза Дмитрий (624)		Авторы: Долгов Борис (624), Галуза Дмитрий (624)
	= Свойства и структура алгоритмов =		= Свойства и структура алгоритмов =

Allocator в 17:43, 3 февраля 2017

2017-02-03T17:43:23Z

← Предыдущая версия		Версия от 17:43, 3 февраля 2017
Строка 4:		Строка 4:
	== Общее описание алгоритма ==		== Общее описание алгоритма ==
	Декомпозиция графа — это разбиение множества вершин графа на подмножества, для обработки каждого из подмножеств на отдельном вычислительном узле.		Декомпозиция графа — это разбиение множества вершин графа на подмножества, для обработки каждого из подмножеств на отдельном вычислительном узле.
	Декомпозиция больших графов (то есть графов, объём описания которых превышает память, доступную одному узлу) происходит в два этапа: выполнение первоначального разбиения вершин графа по вычислительным процессорам, затем — выполнение одного из параллельных алгоритмов декомпозиции. Алгоритм координатной рекурсивной бисекции даёт хорошее первичное распределение узлов сетки по сравнению с простым распределением узлов по номерам и, как правило, используется как первый шаг более сложных алгоритмов.		Декомпозиция больших графов (то есть графов, объём описания которых превышает память, доступную одному узлу) происходит в два этапа: выполнение первоначального разбиения вершин графа по вычислительным процессорам, затем — выполнение одного из параллельных алгоритмов декомпозиции. Алгоритм координатной рекурсивной бисекции даёт хорошее первичное распределение узлов сетки по сравнению с простым распределением узлов по номерам и, как правило, используется как первый шаг более сложных алгоритмов <ref>Якобовский М.В. Введение в параллельные методы решения задач: Учебное пособие / Предисл.: В. А. Садовничий. – М.: Издательство Московского университета, 2012. – 328 с., илл. – (Серия «Суперкомпьютерное образование»), ISBN 978-5-211-06382-2 URL: http://lira.imamod.ru/ITTPMOPS/ </ref>.

	Данный алгоритм использует стратегию рекурсивной бисекции. В соответствии с ней, граф последовательно за k-1 шаг делится на k частей. На первом шаге исходный граф делится на 2 части, на каждом следующем шаге – одна из ранее полученных частей делится ещё на две части. В качестве способа деления на две части используется разделение по координатам вершин. Для этого вершины сортируется вдоль выбранной координаты, и в отсортированном массиве разбиваются на две непрерывные части в заданной пропорции.		Данный алгоритм использует стратегию рекурсивной бисекции. В соответствии с ней, граф последовательно за k-1 шаг делится на k частей. На первом шаге исходный граф делится на 2 части, на каждом следующем шаге – одна из ранее полученных частей делится ещё на две части. В качестве способа деления на две части используется разделение по координатам вершин. Для этого вершины сортируется вдоль выбранной координаты, и в отсортированном массиве разбиваются на две непрерывные части в заданной пропорции.
Строка 48:		Строка 48:
	</source>		</source>
	== Последовательная сложность алгоритма ==		== Последовательная сложность алгоритма ==
	Как было описано ранее, для разбиения графа размером n на p кластеров потребуется p рекурсивных шагов. Таким образом, при использовании оптимальной стратегии разбиения, время работы можно выразить рекуррентным соотношением <math>T(N) = O(Nlog_2(N)) + 2 T(N/2)</math>. Согласно основной теореме о рекуррентных соотношениях ~~ссылка~~ , <math>T(N) = O(Nlog_2(N)log_2(N))</math> в худшем случае (при N = P). При меньшем количестве кластеров, глубина рекурсии будет ограничена <math>log_2(P)</math>, следовательно, время работы алгоритма составит <math>O(log_2(p) * N * log_2(N))</math>		Как было описано ранее, для разбиения графа размером n на p кластеров потребуется p рекурсивных шагов. Таким образом, при использовании оптимальной стратегии разбиения, время работы можно выразить рекуррентным соотношением <math>T(N) = O(Nlog_2(N)) + 2 T(N/2)</math>. Согласно основной теореме о рекуррентных соотношениях <ref> Основная теорема о рекуррентных соотношениях URL: https://ru.wikipedia.org/wiki/%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%80%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D1%85_%D1%81%D0%BE%D0%BE%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D1%8F%D1%85#.D0.92.D0.B0.D1.80.D0.B8.D0.B0.D0.BD.D1.82_2</ref> , <math>T(N) = O(Nlog_2(N)log_2(N))</math> в худшем случае (при N = P). При меньшем количестве кластеров, глубина рекурсии будет ограничена <math>log_2(P)</math>, следовательно, время работы алгоритма составит <math>O(log_2(p) * N * log_2(N))</math>
	== Информационный граф ==		== Информационный граф ==
	Шаг алгоритма заключается в разделении входного множества вершин на два домена. Получается, что граф исполнения шагов представляет из себя бинарное дерево. Каждый шаг инициирует исполнение еще двух шагов.		Шаг алгоритма заключается в разделении входного множества вершин на два домена. Получается, что граф исполнения шагов представляет из себя бинарное дерево. Каждый шаг инициирует исполнение еще двух шагов.
Строка 58:		Строка 58:
	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
	Так как алгоритм работает с координатной сеткой – он обладает координатным параллелизмом.		Так как алгоритм работает с координатной сеткой – он обладает координатным параллелизмом.
	Ярусно-параллельная форма алгоритма имеет высоту в <math>log_2 k</math> уровней, где k – требуемое значение конечных доменов. Соответственно ширина яруса i будет равна <math>2^i</math>. Так как ширина i-го яруса равна <math>2^i</math>, а общее количество вершин примем за n – то в кажом домене на i-м ярусе будет по <math>n / 2^i</math> вершин. Если на каждом шаге использовать оптимальную параллельную сортировку, сложность которой равна <math>(n/p+p)*log_2 (n/p)</math> (где n - количество сортируемых элементов, p - количество процессоров), то получаем итоговую сложность алгоритма как сумму всех ярусов, на которых параллельно запускается оптимальная сортировка.		Ярусно-параллельная форма алгоритма имеет высоту в <math>log_2 k</math> уровней, где k – требуемое значение конечных доменов. Соответственно ширина яруса i будет равна <math>2^i</math>. Так как ширина i-го яруса равна <math>2^i</math>, а общее количество вершин примем за n – то в кажом домене на i-м ярусе будет по <math>n / 2^i</math> вершин. Если на каждом шаге использовать оптимальную параллельную сортировку <ref>URL: Supercomputer Software Department, Математическое моделирование: параллельные алгоритмы, Параллельные алгоритмы сортировки URL: http://ssd.sscc.ru/ru/content/%D0%BF%D0%B0%D1%80%D0%B0%D0%BB%D0%BB%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5-%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8</ref>, сложность которой равна <math>(n/p+p)*log_2 (n/p)</math> (где n - количество сортируемых элементов, p - количество процессоров), то получаем итоговую сложность алгоритма как сумму всех ярусов, на которых параллельно запускается оптимальная сортировка.
	А именно:		А именно:
	<math>\sum_{i=0}^{log_2 k} (n / p + p) / 2^i * log_2 ((n / p + p) / 2^i) =O((n/p + p) * log_2 (n/p + p) * log_2 k)</math>		<math>\sum_{i=0}^{log_2 k} (n / p + p) / 2^i * log_2 ((n / p + p) / 2^i) =O((n/p + p) * log_2 (n/p + p) * log_2 k)</math>
Строка 71:		Строка 71:

	Так как процессы обрабатывают примерно равное количество вершин, полученный алгоритм является '''сбалансированным''' по числу операций на каждом процессе.		Так как процессы обрабатывают примерно равное количество вершин, полученный алгоритм является '''сбалансированным''' по числу операций на каждом процессе.

			= Литература =

Allocator в 17:21, 3 февраля 2017

2017-02-03T17:21:06Z

← Предыдущая версия		Версия от 17:21, 3 февраля 2017
Строка 1:		Строка 1:
			{{Assignment}}
	Авторы: Долгов Борис (624), Галуза Дмитрий (624)		Авторы: Долгов Борис (624), Галуза Дмитрий (624)
	= Свойства и структура алгоритмов =		= Свойства и структура алгоритмов =

Allocator: Новая страница: «Авторы: Долгов Борис (624), Галуза Дмитрий (624) = Свойства и структура алгоритмов = == Общее оп…»

2017-02-03T17:19:08Z

Новая страница: «Авторы: Долгов Борис (624), Галуза Дмитрий (624) = Свойства и структура алгоритмов = == Общее оп…»

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

Авторы: Долгов Борис (624), Галуза Дмитрий (624)
= Свойства и структура алгоритмов =
== Общее описание алгоритма ==
Декомпозиция графа — это разбиение множества вершин графа на подмножества, для обработки каждого из подмножеств на отдельном вычислительном узле.
Декомпозиция больших графов (то есть графов, объём описания которых превышает память, доступную одному узлу) происходит в два этапа: выполнение первоначального разбиения вершин графа по вычислительным процессорам, затем — выполнение одного из параллельных алгоритмов декомпозиции. Алгоритм координатной рекурсивной бисекции даёт хорошее первичное распределение узлов сетки по сравнению с простым распределением узлов по номерам и, как правило, используется как первый шаг более сложных алгоритмов.

Данный алгоритм использует стратегию рекурсивной бисекции. В соответствии с ней, граф последовательно за k-1 шаг делится на k частей. На первом шаге исходный граф делится на 2 части, на каждом следующем шаге – одна из ранее полученных частей делится ещё на две части. В качестве способа деления на две части используется разделение по координатам вершин. Для этого вершины сортируется вдоль выбранной координаты, и в отсортированном массиве разбиваются на две непрерывные части в заданной пропорции.

Так как алгоритм использует предположение о том, что близкие по координатам вершины будут связаны, а удалённые по координатам вершины будут не связаны, он не подходит для разбивания произвольных графов, а лучше всего подходит для разбития координатных сеток.
== Математическое описание алгоритма ==
Пусть задан <math>G = (V, E)</math> – неориентированный граф, где <math>V</math> -- множество вершин, <math>E</math> -- множество рёбер. Каждой вершине соответствует целочисленный координатный вектор <math>c_i</math>, вес <math>v_i</math>. Кроме того, задано желаемое количество доменов <math>p</math>.
Требуется разбить множество <math>V</math> на p непересекающихся подмножеств (доменов) <math>S_1, \ldots, S_p</math>, при этом должны быть выполнены следующие требования:
Домены не пересекаются: <math>S_i \cap S_j = \emptyset</math>
Каждая вершина находится в домене: <math> \cup _i S_i = V</math>
Распределение вершин по доменам примерно равномерное: <math>|S_i| \approx |V| / p</math>
Минимизирован вес разрезанных рёбер: <math>\sum_{i \neq j} \sum_{v_1 \in S_i} \sum_{v2_ \in S_j} e_{i, j} \rightarrow min</math>
Один шаг алгоритма принимает соотношение для разбиения выглядит следующим образом:
* Выполняется поиск координатной оси, имеющей максимальную протяженность. Под протяженностью понимается разность между максимальным и минимальным значением по выбранной координатной оси серди всех вершин. Сам же поиск максимума и минимума по каждой координатной оси осуществляется одним линейным проходом по вершинам. Для выбора среди разностей – производится еще один линейный проход, уже по координатным осям.
* Вершины сортируются по выбранной координатной оси. Считаем, что одна вершина “меньше” другой, если значение выбранной на предыдущем шаге координаты меньше соответствующего значения другой вершины.
* Полученные на предыдущем пункте отсортированные вершины разбиваются на два домена, согласно заданному соотношению.
* Шаг запускается рекурсивно для полученных доменов.
== Вычислительное ядро алгоритма ==
Вычислительным ядром алгоритма является один шаг алгоритма. Основной вклад в вычислительную сложность вносит сортировка вершин, которая при использовании оптимального алгоритма выполняемая со сложностью <math>O(n log_2{n})</math>. Поиск максимально протяжённой координатной оси выполняется за линейное время, а разбиение вершин на два домена – за константное.
== Макроструктура алгоритма ==
Алгоритм декомпозиции на каждом шаге может использовать любой из параллельных алгоритмов сортировки.

При использовании алгоритма сортировки со сложностью <math>S(N)</math>, сложность алгоритма составит <math>p * (S(N) + N)</math>
== Схема реализации последовательного алгоритма ==
<source lang="bash">
# Шаг алгоритма
Bisect(graf, n, subgraf1, n1, subgraf2, n2) {
dim = argmax(i, max(j, graf[j][i]) - min(j, graf[j][i]));
sort(graf, dim);
subgraf1 = graf[0..n1];
subgraf2 = graf[n1+1..n-1];
}
# Схема рекурсивной бисекции
RecursiveBisect(graf, n, k) {
k1 = (k1+1)/2;
k2 = k-k1;
n1=n*k1/k;
n2=n-n1;
Bisect(graf, n, subgraf1, n1, subgraf2, n2);
If (k1>1) RecursiveBisect(subgraf1, n1, k1);
If (k2>1) RecursiveBisect(subgraf2, n2, k2);
}
</source>
== Последовательная сложность алгоритма ==
Как было описано ранее, для разбиения графа размером n на p кластеров потребуется p рекурсивных шагов. Таким образом, при использовании оптимальной стратегии разбиения, время работы можно выразить рекуррентным соотношением <math>T(N) = O(N*log_2(N)) + 2 * T(N/2)</math>. Согласно основной теореме о рекуррентных соотношениях ссылка , <math>T(N) = O(N*log_2(N)*log_2(N))</math> в худшем случае (при N = P). При меньшем количестве кластеров, глубина рекурсии будет ограничена <math>log_2(P)</math>, следовательно, время работы алгоритма составит <math>O(log_2(p) * N * log_2(N))</math>
== Информационный граф ==
Шаг алгоритма заключается в разделении входного множества вершин на два домена. Получается, что граф исполнения шагов представляет из себя бинарное дерево. Каждый шаг инициирует исполнение еще двух шагов.
[[File:allocator_graph.png|thumb|center|800px]]

При этом на каждом шаге выполняются действия, описанные в п 1.2.

== Ресурс параллелизма алгоритма ==
Так как алгоритм работает с координатной сеткой – он обладает координатным параллелизмом.
Ярусно-параллельная форма алгоритма имеет высоту в <math>log_2 k</math> уровней, где k – требуемое значение конечных доменов. Соответственно ширина яруса i будет равна <math>2^i</math>. Так как ширина i-го яруса равна <math>2^i</math>, а общее количество вершин примем за n – то в кажом домене на i-м ярусе будет по <math>n / 2^i</math> вершин. Если на каждом шаге использовать оптимальную параллельную сортировку, сложность которой равна <math>(n/p+p)*log_2 (n/p)</math> (где n - количество сортируемых элементов, p - количество процессоров), то получаем итоговую сложность алгоритма как сумму всех ярусов, на которых параллельно запускается оптимальная сортировка.
А именно:
<math>\sum_{i=0}^{log_2 k} (n / p + p) / 2^i * log_2 ((n / p + p) / 2^i) =O((n/p + p) * log_2 (n/p + p) * log_2 k)</math>
== Входные и выходные данные алгоритма ==
'''Входные данные''': требуемое количество доменов в разбиении, вершины графа. Каждой вершине соответствуют некоторые многомерные числовые координаты. Вершины могут быть произвольно разбиты по вычислительным узлам.

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

'''Детерминированность''' данного алгоритма может быть достигнута, если использовать устойчивый алгоритм сортировки.

Так как процессы обрабатывают примерно равное количество вершин, полученный алгоритм является '''сбалансированным''' по числу операций на каждом процессе.

← Предыдущая версия		Версия от 15:08, 6 февраля 2017
Строка 14:		Строка 14:
	Каждая вершина находится в домене: <math> \cup _i S_i = V</math>		Каждая вершина находится в домене: <math> \cup _i S_i = V</math>
	Распределение вершин по доменам примерно равномерное: <math>\|S_i\| \approx \|V\| / p</math>		Распределение вершин по доменам примерно равномерное: <math>\|S_i\| \approx \|V\| / p</math>
	Минимизирован вес разрезанных рёбер: <math>\sum_{i \neq j} \sum_{v_1 \in S_i} \sum_{v2_ \in S_j} e_{i, j} \rightarrow min</math>		Минимизирован вес разрезанных рёбер: <math>\sum_{i \neq j} \sum_{v_1 \in S_i} \sum_{v2_ \in S_j} e_{v_1, v_2} \rightarrow min</math>
	Один шаг алгоритма принимает соотношение для разбиения выглядит следующим образом:		Один шаг алгоритма принимает соотношение для разбиения выглядит следующим образом:
	* Выполняется поиск координатной оси, имеющей максимальную протяженность. Под протяженностью понимается разность между максимальным и минимальным значением по выбранной координатной оси серди всех вершин. Сам же поиск максимума и минимума по каждой координатной оси осуществляется одним линейным проходом по вершинам. Для выбора среди разностей – производится еще один линейный проход, уже по координатным осям.		* Выполняется поиск координатной оси, имеющей максимальную протяженность. Под протяженностью понимается разность между максимальным и минимальным значением по выбранной координатной оси серди всех вершин. Сам же поиск максимума и минимума по каждой координатной оси осуществляется одним линейным проходом по вершинам. Для выбора среди разностей – производится еще один линейный проход, уже по координатным осям.
Строка 21:		Строка 21:
	* Шаг запускается рекурсивно для полученных доменов.		* Шаг запускается рекурсивно для полученных доменов.
	== Вычислительное ядро алгоритма ==		== Вычислительное ядро алгоритма ==
	Вычислительным ядром алгоритма является ~~один шаг~~ алгоритма~~. Основной вклад в вычислительную сложность вносит сортировка вершин~~, которая при использовании оптимального алгоритма ~~выполняемая~~ со сложностью <math>O(n log_2{n})</math>. Поиск максимально протяжённой координатной оси выполняется за линейное время, а разбиение вершин на два домена – за константное.		Вычислительным ядром алгоритма является сортировка на очередном шаге алгоритма, которая при использовании оптимального алгоритма выполняется со сложностью <math>O(n log_2{n})</math>.
	== Макроструктура алгоритма ==		== Макроструктура алгоритма ==
	Схема работы параллельного алгоритма следующая:		Схема работы параллельного алгоритма следующая:
Строка 31:		Строка 31:
	* При необходимости, каждый из кластеров может быть разделён на подкластеры рекурсивным вызовом этого же алгоритма		* При необходимости, каждый из кластеров может быть разделён на подкластеры рекурсивным вызовом этого же алгоритма

	При использовании алгоритма сортировки со сложностью <math>S(N)</math>, сложность алгоритма составит <math>p * (S(N) + N)</math>
	== Схема реализации последовательного алгоритма ==		== Схема реализации последовательного алгоритма ==
	<source lang="bash">		<source lang="bash">
Строка 77:		Строка 76:
	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
	Так как алгоритм работает с координатной сеткой – он обладает координатным параллелизмом.		Так как алгоритм работает с координатной сеткой – он обладает координатным параллелизмом.
	Ярусно-параллельная форма алгоритма имеет высоту в <math>log_2 k</math> уровней, где k – требуемое значение конечных доменов. Соответственно ширина яруса i будет равна <math>2^i</math>. Так как ширина i-го яруса равна <math>2^i</math>, а общее количество вершин примем за n – то в кажом домене на i-м ярусе будет по <math>n / 2^i</math> вершин. Если на каждом шаге использовать ~~оптимальную~~ параллельную сортировку <ref>URL: Supercomputer Software Department, Математическое моделирование: параллельные алгоритмы, Параллельные алгоритмы сортировки URL: http://ssd.sscc.ru/ru/content/%D0%BF%D0%B0%D1%80%D0%B0%D0%BB%D0%BB%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5-%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8</ref>, сложность которой равна <math>(n/p+p)*log_2 (n/p)</math> (где n - количество сортируемых элементов, p - количество процессоров), то получаем итоговую сложность алгоритма как сумму всех ярусов, на которых параллельно запускается ~~оптимальная~~ сортировка.		Ярусно-параллельная форма алгоритма имеет высоту в <math>log_2 k</math> уровней, где k – требуемое значение конечных доменов. Соответственно ширина яруса i будет равна <math>2^i</math>. Так как ширина i-го яруса равна <math>2^i</math>, а общее количество вершин примем за n – то в кажом домене на i-м ярусе будет по <math>n / 2^i</math> вершин. Если на каждом шаге использовать параллельную сортировку c хорошей сложностью <math>(n/p)(log_2(n/p)+log_2^2(p))</math> (где n - количество сортируемых элементов, p - количество процессоров), то получаем итоговую сложность алгоритма как сумму всех ярусов, на которых параллельно запускается сортировка.
	А именно:		А именно:
	<math>\sum_{i=0}^{log_2 k} (n / p ~~+ p)~~ / 2^i * log_2 ((n / p + p) / 2^i) = O((n/~~p +~~ p) * log_2 (n/p + p) * log_2 k)</math>		<math>\sum_{i=0}^{log_2 k} ((n / 2^i) / (p / 2^i)) (log_2((n / 2^i) / (p / 2^i)) + log_2^2(p / 2^i)) = O((n/p) * (log_2 (n/p) + log_2^2(p)) * log_2 k)</math>
	== Входные и выходные данные алгоритма ==		== Входные и выходные данные алгоритма ==
	'''Входные данные''': требуемое количество доменов в разбиении, вершины графа. Каждой вершине соответствуют некоторые многомерные числовые координаты. Вершины могут быть произвольно разбиты по вычислительным узлам. Таким образом, '''объём входных данных''' пропорционален размеру графа V и количеству измерений N: \|V\|*N.		'''Входные данные''': требуемое количество доменов в разбиении, вершины графа. Каждой вершине соответствуют некоторые многомерные числовые координаты. Вершины могут быть произвольно разбиты по вычислительным узлам. Таким образом, '''объём входных данных''' пропорционален размеру графа V и количеству измерений N: \|V\|*N.