Оценка эффективности распределенных систем при решении задач переменного размера

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 519. 687+004. 75
ОЦЕНКА ЭФФЕКТИВНОСТИ РАСПРЕДЕЛЕННЫХ СИСТЕМ ПРИ РЕШЕНИИ ЗАДАЧ ПЕРЕМЕННОГО РАЗМЕРА
А.С. Хританков
Исследуется проблема описания производительности распределенных систем вычислительных кластеров при решении задач переменной трудоемкости. Для этого используется модель производительности интервальных систем с расписанием, которая в данной работе расширена для учета вероятностного характера трудоемкости задачи. Полученные результаты позволяют применить модель систем с расписанием для расчета верхней границы эффективности и погрешности в ее измерении при решении задач глобальной оптимизации стохастическими алгоритмами.
Ключевые слова: распределенные вычисления, оценка эффективности, глобальная оптимизация.
Введение
Рассмотрим процесс решения задачи глобальной оптимизации эвристическим методом, основанном на подходе Монте-Карло. Важной особенностью является то, что
исходная задача A разбивается на M однотипных подзадач {Ak }M. Например, в методе Basin-Hopping [1] подзадачей является нахождение локального минимума итеративным алгоритмом из начальной точки, выбираемой случайным образом в окрестности предполагаемого минимума. Трудоемкость решения подзадачи напрямую зависит от количества шагов локального алгоритма и сложности вычисления оптимизируемой функции. В широком диапазоне значений параметров алгоритма трудоемкости решения {Lk }M подзадач можно полагать независимыми в совокупности случайными величинами, имеющими одинаковое распределение. Пренебрегая затратами на генерацию начальных точек и относя накладные расходы на распараллеливание и коммуникации к решению подзадач, можно положить, что суммарная трудоемкость решения исходной
задачи A выражается суммой L = ^?=1 Lk. Согласно центральной предельной теореме, распределение случайной величины L при большом количестве подзадач близко к нормальному N (мд, Ма2), где д = ELt, а2 = DLj в силу единого распределения величин Lj. Трудоемкость решения подзадачи для алгоритмов локальной оптимизации в
задачах конформации молекул и докинга протеин-лиганд, согласно экспериментальным данным, имеет положительно асимметричное унимодальное распределение, при этом а"0,4д. Таким образом, отклонение трудоемкости решения задачи A из M = 400 подзадач от среднего значения с вероятностью порядка 95% не превышает 0,04Mд. Вследствие того, что точные значения д и, а неизвестны и должны быть получены в виде оценок, возникает значительная ошибка (около 20%) в определении трудоемкости L, которую необходимо учитывать при сопоставлении экспериментальных данных с моделью работы системы. Кроме того, существенным для модели производительности системы является учет случайного характера изменения трудоемкости подзадач, который приводит к снижению эффективности работы.
В данной работе мы построим модель производительности распределенной системы при решении описанного класса декомпозируемых задач оптимизации Ам, оценим структурную эффективность при решении в рамках интервальной модели, рассмотрим экспериментальный метод оценки трудоемкости решения задачи и получим оценки его точности- сравним построенную модель с работой реального вычислительного комплекса с учетом полученных оценок погрешностей.
Расширение модели систем с расписанием
Для оценки эффективности решения задачи на распределенной вычислительной системе мы будем использовать модель систем с расписанием [2, 3], которую в данном разделе мы кратко изложим. Распределенная система Я представляется как совокупность п вычислителей, выделяемых для решения задачи, А согласно расписанию Я (V). В зависимости от цели исследования выбирается модель решения задачи на данной системе. Модель включает некоторый набор предположений относительно структуры задачи, механизма распараллеливания и позволяет рассчитать время решения задачи. Модель такого рода называется эталонной системой Р и, по сути, является модельной системой с расписанием, работающей согласно сделанным предположениям по тому же расписанию, что и реальная система. Каждому вычислителю приписывается стоимость использования сг- в единицу времени, а также, в условиях модели Р, эталонное время
решения Тг — время, которое данный вычислитель затратил бы на решение задачи А. Эталонное время Т, т. е. время решения задачи системой Р, рассчитывается на основе параметров и предположений модели. Эффективность Е1 по времени решения задачи
системой Я по отношению к системе Р определяется как отношение эталонного времени Т системы Р к реальному времени решения Т: Т
Т'-
Ресурсная эффективность Еф определяется похожим образом — как отношение стоимости использования системы Ф (/) за эталонное время Т к аналогичной стоимости за реальное время:
Е -ФИ ф Ф (Т)'-
В качестве примера рассмотрим универсальную эталонную систему Р, в которой отсутствуют накладные расходы на распараллеливание решения и задача полагается произвольно делимой. Эталонное время решения Т в системе Р вычисляется как решение задачи минимизации:
Et =
min t при условии jj0 Xn=i ПА (x)di = L, п ^
L
Интервальная эталонная система [3], как и универсальная модель, предполагает, что трудоемкость Ь остается постоянной при повторном решении задачи и при переходе от последовательного к параллельному решению. При рассмотрении класса задач Ам данное предположение является слишком строгим. Расширим интервальную систему для решения класса задач с переменной трудоемкостью. Обозначим такую систему Рт, в дополнение к ограничениям интервальной системы будем полагать, что
{Ьк }М — независимые в совокупности случайные величины. В дальнейшем будем считать, что их распределение имеет положительный коэффициент асимметрии и конечный коэффициент эксцесса. Напомним, что интервальная система предполагает решение задачи как набора одинаковых по трудоемкости подзадач на системе из кластеров одинаковых вычислителей, управляемых совместно. Подзадачи назначаются на кластер пакетами, промежуток времени решения пакета задач называется этапом решения.
Для эталонной системы Рт можно оценить распределение трудоемкости решения
задачи. Действительно, так как Ь — Ь^, то при больших М, согласно центральной
предельной теореме, распределение L можно полагать приближенно нормальным
2 2
N (Mд, Mа), где д и, а — математическое ожидание и дисперсия Lk. Итак, мы построили систему Pm, которая отражает основное свойство задач класса Ам — деком-
позируемость на множество подзадач, трудоемкости которых являются одинаково распределенными случайными величинами, и учитывает существенные ограничения на управляемость отдельными вычислителями, характерные для современных распределенных систем.
Оценка структурной неэффективности в интервальной модели
Воспользуемся расширением интервальной модели и оценим величину структурной неэффективности, возникающей вследствие различной трудоемкости подзадач. Рассмотрим решение пакета из M = m ¦ p подзадач класса Ам на кластере из p вычислителей. Вследствие того, что подзадачи имеют разную трудоемкость, вычислители, завершившие последовательный расчет m подзадач, будут простаивать, так как следующий пакет подзадач не может быть получен, пока не будет решена последняя подзадача из данного пакета.
Пусть Xj — случайная величина, выражающая суммарную стоимость решения m
подзадач на вычислителе i, со средним значением дm и дисперсией аm • В среднем долю s p стоимости вычислений, затраченных на решение подзадач, можно оценить как
Es p = E---, A j = max Xj — Xj, Xj* = max Xj,
max X j YJp=1cj j=1& quot-p j=1& quot-p
j=1. p
Es D =У p^EXj- ] = Y, cLEXi^ + ^ e
p ?-4 =1 ^ Y ?-ЧФ1 *" T7V ^
CE
V xi* J
cj EX j + c* ^ X,
*
cE EXj* cE X
*
На практике ЕАг- лежит в пределах от ат до 4ат при р от 10 до 50, возрастая
2
как логарифм от числа вычислителей р, ЕАг- = а 1п р ¦ ат. Дисперсию ат можно оце-
2 2
нить как дисперсию суммы т случайных величин, ат «т ¦а. Для вычислителей из
одного кластера логично положить с = Со = с^ / р, получим:
р -1 ЕХ1 1 ЕХ1 1 ЕА1 Ее р = ---- + - =-- ±--, (1)
Es p
p EX* p EX* p EXt
i * r I
f 1 n V1
i p — 1i с
1 + .- ln p
, а = 0д, EX* = EX j + EAj, C = aQ. (2)
4Р лМ
По построению, величина ер является оценкой сверху ресурсной эффективности
эталонной системы Рт по отношению к универсальной системе Р, усредненной по различным возможным трудоемкостям подзадач.
Из выражения (2) удается получить функцию изоэффективности М = Г (р, ео), указывающую, какого размера (в нашем случае — число подзадач в пакете) должна быть задача, чтобы ее эффективность составляла ео при р вычислителях в кластере:

M «C2
У «^
V
Р 1п2 р. (3)
1 -8о
Оценку средней продолжительности Eт этапа решения кластера для пакета из М задач получим из выражения для среднего ЕХг* максимальной трудоемкости задачи на кластере:
Ет = Дт (1 + Ст& quot-3/21п p). (4)
с0
Следовательно, длительность этапа решения не остается постоянной и при постоянной эффективности возрастает как логарифм количества вычислителей в кластере.
Пусть в распределенной системе имеется N кластеров, долю кластера в полной
стоимости решения задачи обозначим через? у & gt- 0, ^ N=1? у = 1. Тогда ресурсная эффективность Еф системы вычисляется как взвешенная сумма эффективностей кластера Еф:
ЕФ = ! N=1?. (5)
Для определения долей? у для конкретного расписания нужно указать алгоритм
балансировки, например, представленный в работе [3] с продолжительностью этапа решения (4).
Экспериментальная оценка трудоемкости задачи
Для расчета эффективности решения задачи необходимо знать трудоемкость ее решения Ь. Метод экспериментальной оценки состоит в последовательном решении ограниченного набора подзадач, измерения трудоемкости их решения и оценки параметров распределения. После этого, используя предположение о нормальности распределения Ь, рассчитывается среднее значение трудоемкости и дисперсия. Случайным образом выберем К подзадач из М и решим их на вычислителе г последовательно,
измеряя время их решения Тгк. Функцию трудоемкости Ь (•) определим как
= Ь (Л^) = Тк. В данной работе мы будем использовать оценки тк = Хк=1 Ьк / К для 2 к 2
среднего и sк = Хк=1(Ьк — т) /(К -1) для дисперсии. Отсюда получим оценку среднего значения д^ = Мтк и стандартного отклонения а^ = М& amp-к для трудоемкости все задачи Ь. Рассмотрим центральный доверительный интервал для трудоемкости
1 а, р = [ЕДЕ -а§ Е-ЕДЕ + а5Е], где отклонение складывается из математического ожидания Еа^ и дисперсий оценок д^ и о^:
5е = ЕоЕ + + 2СОУ (Де, оЕ).
Выражения для входящих в формулу величин получены в книге [4]. Обозначая коэффициент эксцесса распределения Ьк через к = д4/ о4 — 3, коэффициент корреляции
2
между оценками через р и полагая, а = 9д, получим при М «к:
5е = Мд • 9
1 л/кГб р 1к + 2 ^
+ + -7+ 0(1/к2). (6)
4ы 2у[к к к + 6
В эксперименте наблюдались значения ке[2−4], 9е [0,3−0,5], следовательно, по порядку величины, при, а = 1 и в = 1 (вероятность попадания Р{Ь е /ц} «80%), и К = 25, доверительный интервал для Ь составляет
/1Д = [0,85 • МтК -1,15 • МтК ]. (7)
Основной вклад в точность оценок вносит второе слагаемое в формуле (1), связанное с дисперсией оценки стандартного отклонения. При большом значении коэффициента эксцесса для сохранения точности расчета нужно пропорционально увеличить объем выборки К.
Результаты экспериментов
Для комплекса ВпВ-Опё при выделении 5 модельных кластеров на МВС-100К в силу схемы управления вычислителями М = р. При использовании алгоритма БМВИ
[5] с максимальным числом итераций локального алгоритма Nтях = 8192 и радиусе окрестности возмущения г = 0,9, экспериментально установлено 9 «0,4- исходя из распределения трудоемкости решения подзадач, численно рассчитан коэффициент, а = 0,84. В данном эксперименте трудоемкость рассчитывалась по К = 120 подзадачам. Экспериментально полученные значения ресурсной эффективности, доверительные интервалы / (7), и графики функций (1) и (2) приведены на рис. 1.
Рис. 1. Сравнение модели структурной неэффективности и экспериментальных данных: приближенная модель (пунктир) и точная модель (сплошная)
Рис. 2. Возможности обнаружения отклонений результатов экспериментов от модели при оценке по ограниченной выборке (пунктир) и каждой подзадачи (сплошная)
Заметим, что доверительный интервал при р & lt- 12 больше, так как задача состояла из 120 подзадач, в то время как при 12 & lt- р & lt- 28 — из 512 подзадач. Из графика видно, что различия между (1) и (2) имеют порядок точности измерений, поэтому использование приближения (2) в теоретических выкладках вполне оправдано. Полученная модель оценивает эффективность сверху, отклонения экспериментальных данных, по большей части, объясняются простоем вычислителей кластера при недостатке задач, что заметно при р=7−12, и замедлением при использовании нескольких ядер одного процессора. При этом, как видно из рис. 2, определение трудоемкости по выборке размера К позволило бы обнаружить снижение эффективности только при р=7−12, что
вполне достаточно для реальных задач, когда повторное решение задачи не имеет смысла, а измерение трудоемкости подзадач невозможно в процессе решения. Сплошными линиями на рис. 2 показаны границы при К «М, видно, что при исследовании
1. 0
1. 0
0. 8
0. 8
0. 6
0. 6
0. 4
0. 4
0. 2
0. 2
5
10
15
20
25
30
5
10
15
20
25
30
поведения системы этого достаточно для обнаружения небольших отклонений от модели, ошибка определения эффективности составит при 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 с.
5. Посыпкин М. А. Методы и распределенная программная инфраструктура для численного решения задачи поиска молекулярных кластеров с минимальной энергией // Параллельные вычислительные технологии (ПаВТ'-2009): Труды международной научной конференции (Нижний Новгород, 30 марта — 3 апреля 2009 г.). — Челябинск: Изд. ЮУрГУ, 2009. — 839 с., С. 269−281.
Хританков Антон Сергеевич — Московский физико-технический институт (государственный
университет), аспирант, anton. khritankov@gmail. com

ПоказатьСвернуть
Заполнить форму текущей работой