Алгоритм Δ-шагания - История изменений

ASA в 07:22, 5 июля 2022

2022-07-05T07:22:20Z

← Предыдущая версия		Версия от 07:22, 5 июля 2022
Строка 75:		Строка 75:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	~~=== Локальность данных и вычислений ===~~
	~~==== Локальность реализации алгоритма ====~~
	~~===== Структура обращений в память и качественная оценка локальности =====~~
	~~===== Количественная оценка локальности =====~~
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== ~~Масштабируемость алгоритма и его реализации ===~~		=== Результаты прогонов ===
	~~==== Масштабируемость алгоритма ====~~
	~~==== Масштабируемость реализации алгоритма ====~~
	~~=== Динамические характеристики и эффективность реализации алгоритма~~ ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	~~=== Существующие реализации алгоритма ===~~

	* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#delta-stepping-algorithm delta_stepping_shortest_paths]</code>). {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/25}}
	* Gap: {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/38}}
	== Литература ==		== Литература ==

Apaokin в 14:34, 15 июня 2018

2018-06-15T14:34:25Z

← Предыдущая версия		Версия от 14:34, 15 июня 2018
Строка 1:		Строка 1:
	{{level-a}}		{{level-a}}
	~~<indicator name='toplink'> {{Buttonlink\|http://top53.parallel.ru/algo_results/algorithm/2}} </indicator>~~
	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

Apaokin в 10:41, 15 июня 2018

2018-06-15T10:41:41Z

← Предыдущая версия		Версия от 10:41, 15 июня 2018
Строка 88:		Строка 88:
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

	* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#delta-stepping-algorithm delta_stepping_shortest_paths]</code>).		* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#delta-stepping-algorithm delta_stepping_shortest_paths]</code>). {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/25}}
	{{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/25}}
	* Gap: {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/38}}		* Gap: {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/38}}
	== Литература ==		== Литература ==

Apaokin в 09:49, 15 июня 2018

2018-06-15T09:49:55Z

← Предыдущая версия		Версия от 09:49, 15 июня 2018
Строка 90:		Строка 90:
	* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#delta-stepping-algorithm delta_stepping_shortest_paths]</code>).		* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#delta-stepping-algorithm delta_stepping_shortest_paths]</code>).
	{{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/25}}		{{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/25}}
			* Gap: {{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/38}}
	== Литература ==		== Литература ==

Apaokin в 08:35, 15 июня 2018

2018-06-15T08:35:32Z

← Предыдущая версия		Версия от 08:35, 15 июня 2018
Строка 1:		Строка 1:
	{{level-a}}		{{level-a}}
			<indicator name='toplink'> {{Buttonlink\|http://top53.parallel.ru/algo_results/algorithm/2}} </indicator>
	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

Apaokin в 12:25, 14 июня 2018

2018-06-14T12:25:57Z

← Предыдущая версия		Версия от 12:25, 14 июня 2018
Строка 89:		Строка 89:

	* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#delta-stepping-algorithm delta_stepping_shortest_paths]</code>).		* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html#delta-stepping-algorithm delta_stepping_shortest_paths]</code>).
			{{Buttonlink\|http://top53.parallel.ru/algo_results/implementation/25}}

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

ASA в 13:40, 14 марта 2018

2018-03-14T13:40:55Z

← Предыдущая версия		Версия от 13:40, 14 марта 2018
Строка 95:		Строка 95:

	[[Категория:Начатые статьи]]		[[Категория:Начатые статьи]]

			[[en:Δ-stepping algorithm]]

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

2018-03-06T14:11:08Z

← Предыдущая версия		Версия от 14:11, 6 марта 2018
Строка 1:		Строка 1:
			{{level-a}}

	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

ASA в 11:03, 29 июля 2015

2015-07-29T11:03:46Z

← Предыдущая версия		Версия от 11:03, 29 июля 2015
Строка 1:		Строка 1:
	== Свойства и структура ~~алгоритмов~~ ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	'''Алгоритм дельта-шагания'''<ref>Meyer, U, and P Sanders. “Δ-Stepping: a Parallelizable Shortest Path Algorithm.” Journal of Algorithms 49, no. 1 (October 2003): 114–52. doi:10.1016/S0196-6774(03)00076-2.</ref> (англ. Δ-Stepping) предназначен для решения [[Поиск кратчайшего пути от одной вершины (SSSP)\|задачи поиска кратчайшего пути на графе]]. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм изначально проектировался с целью эффективной параллелизации.		'''Алгоритм дельта-шагания'''<ref>Meyer, U, and P Sanders. “Δ-Stepping: a Parallelizable Shortest Path Algorithm.” Journal of Algorithms 49, no. 1 (October 2003): 114–52. doi:10.1016/S0196-6774(03)00076-2.</ref> (англ. Δ-Stepping) предназначен для решения [[Поиск кратчайшего пути от одной вершины (SSSP)\|задачи поиска кратчайшего пути на графе]]. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм изначально проектировался с целью эффективной параллелизации.

	=== Математическое описание ===		=== Математическое описание алгоритма ===
	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===
	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
	=== ~~Описание схемы~~ реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===
	Псевдокод последовательного алгоритма:		Псевдокод последовательного алгоритма:

Строка 50:		Строка 50:

	=== Информационный граф ===		=== Информационный граф ===
	=== ~~Описание ресурса~~ параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	Средняя время работы параллельного алгоритма на графах со случайными весами на <math>O(n)</math> процессорах составляет <math>O((dL + \ln n) \ln n)</math> со средней работой <math>O(n + m + dL \ln n)</math>		Средняя время работы параллельного алгоритма на графах со случайными весами на <math>O(n)</math> процессорах составляет <math>O((dL + \ln n) \ln n)</math> со средней работой <math>O(n + m + dL \ln n)</math>

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

	'''Входные данные''': взвешенный граф <math>(V, E, W)</math> (<math>n</math> вершин <math>v_i</math> и <math>m</math> рёбер <math>e_j = (v^{(1)}_{j}, v^{(2)}_{j})</math> с весами <math>f_j</math>), вершина-источник <math>u</math>.		'''Входные данные''': взвешенный граф <math>(V, E, W)</math> (<math>n</math> вершин <math>v_i</math> и <math>m</math> рёбер <math>e_j = (v^{(1)}_{j}, v^{(2)}_{j})</math> с весами <math>f_j</math>), вершина-источник <math>u</math>.
Строка 72:		Строка 72:
	* при <math>\Delta \to \infty</math>: [[алгоритм Беллмана-Форда]].		* при <math>\Delta \to \infty</math>: [[алгоритм Беллмана-Форда]].

	== Программная реализация ~~алгоритмов~~ ==		== Программная реализация алгоритма ==
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
	=== ~~Описание локальности~~ данных и вычислений ===		=== Локальность данных и вычислений ===
	=== Возможные способы и особенности реализации ~~параллельного~~ алгоритма ===		==== Локальность реализации алгоритма ====
			===== Структура обращений в память и качественная оценка локальности =====
			===== Количественная оценка локальности =====
			=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
			==== Масштабируемость алгоритма ====
			==== Масштабируемость реализации алгоритма ====
	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
Строка 86:		Строка 91:

	<references />		<references />

			[[Категория:Начатые статьи]]

Daryin: /* Описание входных и выходных данных */

2015-06-25T14:17:59Z

Описание входных и выходных данных

← Предыдущая версия		Версия от 14:17, 25 июня 2015
Строка 55:		Строка 55:

	=== Описание входных и выходных данных ===		=== Описание входных и выходных данных ===

			'''Входные данные''': взвешенный граф <math>(V, E, W)</math> (<math>n</math> вершин <math>v_i</math> и <math>m</math> рёбер <math>e_j = (v^{(1)}_{j}, v^{(2)}_{j})</math> с весами <math>f_j</math>), вершина-источник <math>u</math>.

			'''Объём входных данных''': <math>O(m + n)</math>.

			'''Выходные данные''' (возможные варианты):
			# для каждой вершины <math>v</math> исходного графа – последнее ребро <math>e^*_v = (w, v)</math>, лежащее на кратчайшем пути от вершины <math>u</math> к <math>v</math>, или соответствующая вершина <math>w</math>;
			# для каждой вершины <math>v</math> исходного графа – суммарный вес <math>f^*(v)</math> кратчайшего пути от от вершины <math>u</math> к <math>v</math>.

			'''Объём выходных данных''': <math>O(n)</math>.

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