Стронгин Р.Г (ред.) Высокопроизводительные параллельные вычисления на кластерных системах
Подождите немного. Документ загружается.
171
сетевых средств и согласованного по всей инфраструктуре связующего
программного обеспечения, поддерживающего дистанционные
операции, а также выполняющего функции контроля и управления
операционной средой [1].
Современное состояние управления ресурсами недостаточно
развито как с точки зрения качества реализации, так и с точки зрения
богатства операций. В частности, к недостаткам можно отнести
отсутствие средств совместного
резервирования распределенных
вычислительных ресурсов и пропускной полосы каналов передачи
данных, что необходимо для запуска в сетях Grid параллельных и
распределенных приложений [2].
В работе предлагается подход к оптимизации резервирования
распределенных вычислительных ресурсов на основе предложенного
автором алгоритма нахождения граф-подграф изоморфизма [3, 4].
Постановка задачи
Для решения проблемы резервирования распределенных
вычислительных ресурсов предлагается применить графово-
аналитический подход.
Пусть
),,,(
NNNNN
JIVEG =
- граф вычислительной сети, где E
N
–
множество ребер, соответствующих физическим сетевым каналам
связи, V
N
– множество вершин, соответствующих вычислительным
узлам сети, I
N
– веса, приписанные ребрам графа, соответствующие
пропускной способности (латентности) сетевых соединений, J
N
– веса,
приписанные вершинам графа, соответствующие вычислительной
производительности узлов сети (например в MIPS или MFLOPS); граф
),,,(
TTTTT
JIVEG =
- граф параллельной задачи, требующей
резервирования распределенных вычислительных ресурсов, где E
T
–
множество ребер графа, соответствующих сетевым взаимодействиям
между процессами задачи, V
T
– множество вершин графа,
соответствующих вычислительным процессам распределенной задачи,
I
T
– множество весов, приписанных ребрам графа, соответствующих
потребностям задачи в пропускной способности (латентности) сетевых
соединений, J
T
– множество весов, приписанных вершинам графа,
соответствующих потребности процессов в производительности
вычислительных узлов (в MIPS или MFLOPS).
Тогда задача резервирования распределенных вычислительных
ресурсов формулируется следующим образом. Необходимо найти
172
подстановку
NT
VV →:
ϕ
, такую, что для каждой пары вершин
Tji
Vvv ∈,
, если
(
)
Tji
Evv
∈
,
, то
(
)
(
)
(
)
Nji
Evv
∈
ϕ
ϕ
,
,
(
)
()
(
)
(
)
NjiTji
NiiNii
∈
≤∈
φ
φ
,,
и для всех
Ti
Jj
∈
выполняется
()
NiTi
JjJj ∈≤∈
φ
. Это полностью соответствует постановке задачи
граф-подграф изоморфизма на взвешенных графах. Такая постановка
задачи характерна для систем реального времени, которые
предъявляют жесткие требования к аппаратным ресурсам, для
гарантированного обслуживания заданий при допустимых пиковых
вычислительных нагрузках.
Для задач параллельного программирования характерна несколько
другая постановка задачи резервирования ресурсов, связанная с тем,
что
возможно совместное размещение двух и более процессов на
одном вычислительном узле. При этом возрастает количество
возможных вариантов размещения процессов задачи среди узлов
вычислительной сети и связанные с этим временные затраты при
использовании переборных алгоритмов. Для ускорения поиска в этом
случае планируется применять гибридные алгоритмы, совмещающие в
себе элементы как точного переборного
, так и эвристического
подходов.
Алгоритм резервирования распределенных вычислительных
ресурсов
Описание алгоритма удобно производить в терминах поиска в
пространстве состояний. Каждому состоянию соответствует частичная
подстановка
(
)
s
ϕ
, содержащая лишь часть вершин графов, которые
уже были совмещены. Алгоритм состоит из предварительной и
основной части.
Предварительная часть алгоритма
Основной задачей предварительной части алгоритма является
выполнение всех проверок, которые основаны на данных, известных
до начала работы алгоритма и не базируются на информации об уже
совмещенных вершинах частичной подстановки
(
)
s
ϕ
. На их основе
формируется матрица возможных совмещений. Так же в
предварительной части алгоритма производится сортировка вершин
графов.
173
Центральным элементом предварительной части алгоритма
является матрица возможных совмещений. Это бинарная таблица
ji
M
,
,
каждая ячейка которой хранит агрегированное значение о
возможности либо невозможности совмещения вершин
iN
V
,
и
jT
V
,
.
Значения матрицы формируются на основании предварительных
проверок и могут принимать значения «истина» или «ложь» в
зависимости от того, перспективно или нет совмещение
соответствующих вершин в основной части алгоритма на основании
проверок, выполненных в предварительной части алгоритма.
В представленном алгоритме реализовано несколько базовых
проверок, формирующих матрицу возможных совмещений
ji
M
,
. Если
результат проверки условия – «истина», то значение матрицы,
соответствующее проверяемым вершинам
iN
V
,
и
jT
V
,
, устанавливается
равным «ложь».
Условия, формирующие ограничения предварительной части
алгоритма, основаны на сравнении степеней вершин, сравнении весов,
приписанных вершинам и ребрам графов, сравнении числа входящих и
исходящих дуг и на сравнении числа, а также весов, приписанных
вершинам и ребрам в волновом разложении графа [5].
Переборная часть алгоритма
Переборная часть алгоритма объединяет в себе все действия,
направленные на поиск полной подстановки
ϕ
, являющейся решением
задачи. Алгоритм представлен рекурсивной функцией поиска в
пространстве состояний, которая на каждом шаге вложенности
генерирует новую частичную постановку
(
)
s
i 1+
ϕ
из предыдущей
частичной подстановки
(
)
s
i
ϕ
путем добавления одной вершины в
частичную подстановку.
Начальное состояние
(
)
0
0
=
s
ϕ
. На каждом шаге функция
перебирает все вершины графа
N
G
, которые имеют пометку «истина»
в строке матрицы возможных совмещений, соответствующей вершине
iT
V
,
, используемой на текущем уровне вложенности алгоритма i. Для
каждой вершины
jN
V
,
алгоритм производит несколько проверок,
имеющих целью удостовериться, что все необходимые условия для
174
включения новой вершины в частичную подстановку
(
)
s
i 1+
ϕ
выполнены.
Основными являются проверки, основанные на значениях матрицы
возможных совмещений, числе и сумме весов ребер, инцидентных
подмножеству вершин, вошедших в частичную подстановку.
Поиск оптимальной области резервирования
Для поиска оптимальной области резервирования используется
особенность реализации алгоритма, заключающаяся в том, что перебор
возможных подстановок
(
)
s
ϕ
можно продолжать после нахождения
первой полной подстановки и перебрать все полные подстановки,
которых может быть несколько. Из всех полных подстановок, которые
будут найдены алгоритмом, выбирается та, что соответствует
критерию оптимальности.
Оптимизация выделения распределенных ресурсов может
производиться по следующим критериям:
1.
По критерию минимального числа задействованных
вычислительных узлов. Решение этой задачи основано на
применении модифицированного алгоритма, в процессе
работы которого из всех возможных совмещений выбирается
то, при котором задействовано минимальное число вершин в
исходном графе, соответствующих вычислительным узлам.
2.
По критерию минимальной суммарной нераспределенной
вычислительной нагрузки. В качестве решения используется
частичная подстановка, отвечающая требованию
минимальности суммы весов нераспределенных вершин.
3.
По критерию минимального числа задействованных сетевых
соединений. Для решения задачи находятся реберные графы
вычислительной сети и резервируемой области и вычисления
производятся на реберных графах согласно пункту 1.
Результат соответствует резервируемой области с
минимальным числом задействованных сетевых соединений.
4.
По критерию минимальной суммарной нераспределенной
пропускной полосы каналов связи. Решение получается,
согласно пункту 2, для реберных графов вычислительной сети
и распределяемой области.
175
Выводы
В работе представлен переборный алгоритм оптимизации
резервирования распределенных вычислительных ресурсов. В
алгоритме использованы составные условия, ограничивающие область
поиска переборной части алгоритма, в том числе, основанные на
волновом разложении графов, значительно сокращающие время
поиска оптимального решения.
Рассмотренные в работе четыре направления оптимизации
выделения резервируемой области покрывают возможные требования
к оптимизации распределения зарезервированных
областей
вычислительной сети Grid, предъявляемые на данном этапе
использования технологии. Совместное последовательное
использование приведенных методов оптимизации дает эффект
субоптимального распределения зарезервированных областей в
масштабах всей сети. Строго оптимальное распределение можно
получить при использовании в качестве графа резервируемой области
составного графа, сформированного как сумма графов резервируемых
подсетей, но ввиду экспоненциального характера вычислительной
сложности алгоритма, применяемого для оптимизации, затраты
времени на выполнение строгой глобальной оптимизации в масштабах
реальных сетей Grid могут быть достаточно велики.
В работе впервые предложены подходы к оптимизации
резервирования распределенных вычислительных ресурсов в сетях
Grid, основанные на применении модификации точного алгоритма
поиска наибольшего подграфа.
Литература
1. Коваленко В., Корягин Д. Организация grid: есть ли
альтернативы? // Открытые системы. №12. 2004.
2.
Коваленко В., Корягин Д. Эволюция и проблемы Grid //
Открытые системы №01. 2003.
3.
Ильяшенко М.Б. Разработка и исследование параллельного
алгоритма проверки граф-подграф изоморфизма //
Радиоэлектроника. Информатика. Управление. – 2006. – N 1. –
С. 63-69.
4.
Ильяшенко М.Б. Алгоритм нахождения граф-подграф
изоморфизма для взвешенных графов и его применение //
Радиоэлектроника, Информатика, Управление. – 2007. – №1. –
С. 62-68.
176
5.
Пинчук В.П. Табличные инварианты на графах и их
применение // Кибернетика и системный анализ. – 2001. – №4
– С.33-45.
РАСЧЁТ НА ВЫСОКОПРОИЗВОДИТЕЛЬНОМ КЛАСТЕРЕ
ДИФФЕРЕНЦИАЛЬНО-РАЗНОСТНОЙ ЗАДАЧИ
УПРАВЛЕНИЯ ТЕМПЕРАТУРОЙ
Г.Г. Исламов, Ю.В. Коган, А.Г. Исламов, О.Л. Лукин
Удмуртский госуниверситет, Ижевск
Пусть вектор
T
n
xxx ),...,(
1
=
пробегает точки
n
-мерного
параллепипеда
],[],[
11 nn
babaG
×
×
=
L
. Рассмотрим в течение
времени
T
процесс изменения температуры
),( txu
в параллепипеде
G
с удельной теплоёмкостью
)(xc
, плотностью
)( x
ρ
и коэффициентом
теплопроводности
)( xk
при воздействии на него тепловыми
источниками и стоками плотности
)()(),( twxbtxF =
, где при
],0[ Tt
∈
имеем
maxmin
)( wtww
≤
≤
. Как известно, температура
),( txu
должна
удовлетворять для
),0(),( TGtx
×
∈
дифференциальному уравнению
теплопроводности
).,()()(
)(
1
)()(
11
txF
x
u
xpxk
xxpt
u
xxc
i
i
n
i
i
n
i
i
+
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
∂
∂
∂
∂
=
∂
∂
∑∏
==
ρ
(1)
Здесь
i
n
ij
j
j
i
H
H
p
∏
≠
=
=
1
при
2>n
и
i
i
H
p
1
=
при
2,1
=
n
;
i
H
-
коэффициенты Ламэ криволинейной ортогональной системы
координат, такие, что
)1(
1
1
−
≠
=
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
∏
n
n
ji
i
ij
pH
при
2>n
.
Задачу управления температурой поставим следующим образом.
Требуется построить такое кусочно-постоянное допустимое
управление
)),0(,)(()(
maxmin
Ttwtwwtw
∈
≤
≤
,
177
при котором уравнение
)1(
имеет гладкое решение
),( txu
,
удовлетворяющее граничному условию
Gxtxtxu
∂
∈
= ),,(),(
μ
(2)
и дополнительному ограничению вида
),(),(),( txtxutx
β
α
≤
≤
(3)
в области
),0(),( TGtx
×
∈
. Здесь функции
),( tx
α
и
),( tx
β
задают
диапазон изменения температуры внутри параллепипеда
G
. Заметим,
что мы не фиксируем начальную температуру
)0,(xu
. Как раз её
необходимо определить таким образом, чтобы с помощью управления
)(tw
из заданного диапазона
],[
maxmin
ww
можно было обеспечить
заданный температурный режим для указанной температуры
),( tx
μ
на
границе
G∂
параллепипеда размерности
n
.
Поставленная задача порождает дифференциально-разностный
аналог задачи управления температурой, описание которой приводится
ниже. Введём удобные для этого описания соглашения и обозначения.
Если индекс
i принимает значения
n,...,2,1
, то будем писать
ni ,1=
.
Пусть
),...,(
1 n
NNN =
есть целочисленный вектор с положительными
компонентами. Пусть, далее, мультииндексная переменная
),..,(
1 n
jjJ =
ограничена условием
nkNj
kk
,1,,0 ==
. Тогда
множество её значений образует целочисленную сетку
NJ
≤
≤
0
(неравенство векторов понимается покомпонентно). Как правило, мы
будем отождествлять переменную
J
с её значением. Мультииндекс
J
назвается внутренним, если при всех
nk ,1=
имеем
0
≠
k
j
и
kk
Nj
≠
.
Пусть
),..,(
1 n
jjJ =
есть внутренний мультииндекс. Рассматривая
уравнение
)1( во внутреннем узле
nkNabhhjhjx
kkkknn
J
,1,/)(),,...,(
11
=−==
,
параллепипеда
G
при всех
),0( Tt
∈
имеем точное равенство
).()(
),(
)()(
)(
1),(
)()(
11
twxb
x
txu
xpxk
xxpt
txu
xxc
J
xx
i
i
n
i
i
n
i
J
i
J
JJ
J
+
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
∂
∂
∂
∂
=
∂
∂
=
==
∑∏
ρ
(4)
Для тех же
t будем иметь
.),(),(),( txtxutx
JJJ
βα
≤≤
(5)
178
Обозначим через
F
конечномерное пространство
вещественнозначных функций, определённых на конечном множестве
внутренних мультииндексов
J
целочисленной сетки
.0 NJ
≤
≤
Пусть
вектор-функция
FTy →),0(:
определяется равенством
),(])[( txuJty
J
=
, а вектор
F
B
∈
задаётся как
)()(
)(
][
JJ
J
xxc
xb
JB
ρ
=
.
Тогда уравнение (4) может быть записано в виде конечномерной
системы дифференциальных уравнений
).,0(),()()()(' TtttBwtAyty
∈
+
+
=
ν
(6)
Здесь
A
есть матрица, порождённая одной из распространённых
схем дискретизации оператора Лапласа, стоящего в правой части
равенства (4). Вектор-функция
FT →),0(:
ν
порождена граничным
условием (2) и играет роль «помехи», которую необходимо
компенсировать с помощью управления
)(tw
из указанного выше
диапазона. В дальнейшем континуальное неравенство (5) мы заменим
дискретным аналогом
mity
iii
,1,)( =≤≤
βα
. (7)
Здесь
)0(
1
Tttt
iii
<
<
<
+
есть моменты наблюдения за
температурой, а векторы
)(,
iiii
F
β
α
β
α
≤
∈
порождены
соответственно выражениями
),(
i
J
tx
α
и
),(
i
J
tx
β
. В наших
обозначениях вектор
Fy
∈
)0(
характеризует начальную температуру
во внутренних узлах параллепипеда
.G
Теперь мы в состоянии
применить результаты работы [1] для получения необходимых и
достаточных условий разрешимости задачи (6)-(7) при заданном
допустимом управлении
)(tw
, а также принципа максимума для
указания точек переключения кусочно-постоянного управления
)(tw
,
принимающего лишь крайние значения
min
w
и
max
w
.
Если линейный функционал
λ
принадлежит сопряженному
пространству
*
F
и вектор
F
g
∈
, то
g⋅
λ
обозначает значение этого
функционала на элементе
g
. Функционал
λ
называется
неотрицательным, если
0≥
⋅
g
λ
для всех
Fgg
∈
≥ ,0
.
Теорема 1. Задача (6)-(7) разрешима тогда и только тогда, когда
неравенство
179
))}()({())}()({(
1
0
)(
2
1
0
)(
1
∑
∫
∑
∫
=
−
=
−
+−⋅≥+−⋅
m
i
t
stA
ii
m
i
t
stA
ii
i
i
i
i
dsssBwedsssBwe
ναλνβλ
(8)
имеет место для любого семейства неотрицательных функционалов
m
iii 1
21
},{
=
λλ
из сопряженного пространства
*
F
, удовлетворяющего
уравнению
ii
At
m
i
i
At
m
i
i
ee
∑∑
==
=
1
2
1
1
λλ
. (9)
Замечание 1. В действительности неравенство (8) достаточно
проверить на конечном числе образующих конуса неотрицательных
решений уравнения (9), для отыскания которых можно применить
вычислительную схему Н.В. Черниковой [1] либо воспользоваться
модификацией симплекс-метода.
Теорема 2. Пусть
)(t
ν
есть допустимая помеха для задачи
управления (6)-(7), то есть найдётся такое допустимое управление
)),0(,)(()(
maxmin
Ttwtwwtw
∈
≤
≤
, при котором указанная задача
разрешима. Тогда для некоторого семейства нетривиальных
неотрицательных функционалов
m
iii 1
21
},{
=
λλ
из сопряженного
пространства
*
F
, удовлетворяющего уравнению )9( , найдётся
компенсирующее помеху
)(t
ν
допустимое управление
)(
*
tw
,
удовлетворяющее при почти всех
),0( Ts
∈
принципу максимума
wssws
www
)(max)()(
maxmin
*
ϕϕ
≤≤
= ,
где скалярная функция
Bests
stA
i
m
i
ii
i
)(
2
1
1
)()(sign)(
−
=
⋅−−=
∑
+
λλϕ
.
Здесь используется положительная часть
2/|)|(
σσσ
+=
+
числа
σ
.
Замечание 2. Заметим, что вид уравнения (9) и скалярной
функции
)(s
ϕ
упростится, если ввести обозначение
21
iii
λλλ
−=
, при
этом не надо требовать неотрицательности этого функционала. Кроме
того, нетрудно установить следующее свойство кусочно-непрерывной
функции
)(s
ϕ
, концы интервалов знакопостоянства которой
180
определяют точки переключения в нашей задаче управления
температурой:
0)(
≡
s
ϕ
при
),(
1 m
tts
∉
и
Bes
As
k
−
⋅=
γϕ
)(
при
mktts
kk
,2],,(
1
=∈
−
, где функционалы
∑
=
=
m
ki
At
ik
i
e
λγ
, причём
0
1
1
==
∑
=
m
i
At
i
i
e
λγ
и для функционала
k
λ
имеем представление
mk
At
mm
At
kkk
emke
−−
+
=−=−=
γλγγλ
,1,1,)(
1
. Выбирая произвольно
функционалы
mk
k
,2, =
γ
, и считая, что
0
1
=
γ
, из последних формул
получим любое решение системы
∑
=
=
m
i
At
i
i
e
1
0
λ
. Теперь остаётся найти
положительную и отрицательную части
+
i
λ
и
−
i
λ
функционала
i
λ
и
положить в теореме 1 соответственно
δλλ
+=
+
ii
1
и
δλλ
+=
−
ii
2
, где
δ
есть произвольный неотрицательный функционал.
На основе этих результатов разработаны эффективные
алгоритмы расчёта точек переключения в диффенциально-разностной
задаче управления температурой двумерных и трёхмерных
параллепипедов. Дано сравнение численных результатов, полученных
на вычислительном кластере с использованием различных технологий
распределённого и параллельного программирования (sockets,
PThreads, PVM, MPI, OpenMP) .
Литература
1. Исламов Г.Г. О допустимых помехах линейных управляемых
систем // Изв. Вузов. Математика. – 2002. - № 2. – С. 37-40.