МОДЕЛИРОВАНИЕ РАСПАРАЛЛЕЛИВАНИЯ ЗАДАЧИ С ПОМОЩЬЮ ГРАФА ПОТОКОВ ДАННЫХ

В.И. Костин, М.В. Краснокутская

кафедра ПМИ ДонНТУ

Abstract

V.I. Kostin, M.V. Krasnokutskaya. Simulation of problem parallelization by means of dataflow graph. We describe a flowgraph representation of a problem parallelization. Balancing of the computational load across processors is abstracted to a graph partitioning problem. We propose two algorithms to solve this problem and describe some peculiarities of their use to graphs with high number of nodes.

Key words: PARALLELIZATION, DATAFLOW GRAPH, PARTITION, NODE, EDGE, EIGENVECTOR, EIGENVALUE.

Реферат

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

Ключевые слова: РАСПАРАЛЛЕЛИВАНИЕ, ГРАФ ПОТОКОВ ДАННЫХ, РАЗБИЕНИЕ, ВЕРШИНА, РЕБРО, СОБСТВЕННЫЙ ВЕКТОР, СОБСТВЕННОЕ ЗНАЧЕНИЕ.

Введение

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

Одна из основных проблем, которая возникает в каждом параллельном вычислении, это распределение обработки данных между процессорами. Решением может быть использование математической модели, в основе которой лежит граф потоков данных (ГПД). Программа представляется набором вычислительных узлов-подзадач, которые имеют фиксированное количество информационных входов и выходов. Каждая подзадача выполняется на отдельном процессоре. Узлы-подзадачи – вершины графа потоков данных, а информационные потоки между ними – ребра графа. Оптимальное распределение обработки данных между процессорами минимизирует время выполнения всех вычислений. Задача распределения обработки данных на процессоры, сводится к задаче разбиения графа. Необходимо разбить граф потоков данных так, чтобы количество связей между подграфами было минимальным.

В настоящее время известно большое количество алгоритмов, решающих проблему разбиения графа. Но так как разбиение графа является NP-трудной задачей, то все известные алгоритмы дают приближение к оптимальному решению. Среди наиболее известных можно выделить алгоритм Kernighan-Lin / Fiduccia-Mattheyses (KL/FM), алгоритм спектральной бисекции.

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

Алгоритмы разбиения графа

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

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

Суть алгоритма заключается в том, что необходимо найти два множества вершин одинаковой мощности Х и Y, из А и В соответственно. Х и Y выбираются таким образом, что перемещение X в B и Y в А даcт максимально возможное уменьшение грань-соединения. Такой обмен выполняется до тех пор, пока улучшается необходимый критерий.

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

Fiduccia and Mattheyses [2] предложили модификацию KL алгоритма. FM алгоритм использует KL алгоритм в качестве базового, но за один его шаг можно переместить только одну вершин. На каждом шаге алгоритма для каждой вершины пересчитывается вес. После того как вес вершины пересчитан, для каждого подмножества строится очередь вершин. Вершины помещаются в очередь в порядке убывания веса. Просмотр вершин происходит в том порядке, в котором вершины расположены в очереди. Вершина перемещается только в том случае, если условия балансировки не нарушается. При перемещении вершины в другой набор она удаляется из очереди. При пересчете весов всех вершин очереди строятся заново.

KL/FM алгоритм позволяет избежать некоторых типов локальных минимумов, так как позволяет временно увеличивать грань-соединение.

Хотя алгоритм KL/FM позволяет избежать локальных минимумов, возможности его ограничены. Качество разбиения сильно зависит от начального разбиения.

В алгоритме спектральной бисекции в соответствии каждой вершине графа ставится переменная x, равная +1 или –1, таким образом, что сумма всех x-ов равна 0. Первое условие подразумевает разбиение на два различных набора. Второе требует чтобы наборы были равного размера, учитывая четность исходного количества. Назовем вектор x вектор-индикатор, т.к. он показывает принадлежность каждой вершины к набору.

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

где 1 – это n мерный вектор (1,1,1,1,..)^t,

n – число вершин графа,

L – матрица Лапласа

di- это число граней, смежных i-ой вершине.

Эта непрерывная задача - только приближение к дискретной, и значения, определяющие ее решение, должны быть отображены назад к ±1 в соответствии с некоторой соответствующей схемой. Идеально, когда решение близко к ±1 .

Если U₁, U₂ …- нормализованные собственные векторы L с соответствующими собственными значениями λ₁ < =λ₂ <= λ₃…., то матрица L имеет следующие свойства:

(I) L - симметрична.

(II) Ui попарно ортогональны.

(III) U1=n^-0.51, λ₁=0

(IV) Если граф замкнутый, то только λ₁ принимает нулевое значение.

Затем выразим Х в терминах собственных векторов L: x=Σα_iU_i, где α_i – вещественные константы, такие, что Σ(α_i)² =n . Свойство (II) гарантирует, что это всегда возможно. Заменой для x мы получаем функцию, для минимизации, зависящую от собственного значения матрицы Лапласа λ₂.

f (x)=0.25(α₂² λ₂+ α₃² λ₃ +…+ α_n² λn) начиная с λ₁=0.

Очевидно

(α₂² + α₃² +…+ α_n² ) λ₂ <= (α₂² λ₂+ α₃² λ₃ +…+ α_n² λn) учитывая упорядоченность собственных величин f(x)>=n λ₂/4.

Мы можем минимизировать f(x)=n λ₂/4, выбирая x =.

Полученный вектор x – решение непрерывной задачи. Остается решить задачу отображения вектора x к дискретному разделению. Для єтого находится медиана значений x_i, и затем отображается вершины выше значения медианы в один набор, ниже в другой. Если несколько вершин имеют значение медианы, то они распределяются, не нарушая равновесия. Это решение - самая близкая дискретная точка к непрерывному оптимуму.

Особенности применения алгоритмов к графам большой размерности

При программной реализации любого из этих алгоритмов встает задача выбора типа данных для представления информации о графе.

Задание графов с помощью матриц удобно для алгоритмов, использующие матричные вычисления (например, алгоритм спектральной бисекции). Однако, при обработке графа большой размерности (n=1000, 10000), матрицы занимают слишком много памяти.

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

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

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

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

Выводы

Использование списка ребер эффективно при разреженности матрицы смежности графа более 50%. Использование структуры смежности эффективно при любой разреженности матрицы смежности графа.

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

Литература

1. B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 1970

2. C. M. Fiduccia and R. M. Mattheyses. A linear time heuristic for improving network partitions. In In Proc. 19th IEEE Design Automation Conference, 1982.

3. B. Hendricson and R. Leland. Multidemensional spectral load balancing. Sandia National Laboratories, Albuquerque, NM, 1993.