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

↑

Стр 1 из 5Следующая ⇒

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

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

Естественной и адекватной моделью распределения задач по процессорам кластера является взвешенный неориентированный граф 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 и обеспечат достижение заданного ускорения.

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии