Параллельные методы на графах

10.1.6. Программная реализация

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

1. Главная функция программы. Реализует логику работы алгоритма, последовательно вызывает необходимые подпрограммы.

// Программа 10.1. — Алгоритм Флойда
int ProcRank;    // Ранг текущего процесса
int ProcNum;     // Количество процессов

// Функция вычисления минимума
int Min(int A, int B) {
  int Result = (A < B) ? A : B;

  if((A < 0)  (B >= 0)) Result = B;
  if((B < 0)  (A >= 0)) Result = A;
  if((A < 0)  (B < 0))  Result = -1;

  return Result;
}

// Главная функция программы
int main(int argc, char* argv[]) {
  int *pMatrix;     	// Матрица смежности
  int  Size;        	// Размер матрицы смежности
  int *pProcRows;   	// Строки матрицы смежности текущего процесса
  int  RowNum;      	// Число строк для текущего процесса

  MPI_Init(argc, argv);
  MPI_Comm_size(MPI_COMM_WORLD, ProcNum);
  MPI_Comm_rank(MPI_COMM_WORLD, ProcRank);

  // Инициализация данных
  ProcessInitialization(pMatrix, pProcRows, Size, RowNum);

  // Распределение данных между процессами
  DataDistribution(pMatrix, pProcRows, Size, RowNum);

  // Параллельный алгоритм Флойда
  ParallelFloyd(pProcRows, Size, RowNum);

  // Сбор результатов работы алгоритма
  ResultCollection(pMatrix, pProcRows, Size, RowNum);

  // Завершение вычислений процесса
  ProcessTermination(pMatrix, pProcRows);

  MPI_Finalize();
  return 0;
}

Функция Min вычисляет меньшее из двух целых чисел, учитывая применяемый способ задания несуществующих дуг в матрице смежности (в рассматриваемой реализации для этого используется значение -1).

Функция ProcessInitialization определяет исходные данные решаемой задачи (количество вершин графа ), выделяет память для хранения данных, осуществляет ввод матрицы смежности (или формирует ее при помощи какого-либо датчика случайных числе).

Функция DataDistribution распределяет исходные данные между процессами. Каждый процесс получает горизонтальную полосу матрицы смежности.

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

Функция ProcessTermination выполняет необходимый вывод результатов решения задачи и освобождает всю ранее выделенную память для хранения данных.

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

2. Функция ParallelFloyd. Данная функция осуществляет итеративное изменение матрицы смежности в соответствии с алгоритмом Флойда.

// Параллельный алгоритм Флойда
void ParallelFloyd(int *pProcRows, int Size, int RowNum) {
  int *pRow = new int[Size];
  int t1, t2;

  for(int k = 0; k < Size; k++) {
    // Распределение k-й строки среди процессов 
    RowDistribution(pProcRows, Size, RowNum, k, pRow);

    // Обновление элементов матрицы смежности
    for(int i = 0; i < RowNum; i++) 
      for(int j = 0; j < Size; j++)
        if( (pProcRows[i * Size + k] != -1)  (pRow [j]!= -1)){
          t1 = pProcRows[i * Size + j];
          t2 = pProcRows[i * Size + k] + pRow[j];
          pProcRows[i * Size + j] = Min(t1, t2);
        }
  }
    
  delete []pRow;
}

3. Функция RowDistribution. Данная функция рассылает k -ю строку матрицы смежности всем процессам программы.

// Функция для рассылки строки всем процессам
void RowDistribution(int *pProcRows, int Size, int RowNum, int k,
  int *pRow) {
  int ProcRowRank; 	// Ранг процесса, которому принадлежит k-я строка
  int ProcRowNum;	// Номер k-й строки в полосе матрицы

  // Нахождение ранга процесса – владельца k-й строки
  int RestRows = Size;
  int Ind = 0;
  int Num = Size / ProcNum;
  
  for(ProcRowRank = 1; ProcRowRank < ProcNum + 1; ProcRowRank ++)      {
    if(k < Ind + Num ) break;
    RestRows -= Num;
    Ind      += Num;
    Num       = RestRows / (ProcNum - ProcRowRank);
  }
  ProcRowRank = ProcRowRank - 1;
  ProcRowNum  = k - Ind;

  if(ProcRowRank == ProcRank)
    // Копирование строки в массив pRow
    copy(pProcRows[ProcRowNum * Size], pProcRows[(ProcRowNum + 1) *
      Size], pRow);

  // Распределение k-й строки между процессами  
  MPI_Bcast(pRow, Size, MPI_INT, ProcRowRank, MPI_COMM_WORLD);
}

10.1.7. Результаты вычислительных экспериментов

Эксперименты проводились на вычислительном кластере Нижегородского университета на базе процессоров Intel Xeon 4 EM64T, 3000 МГц и сети Gigabit Ethernet под управлением операционной системы Microsoft Windows Server 2003 Standard x64 Edition и системы управления кластером Microsoft Compute Cluster Server.

Для оценки длительности $$\tau$$ базовой скалярной операции выбора минимального значения проводилось решение задачи поиска всех кратчайших путей при помощи последовательного алгоритма и полученное таким образом время вычислений делилось на общее количество выполненных операций – в результате для величины $$\tau$$ было получено значение 7,14 нсек. Эксперименты, выполненные для определения параметров сети передачи данных, показали значения латентности $$\alpha$$ и пропускной способности $$\beta$$ соответственно 130 мкс и 53,29 Мбайт/с. Все вычисления производились над числовыми значениями типа int, размер которого на данной платформе равен 4 байта (следовательно, w=4 ).

Результаты вычислительных экспериментов приведены в таблице 10.1. Эксперименты выполнялись с использованием двух, четырех и восьми процессоров. Время указано в секундах.

Сравнение времени выполнения эксперимента $$T^*_p$$ и теоретической оценки Tp из (10.3) приведено в таблице 10.2 и на рис. 10.5.

10.2. Задача нахождения минимального охватывающего дерева

Охватывающим деревом (или остовом ) неориентированного графа G называется подграф T графа G, который является деревом и содержит все вершины из G. Определив вес подграфа для взвешенного графа как сумму весов входящих в подграф дуг, под минимально охватывающим деревом (МОД) T будем понимать охватывающее дерево минимального веса. Содержательная интерпретация задачи нахождения МОД может состоять, например, в практическом примере построения локальной сети персональных компьютеров с прокладыванием соединительных линий связи минимальной длины. Пример взвешенного неориентированного графа и соответствующего ему минимально охватывающего дерева приведен на рис. 10.6.

Дадим общее описание алгоритма решения поставленной задачи, известного под названием метода Прима ( the Prim method ); более полная информация может быть получена, например, в [].

10.2.1. Последовательный алгоритм Прима

Алгоритм начинает работу с произвольной вершины графа, выбираемой в качестве корня дерева, и в ходе последовательно выполняемых итераций расширяет конструируемое дерево до МОД. Пусть VT есть множество вершин, уже включенных алгоритмом в МОД, а величины di, 1<=i<=n, характеризуют дуги минимальной длины от вершин, еще не включенных в дерево, до множества VT, т.е.$$\forall i \notin V_T \Rightarrow d_i = \min\{ w(i,u):u\in V_T,(i,u)\in R\}$$ (если для какой-либо вершины $$i\notin V_{T}$$ не существует ни одной дуги в VT, значение di устанавливается равным $$\infty$$ ). В начале работы алгоритма выбирается корневая вершина МОД s и полагается VT={s}, ds=0.

Действия, выполняемые на каждой итерации алгоритма Прима, состоят в следующем:

После выполнения n-1 итерации метода МОД будет сформировано. Вес этого дерева может быть получен при помощи выражения$$W_T = \sum_{i=1}^n d_i.$$

Трудоемкость нахождения МОД характеризуется квадратичной зависимостью от числа вершин графа T1~n2.

10.2.2. Разделение вычислений на независимые части

Оценим возможности параллельного выполнения рассмотренного алгоритма нахождения минимально охватывающего дерева.

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

Распределение данных между процессорами вычислительной системы должно обеспечивать независимость перечисленных операций алгоритма Прима. В частности, это может быть реализовано, если каждая вершина графа располагается на процессоре вместе со всей связанной с вершиной информацией. Соблюдение данного принципа приводит к тому, что при равномерной загрузке каждый процессор pj, 1<=j<=p, должен содержать:

Как итог можем заключить, что базовой подзадачей в параллельном алгоритме Прима может служить процедура вычисления блока значений $$\Delta _{j}$$ для вершин Vj матрицы смежности A графа G.

10.2.3. Выделение информационных зависимостей

С учетом выбора базовых подзадач общая схема параллельного выполнения алгоритма Прима будет состоять в следующем:

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

10.2.4. Масштабирование и распределение подзадач по процессорам

По определению количество базовых подзадач всегда соответствует числу имеющихся процессоров, и, тем самым, проблема масштабирования для параллельного алгоритма не возникает.

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

10.2.5. Анализ эффективности параллельных вычислений

Общий анализ сложности параллельного алгоритма Прима для нахождения минимального охватывающего дерева дает идеальные показатели эффективности параллельных вычислений:$$S_p = \frac{n^2}{(n^2/p)}=p \quad \text{и} \quad E_p = \frac{n^2}{p\cdot(n^2/p)}=1.$$

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

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

При выполнении вычислений на отдельной итерации параллельного алгоритма Прима каждый процессор определяет номер ближайшей вершины из Vj до охватывающего дерева и осуществляет корректировку расстояний di после расширения МОД. Количество выполняемых операций в каждой из этих вычислительных процедур ограничивается сверху числом вершин, имеющихся на процессорах, т.е. величиной $$\lceil n/p\rceil$$. Как результат, с учетом общего количества итераций n время выполнения вычислительных операций параллельного алгоритма Прима может быть оценено при помощи соотношения:$$T_p(calc)=2n\lceil n/p \rceil \cdot \tau$$ (здесь, как и ранее, $$\tau$$ есть время выполнения одной элементарной скалярной операции).

Операция сбора данных от всех процессоров на одном из процессоров может быть произведена за $$\lceil log_{2}p\rceil$$ итераций, при этом общая оценка длительности выполнения передачи данных определяется выражением (более подробное рассмотрение данной коммуникационной операции содержится в лекции 3):$$T_p^1(comm)=n(\alpha \log_2 p +3w(p-1)/ \beta),$$ где $$\alpha$$ – латентность сети передачи данных, $$\beta$$ – пропускная способность сети, а w есть размер одного пересылаемого элемента данных в байтах (коэффициент 3 в выражении соответствует числу передаваемых значений между процессорами – длина минимальной дуги и номера двух вершин, которые соединяются этой дугой).

Коммуникационная операция передачи данных от одного процессора всем процессорам вычислительной системы также может быть выполнена за $$\lceil log_{2}p\rceil$$ итераций при общей оценке времени выполнения вида:$$T_p^2(comm)=n\log_2p(\alpha+w/ \beta)$$

С учетом всех полученных соотношений общее время выполнения параллельного алгоритма Прима составляет:$$T_p=2n\lceil n/p\rceil\cdot\tau+n(\alpha\cdot\log_2p+3w(p-1)/ \beta+log_2p(\alpha+w/ \beta)).$$

10.2.6. Результаты вычислительных экспериментов

Вычислительные эксперименты для оценки эффективности параллельного алгоритма Прима осуществлялись при тех же условиях, что и ранее выполненные (см. п. 10.1.7).

Для оценки длительности $$\tau$$ базовой скалярной операции проводилось решение задачи нахождения минимального охватывающего дерева при помощи последовательного алгоритма и полученное таким образом время вычислений делилось на общее количество выполненных операций – в результате подобных экспериментов для величины $$\tau$$ было получено значение 4,76 нсек. Все вычисления производились над числовыми значениями типа int, размер которого на данной платформе равен 4 байта (следовательно, w=4 ).

Результаты вычислительных экспериментов даны в таблице 10.3. Эксперименты проводились с использованием двух, четырех и восьми процессоров. Время указано в секундах.

Сравнение времени выполнения эксперимента $$T^*_p$$ и теоретической оценки Tp из (10.8) приведено в таблице 10.4 и на рис. 10.8.

Как можно заметить из табл. 10.4 и рис. 10.8, теоретические оценки определяют время выполнения алгоритма Прима с достаточно высокой погрешностью. Причина такого расхождения может состоять в том, что модель Хокни менее точна при оценке времени передачи сообщений с небольшим объемом передаваемых данных. Для уточнения получаемых оценок необходимым является использование других более точных моделей расчета трудоемкости коммуникационных операций – обсуждение этого вопроса проведено в лекции 3.

10.3. Задача оптимального разделения графов

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

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

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

Дополнительная информация по проблеме разделения графов может быть получена, например, в [].

Задача оптимального разделения графов сама может являться предметом распараллеливания. Это бывает необходимо в тех случаях, когда вычислительной мощности и объема оперативной памяти обычных компьютеров недостаточно для эффективного решения задачи. Параллельные алгоритмы разделения графов рассматриваются во многих научных работах: [, , , , , , ].

10.3.1. Постановка задачи оптимального разделения графов

Пусть дан взвешенный неориентированный граф G=(V,E), каждой вершине $$\nu \in V$$ и каждому ребру $$e\in E$$ которого приписан вес. Задача оптимального разделения графа состоит в разбиении его вершин на непересекающиеся подмножества с максимально близкими суммарными весами вершин и минимальным суммарным весом ребер, проходящих между полученными подмножествами вершин.

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

Далее для простоты изложения учебного материала будем полагать веса вершин и ребер графа равными единице.

10.3.2. Метод рекурсивного деления пополам

Для решения задачи разбиения графа можно рекурсивно применить метод бинарного деления ( the binary bisection method ), при котором на первой итерации граф разделяется на две равные части, далее на втором шаге каждая из полученных частей также разбивается на две части и т. д. В данном подходе для разбиения графа на k частей необходимо log2k уровней рекурсии и выполнение k-1 деления пополам. В случае когда требуемое количество разбиений k не является степенью двойки, каждое деление пополам необходимо осуществлять в соответствующем соотношении.

Поясним схему работы метода деления пополам на примере разделения графа на рис. 10.11 на 5 частей. Сначала граф следует разделить на 2 части в оотношении 2:3 (непрерывная линия), затем правую часть разбиения – в отношении 1:3 (штриховая линия), после этого осталось разделить 2 крайние подобласти слева и справа в отношении 1:1 (штрих-пунктир).

10.3.3. Геометрические методы

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

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

10.3.3.1. Покоординатное разбиение

Покоординатное разбиение ( the coordinate nested dissection ) – это метод, основанный на рекурсивном делении пополам сети по наиболее длинной стороне. В качестве иллюстрации на рис. 10.12 показан пример сети, при разделении которой именно такой способ разбиения дает существенно меньшее количество информационных связей между разделенными частями, по сравнению со случаем, когда сеть делится по меньшей (вертикальной) стороне.

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

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

10.3.3.2. Рекурсивный инерционный метод деления пополам

Предыдущая схема могла производить разбиение сети только по линии, перпендикулярной одной из координатных осей. Во многих случаях такое ограничение оказывается критичным для построения качественного разбиения. Достаточно повернуть сеть на рис. 10.12 под острым углом к координатным осям (см. рис. 10.13), чтобы убедиться в этом. Для минимизации границы между подсетями желательна возможность проведения линии разделения с любым требуемым углом поворота. Возможный способ определения угла поворота, используемый в рекурсивном инерционном методе деления пополам ( the recursive inertial bisection ), состоит в использовании главной инерционной оси (см., например, []), считая элементы сети точечными массами. Линия бисекции, ортогональная полученной оси, как правило, дает границу наименьшей длины.

10.3.3.3. Деление сети с использованием кривых Пеано

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

Один из таких методов упорядочивает элементы в соответствии с позициями центров их масс вдоль кривых Пеано. Кривые Пеано – это кривые, полностью заполняющие области больших размерностей (например, квадрат или куб). Применение таких кривых обеспечивает близость точек фигуры, которые соответствуют точкам, близким на кривой. После получения списка элементов сети, упорядоченного в зависимости от расположения на кривой, достаточно разделить список на необходимое число частей в соответствии с установленным порядком. Получаемый в результате такого подхода метод носит в литературе наименование алгоритма деления сети с использованием кривых Пеано ( the space-filling curve technique ). Подробнее о методе можно прочитать в работах [, , ].

10.3.4. Комбинаторные методы

В отличие от геометрических методов, комбинаторные алгоритмы (см., например, [, ]) обычно оперируют не с сетью, а с графом, построенным для этой сети. Соответственно, в отличие от геометрических схем, комбинаторные методы не принимают во внимание информацию о близости расположения элементов сети друг относительно друга, руководствуясь только смежностью вершин графа. Комбинаторные методы обычно обеспечивают более сбалансированное разбиение и меньшее информационное взаимодействие полученных подсетей. Однако комбинаторные методы имеют тенденцию работать существенно дольше, чем их геометрические аналоги.

10.3.4.1. Деление с учетом связности

С самых общих позиций понятно, что при разделении графа информационная зависимость между разделенными подграфами будет меньше, если соседние вершины (вершины, между которыми имеются дуги) будут находиться в одном подграфе. Алгоритм деления графов с учетом связности ( the levelized nested dissection algorithm ) пытается достичь этого, последовательно добавляя к формируемому подграфу соседей. На каждой итерации алгоритма происходит разделение графа на 2 части. Таким образом, разделение графа на требуемое число частей достигается путем рекурсивного применения алгоритма.

Общая схема алгоритма может быть описана при помощи следующего набора правил.

Алгоритм 10.2. Общая схема выполнения алгоритма деления графов с учетом связности

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

Пример работы алгоритма приведен на рис. 10.15. Цифрами показаны номера, которые получили вершины в процессе разделения. Сплошной линией показана граница, разделяющая 2 подграфа. Также на рисунке показано лучшее решение (пунктирная линия). Очевидно, что полученное алгоритмом разбиение далеко от оптимального, так как в приведенном примере есть решение только с тремя пересеченными ребрами вместо пяти.

10.3.4.2. Алгоритм Кернигана – Лина

В алгоритме Кернигана – Лина ( the Kernighan – Lin algorithm ) используется несколько иной подход для решения проблемы оптимального разбиения графа – предполагается, что некоторое начальное разбиение графа уже существует, затем имеющееся приближение улучшается в течение некоторого количества итераций. Применяемый способ улучшения в алгоритме Кернигана – Лина состоит в обмене вершинами между подмножествами имеющегося разбиения графа (см. рис. 10.16). Для формирования требуемого количества частей графа может быть использована, как и ранее, рекурсивная процедура деления пополам.

Общая схема одной итерации алгоритма Кернигана – Лина может быть представлена следующим образом.

Алгоритм 10.3. Общая схема алгоритма Кернигана – Лина

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

10.3.5. Сравнение алгоритмов разбиения графов

Рассмотренные алгоритмы разбиения графов различаются точностью получаемых решений, временем выполнения и возможностями для распараллеливания (под точностью понимается величина близости получаемых при помощи алгоритмов решений к оптимальным вариантам разбиения графов ). Выбор наиболее подходящего алгоритма в каждом конкретном случае является достаточно сложной и неочевидной задачей. Проведению такого выбора может содействовать сведенная воедино в ]) общая характеристика ряда алгоритмов разделения графов, рассмотренных в данном разделе. Дополнительная информация по проблеме оптимального разбиения графов может быть получена, например, в [].

Столбец "Необходимость координатной информации" отмечает использование алгоритмом координатной информации об элементах сети или вершинах графа.

Столбец "Точность" дает качественную характеристику величины приближения получаемых алгоритмом решений к оптимальным вариантам разбиения графов. Каждый дополнительный закрашенный кружок определяет примерно 10%-процентное улучшение точности приближения.

Столбец "Время выполнения" показывает относительное время, затрачиваемое различными алгоритмами разбиения. Каждый дополнительный закрашенный кружок соответствует увеличению времени разбиения примерно в 10 раз.

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

10.4. Краткий обзор лекции

В лекции рассмотрен ряд алгоритмов для решения типовых задач обработки графов. Кроме того, приведен обзор методов разделения графа.

В подразделе 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 ). Для сопоставления рассмотренных подходов приводится общая сравнительная характеристика алгоритмов по времени выполнения, точности получаемого решения, возможностям для распараллеливания и т.п.

10.5. Обзор литературы

Дополнительная информация по алгоритмам Флойда и Прима может быть получена, например, в [].

Подробное рассмотрение вопросов, связанных с проблемой разделения графов, содержится в работах [, , , , , , , , , ].

Параллельные алгоритмы разделения графов рассматриваются в [, , , , , , ].

10.6. Контрольные вопросы

10.7. Задачи и упражнения