Участник:Dmarkin/Алгоритм кластеризации, основанный на минимальном покрывающем дереве: различия между версиями
Dmarkin (обсуждение | вклад) |
ASA (обсуждение | вклад) |
||
(не показано 37 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
+ | {{Assignment|ASA}} | ||
+ | |||
'''Автор описания:''' [[Участник:Dmarkin | Маркин Дмитрий Валерьевич, группа 611]] | '''Автор описания:''' [[Участник:Dmarkin | Маркин Дмитрий Валерьевич, группа 611]] | ||
== Свойства и структура алгоритмов == | == Свойства и структура алгоритмов == | ||
Строка 5: | Строка 7: | ||
Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны. | Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны. | ||
− | Алгоритм кластеризации на | + | Алгоритм кластеризации на <math>K</math> кластеров, основанный на построении минимального остовного дерева (<math>MST</math>): |
#По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой); | #По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой); | ||
#Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: [[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]]) | #Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: [[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]]) | ||
− | #Удаляется | + | #Удаляется <math>K-1</math> ребро минимального остовного дерева с максимальным весом и получаются k компонент связности. |
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
Строка 24: | Строка 26: | ||
#Построение графа и вычисление расстояний. Сложность <math>O(N^2)</math>; | #Построение графа и вычисление расстояний. Сложность <math>O(N^2)</math>; | ||
− | #Построение минимального покрывающего дерева при помощи одного из наиболее распространенных методов ([[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]]). Сложность <math> O(N^2 log | + | #Построение минимального покрывающего дерева при помощи одного из наиболее распространенных методов ([[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]]). Сложность <math> O(N^2 \log N) </math>; |
#Разбиение на кластеры. Сложность в худшем случае <math>O(N)</math>. | #Разбиение на кластеры. Сложность в худшем случае <math>O(N)</math>. | ||
Строка 31: | Строка 33: | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
− | + | Макроструктура алгоритма описана в пункте 1.3. | |
+ | Отметим основные макрооперации, которые входят в состав алгоритма: | ||
+ | * Вычисление расстояний между вершинами; | ||
* Добавление ребра в граф; | * Добавление ребра в граф; | ||
− | |||
* Нахождение минимального покрывающего дерева, что является вычислительным ядром алогоритма; | * Нахождение минимального покрывающего дерева, что является вычислительным ядром алогоритма; | ||
* Удаление ребра из графа. | * Удаление ребра из графа. | ||
Строка 42: | Строка 45: | ||
==== Обозначения ==== | ==== Обозначения ==== | ||
− | * <math> | + | * <math>D(i) </math> — расстояние от <math>i</math>-й вершины до построенного дерева; |
+ | * <math>P(i) </math> — предок <math>i</math>-й вершины, то есть такая вершина <math>u</math>, что <math>(u,i)</math> легчайшее из всех рёбер, соединяющее <math>i</math> с вершиной из построенного дерева; | ||
+ | * <math>W(i,j)</math> — вес ребра <math>(i,j)</math>; | ||
+ | * <math>Q</math> — приоритетная очередь вершин графа, где ключ — <math>D(i)</math>; | ||
+ | * <math>T</math> — множество ребер минимального остовного дерева. | ||
+ | |||
+ | ==== Псевдокод ==== | ||
+ | |||
+ | <math>T \gets </math> {} //множество ребер минимального остовного дерева объявляется пустым | ||
+ | Для каждой вершины <math> i \in V </math> | ||
+ | <math>D(i) \gets \infty </math> //расстояние до построенного дерева объявляется максимальным | ||
+ | <math>P(i) \gets nil</math> //вершина не имеет предков из построенного дерева | ||
+ | <math>D(1) \gets 0</math> //включаем вершину с номером 1 в дерево | ||
+ | <math>Q \gets V</math> //записываем в очередь множество всех вершин | ||
+ | Пока <math>Q </math> не пуста | ||
+ | <math>v \gets\ Extract.min(Q) </math> //извлекаем из очереди вершину с минимальным расстоянием до построенного дерева | ||
+ | Для каждой вершины <math>u</math> смежной с <math>v</math> | ||
+ | Если <math>u \in Q</math> и <math>W(v,u) < D(u)</math> | ||
+ | <math>D(u) \gets W(v,u)</math> | ||
+ | <math>P(u) \gets v</math> | ||
+ | <math>v \gets Extract.Min(Q)</math> | ||
+ | <math>T \gets T+(P(v),v)</math> //добавляем выбранное ребро в дерево | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
+ | |||
+ | Последовательная сложность определяется суммой сложностей трёх основных этапов: | ||
+ | |||
+ | <math>T(N) = O(N^2) + O(N^2 \log N) + O(N) = O(N^2 \log N)</math> | ||
+ | |||
=== Информационный граф === | === Информационный граф === | ||
− | [[Файл: | + | [[Файл:15.png|border|мини|центр|1000px|Информационный граф параллельного алгоритма построения минимального покрывающего дерева]] |
=== Ресурс параллелизма алгоритма === | === Ресурс параллелизма алгоритма === | ||
+ | |||
+ | Рассмотрим основные свойства задачи: | ||
+ | *'''Схлопывание фрагментов'''. Пусть <math>F</math> – фрагмент минимального остовного дерева графа <math>G</math>, а граф <math>G'</math> получен из <math>G</math> склеиванием вершин, принадлежащих <math>F</math>. Тогда объединение <math>F</math> и минимального остовного дерева графа <math>G'</math> даёт минимальное остовное дерево исходного графа <math>G</math>. | ||
+ | *'''Ассоциативность по рёбрам'''. Пусть <math>MSF(E)</math> – минимальный остовный лес графа с рёбрами <math>E</math>. Тогда:<math> | ||
+ | MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)). | ||
+ | </math> | ||
+ | *'''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны [[алгоритм Борувки]] и [[алгоритм Прима]]. | ||
+ | |||
+ | Ресурс параллелизма основан на следующих возможностях: | ||
+ | # Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов. | ||
+ | # Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными. | ||
+ | # Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента. | ||
+ | |||
+ | Существуют распределённые алгоритмы построения минимального покрывающего дерева, имеющие асимптотическую параллельную сложность <math>O(N \log N)</math>. Например, '''[[Алгоритм GHS]]''' (Gallager, Humblet, Spira) является распределённым вариантом алгоритма Борувки. Последующие версии этого алгоритма имеют более низкую параллельную сложность. | ||
+ | |||
=== Входные и выходные данные алгоритма === | === Входные и выходные данные алгоритма === | ||
+ | '''Входные данные:''' множество объектов <math>x = (x_1,...,x_N)</math>. Объём <math>O(N)</math>. | ||
+ | |||
+ | '''Выходные данные:''' множество кластеров <math>Clust = (Clust_1,...,Clust_K)</math>, где <math>Clust_i = (x_{i,1},..., x_{i, N_i}), x_{i, l} \ne x_{j, m}, i \ne j, \forall l</math> и <math>m, \sum_{i=1}^K {N_i} = N </math>. Объём <math>O(N)</math>. | ||
+ | |||
=== Свойства алгоритма === | === Свойства алгоритма === | ||
+ | * Алгоритм останавливается за конечное число шагов, поскольку на каждом шаге становится по крайней мере на один фрагмент меньше. | ||
+ | * Число фрагментов на каждом шаге уменьшается как минимум вдвое, так что общее число шагов составляет не более <math>\log_2 N</math>. | ||
+ | * Соотношение последовательной и параллельной сложности: <math> \frac{N^2 \log N} {N \log N} = N </math>. | ||
+ | * Вычислительная мощность: <math> \frac {N^2 \log N} {N} = N \log N</math>. | ||
+ | * Алгоритм детерминирован. Если случается, что имеются два ребра <math>(x_i,x_j)</math> и <math>(x_l,x_m)</math>, такие что <math>d(x_i,x_j) = d(x_l,x_m)</math>, то алгоритм должен выбрать ребро, одна из вершин которого имеет минимальный индекс <math>\min(i,j,l,m)</math>, если эти два ребра выходят из одной вершины, индекс которой является минимальным (например, <math>i=l</math> ), то выбирается ребро, вершина которого имеет наименьший индекс из двух других вершин <math>\min(j,m)</math>. | ||
== Программная реализация алгоритма == | == Программная реализация алгоритма == | ||
Строка 56: | Строка 109: | ||
=== Возможные способы и особенности параллельной реализации алгоритма === | === Возможные способы и особенности параллельной реализации алгоритма === | ||
=== Масштабируемость алгоритма и его реализации === | === Масштабируемость алгоритма и его реализации === | ||
+ | |||
+ | Масштабируемость алгоритма Прима исследована на параллельной версии, представленной в [http://portal.tpu.ru/SHARED/a/AXOENOWSW/Publications_rus/Tab3/Tab/Гергель%20В.П.%20-%20Высокопроизводит.pdf книге]. При помощи директив OpenMP алгоритм распараллеливался по ядрам. В данном источнике представлены результаты экспериментов при использовании 2 и 4 вычислительных ядер и изменении объёма входных данных от 100 до 1000. Эксперименты проводились на двухпроцессорном вычислительном узле на базе четырехядерных процессоров Intel Xeon E5320, 1.86 ГГц, 4 Гб RAM под управлением операционной системы Microsoft Windows HPC Server 2008. Разработка программ проводилась в среде Microsoft Visual Studio 2008, для компиляции использовался Intel C++ Compiler 10.0 for Windows. | ||
+ | |||
+ | [[Файл:2017-02-08_06-56-11.png|border|мини|центр|1000px|Результаты вычислительных экспериментов для параллельного алгоритма Прима (при использовании двух и четырех вычислительных ядер) ]] | ||
+ | |||
+ | Из графика видно, что время выполнения увеличивается при увеличении объёма входных данных, но уменьшается при увеличении вычислительных ядер. | ||
+ | |||
=== Динамические характеристики и эффективность реализации алгоритма === | === Динамические характеристики и эффективность реализации алгоритма === | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
+ | *[https://github.com/jakevdp/mst_clustering Python: MST Clustering] | ||
+ | *[http://www.boost.org/doc/libs/1_62_0/libs/graph_parallel/doc/html/index.html С++: Parallel boost graph library] | ||
+ | *[http://www.boost.org/doc/libs/1_53_0/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html C++: Minimum Spanning Tree] | ||
+ | *[http://jgrapht.org/javadoc/org/jgrapht/alg/PrimMinimumSpanningTree.html Java: JGraphT PrimMinimumSpanningTree] | ||
+ | *[http://jgrapht.org/javadoc/org/jgrapht/alg/KruskalMinimumSpanningTree.html Java: JGraphT KruskalMinimumSpanningTree] | ||
+ | *[http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html Python: SciPy] | ||
+ | *[https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.mst.html Python: NetworkX] | ||
== Литература == | == Литература == | ||
+ | # Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с. | ||
+ | # Нейский И.М. Классификация и сравнение методов кластеризации | ||
+ | # C. Kingsford. Minimum Spanning Trees & Clustering | ||
+ | # Y. Zhou et al. Clustering with Minimum Spanning Trees | ||
+ | # 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. | ||
+ | # 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. | ||
+ | # 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. | ||
+ | # Гергель В.П. Высокопроизводительные вычисления для многоядерных многопроцессорных систем |
Текущая версия на 14:00, 8 февраля 2017
Эта работа прошла предварительную проверку Дата последней правки страницы: 08.02.2017 Данная работа соответствует формальным критериям. Проверено ASA. |
Автор описания: Маркин Дмитрий Валерьевич, группа 611
Содержание
- 1 Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны.
Алгоритм кластеризации на [math]K[/math] кластеров, основанный на построении минимального остовного дерева ([math]MST[/math]):
- По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой);
- Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: Алгоритм Крускала, Алгоритм Борувки, Алгоритм Прима)
- Удаляется [math]K-1[/math] ребро минимального остовного дерева с максимальным весом и получаются k компонент связности.
1.2 Математическое описание алгоритма
Имеем [math]N[/math] объектов [math]x[/math], которые представляют собой элемент метрического пространства с метрикой [math]d(x_i,x_j)=\sqrt{\sum^{n}_{k=1} {(x_{ik}-x_{jk})^2}}[/math].
На первом шаге строим граф [math]G=(V,E)[/math] с множеством вершин [math]V[/math] ([math]|V|=N[/math]) и множеством ребер [math]E[/math] ([math]|E|=\frac{N*(N-1)} {2}[/math]).
На втором этапе строится минимальное покрывающее дерево [math]MST(G)[/math].
На третьем этапе удаляется [math]K-1[/math] ребро, и дерево распадается на поддеревья [math]MST_i[/math], вершины которых объявляются принадлежащими кластеру с номером [math]i[/math].
1.3 Вычислительное ядро алгоритма
Алгоритм состоит из трёх независимых шагов:
- Построение графа и вычисление расстояний. Сложность [math]O(N^2)[/math];
- Построение минимального покрывающего дерева при помощи одного из наиболее распространенных методов ( Алгоритм Крускала, Алгоритм Борувки, Алгоритм Прима). Сложность [math] O(N^2 \log N) [/math];
- Разбиение на кластеры. Сложность в худшем случае [math]O(N)[/math].
Отсюда следует, что вычислительным ядром алгоритма является этап построения минимального покрывающего дерева, поскольку он имеет наибольшую сложность.
1.4 Макроструктура алгоритма
Макроструктура алгоритма описана в пункте 1.3. Отметим основные макрооперации, которые входят в состав алгоритма:
- Вычисление расстояний между вершинами;
- Добавление ребра в граф;
- Нахождение минимального покрывающего дерева, что является вычислительным ядром алогоритма;
- Удаление ребра из графа.
1.5 Схема реализации последовательного алгоритма
1.5.1 Обозначения
- [math]D(i) [/math] — расстояние от [math]i[/math]-й вершины до построенного дерева;
- [math]P(i) [/math] — предок [math]i[/math]-й вершины, то есть такая вершина [math]u[/math], что [math](u,i)[/math] легчайшее из всех рёбер, соединяющее [math]i[/math] с вершиной из построенного дерева;
- [math]W(i,j)[/math] — вес ребра [math](i,j)[/math];
- [math]Q[/math] — приоритетная очередь вершин графа, где ключ — [math]D(i)[/math];
- [math]T[/math] — множество ребер минимального остовного дерева.
1.5.2 Псевдокод
[math]T \gets [/math] {} //множество ребер минимального остовного дерева объявляется пустым Для каждой вершины [math] i \in V [/math] [math]D(i) \gets \infty [/math] //расстояние до построенного дерева объявляется максимальным [math]P(i) \gets nil[/math] //вершина не имеет предков из построенного дерева [math]D(1) \gets 0[/math] //включаем вершину с номером 1 в дерево [math]Q \gets V[/math] //записываем в очередь множество всех вершин Пока [math]Q [/math] не пуста [math]v \gets\ Extract.min(Q) [/math] //извлекаем из очереди вершину с минимальным расстоянием до построенного дерева Для каждой вершины [math]u[/math] смежной с [math]v[/math] Если [math]u \in Q[/math] и [math]W(v,u) \lt D(u)[/math] [math]D(u) \gets W(v,u)[/math] [math]P(u) \gets v[/math] [math]v \gets Extract.Min(Q)[/math] [math]T \gets T+(P(v),v)[/math] //добавляем выбранное ребро в дерево
1.6 Последовательная сложность алгоритма
Последовательная сложность определяется суммой сложностей трёх основных этапов:
[math]T(N) = O(N^2) + O(N^2 \log N) + O(N) = O(N^2 \log N)[/math]
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
Рассмотрим основные свойства задачи:
- Схлопывание фрагментов. Пусть [math]F[/math] – фрагмент минимального остовного дерева графа [math]G[/math], а граф [math]G'[/math] получен из [math]G[/math] склеиванием вершин, принадлежащих [math]F[/math]. Тогда объединение [math]F[/math] и минимального остовного дерева графа [math]G'[/math] даёт минимальное остовное дерево исходного графа [math]G[/math].
- Ассоциативность по рёбрам. Пусть [math]MSF(E)[/math] – минимальный остовный лес графа с рёбрами [math]E[/math]. Тогда:[math] MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)). [/math]
- Минимальное ребро фрагмента. Пусть [math]F[/math] – фрагмент минимального остовного дерева и [math]e_F[/math] – ребро наименьшего веса, исходящее из [math]F[/math] (т.е. ровно один его конец является вершиной из [math]F[/math]). Если ребро [math]e_F[/math] единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны алгоритм Борувки и алгоритм Прима.
Ресурс параллелизма основан на следующих возможностях:
- Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
- Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
- Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.
Существуют распределённые алгоритмы построения минимального покрывающего дерева, имеющие асимптотическую параллельную сложность [math]O(N \log N)[/math]. Например, Алгоритм GHS (Gallager, Humblet, Spira) является распределённым вариантом алгоритма Борувки. Последующие версии этого алгоритма имеют более низкую параллельную сложность.
1.9 Входные и выходные данные алгоритма
Входные данные: множество объектов [math]x = (x_1,...,x_N)[/math]. Объём [math]O(N)[/math].
Выходные данные: множество кластеров [math]Clust = (Clust_1,...,Clust_K)[/math], где [math]Clust_i = (x_{i,1},..., x_{i, N_i}), x_{i, l} \ne x_{j, m}, i \ne j, \forall l[/math] и [math]m, \sum_{i=1}^K {N_i} = N [/math]. Объём [math]O(N)[/math].
1.10 Свойства алгоритма
- Алгоритм останавливается за конечное число шагов, поскольку на каждом шаге становится по крайней мере на один фрагмент меньше.
- Число фрагментов на каждом шаге уменьшается как минимум вдвое, так что общее число шагов составляет не более [math]\log_2 N[/math].
- Соотношение последовательной и параллельной сложности: [math] \frac{N^2 \log N} {N \log N} = N [/math].
- Вычислительная мощность: [math] \frac {N^2 \log N} {N} = N \log N[/math].
- Алгоритм детерминирован. Если случается, что имеются два ребра [math](x_i,x_j)[/math] и [math](x_l,x_m)[/math], такие что [math]d(x_i,x_j) = d(x_l,x_m)[/math], то алгоритм должен выбрать ребро, одна из вершин которого имеет минимальный индекс [math]\min(i,j,l,m)[/math], если эти два ребра выходят из одной вершины, индекс которой является минимальным (например, [math]i=l[/math] ), то выбирается ребро, вершина которого имеет наименьший индекс из двух других вершин [math]\min(j,m)[/math].
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
Масштабируемость алгоритма Прима исследована на параллельной версии, представленной в книге. При помощи директив OpenMP алгоритм распараллеливался по ядрам. В данном источнике представлены результаты экспериментов при использовании 2 и 4 вычислительных ядер и изменении объёма входных данных от 100 до 1000. Эксперименты проводились на двухпроцессорном вычислительном узле на базе четырехядерных процессоров Intel Xeon E5320, 1.86 ГГц, 4 Гб RAM под управлением операционной системы Microsoft Windows HPC Server 2008. Разработка программ проводилась в среде Microsoft Visual Studio 2008, для компиляции использовался Intel C++ Compiler 10.0 for Windows.
Из графика видно, что время выполнения увеличивается при увеличении объёма входных данных, но уменьшается при увеличении вычислительных ядер.
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
- Python: MST Clustering
- С++: Parallel boost graph library
- C++: Minimum Spanning Tree
- Java: JGraphT PrimMinimumSpanningTree
- Java: JGraphT KruskalMinimumSpanningTree
- Python: SciPy
- Python: NetworkX
3 Литература
- Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.
- Нейский И.М. Классификация и сравнение методов кластеризации
- C. Kingsford. Minimum Spanning Trees & Clustering
- Y. Zhou et al. Clustering with Minimum Spanning Trees
- 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.
- 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.
- 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.
- Гергель В.П. Высокопроизводительные вычисления для многоядерных многопроцессорных систем