Перевод части статьи George Karypis, Kirk Schloegel and Vipin Kumar. PARMETIS Parallel Graph Partitioning and Sparse Matrix Ordering Library, Version 3.0. - University of Minnesota, Department of Computer Science and Engineering, Army HPC Research Center, Minneapolis, MN 55455: March 28, 2002. Выполнила Шелест Лариса.

Пакет ParMETIS.

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

Алгоритмы в PARMETIS основаны на многоуровневом разбиении, которые были реализованы в пакете METIS. Однако, PARMETIS расширяет функциональность предоставляемую пакетом METIS и включает подпрограммы, которые преимущественно предназначены для параллельных вычислений широко-масштабных численных моделей [13].

Параллельный алгоритм разбиения графов.

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

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

Пусть p - количество процессоров для вычисления р-фазного разбиения графа G = (V; E). G первоначально распределяется между процессорами, используя однонаправленное распределение так, что каждый процессор получает n=p вершин и списки их смежности. В конце алгоритма номер сегмента присваивается каждой вершине графа.

Раскраска графа.

Раскраска графа G = (V; E) присваивает цвета вершинам графа G так, что смежные вершины имеют различные цвета. В ParMETIS ищется такая раскраска, чтобы количество отдельных используемых цветов было малым. Параллельный алгоритм раскраски, разработанный авторами ParMETIS, включает несколько итераций. В каждой итерации максимально независимое множество вершин I выбирается с использованием измененного алгоритма Луби (см. [15]). Всем вершинам в независимом множестве присваивается одинаковый цвет. Перед началом следующей операции вершины из множества I удаляются из графа, а образовавшийся меньший граф становится входным графом для следующей итерации. Максимально независимое множество I множества вершин S вычисляется в инкрементном порядке, используя алгоритм Луби следующим образом.

Каждой вершине присваивается случайное число, а если вершина получает случайный номер, который меньше, чем все номера смежных вершин, то эта вершина включается во множество I. После этого процесс повторяется для вершин из множества S, которые и не входят во множество I, и не являются смежными с вершинами из I, а I расширяется подобным образом. Это инкрементное наращивание множества I заканчивается тогда, когда больше нет вершин, которые могут быть вставлены в I. В [15] показано, что одна итерация алгоритма Луби требует всего O(log|S|) таких расширяющих шагов для поиска максимально независимого множества вершин из множества S.

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