Современные распределённые вычислительные системы состоят из тысяч и десятков тысяч процессоров. Увеличение числа процессоров ведёт к усложнению коммуникационной среды и росту накладных расходов на обмен информацией между вычислительными устройствами. Эффективность современных многопроцессорных систем зависит не только от характеристик отдельных вычислительных устройств, но и от характеристик коммуникационной среды. Труды XIX Международной конференции «Аналитика и управление данными в областях с интенсивным использованием данных» (DAMDID/ RCDL’2017), Москва, Россия, 10–13 октября 2017 года и использование в реальном времени информации о задержках при передаче сообщений для каждой пары вычислительных узлов. Рисунок 1 Пример картины задержек при передаче сообщений. Суперкомпьютер BlueGene/P
Величины задержек зависят от множества факторов, специфичных для разных вычислительных систем и меняющихся со временем, учёт которых при моделировании задержек требует анализа программного и аппаратного обеспечения на всех уровнях сетевого протокола, что возможно лишь для самых простых архитектур. В связи с этим начали активно развиваться системы MPI-тестирования коммуникационной среды [13]. Поскольку на практике размеры вычислительных кластеров не позволяют хранить выборки задержек для всех пар вычислительных узлов, для описания используются некоторые эмпирические статистики, вычисленные по выборкам величин задержек, которые могут не отражать в полной мере структуры задержек. В качестве альтернативы предлагается стохастическая модель, в которой неконтролируемые факторы рассматриваются как скрытые параметры, а задержки – как случайные величины с некоторыми распределениями. Такая модель одновременно описывает картину задержек более полно, чем набор статистик, и позволяет хранить информацию в сильно сжатом виде – всего несколько чисел – параметров модели вместо выборки.
Проведенные ранее исследования задержек в локальных сетях и интернете [5, 10, 11] показали, что величины задержек хорошо описываются трёхпараметрическим гамма- или логнормальным распределением. В коммуникационных средах вычислительных кластеров, однако, наблюдаются следующие особенности [6]: • распределение задержек является
многомодальным; • в данных много повторов и мало уникальных
значений. На Рис. 1 приведена картина задержек в коммуникационной среде суперкомпьютера BlueGene/P, на которой явно видны указанные особенности. Исходя из этого, в работе [6] в качестве модели задержек предложено использовать смесь трёхпараметрических логнормальных распределений. Однако проблемы возникают даже при параметрическом восстановлении одного компонента такой смеси. Подробнее об этих проблемах сказано ниже.
Работа посвящена разработке и исследованию специализированных методов восстановления трёхпараметрических логнормальных распределений по конечным выборкам задержек передачи информации в коммуникационной среде суперкомпьютера. Статья устроена следующим образом. В разделе 2 введены используемые основные определения Разделы 3, 4 и 5 посвящены обзору существующих методов оценки параметров трёхпараметрического логнормального распределения (метод максимального правдоподобия, метод моментов, метод L-моментов и методы минимизации расстояния). В разделе 6 описаны данные, использованные в вычислительном эксперименте (модельные и реальные). Раздел 7 посвящён сравнению методов оценивания параметров, рассмотренных в разделах 3, 4 и 5, на синтетических и реальных данных. 2 Основные обозначения и определения
Трёхпараметрическое логнормальное распределение (3LN распределение) – это абсолютно непрерывное одномерное распределение, функция плотности вероятности которого выражается формулой ( ; , , )
1 (ln( − )− )2 = {√2 ( – ) exp(− 2 2
), ≥ , 0, может < .
быть Функция распределения 3LN записана в виде ( ; , , ) = Φ (ln( − )− ), где
σ Φ( ) – функция распределения стандартного нормального закона [4]. Основные моментные характеристики распределения указаны в таблице 1.
Набор параметров , , будем обозначать . Будем обозначать случайную выборку длины = ( 1, … , ), её реализацию – = ( 1, … , ), -ю порядковую статистику и её реализацию – ( ) и ( ) соответственно. 3 Метод максимума правдоподобия и его модификации
Наиболее популярным подходом к параметрической оценке плотности распределения является метод максимального правдоподобия (ММП). В качестве меры адекватности распределения (∙, ) данным используется функция правдоподобия ( )= ( ; ) – совместная плотность вероятности объектов выборки. Полагается, что чем больше значение функции правдоподобия, тем лучше модель описывает данные. Оценки максимального правдоподобия для многих задач оказываются состоятельными, асимптотически нормальными и асимптотически эффективными. Для семейства 3LN распределений логарифм
) = 0, ∑ =1 (−1 + ln( − )−
2 (ln( − )− )2 2
) = 0. ⎧ ∂ln ⎪ ∂ ⎪ ∂ln
∂ ⎪ ⎪ ∂ln ⎪ ∂ ⎪ ⎪ ⎨ ⎪ ⎩ его
) = 0. 4 Общий метод моментов
При оценке параметров с использованием метода моментов на распределение (⋅; ) накладывается последовательность
ограничений типа равенства, образующая систему уравнений
вида ( )= выборочными оценками,
как ℎ ( ), = 1, , где функции ( ) характеризуют теоретическое распределение, а ℎ ( )являются их
правило, несмещёнными или хотя бы
асимптотически несмещёнными. Таблица 1 Основные моменты 3LN распределения , = γ + β√ω β2ω(ω − 1)
) √ω − 1(ω + 2) ω4 + 2ω3 + 3ω2 − 6 = 0, с параметрами , и ( = Математическое ожидание Дисперсия Коэффициент асимметрии 3 Коэффициент эксцесса 4 выше [4]. использовались качестве ℎ ( ), = 1,2,3, – их выборочные оценки 3
.
2 ) . 2 ( − 1)= + √ = 1 ∑ , =1 1 − 1
1 ( − 1 ∑( − )2 , =1
=1 ∑
( − )2)2 ( − 1)( − 2) =1( − )3
∑
Третье уравнение не содержит переменных и и имеет вид 3 + 3 2 − (4 + 2)= 0. Если 2 > 0, уравнение имеет единственное решение, большее 1, которое вычисляется по формуле = 1 + ( √ 3 ( 3 + 4)2 + 3 − √
3 ( 3 + 4)2 − 3 2
2 Оценки для = √ln , = ln и получаются аналитически. то есть L-момент представляет собой линейную комбинацию математических ожиданий порядковых статистик распределения специального
вида. Выборочный L-момент порядка ≤ определяется Эти статистики являются несмещёнными оценками теоретических
L-моментов.
Метод
L-моментов имеет ряд преимуществ по сравнению с «обычным» методом моментов:
L-моменты
однозначно определяют параметры, устойчивы к выбросам в данных, а при малых размерах выборки зачастую дают более качественные оценки, чем
метод максимального правдоподобия [9].
,
2
где erf – функция ошибок. Для этой системы можно
найти приближённое решение [
√(8/3)Φ−1 (1 + 3/ 2), 0,999281 − 0,006118 3 + 0,000127 5, 2 ln( erf( )) −
2 1 − exp( + 2 2 2 2 2 , ). 5 Метод минимизации расстояния привлекательных свойств оценок
минимального расстояния является их робастность, то
есть
устойчивость к возмущениям в данных [
Применительно к задаче оценки параметров 3LN распределения в работе [6] отмечалось, что методы минимизации расстояния, как правило, оказываются предпочтительнее других методов: они дают более точные оценки параметров, чем другие методы, в частности, метод максимального правдоподобия, и они не страдают от проблем со
сходимостью оптимизационной процедуры.
Несмотря на
эти положительные свойства, до нас никто подробно не применение методов
минимизации к задаче оценки параметров
3LN исследовал расстояния распределения. 6 Модельные и реальные данные
Ниже нам предстоит настраивать и сравнивать отобранные методы
оценивания параметров. Для этого мы использовали модельные и
реальные данные из рассматриваемой предметной области.
Таблица 2 Параметры модельных распределений 3 1 3 2 10 3 3 16 3 4 10 2 5 10 4 6 10
3 7 Сравнение методов оценки параметров
С целью сравнения описанных выше методов оценки параметров распределения мы провели Колмогорова–Смирнова и, наконец, ММР Крамера–фон Мизеса. 3. Следует отметить, что, хотя метод моментов и метод L-моментов уступают ММП, они всё же дают оценки очень высокой точности и при этом работают на порядок быстрее ММП. Поскольку для моделирования задержек предлагается использовать смесь 3LN распределений, метод L-моментов может быть использован в качестве промежуточного шага в задаче разделения смеси с целью ускорения работы. 8 Запуск на реальных данных
Мы провели несколько запусков рассмотренных выше методов оценки параметров на реальных данных о задержках в коммуникационной среде суперкомпьютера BlueGene/P. Поскольку для реальных данных на данном этапе работы не представляется возможным ввести объективный численный критерий качества, нашей основной целью было визуальное наблюдение полученных функций плотности. Результат можно видеть на рис. 2. Видно, что рассмотренные методы применимы в условиях реальных данных, и полученные распределения хорошо описывают картину задержек. 9 Заключение
В работе обоснована потребность в построении стохастической модели задержек. На основании анализа смежной предметной области (локальные сети и интернет), а также особенностей, присущих коммуникационным средам, предложена стохастическая модель задержек – смесь 3LN распределений. Поскольку задача параметрического восстановления даже одного компонента смеси оказалась нетривиальной, мы провели обзор существующих методов, а также предложили ранее не применявшийся методы минимизации расстояния. Проведённый нами анализ методов на модельных данных показал, что ММП даёт оценки наибольшей точности, однако метод L-моментов даёт хорошие оценки и при этом работает на порядок быстрее.
В дальнейшем результаты работы предполагается использовать для решения задачи разделения смеси 3LN распределений с целью построения точной и при этом компактной модели задержек для использования в задачах динамического планирования выполнения и диагностики кластера. Благодарности
Работа выполнена при частичной поддержке РФФИ, проекты 15-07-09214, 16-57-45054, 16-0100196. Рисунок 2 Работа методов оценки параметров на реальных данных о задержках для суперкомпьютера BlueGene/P. Линиями показаны восстановленные плотности распределений, светлая столбчатая диаграмма на фоне показывает реальные данные Литература [4] Cohen, A., Whitten, B.: Parameter Estimation in Statistics. J. of the Royal Statistical Society. Series B Reliability and Life Span Models. Marcel Dekker, (Methodological), 52 (1), pp. 105-124 (1990) New York (1988) [10] Karakaş, M.: Determination of Network Delay [5] Corlett, A., Pullin, D., Sargood, S.: Statistics of One- Distribution over the Internet. Citeseer (2003) way Internet Packet Delays. 53rd IETF (2002) [11] Mukherjee, A.: On the Dynamics and Significance of [6] Gorelov, A., Maysuradze, A. Salnikov, A.: Delay Low Frequency Components of Internet Load.
Structure Mining in Computing Cluster. CEUR Technical Reports (CIS), 300 p. (1992) Workshop Proceedings, 1482. Aachen: M. Jeusfeld [12] Salnikov, A.: Parus: A Parallel Programming c/o Redaktion Sun SITE, Informatik V, RWTH Framework for Heterogeneous Multiprocessor Aachen Germany Germany, pp. 546-551 (2015) Systems. Lecture Notes in Computer Science, 4192, [7] Harter, H., Moore, A.: Local-maximum-likelihood pp. 408-409 (2006)
Estimation of the Parameters of Three-parameter [13] Salnikov, A., Andreev, D., Lebedev, R.: Toolkit for Lognormal Populations from Complete and Censored Analyzing the Communication Environment Samples. J. of the American Statistical Association, Characteristics of a Computational Cluster based on 61 (315), pp. 842-851 (1966) MPI Standard Functions. Moscow University [8] Hill, B.: The Three-parameter Lognormal Computational Mathematics and Cybernetics, 36 (1), Distribution and Bayesian Analysis of a Point-source pp. 41-49 (2012) Epidemic. J. of the American Statistical Association, [14] Кобзарь, А.И.: Прикладная математическая 58 (301), pp. 72-84 (1963) статистика. М.: Физматлит (2006) [9] Hosking, J.: L-Moments: Analysis and Estimation of
Distributions Using Linear Combinations of Order