Теория и практика параллельных вычислений
Краткий обзор лекции
В лекции рассмотрен ряд алгоритмов для решения типовых задач обработки графов. Кроме того, приведен обзор методов разделения графа.
В подразделе 10.1 представлен алгоритм Флойда (the Floyd algorithm) – дается общая вычислительная схема последовательного варианта метода, обсуждаются способы его распараллеливания, проводится анализ эффективности получаемых параллельных вычислений, рассматривается программная реализация метода и приводятся результаты вычислительных экспериментов. Используемый подход к распараллеливанию алгоритма Флойда состоит в разделении вершин графа между процессорами, а необходимое при этом информационное взаимодействие состоит в передаче одной строки матрицы смежности от одного процессора всем процессорам вычислительной системы на каждой итерации метода.
В подразделе 10.2 рассматривается алгоритм Прима (the Prim algorithm) для решения задачи поиска минимального охватывающего дерева (остова) неориентированного взвешенного графа. Остовом графа называют связный подграф без циклов (дерево), который содержит все вершины исходного графа и ребра, имеющие минимальный суммарный вес. Для алгоритма дается общее описание его исходного последовательного варианта, определяются возможные способы его параллельного выполнения, теоретические оценки ускорения и эффективности параллельных вычислений; также рассматриваются результаты проведенных вычислительных экспериментов. Параллельный вариант алгоритма Прима, как и в предыдущем случае, основывается на разделении вершин графа между процессорами при несколько большем объеме информационных взаимодействий – на каждой итерации алгоритма необходимой является операция сбора данных на одном процессоре и последующая рассылка номера выбранной вершины графа всем процессорам вычислительной системы.
Рассматриваемая в подразделе 10.3 задача оптимального разделения графов является важной для многих научных исследований, использующих параллельные вычисления. Для примера в подразделе приведен общий способ перехода от двумерной или трехмерной сети, моделирующей процесс вычислений, к соответствующему ей графу. Для решения задачи разбиения графов были рассмотрены геометрические методы, использующие при разделении сетей только координатную информацию об узлах сети, и комбинаторные алгоритмы, руководствующиеся смежностью вершин графа. К числу рассмотренных геометрических методов относятся покоординатное разбиение (the coordinate nested dissection method), рекурсивный инерционный метод деления пополам (the recursive inertial bisection method), деление сети с использованием кривых Пеано (the space-filling curve techniques). К числу рассмотренных комбинаторных алгоритмов относятся деление с учетом связности (the levelized nested dissection) и алгоритм Кернигана – Лина (the Kernighan – Lin algorithm). Для сопоставления рассмотренных подходов приводится общая сравнительная характеристика алгоритмов по времени выполнения, точности получаемого решения, возможностям для распараллеливания и т.п.
