Тезисы доклада "Исследование методов разбиения графов большой размерности со многими ограничениями при параллельной работе (система ParMETIS, hMETIS, METIS)". Шелест Л.Н., Костин В.И.

В этом докладе рассматривается объект исследования: алгоритмы разбиения графов большой размерности со многими ограничениями. Одноцелевая задача разбиения графа с одним ограничением широко используется для статического распределения сети в научном параллельном моделировании и называется задачей балансировки. Основной целью работы является исследование методов разбиения графов большой размерности со многими ограничениями. Исследование существующих пакетов для разбиения графов METIS, ParMETIS и hMETIS.

1. Задача о разбиении графов

Традиционная задача о разбиении графов сфокусирована на вычислении k-фазного сегмента графа такого, что деление ребер минимизировано, а каждый сегмент содержит одинаковое количество вершин (или, в случае взвешенного графа, каждый сегмент имеет одинаковую сумму весов вершин). Задача минимизации деления ребер может рассматриваться как цель, а требование того, чтобы сегменты были одинакового размера, может рассматриваться как ограничение. Эта одноцелевая задача разбиения графа с одним ограничением широко используется для статического распределения сети в научном параллельном моделировании.

Для представления многих ограничений балансировки, необходимо расширить традиционную модель графа. Каждая вершина, вместо одного веса, ассоциированного с ней, имеет вектор весов. Размер этого вектора - m. Этот размер соответствует количеству ограничений балансировки. Используя эту дополненную модель графа, можно сформулировать задачу разбиения графа со многими ограничениями.

Рассчитать k-фазное разбиение так, чтобы каждый из m весов был индивидуально сбалансирован с установленным допуском. [1]

Иными словами, если c - вектор размера m, который определяет допуск разбалансировки нагрузки, тогда цель в этом определении задачи со многими ограничениями состоит в вычислении таких сегментов таких, что разбалансировка нагрузки относительно i-ого веса должна быть меньше чем c_i.

Например, если мы имеем два веса (m = 2), тогда вектор допуска c = {1.05, 1.5} показывает, что мы ищем разбиение такое, в котором разбалансировка нагрузки относительно первого веса должна быть меньше или равна 5%, а для второго веса - меньше или равна 50%. [1]

2. Пакеты для разбиения графов

В данной главе приводится описание пакетов для разбиения графов METIS, hMETIS и ParMETIS. Приводится описание алгоритмов, используемых в этих пакетах.

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

Алгоритмы многоуровневого разбиения уменьшают размер графа путем стягивания вершин и ребер, разбивают меньший граф, а затем уточняют его для построения сегментов исходного графа. METIS использует новые решения, как для последовательного уменьшения графа, так и для улучшения разбиения в течение фазы уточнения. В процессе огрубления METIS использует алгоритмы, которые упрощают поиск высококачественного разбиения в огрубленном. Во время фазы детализации METIS в основном фокусируется на той части графа, которая расположена ближе всего к границам. Эти сильно оптимизированные алгоритмы позволяют METIS'у быстро находить высококачественные разбиения для широкого множества графов. [2]

3. Алгоритм многоуровневого k-фазного разбиения

Задачу k-фазного разбиения графа можно определить следующим образом. Пусть имеется граф G = (V, E), где |V| = n. Множество V необходимо разбить на k подмножеств V₁, V₂, V₃, ..., V_k так, что V_i Ω V_j = Ø для i ≠ j, | V_i | = n / k и U_i V_i = V, а количество ребер из множества E, смежные вершины которых принадлежат разным подмножествам, минимизировано. K-фазное разбиение обычно представляется вектором разбиения P длины n таким, что для каждой вершины v Є V, P[v] - это целое число между 1 и k, показывающее сегмент, которому принадлежит вершина v. Рассмотрим разбиение P: количество ребер, смежные вершины которых принадлежат разным сегментам, называется реберным разрезом (edge-cut) разбиения. [4]

Основная структура многоуровневого k-фазного разбиения очень простая. Граф G = (V, E) сначала стягивается к малому количеству вершин, затем рассчитывается разбиение этого намного меньшего графа, а после этого полученное разбиение проектируется назад в оригинальный граф, путем последовательных улучшений на каждом уровне.

В работе рассмотрены методы разбиения графов большой размерности со многими ограничениями, которые используются в пакетах METIS, ParMETIS и hMETIS. Установлено, что все эти пакеты используют модификации одного и того же алгоритма. Этот многоуровневый алгоритм состоит из трех фаз:

1. стягивание графа - для получения грубого уменьшенного графа;
2. начальное разбиение - получение разбиения уменьшенного графа;
3. уточнение - получение разбиения исходного графа путем последовательного проецирования разбиений на детализированные графы каждого уровня, и путем уточнения разбиения на каждом уровне.

Пакет METIS использует последовательный алгоритм для разбиения графов. Пакет hMETIS использует тот же алгоритм, но модифицированный для поиска разбиений на гиперграфе. Пакет ParMETIS использует параллельный алгоритм разбиения, который похож на последовательный, но использует алгоритм раскраски графов, необходимый для предупреждения многих конфликтных ситуаций, вызываемых распараллеливанием.

литература

1. George Karypis, Vipin Kumar. Multilevel Algorithms for Multi-Constraint Graph Partitioning. University of Minnesota, Department of Computer Science / Army HPC Research Center. Minneapolis, MN 55455. Technical Report # 98-019.
2. George Karypis. Vipin Kumar. METIS. A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices Version 4.0. - University of Minnesota: September 20, 1998
3. G. Karypis and V. Kumar. A fast and highly quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 1998 (to appear). Also available on WWW at URL http://www.cs.umn.edu/?karypis. A short version appears in Intl. Conf. on Parallel Processing 1995.
4. G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 48(1):96-129, 1998. Also available on WWWat URL http://www.cs.umn.edu/?karypis.