Например, Бобцов

ОЦЕНКА ЭФФЕКТИВНОСТИ РАСПРЕДЕЛЕННЫХ СИСТЕМ ПРИ РЕШЕНИИ ЗАДАЧ ПЕРЕМЕННОГО РАЗМЕРА

ОЦЕНКА ЭФФЕКТИВНОСТИ РАСПРЕДЕЛЕННЫХ СИСТЕМ...
УДК 519.687+004.75
ОЦЕНКА ЭФФЕКТИВНОСТИ РАСПРЕДЕЛЕННЫХ СИСТЕМ ПРИ РЕШЕНИИ ЗАДАЧ ПЕРЕМЕННОГО РАЗМЕРА
А.С. Хританков
Исследуется проблема описания производительности распределенных систем вычислительных кластеров при решении задач переменной трудоемкости. Для этого используется модель производительности интервальных систем с расписанием, которая в данной работе расширена для учета вероятностного характера трудоемкости задачи. Полученные результаты позволяют применить модель систем с расписанием для расчета верхней границы эффективности и погрешности в ее измерении при решении задач глобальной оптимизации стохастическими алгоритмами. Ключевые слова: распределенные вычисления, оценка эффективности, глобальная оптимизация.
Введение
Рассмотрим процесс решения задачи глобальной оптимизации эвристическим методом, основанном на подходе Монте-Карло. Важной особенностью является то, что исходная задача A разбивается на M однотипных подзадач {Ak }1M . Например, в методе Basin–Hopping [1] подзадачей является нахождение локального минимума итеративным алгоритмом из начальной точки, выбираемой случайным образом в окрестности предполагаемого минимума. Трудоемкость решения подзадачи напрямую зависит от количества шагов локального алгоритма и сложности вычисления оптимизируемой функции. В широком диапазоне значений параметров алгоритма трудоемкости решения {Lk }1M подзадач можно полагать независимыми в совокупности случайными величинами, имеющими одинаковое распределение. Пренебрегая затратами на генерацию начальных точек и относя накладные расходы на распараллеливание и коммуникации к решению подзадач, можно положить, что суммарная трудоемкость решения исходной
задачи A выражается суммой L = ∑kM=1Lk . Согласно центральной предельной теореме,
распределение случайной величины L при большом количестве подзадач близко к
( )нормальному Ν M μ,M σ2 , где μ = ELi , σ2 = DLi в силу единого распределения ве-
личин Li . Трудоемкость решения подзадачи для алгоритмов локальной оптимизации в задачах конформации молекул и докинга протеин-лиганд, согласно экспериментальным данным, имеет положительно асимметричное унимодальное распределение, при этом σ ≈ 0,4μ . Таким образом, отклонение трудоемкости решения задачи A из M = 400 подзадач от среднего значения с вероятностью порядка 95% не превышает 0, 04M μ . Вследствие того, что точные значения μ и σ неизвестны и должны быть получены в виде оценок, возникает значительная ошибка (около 20%) в определении трудоемкости L , которую необходимо учитывать при сопоставлении экспериментальных данных с моделью работы системы. Кроме того, существенным для модели производительности системы является учет случайного характера изменения трудоемкости подзадач, который приводит к снижению эффективности работы.
В данной работе мы построим модель производительности распределенной системы при решении описанного класса декомпозируемых задач оптимизации ΑM , оценим структурную эффективность при решении в рамках интервальной модели, рассмотрим экспериментальный метод оценки трудоемкости решения задачи и получим оценки его точности; сравним построенную модель с работой реального вычислительного комплекса с учетом полученных оценок погрешностей.
66 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 2(66)

А.С. Хританков

Расширение модели систем с расписанием

Для оценки эффективности решения задачи на распределенной вычислительной

системе мы будем использовать модель систем с расписанием [2, 3], которую в данном

разделе мы кратко изложим. Распределенная система R представляется как совокуп-

ность n вычислителей, выделяемых для решения задачи A согласно расписанию h(t) .

В зависимости от цели исследования выбирается модель решения задачи на данной

системе. Модель включает некоторый набор предположений относительно структуры

задачи, механизма распараллеливания и позволяет рассчитать время решения задачи.

Модель такого рода называется эталонной системой Ρ и, по сути, является модельной системой с расписанием, работающей согласно сделанным предположениям по тому же

расписанию, что и реальная система. Каждому вычислителю приписывается стоимость

использования ci в единицу времени, а также, в условиях модели Ρ , эталонное время

решения Τi – время, которое данный вычислитель затратил бы на решение задачи A .

Эталонное время Τ , т.е. время решения задачи системой Ρ , рассчитывается на основе

параметров и предположений модели. Эффективность Et по времени решения задачи

системой R по отношению к системе Ρ определяется как отношение эталонного времени Τ системы Ρ к реальному времени решения T :

Et

=

Τ T

.

Ресурсная эффективность Eϕ определяется похожим образом – как отношение стоимо-

сти использования системы Φ(t) за эталонное время Τ к аналогичной стоимости за ре-

альное время:



=

Φ(Τ) Φ(T )

.

В качестве примера рассмотрим универсальную эталонную систему Ρ , в которой отсутствуют накладные расходы на распараллеливание решения и задача полагается

произвольно делимой. Эталонное время решения Τ в системе Ρ вычисляется как решение задачи минимизации:

min t
t

при условии

∫0t ∑in=1πihi (τ)dτ = L ,

πi

=L Τi

.

Интервальная эталонная система [3], как и универсальная модель, предполагает,

что трудоемкость L остается постоянной при повторном решении задачи и при пере-

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

ΑM данное предположение является слишком строгим. Расширим интервальную систему для решения класса задач с переменной трудоемкостью. Обозначим такую систе-

му Ρm , в дополнение к ограничениям интервальной системы будем полагать, что

{Lk }1M – независимые в совокупности случайные величины. В дальнейшем будем счи-

тать, что их распределение имеет положительный коэффициент асимметрии и конеч-

ный коэффициент эксцесса. Напомним, что интервальная система предполагает реше-

ние задачи как набора одинаковых по трудоемкости подзадач на системе из кластеров

одинаковых вычислителей, управляемых совместно. Подзадачи назначаются на кластер

пакетами, промежуток времени решения пакета задач называется этапом решения.

Для эталонной системы Ρm можно оценить распределение трудоемкости решения

задачи. Действительно, так как L = ∑kM=1Lk , то при больших M , согласно центральной

Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 2(66)

67

ОЦЕНКА ЭФФЕКТИВНОСТИ РАСПРЕДЕЛЕННЫХ СИСТЕМ...

предельной теореме, распределение L можно полагать приближенно нормальным
N (M μ, M σ2 ) , где μ и σ2 – математическое ожидание и дисперсия Lk . Итак, мы по-
строили систему Ρm , которая отражает основное свойство задач класса ΑM – декомпозируемость на множество подзадач, трудоемкости которых являются одинаково распределенными случайными величинами, и учитывает существенные ограничения на управляемость отдельными вычислителями, характерные для современных распределенных систем.

Оценка структурной неэффективности в интервальной модели

Воспользуемся расширением интервальной модели и оценим величину структур-

ной неэффективности, возникающей вследствие различной трудоемкости подзадач.

Рассмотрим решение пакета из M = m ⋅ p подзадач класса ΑM на кластере из p вычислителей. Вследствие того, что подзадачи имеют разную трудоемкость, вычислители,

завершившие последовательный расчет m подзадач, будут простаивать, так как сле-

дующий пакет подзадач не может быть получен, пока не будет решена последняя под-

задача из данного пакета.

Пусть X i – случайная величина, выражающая суммарную стоимость решения m

подзадач на вычислителе i , со средним значением μm и дисперсией σm2 . В среднем

долю ε p стоимости вычислений, затраченных на решение подзадач, можно оценить

как

Eε p

=

E

∑ip=1ci X i

max
i=1.. p

X

i

∑ip=1ci

,

Δj

=

max
i=1.. p

X

i



X

j

,

X i*

=

max
i=1.. p

X

i

,

Eε p

=

∑ip=1

ci cΣ

E⎜⎛⎜⎝

Xi X i*

⎟⎠⎞⎟

=

∑i≠i*

ci cΣ

EX i EX i*

+

ci* cΣ

E

X i* X i*

.

На практике EΔi лежит в пределах от σm до 4σm при p от 10 до 50, возрастая

как логарифм от числа вычислителей

p,

EΔi = a ln p ⋅ σm . Дисперсию

σ

2 m

можно оце-

нить как дисперсию суммы m случайных величин, σm2 ≈ m ⋅ σ2 . Для вычислителей из

одного кластера логично положить ci = c0 = cΣ / p , получим:

Eε p

=

p −1 EX i p EX i*

+

1 p

=

EX i EX i*

+

1 p

EΔi EX i*

,

(1)

Eε p

≈ ⎜⎜⎛⎝1 +

p −1ln p

p

C M

⎞⎟⎠⎟−1 , σ = θμ ,

EXi* = EXi + EΔi ,

C

= aθ .

(2)

По построению, величина ε p является оценкой сверху ресурсной эффективности

эталонной системы Ρm по отношению к универсальной системе Ρ , усредненной по различным возможным трудоемкостям подзадач.
Из выражения (2) удается получить функцию изоэффективности M = F ( p, ε0) , указывающую, какого размера (в нашем случае – число подзадач в пакете) должна быть задача, чтобы ее эффективность составляла ε0 при p вычислителях в кластере:

68 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 2(66)

А.С. Хританков

M



C

2

⎛⎝⎜⎜

1

ε0 − ε0

⎟⎞⎟⎠2

p ln2

p.

(3)

Оценку средней продолжительности Eτ этапа решения кластера для пакета из M

задач получим из выражения для среднего EXi* максимальной трудоемкости задачи на кластере:



=

μm c0

(1

+

Cm−3 /

2

ln

p)

.

(4)

Следовательно, длительность этапа решения не остается постоянной и при постоянной

эффективности возрастает как логарифм количества вычислителей в кластере.

Пусть в распределенной системе имеется N кластеров, долю кластера в полной

стоимости решения задачи обозначим через ξ j > 0 , ∑ Nj =1ξ j = 1. Тогда ресурсная эф-

фективность Eϕ системы вычисляется как взвешенная сумма эффективностей класте-

ров Eϕj :

∑Eϕ =

N j =1

ξ

j

Eϕj

.

(5)

Для определения долей ξ j для конкретного расписания нужно указать алгоритм

балансировки, например, представленный в работе [3] с продолжительностью этапа

решения (4).

Экспериментальная оценка трудоемкости задачи

Для расчета эффективности решения задачи необходимо знать трудоемкость ее решения L . Метод экспериментальной оценки состоит в последовательном решении ограниченного набора подзадач, измерения трудоемкости их решения и оценки параметров распределения. После этого, используя предположение о нормальности распределения L , рассчитывается среднее значение трудоемкости и дисперсия. Случайным образом выберем K подзадач из M и решим их на вычислителе i последовательно,
измеряя время их решения Τik . Функцию трудоемкости L( ⋅ ) определим как
Lk = L(Ak ) = Τik . В данной работе мы будем использовать оценки mK = ∑kK=1 Lk / K для
среднего и sK2 = ∑kK=1(Lk − m)2 /(K −1) для дисперсии. Отсюда получим оценку сред-
него значения μΣ = MmK и стандартного отклонения σΣ = MsK для трудоемкости все задачи L . Рассмотрим центральный доверительный интервал для трудоемкости
Iα,β = [EμΣ − αδΣ ; EμΣ + αδΣ ] ,
где отклонение δΣ складывается из математического ожидания EσΣ и дисперсий оценок μΣ и σΣ :
δΣ = EσΣ + β DσΣ + DμΣ + 2Cov(μΣ , σΣ ) . Выражения для входящих в формулу величин получены в книге [4]. Обозначая коэффициент эксцесса распределения Lk через κ = μ4 / σ4 − 3, коэффициент корреляции
между оценками через ρ и полагая σ = θμ , получим при M ≈ K 2 :

δΣ = Mμ ⋅ θ⎜⎛⎝⎜

1 M

+

κ 2

+6 K

+

ρ K

κ κ

+ +

2 6

+

O(1/

K 2)⎞⎟⎟⎠ .

(6)

Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 2(66)

69

ОЦЕНКА ЭФФЕКТИВНОСТИ РАСПРЕДЕЛЕННЫХ СИСТЕМ...

В эксперименте наблюдались значения κ ∈[2;4] , θ ∈[0,3;0,5] , следовательно, по

порядку величины, при α = 1 и β = 1 (вероятность попадания P{L ∈ I1,1} ≈ 80% ), и

K = 25 , доверительный интервал для L составляет

I1,1 = [0,85⋅ MmK ;1,15⋅ MmK ].

(7)

Основной вклад в точность оценок вносит второе слагаемое в формуле (1), связанное с дисперсией оценки стандартного отклонения. При большом значении коэффи-

циента эксцесса для сохранения точности расчета нужно пропорционально увеличить объем выборки K .

Результаты экспериментов
Для комплекса BnB-Grid при выделении 5 модельных кластеров на МВС-100К в силу схемы управления вычислителями M = p . При использовании алгоритма SMBH [5] с максимальным числом итераций локального алгоритма Nmax = 8192 и радиусе окрестности возмущения r = 0,9 , экспериментально установлено θ ≈ 0,4 ; исходя из распределения трудоемкости решения подзадач, численно рассчитан коэффициент a = 0,84 . В данном эксперименте трудоемкость рассчитывалась по K = 120 подзадачам. Экспериментально полученные значения ресурсной эффективности, доверительные интервалы I1,1 (7), и графики функций (1) и (2) приведены на рис. 1.
1.0 1.0
0.8 0.8
0.6 0.6
0.4 0.4
0.2 0.2

0 5 10 15 20 25 30
Рис. 1. Сравнение модели структурной неэффективности и экспериментальных данных: приближенная модель (пунктир) и
точная модель (сплошная)

0 5 10 15 20 25 30
Рис. 2. Возможности обнаружения отклонений результатов экспериментов от модели при оценке по ограниченной выборке (пунктир) и каждой подзадачи
(сплошная)

Заметим, что доверительный интервал при p ≤ 12 больше, так как задача состояла
из 120 подзадач, в то время как при 12 < p ≤ 28 – из 512 подзадач. Из графика видно,
что различия между (1) и (2) имеют порядок точности измерений, поэтому использование приближения (2) в теоретических выкладках вполне оправдано. Полученная модель оценивает эффективность сверху, отклонения экспериментальных данных, по большей части, объясняются простоем вычислителей кластера при недостатке задач, что заметно при p=7–12, и замедлением при использовании нескольких ядер одного процессора. При этом, как видно из рис. 2, определение трудоемкости по выборке размера
K ≈ M позволило бы обнаружить снижение эффективности только при p=7–12, что вполне достаточно для реальных задач, когда повторное решение задачи не имеет смысла, а измерение трудоемкости подзадач невозможно в процессе решения. Сплошными линиями на рис. 2 показаны границы при K ≈ M , видно, что при исследовании

70 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 2(66)

А.С. Хританков

поведения системы этого достаточно для обнаружения небольших отклонений от модели, ошибка определения эффективности составит при M ≈ 500 порядка 5%.

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

Литература

1. Wales D.J., Doye J.P.K. Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms // Journal of Physical Chemistry. – 1997. – № 101. – Р. 5111–5116.
2. Посыпкин М.А., Хританков А.С. О понятии ускорения и эффективности в распределенных системах // Научный сервис в сети Интернет'2008: решение больших задач: Труды конференции. – 2008. – С. 149–156.
3. Хританков А.С. Об одном алгоритме балансировки вычислительной нагрузки в распределенных системах // Параллельные вычислительные технологии (ПаВТ’2009): Труды международной научной конференции (Нижний Новгород, 30 марта – 3 апреля 2009 г.). – Челябинск: Изд. ЮУрГУ, 2009. – 839 с., С. 778–783.
4. Крамер Г. Математические методы статистики. – 2-е изд. – М.: Мир, 1975. – 648 c. 5. Посыпкин М.А. Методы и распределенная программная инфраструктура для чис-
ленного решения задачи поиска молекулярных кластеров с минимальной энергией // Параллельные вычислительные технологии (ПаВТ’2009): Труды международной научной конференции (Нижний Новгород, 30 марта – 3 апреля 2009 г.). – Челябинск: Изд. ЮУрГУ, 2009. – 839 с., С. 269-281.

Хританков Антон Сергеевич

– Московский физико-технический институт (государственный университет), аспирант, anton.khritankov@gmail.com

Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 2(66)

71