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

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

2022-07-05T07:54:22Z

@@ Строка 74: / Строка 74: @@
 == Программная реализация алгоритма ==
 === Особенности реализации последовательного алгоритма ===
 === Возможные способы и особенности параллельной реализации алгоритма ===
-=== Масштабируемость алгоритма и его реализации ===
+=== Результаты прогонов ===
 === Выводы для классов архитектур ===
 == Литература ==

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

2018-03-14T13:43:39Z

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

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

			[[en:Floyd-Warshall algorithm]]

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

2018-03-06T14:12:02Z

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

	Автор: Екатерина Шевченко		Автор: Екатерина Шевченко
	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==

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

2017-12-01T08:11:29Z

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

← Предыдущая версия		Версия от 08:11, 1 декабря 2017
Строка 88:		Строка 88:
	==== Масштабируемость реализации алгоритма ====		==== Масштабируемость реализации алгоритма ====
	Проведём исследование масштабируемости параллельной реализации алгоритма. Работа выполнена с использованием оборудования Центра коллективного пользования сверхвысокопроизводительными вычислительными ресурсами МГУ имени М.В. Ломоносова.		Проведём исследование масштабируемости параллельной реализации алгоритма. Работа выполнена с использованием оборудования Центра коллективного пользования сверхвысокопроизводительными вычислительными ресурсами МГУ имени М.В. Ломоносова.
	Сильная масштабируемость показывает, как меняется время решения задачи с увеличением количества процессоров (или вычислительных узлов) при неизменном общем объёме задачи~~. Исследование показало, что параллельный алгоритм Флойда-Уоршелла сильно масштабируем~~.		Сильная масштабируемость показывает, как меняется время решения задачи с увеличением количества процессоров (или вычислительных узлов) при неизменном общем объёме задачи.

	[[file: Pic1.jpg\|thumb\|center\|700px\|Сравнение времени параллельной работы алгоритма Флойда-Уоршелла в зависимости от количества процессоров.]]		[[file: Pic1.jpg\|thumb\|center\|700px\|Сравнение времени параллельной работы алгоритма Флойда-Уоршелла в зависимости от количества процессоров.]]

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

2017-12-01T08:11:06Z

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

← Предыдущая версия		Версия от 08:11, 1 декабря 2017
Строка 88:		Строка 88:
	==== Масштабируемость реализации алгоритма ====		==== Масштабируемость реализации алгоритма ====
	Проведём исследование масштабируемости параллельной реализации алгоритма. Работа выполнена с использованием оборудования Центра коллективного пользования сверхвысокопроизводительными вычислительными ресурсами МГУ имени М.В. Ломоносова.		Проведём исследование масштабируемости параллельной реализации алгоритма. Работа выполнена с использованием оборудования Центра коллективного пользования сверхвысокопроизводительными вычислительными ресурсами МГУ имени М.В. Ломоносова.
			Сильная масштабируемость показывает, как меняется время решения задачи с увеличением количества процессоров (или вычислительных узлов) при неизменном общем объёме задачи. Исследование показало, что параллельный алгоритм Флойда-Уоршелла сильно масштабируем.

	[[file: Pic1.jpg\|thumb\|center\|700px\|Сравнение времени параллельной работы алгоритма Флойда-Уоршелла в зависимости от количества процессоров.]]		[[file: Pic1.jpg\|thumb\|center\|700px\|Сравнение времени параллельной работы алгоритма Флойда-Уоршелла в зависимости от количества процессоров.]]

EkaterinaShevchenko: /* Свойства и структура алгоритма */

2017-11-30T22:24:26Z

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

← Предыдущая версия		Версия от 22:24, 30 ноября 2017
Строка 1:		Строка 1:
			Автор: Екатерина Шевченко
	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

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

2017-11-30T22:23:02Z

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

← Предыдущая версия		Версия от 22:23, 30 ноября 2017
Строка 86:		Строка 86:

	==== Масштабируемость реализации алгоритма ====		==== Масштабируемость реализации алгоритма ====
			Проведём исследование масштабируемости параллельной реализации алгоритма. Работа выполнена с использованием оборудования Центра коллективного пользования сверхвысокопроизводительными вычислительными ресурсами МГУ имени М.В. Ломоносова.

			[[file: Pic1.jpg\|thumb\|center\|700px\|Сравнение времени параллельной работы алгоритма Флойда-Уоршелла в зависимости от количества процессоров.]]

			[[file: Pic3.jpg\|thumb\|center\|700px\|Ускорение параллельного алгоритма Флойда-Уоршелла с ростом числа процессоров.]]

			Как видно из представленных графиков параллельный алгоритм сильно масштабируем.

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

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

2017-11-30T20:54:52Z

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

← Предыдущая версия		Версия от 20:54, 30 ноября 2017
Строка 78:		Строка 78:
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	==== Масштабируемость алгоритма ====		==== Масштабируемость алгоритма ====
			Возможность обрабатывать фрагменты независимо означает хорошую масштабируемость алгоритма. Сдерживающие факторы: <br>
			1)Пропускная способность памяти при чтении данных графа.<br>
			2)Соперничество потоков при выполнении атомарных операций с памятью. <br>
			3)Синхронизация после каждого подшага алгоритма. <br>

			Алгоритм Флойда-Уоршелла обладает большим потенциалом масштабируемости, так как вычисление кратчайших путей можно распределить между независимыми процессами вплоть до вычисления каждым отдельным процессом одного элемента матрицы смежности.

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

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

2017-11-30T20:13:00Z

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

← Предыдущая версия		Версия от 20:13, 30 ноября 2017
Строка 48:		Строка 48:

	=== Информационный граф ===		=== Информационный граф ===
			[[file:Graphforfloyd.png\|thumb\|center\|300px\|Рис.1. Информационная структура предельной параллелизации алгоритма Флойда-Уоршелла]]

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

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	В последовательном алгоритме единственная операция - это нахождение минимума, ее нет смысла распараллеливать. Вся сложность алгоритма заключается в полном переборе «матрицы смежности». Идея параллельных схем алгоритма Флойда-Уоршелла состоит в том, чтобы модифицировать матрицу смежности одновременно несколькими процессорами. Можно выделить два основных подхода.		В последовательном алгоритме единственная операция - это нахождение минимума, ее нет смысла распараллеливать. Вся сложность алгоритма заключается в полном переборе «матрицы смежности». Идея параллельных схем алгоритма Флойда-Уоршелла состоит в том, чтобы модифицировать матрицу смежности одновременно несколькими процессорами. Можно выделить два основных подхода.

EkaterinaShevchenko: /* Свойства и структура алгоритма */

2017-11-30T19:03:50Z

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

← Предыдущая версия		Версия от 19:03, 30 ноября 2017
Строка 22:		Строка 22:

	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
			Ключевая часть алгоритма состоит из трех циклов:<br>
			Для k от 1 до \|V\| выполнять <br>
			Для i от 1 до \|V\| выполнять <br>
			Для j от 1 до \|V\| выполнять <br>
			Если <math>{D_{ik}+D_{kj} < D_{ij}}</math>, то <math>{D_{ij} := D_{ik}+D_{kj}}</math>. <br>

			При этом вычисляются минимумы из двух чисел <math>min({D_{ik}+D_{kj}}, D_{ij})</math> и их значения становятся новыми значениями элементов смежной матрицы. <br>
	=== Схема реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===
	matrix - матрица смежности, numberOfVert - число вершин в графе		matrix - матрица смежности, numberOfVert - число вершин в графе