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

ASA в 07:23, 7 июля 2022

2022-07-07T07:23:49Z

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

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

	<references />		<references />

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

2018-03-14T13:49:38Z

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

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

			[[en:GHS algorithm]]

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

2018-03-06T14:13:25Z

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

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

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

2015-07-29T11:17:42Z

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

	'''Алгоритм GHS''' (сокр. от фамилий авторов: Gallager, Humblet, Spira)<ref>Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.</ref> предназначен для распределённого [[Построение минимального остовного дерева (MST)\|построения минимального остовного дерева]] во взвешенном неориентированном графе. Алгоритм GHS основан на [[алгоритм Борувки\|алгоритме Борувки]], адаптированном для применения в распределённой среде. Известны модификации алгоритма, улучшающие среднее и наихудшее время работы<ref>Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.</ref><ref>Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.</ref><ref>Garay, Juan A, Shay Kutten, and David Peleg. “A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees.” SIAM Journal on Computing 27, no. 1 (February 1998): 302–16. doi:10.1137/S0097539794261118.</ref><ref>Faloutsos, Michalis, and Mart Molle. “A Linear-Time Optimal-Message Distributed Algorithm for Minimum Spanning Trees.” Distributed Computing 17, no. 2 (August 2004). doi:10.1007/s00446-004-0107-2.</ref>.		'''Алгоритм GHS''' (сокр. от фамилий авторов: Gallager, Humblet, Spira)<ref>Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.</ref> предназначен для распределённого [[Построение минимального остовного дерева (MST)\|построения минимального остовного дерева]] во взвешенном неориентированном графе. Алгоритм GHS основан на [[алгоритм Борувки\|алгоритме Борувки]], адаптированном для применения в распределённой среде. Известны модификации алгоритма, улучшающие среднее и наихудшее время работы<ref>Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.</ref><ref>Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.</ref><ref>Garay, Juan A, Shay Kutten, and David Peleg. “A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees.” SIAM Journal on Computing 27, no. 1 (February 1998): 302–16. doi:10.1137/S0097539794261118.</ref><ref>Faloutsos, Michalis, and Mart Molle. “A Linear-Time Optimal-Message Distributed Algorithm for Minimum Spanning Trees.” Distributed Computing 17, no. 2 (August 2004). doi:10.1007/s00446-004-0107-2.</ref>.

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

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

	~~<references />~~		[[Категория:Начатые статьи]]

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

2015-06-11T14:41:44Z

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

← Предыдущая версия		Версия от 14:41, 11 июня 2015
Строка 2:		Строка 2:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	Алгоритм GHS (Gallager, Humblet, Spira)<ref>Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.</ref> предназначен для распределённого [[Построение минимального остовного дерева (MST)\|построения минимального остовного дерева]] во взвешенном неориентированном графе. Алгоритм GHS основан на [[алгоритм Борувки\|алгоритме Борувки]], адаптированном для применения в распределённой среде. Известны модификации алгоритма, улучшающие среднее и наихудшее время работы<ref>Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.</ref><ref>Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.</ref><ref>Garay, Juan A, Shay Kutten, and David Peleg. “A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees.” SIAM Journal on Computing 27, no. 1 (February 1998): 302–16. doi:10.1137/S0097539794261118.</ref><ref>Faloutsos, Michalis, and Mart Molle. “A Linear-Time Optimal-Message Distributed Algorithm for Minimum Spanning Trees.” Distributed Computing 17, no. 2 (August 2004). doi:10.1007/s00446-004-0107-2.</ref>.		'''Алгоритм GHS''' (сокр. от фамилий авторов: Gallager, Humblet, Spira)<ref>Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.</ref> предназначен для распределённого [[Построение минимального остовного дерева (MST)\|построения минимального остовного дерева]] во взвешенном неориентированном графе. Алгоритм GHS основан на [[алгоритм Борувки\|алгоритме Борувки]], адаптированном для применения в распределённой среде. Известны модификации алгоритма, улучшающие среднее и наихудшее время работы<ref>Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.</ref><ref>Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.</ref><ref>Garay, Juan A, Shay Kutten, and David Peleg. “A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees.” SIAM Journal on Computing 27, no. 1 (February 1998): 302–16. doi:10.1137/S0097539794261118.</ref><ref>Faloutsos, Michalis, and Mart Molle. “A Linear-Time Optimal-Message Distributed Algorithm for Minimum Spanning Trees.” Distributed Computing 17, no. 2 (August 2004). doi:10.1007/s00446-004-0107-2.</ref>.

	=== Математическое описание ===		=== Математическое описание ===

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

2015-06-01T15:00:57Z

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

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

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

Алгоритм GHS (Gallager, Humblet, Spira)<ref>Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.</ref> предназначен для распределённого [[Построение минимального остовного дерева (MST)|построения минимального остовного дерева]] во взвешенном неориентированном графе. Алгоритм GHS основан на [[алгоритм Борувки|алгоритме Борувки]], адаптированном для применения в распределённой среде. Известны модификации алгоритма, улучшающие среднее и наихудшее время работы<ref>Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.</ref><ref>Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.</ref><ref>Garay, Juan A, Shay Kutten, and David Peleg. “A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees.” SIAM Journal on Computing 27, no. 1 (February 1998): 302–16. doi:10.1137/S0097539794261118.</ref><ref>Faloutsos, Michalis, and Mart Molle. “A Linear-Time Optimal-Message Distributed Algorithm for Minimum Spanning Trees.” Distributed Computing 17, no. 2 (August 2004). doi:10.1007/s00446-004-0107-2.</ref>.

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

<references />