Алгоритм Борувки - История изменений

ASA в 10:52, 5 июля 2022

2022-07-05T10:52:50Z

Apaokin в 11:42, 19 июня 2018

2018-06-19T11:42:43Z

← Предыдущая версия		Версия от 11:42, 19 июня 2018
Строка 292:		Строка 292:
	* 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/dehne_gotz_min_spanning_tree.html#dense-boruvka-minimum-spanning-tree dense_boruvka_minimum_spanning_tree]</code>, <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#boruvka-then-merge boruvka_then_merge]</code>, <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#boruvka-mixed-merge boruvka_mixed_merge]</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/dehne_gotz_min_spanning_tree.html#dense-boruvka-minimum-spanning-tree dense_boruvka_minimum_spanning_tree]</code>, <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#boruvka-then-merge boruvka_then_merge]</code>, <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#boruvka-mixed-merge boruvka_mixed_merge]</code> сочетают алгоритм Борувки и [[алгоритм Крускала]].
	* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] {{Buttonlinkimp\|28}}		* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] {{Buttonlinkimp\|28}}
	* RCC for CPU {{Buttonlinkimp\|15}}		* RCC for CPU: {{Buttonlinkimp\|15}}
	* RCC for GPU {{Buttonlinkimp\|13}}		* RCC for GPU: {{Buttonlinkimp\|13}}
	== Литература ==		== Литература ==

Apaokin в 11:32, 19 июня 2018

2018-06-19T11:32:47Z

← Предыдущая версия		Версия от 11:32, 19 июня 2018
Строка 291:		Строка 291:

	* 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/dehne_gotz_min_spanning_tree.html#dense-boruvka-minimum-spanning-tree dense_boruvka_minimum_spanning_tree]</code>, <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#boruvka-then-merge boruvka_then_merge]</code>, <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#boruvka-mixed-merge boruvka_mixed_merge]</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/dehne_gotz_min_spanning_tree.html#dense-boruvka-minimum-spanning-tree dense_boruvka_minimum_spanning_tree]</code>, <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#boruvka-then-merge boruvka_then_merge]</code>, <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#boruvka-mixed-merge boruvka_mixed_merge]</code> сочетают алгоритм Борувки и [[алгоритм Крускала]].
			* C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] {{Buttonlinkimp\|28}}
			* RCC for CPU {{Buttonlinkimp\|15}}
			* RCC for GPU {{Buttonlinkimp\|13}}
	== Литература ==		== Литература ==

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

2017-11-28T20:54:05Z

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

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

2017-11-28T20:35:18Z

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

← Предыдущая версия		Версия от 20:35, 28 ноября 2017
Строка 263:		Строка 263:
	[[file:Boruvka Loadavg.png\|thumb\|center\|700px\|Рисунок 10. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма Борувки]]		[[file:Boruvka Loadavg.png\|thumb\|center\|700px\|Рисунок 10. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма Борувки]]

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

	[[file:Boruvka L1.png\|thumb\|center\|700px\|Рисунок 11. График кэш-промахов L1 в секунду при работе алгоритма Борувки]]		[[file:Boruvka L1.png\|thumb\|center\|700px\|Рисунок 11. График кэш-промахов L1 в секунду при работе алгоритма Борувки]]
Строка 271:		Строка 271:
	[[file:Boruvka L2.png\|thumb\|center\|700px\|Рисунок 12. График кэш-промахов L1 в секунду при работе алгоритма Борувки]]		[[file:Boruvka L2.png\|thumb\|center\|700px\|Рисунок 12. График кэш-промахов L1 в секунду при работе алгоритма Борувки]]

	На графике кэш-промахов второго уровня видно, что число промахов достаточно ~~тоже~~ высокое и находится на уровне 30 млн/сек . На графике промахов второго уровня факт увеличения числа промахов к концу итерации проявляется более явно и увеличивается до значения в 50млн/сек.		На графике кэш-промахов второго уровня видно, что число промахов тоже достаточно высокое и находится на уровне 30 млн/сек . На графике промахов второго уровня факт увеличения числа промахов к концу итерации проявляется более явно и увеличивается до значения в 50млн/сек.

	[[file:Boruvka L3.png\|thumb\|center\|700px\|Рисунок 13. График кэш-промахов L3 в секунду при работе алгоритма Борувки]]		[[file:Boruvka L3.png\|thumb\|center\|700px\|Рисунок 13. График кэш-промахов L3 в секунду при работе алгоритма Борувки]]

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

2017-11-28T16:34:50Z

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

← Предыдущая версия		Версия от 16:34, 28 ноября 2017
Строка 239:		Строка 239:

	==== Масштабируемость реализации алгоритма ====		==== Масштабируемость реализации алгоритма ====
	Проведём исследование масштабируемости параллельной реализации алгоритма Борувки согласно [[Scalability methodology\|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов-2 [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].		Проведём исследование масштабируемости параллельной реализации алгоритма Борувки согласно [[Scalability methodology\|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов-2" [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].

	Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:		Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:

Ikramov: /* Локальность данных и вычислений */

2017-11-28T08:23:50Z

Локальность данных и вычислений

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

	На этапе поиска минимального ребра происходят следующие обращения к памяти:		На этапе поиска минимального ребра происходят следующие обращения к памяти:
	# Чтение информации о рёбрах. Может ~~производится~~ последовательно.		# Чтение информации о рёбрах. Может производиться последовательно.
	# Проверка принадлежности ребра одному и тому же фрагменту - два чтения массива <math>parent(u)</math> с вероятным ~~промахой~~ по кэшу.		# Проверка принадлежности ребра одному и тому же фрагменту - два чтения массива <math>parent(u)</math> с вероятным промахом по кэшу.
	# Чтение и обновление минимального веса ребра фрагмента. Данная информация может быть закеширована, особенно на поздних шагах, однако обновление необходимо производить атомарно, что требует инвализации кэша.		# Чтение и обновление минимального веса ребра фрагмента. Данная информация может быть закеширована, особенно на поздних шагах, однако обновление необходимо производить атомарно, что требует инвализации кэша.

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

2017-11-27T16:36:59Z

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

← Предыдущая версия		Версия от 16:36, 27 ноября 2017
Строка 118:		Строка 118:
	Итак, алгоритм Борувки обладает двумя уровнями параллелизма.		Итак, алгоритм Борувки обладает двумя уровнями параллелизма.

	На верхнем уровне минимальные остовные деревья могут искаться для отдельных частей списка ребер графа (параллельные compute_MST на рисунке 2). Однако, затем должно последовать финальное объединение полученных ребер и вычисление минимального остовного дерева для полученного графа, которое будет производиться последовательно.		На верхнем уровне минимальные остовные деревья могут искаться для отдельных частей списка ребер графа (параллельные compute_MST на рисунке 2). Однако затем должно последовать финальное объединение полученных ребер и вычисление минимального остовного дерева для полученного графа, которое будет производиться последовательно.

	Кроме того, вычисление каждого из минимальных остовных деревьев (параллельные compute_MST на рисунке 2) обладает внутренним ресурсом параллелизма, описанным далее. Операции инициализации и копирования данных ([1], [2], [9] на рисунке 1) могут производиться параллельно за <math>O(\|V\|)</math> операций. ~~Так же~~ параллельно могут производиться операции поиска минимальных исходящих ребер ([3],[4],[5]), при ~~том~~ для каждой дуги и обратной к ней независимо, что даёт <math>2*O(\|E\|)</math> параллельных операций. Помимо этого, операции объединения деревьев [6], [7], [8] могут ~~так же~~ производиться параллельно за <math>O(\|V\|)</math> операций.		Кроме того, вычисление каждого из минимальных остовных деревьев (параллельные compute_MST на рисунке 2) обладает внутренним ресурсом параллелизма, описанным далее. Операции инициализации и копирования данных ([1], [2], [9] на рисунке 1) могут производиться параллельно за <math>O(\|V\|)</math> операций. Также параллельно могут производиться операции поиска минимальных исходящих ребер ([3],[4],[5]), при этом для каждой дуги и обратной к ней независимо, что даёт <math>2*O(\|E\|)</math> параллельных операций. Помимо этого, операции объединения деревьев [6], [7], [8] могут также производиться параллельно за <math>O(\|V\|)</math> операций.

	В результате, для классического алгоритма Борувки ширина ярусно-параллельной формы равна <math>O(\|E\|)</math>, а высота ЯПФ зависит от числа шагов алгоритма, и ограничена сверху <math>O(ln(\|V\|))</math>.		В результате для классического алгоритма Борувки ширина ярусно-параллельной формы равна <math>O(\|E\|)</math>, а высота ЯПФ зависит от числа шагов алгоритма и ограничена сверху <math>O(ln(\|V\|))</math>.

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

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

2017-11-27T13:45:13Z

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

← Предыдущая версия		Версия от 13:45, 27 ноября 2017
Строка 98:		Строка 98:
	=== Информационный граф ===		=== Информационный граф ===

	В описанном подходе существует два уровня параллелизма: параллелизм в классическом алгоритме Борувки (нижний), и параллелизм в алгоритме ~~обработка~~ графа, не помещающегося в память.		В описанном подходе существует два уровня параллелизма: параллелизм в классическом алгоритме Борувки (нижний) и параллелизм в алгоритме обработки графа, не помещающегося в память.

	'''Нижний уровень параллелизма''': поиск минимальных исходящих рёбер может выполняться независимо для каждого фрагмента, благодаря чему данную стадию вычислений можно эффективно параллелизовать (как на GPU, так и на CPU). Объединение фрагментов также может быть реализовано параллельно, с использованием ~~описанной структуры~~ Union-Find.		'''Нижний уровень параллелизма''': поиск минимальных исходящих рёбер может выполняться независимо для каждого фрагмента, благодаря чему данную стадию вычислений можно эффективно параллелизовать (как на GPU, так и на CPU). Объединение фрагментов также может быть реализовано параллельно с использованием описанного выше алгоритма Union-Find.

	'''Верхний уровень параллелизма''': построение отдельных минимальных основных деревьев для каждого из списков ребер может производиться параллельно. Например, список ребер может разбиваться на две части, одна из которых обрабатывается на GPU, а вторая параллельно на CPU.		'''Верхний уровень параллелизма''': построение отдельных минимальных основных деревьев для каждого из списков ребер может производиться параллельно. Например, список ребер может разбиваться на две части, одна из которых обрабатывается на GPU, а вторая параллельно на CPU.
Строка 106:		Строка 106:
	[[file:MST low.png\|thumb\|center\|1000px\|Рисунок 1. Информационный граф нижнего уровня параллелизма]]		[[file:MST low.png\|thumb\|center\|1000px\|Рисунок 1. Информационный граф нижнего уровня параллелизма]]

	Рассмотрим информационные графы и подробное описание каждого из них. ~~Так же~~ можно считать, что на рисунке 1 представлен информационный граф классического алгоритма Борувки, а на рисунке 2 — алгоритма обработки графа.		Рассмотрим информационные графы и подробное описание каждого из них. Также можно считать, что на рисунке 1 представлен информационный граф классического алгоритма Борувки, а на рисунке 2 — алгоритма обработки графа.

	Нижний уровень параллелизма на графе алгоритма (рисунок 1) расположен на уровнях {3, 4, 5}, ~~соответствующим~~ операциям параллельного поиска минимальных исходящих ребер, а ~~так же~~ уровнях {6, 7, 8}, ~~соответствующим~~ операциям параллельного объединения деревьев. ~~Так же,~~ различные операции копирования {1, 2, 8, 9} выполняются параллельно. После выполнения тела цикла, производится проверка {12} того, сколько деревьев осталось на текущем шаге, и если данное число не изменилось, то происходит выход из цикла, иначе ~~аналогичная следующая итерация~~.		Нижний уровень параллелизма на графе алгоритма (рисунок 1) расположен на уровнях {3, 4, 5}, соответствующих операциям параллельного поиска минимальных исходящих ребер, а также на уровнях {6, 7, 8}, соответствующих операциям параллельного объединения деревьев. Также различные операции копирования {1, 2, 8, 9} выполняются параллельно. После выполнения тела цикла производится проверка {12} того, сколько деревьев осталось на текущем шаге, и если данное число не изменилось, то происходит выход из цикла, иначе переход к следующей итерации.

	Верхний уровень параллелизма (рисунок 2), как уже говорилось, заключается в параллельном вычислении минимального ~~основного~~ дерева (compute mst) для различных частей графа. Перед этим производится процесс инициализации (init process), данные которого используют последующие параллельные compute mst. Затем, после параллельных вычислений mst, происходит вычисление ~~итого~~ основного ~~дерево~~, ~~после чего~~ после чего полученный результат сохраняется (save results).		Верхний уровень параллелизма (рисунок 2), как уже говорилось, заключается в параллельном вычислении минимального остовного дерева (compute mst) для различных частей графа. Перед этим производится процесс инициализации (init process), данные которого используют последующие параллельные операции compute mst. Затем, после параллельных вычислений mst, происходит вычисление итогового основного дерева, после чего полученный результат сохраняется (save results).

	[[file:MST up.png\|thumb\|center\|1000px\|Рисунок 2. Информационный граф верхнего уровня параллелизма]]		[[file:MST up.png\|thumb\|center\|1000px\|Рисунок 2. Информационный граф верхнего уровня параллелизма]]

Ikramov: /* Схема реализации последовательного алгоритма */

2017-11-27T12:37:44Z

Схема реализации последовательного алгоритма

← Предыдущая версия		Версия от 12:37, 27 ноября 2017
Строка 76:		Строка 76:
	* Минимальные рёбра добавляются в минимальное остовное дерево, а соответствующие фрагменты объединяются.		* Минимальные рёбра добавляются в минимальное остовное дерево, а соответствующие фрагменты объединяются.

	3. Алгоритм останавливается, когда остаётся только один фрагмент, либо когда ни у одного из фрагментов нет исходящих рёбер.		3. Алгоритм останавливается, когда остаётся только один фрагмент либо когда ни у одного из фрагментов нет исходящих рёбер.

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

	Объединение фрагментов также может быть реализовано параллельно, с использованием ~~описанной выше~~ параллельной версии ~~структуры~~ Union-Find.		Объединение фрагментов также может быть реализовано параллельно с использованием параллельной версии описанного выше алгоритма Union-Find.

	Аккуратный подсчёт количества активных фрагментов позволяет остановить алгоритм Борувки на один шаг раньше обычного:		Аккуратный подсчёт количества активных фрагментов позволяет остановить алгоритм Борувки на один шаг раньше обычного:

← Предыдущая версия		Версия от 20:54, 28 ноября 2017
Строка 257:		Строка 257:
	Для проведения экспериментов использовалась реализация алгоритма Борувки, реализованная для CPU. Все результаты получены на суперкомпьютере «Ломоносов-2». Использовались процессоры Intel Xeon E5-2697v3, задача решалась для графа большого размера на одном узле.		Для проведения экспериментов использовалась реализация алгоритма Борувки, реализованная для CPU. Все результаты получены на суперкомпьютере «Ломоносов-2». Использовались процессоры Intel Xeon E5-2697v3, задача решалась для графа большого размера на одном узле.
	На рисунках показана эффективность реализации алгоритма Борувки, запуск проводился на 1 узле для графа 2^27, выполнялась 1 итерация.		На рисунках показана эффективность реализации алгоритма Борувки, запуск проводился на 1 узле для графа 2^27, выполнялась 1 итерация.
	[[file:Boruvka cpu.png\|thumb\|center\|700px\|Рисунок 9. График загрузки CPU при выполнении алгоритма Борувки]]		[[file:Boruvka cpu.png\|thumb\|center\|700px\|Рисунок 11. График загрузки CPU при выполнении алгоритма Борувки]]

	На графике загрузки процессора видно, что почти все время работы программы не загружены и средний уровень загрузки составляет около 10%. Это нормальная картина для программ, запущенных c использованием одного ядра в реализации.		На графике загрузки процессора видно, что почти все время работы программы не загружены и средний уровень загрузки составляет около 10%. Это нормальная картина для программ, запущенных c использованием одного ядра в реализации.

	[[file:Boruvka Loadavg.png\|thumb\|center\|700px\|Рисунок 10. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма Борувки]]		[[file:Boruvka Loadavg.png\|thumb\|center\|700px\|Рисунок 12. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма Борувки]]

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

	[[file:Boruvka L1.png\|thumb\|center\|700px\|Рисунок 11. График кэш-промахов L1 в секунду при работе алгоритма Борувки]]		[[file:Boruvka L1.png\|thumb\|center\|700px\|Рисунок 13. График кэш-промахов L1 в секунду при работе алгоритма Борувки]]

	На графике кэш-промахов первого уровня видно, что число промахов очень высокое и находится на уровне 40 млн/сек . Интересен факт увеличения числа промахов к концу итерации до уровня в 70 млн/сек.		На графике кэш-промахов первого уровня видно, что число промахов очень высокое и находится на уровне 40 млн/сек . Интересен факт увеличения числа промахов к концу итерации до уровня в 70 млн/сек.

	[[file:Boruvka L2.png\|thumb\|center\|700px\|Рисунок 12. График кэш-промахов L1 в секунду при работе алгоритма Борувки]]		[[file:Boruvka L2.png\|thumb\|center\|700px\|Рисунок 14. График кэш-промахов L1 в секунду при работе алгоритма Борувки]]

	На графике кэш-промахов второго уровня видно, что число промахов тоже достаточно высокое и находится на уровне 30 млн/сек . На графике промахов второго уровня факт увеличения числа промахов к концу итерации проявляется более явно и увеличивается до значения в 50млн/сек.		На графике кэш-промахов второго уровня видно, что число промахов тоже достаточно высокое и находится на уровне 30 млн/сек . На графике промахов второго уровня факт увеличения числа промахов к концу итерации проявляется более явно и увеличивается до значения в 50млн/сек.

	[[file:Boruvka L3.png\|thumb\|center\|700px\|Рисунок 13. График кэш-промахов L3 в секунду при работе алгоритма Борувки]]		[[file:Boruvka L3.png\|thumb\|center\|700px\|Рисунок 15. График кэш-промахов L3 в секунду при работе алгоритма Борувки]]

	На графике кэш-промахов последнего уровня видно, что число промахов тоже достаточно большое и составляет около 30 млн/сек по всем узлам. Эт указывает на то, что задача очень плохо укладывается в кэш-память, и программа постоянно работает с оперативной памятью, что объясняется очень большим размером использованного графа.		На графике кэш-промахов последнего уровня видно, что число промахов тоже достаточно большое и составляет около 30 млн/сек по всем узлам. Это указывает на то, что задача очень плохо укладывается в кэш-память, и программа постоянно работает с оперативной памятью, что объясняется очень большим размером использованного графа.

	[[file:Boruvka Inf data.png\|thumb\|center\|700px\|Рисунок 13. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма Борувки]]		[[file:Boruvka Inf data.png\|thumb\|center\|700px\|Рисунок 16. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма Борувки]]

	На графике скорости передачи данных по сети Infiniband наблюдается достаточно высокая интенсивность использования сети на ~~кпервом~~ этапе. Это объясняется программной логикой, которая предполагает чтение графа из файла с диска, коммуникации с которым происходят на Ломоносов-2 через выделенную для этих задач сеть Infiniband.		На графике скорости передачи данных по сети Infiniband наблюдается достаточно высокая интенсивность использования сети на первом этапе. Это объясняется программной логикой, которая предполагает чтение графа из файла с диска, коммуникации с которым происходят на Ломоносов-2 через выделенную для этих задач сеть Infiniband.

	[[file:Boruvka inf pckts.png\|thumb\|center\|700px\|Рисунок 14. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма Борувки]]		[[file:Boruvka inf pckts.png\|thumb\|center\|700px\|Рисунок 17. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма Борувки]]

	На графике скорости передачи данных в пакетах в секунду наблюдается аналогичная картина очень высокой интенсивности на первом этапе выполнения задачи. Далее сеть почти не используется.		На графике скорости передачи данных в пакетах в секунду наблюдается аналогичная картина очень высокой интенсивности на первом этапе выполнения задачи. Далее сеть почти не используется.