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

Поиск минимального разбиения множества вершин взвешенного графа, с. 1..13.

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

Естественной и адекватной моделью распределения задач по процессорам кластера является взвешенный неориентированный граф G, который задан множеством вершин V и множеством рёбер U: G(V, E). Кроме того, на множестве вершин определена неотрицательная функция F1(V), а на множестве рёбер также неотрицательная функция F2(E). Значения функции F1 называются весами вершин графа, а значения функции F2 – весами рёбер графа. Каждая вершина этого графа представляет собой одну из задач, а вес этой вершины - число операций, выполняемых при решении этой задачи. Вес ребер моделирует коммуникационные затраты на обмен данными между задачами, соответствующими вершинам, соединенным этими ребрами. С помощью этой модели распределение задач по процессорам представляется как разбиение множества вершин графа V на непересекающиеся подмножества, которое порождает разбиение графа G(V,E) на непересекающиеся подграфы. При этом каждый подграф ассоциируется с некоторым процессором, который будет использоваться для решения всех задач, соответствующих вершинам этого подграфа. Таким образом, оптимальное распределение вычислительной нагрузки между доступными процессорами сводится к оптимальному разделению графа G(V, E). Критериями оптимальности могут быть: 1) равенство сумм весов вершин подграфов, 2) минимальность суммы весов ребер, соединяющих вершины, принадлежащие разным подграфам; 3) число подграфов.

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

Задача оптимального разделения графа является NP – полной и, как показывает анализ состояния исследований в этой области, в общей постановке задача эта задача решается только в узком диапазоне значений параметров k, n, m. На практике обычно оптимальное разделение графа выполняется для некоторого частного случая, например: 1) веса вершин и ребер графа равны 1 и в качестве приоритетного критерия используется либо условие 1, либо условие 2; 2) веса вершин различны, веса ребер равны 0, и в качестве критерия оптимальности используется только условие 1. В последнем частном случае задача оптимального разделения графа сводится к задаче оптимального разбиения множества, для решения которой может быть применён метод ветвей и границ [1]. Ниже описывается постановка задачи (модель) оптимального разбиения вершин графа, критерий решения которой предполагает балансировку сумм вычислительных нагрузок и коммуникационных затрат, требуемых для решения задач, ассоциированных с каждым процессором. На основе указанной модели предлагается комбинаторный подход к поиску минимального разбиения множества вершин графа G(V, E), основанный на конструктивном перечислении вариантов разбиений указанного множества. Целью этого поиска минимального разбиения множества вершин графа является определение минимального количества процессоров, совокупность которых обеспечивает заданное ускорение

Пусть задан неориентированный взвешенный граф G(V,E) с числом вершин равным n: V={v₁,…,v_n}, и числом рёбер равным m: E ={e₁,…,e_m}. Функция F1 ставит в соответствие каждой вершине графа v_i ее вес q_i, аналогично функция F2 ставит в соответствие каждому ребру графа e_i его вес r_i. Такой граф определяет, что при использовании одного процессора все задачи могут быть решены в результате выполнения T₁ операций, где T₁ представляет собой сумму весов всех вершин множества V: T₁= F1(V).

Теперь рассмотрим разбиения множества вершин V графа G(V,E) на k непересекающихся подмножеств P={V₁,…,V_k}. Этими подмножествами вершин определяются подграфы G₁(V₁,E₁),…, G_k(V_k,E_k), для которых выполняются следующие соотношения:

1) ∀ i,j ∈{1, 2, …, k} (i≠ j) ⇒ V_i ⋂ V_j =∅; 2) V₁⋃ V₂ ⋃ …⋃V_k=V;
3) n₁ + n₂ + …+ n_k = n, где n₁= |V₁|, n₂=|V₂|, …, n_k=|V_k|, n=|V|.

Будем считать, что при заданном разбиении число операций выполняемых i-тым процессором определяется как сумма весов вершин
i-того подмножества: Q_i =∑ F1(V_i). Пусть C (V_i, V_j) множество рёбер, соединяющих вершины из множества V_iс вершинами множества V_j: C (V_i, V_j) = {(u,w)|u∈V_i,w∈V_j}. Тогда сечением R_i по подмножеству V_iграфа G(V,E) будем называть совокупность ребер, соединяющих вершины принадлежащие множеству V_iс вершинами, не принадлежащими этому множеству: E_i=⋃_j(C (V_i, V_j)), где i≠j. Тогда затраты на передачу и получение информации i-тым процессором можно определить как сумму весов рёбер i-того сечения: R_i= F2 (E_i). Исчисляемое в числе операций время решения всех задач для данного разбиения с использованием k процессоров будет равно: T_k=max((Q_i + R_i), где i=1, 2, …, k).

Далее пусть задан требуемый коэффициент ускорения S. Тогда поиск минимального разбиения множества вершин графа G(V,E) сводится к поиску разбиения, минимального по числу непересекающиеся подмножеств P={V₁,…,V_k}, для которого выполняются условия достижения заданного ускорения: max((Q_i + R_i), где i=1, 2, …, k)≤ T₁/S. (1.1)

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

2. Проверка монотонности зависимости T_k от числа процессоров к

Результаты теоретического анализа предложенных вычислительных схем и экспериментального исследования временной сложности алгоритма Eq2_1 показали эффективность этого математического обеспечения. Но эта эффективность основывалась на неявном предположении о монотонном убывании значений функции T_k, удовлетворяющего соотношению (1.1), при увеличении числа процессоров k. Проверка монотонности T_k выполнялась с использованием статистического моделирования: в каждой точке эксперимента рассчитывалась матрица смежности вершин взвешенного графа (матрица A), который затем подвергался разбиению. Каждая экспериментальная точка характеризовалась числом вершин в графе (n =10, 11, …, 15) и диапазоном отклонения весов вершин и рёбер графа от среднего значения (dtmax=10, 20, …50). При генерации случайных значений матрицы матрица A, подчиняющихся равномерному распределению, использовались стандартные функции языка Си [2, стр. 753]. В ходе вычислительного эксперимента анализировались все возможные варианты разбиения множества V. Эти варианты разбиений были разбиты на классы эквивалентности, каждый из которых включал в себя разбиения с одинаковым числом подмножеств (np). Это число подмножеств являлось номером соответствующего класса эквивалентности. Таким образом, классы эквивалентности получили номера 1, 2, …, n, где n – это число вершин в графе G(V,E). Для каждого класса эквивалентности определялось разбиение, обеспечивающее минимизацию функции T_k.

Основные результаты вычислительного эксперимента с программной реализацией приведённого выше алгоритма представлены в таблицах 1, 2.

Таблица 1

Таблица 2

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