Моделирование задержек передачи информации в вычислительном кластере для мониторинга коммуникационной среды © А.И. Майсурадзе © В.Д. Козлов Московский государственный университет имени М.В. Ломоносова, Москва, Россия maysuradze@cs.msu.ru kozlov2.volodia2@gmail.com Аннотация. Эффективное использование современных вычислительных кластеров опирается не только на характеристики составляющих их узлов, но и на характеристики коммуникационной среды. Чтобы проверять работоспособность коммуникационной среды и динамически планировать расписание заданий, существуют различные подходы. В данной работе рассмотрен подход, опирающийся на предварительный сбор информации о задержках передачи сообщений и их последующий анализ. Такой сбор занимает много времени и порождает большое количество первичной информации. Требуются модели задержек, которые позволяют существенно ускорить сбор данных и сократить объем хранимой информации. В работе предложены такая модель и методы её настройки, которые сочетают высокое качество и скорость. Ключевые слова: вычислительный кластер, задержка передачи сообщений, анализ коммуникационной среды, сбор данных, настройка модели. Modeling Message Passing Delays in a Computer Cluster to Monitor its Network © A. Maysuradze © V. Kozlov Lomonosov Moscow State University Moscow, Russia kozlov2.volodia2@gmail.com maysuradze@cs.msu.ru Abstract. The effective use of a modern computer cluster relies not only on the characteristics of its nodes, but its communication environment as well. There are different approaches to monitor communication environment and dynamically schedule tasks. In the paper, we consider an approach based on the preliminary collection of data on delays of the message passing and their subsequent analysis. This collection takes a lot of time and generates a large amount of raw data. Delay models are required that can significantly speed up data collection and reduce the amount of stored information. We proposes and study such a model and methods of its learning, which combine high quality and speed. Keywords: computer cluster, message passing delay, network analysis, data collection, model learning. 1 Введение Одним из ключевых инструментов разработки параллельных приложений для многопроцессорных Современные распределённые вычислительные систем является библиотечная реализация стандарта системы состоят из тысяч и десятков тысяч MPI (Message Passing Interface). При использовании процессоров. Увеличение числа процессоров ведёт к технологии MPI программа разделяется на процессы, усложнению коммуникационной среды и росту взаимодействующие посредством обмена накладных расходов на обмен информацией между сообщениями. Информация о задержках, вычислительными устройствами. Эффективность современных многопроцессорных систем зависит не возникающих при передаче сообщений, может быть только от характеристик отдельных вычислительных использована для повышения эффективности работы устройств, но и от характеристик коммуникационной вычислительной системы, в частности, решения среды. задач динамического планирования выполнения параллельных программ, а также для диагностики коммуникационной среды. Таким образом, Труды XIX Международной конференции возникает потребность в моделировании задержек. «Аналитика и управление данными в областях с При этом модель должна не только полной, но интенсивным использованием данных» достаточно компактной, чтобы обеспечить хранение (DAMDID/ RCDL’2017), Москва, Россия, 10–13 октября 2017 года 93 и использование в реальном времени информации о распределений. Однако проблемы возникают даже задержках при передаче сообщений для каждой пары при параметрическом восстановлении одного вычислительных узлов. компонента такой смеси. Подробнее об этих проблемах сказано ниже. Работа посвящена разработке и исследованию специализированных методов восстановления трёхпараметрических логнормальных распределений по конечным выборкам задержек передачи информации в коммуникационной среде суперкомпьютера. Статья устроена следующим образом. В разделе 2 введены используемые основные определения Разделы 3, 4 и 5 посвящены обзору существующих методов оценки параметров трёхпараметрического логнормального распределения (метод максимального правдоподобия, метод моментов, метод L-моментов и методы минимизации расстояния). В разделе 6 Рисунок 1 Пример картины задержек при передаче описаны данные, использованные в вычислительном сообщений. Суперкомпьютер BlueGene/P эксперименте (модельные и реальные). Раздел 7 посвящён сравнению методов оценивания Величины задержек зависят от множества параметров, рассмотренных в разделах 3, 4 и 5, на факторов, специфичных для разных вычислительных синтетических и реальных данных. систем и меняющихся со временем, учёт которых при моделировании задержек требует анализа 2 Основные обозначения и определения программного и аппаратного обеспечения на всех Трёхпараметрическое логнормальное уровнях сетевого протокола, что возможно лишь для распределение (3LN распределение) – это абсолютно самых простых архитектур. В связи с этим начали непрерывное одномерное распределение, функция активно развиваться системы MPI-тестирования плотности вероятности которого выражается коммуникационной среды [13]. Поскольку на формулой практике размеры вычислительных кластеров не 𝑝(𝑥; ⁡𝛾, 𝜇, 𝜎) позволяют хранить выборки задержек для всех пар 1 (ln(𝑥 − ⁡𝛾) − ⁡𝜇)2 вычислительных узлов, для описания используются exp (− ) , 𝑥 ≥ 𝛾, = {√2𝜋𝜎(𝑥⁡– ⁡𝛾) 2𝜎 2 некоторые эмпирические статистики, вычисленные по выборкам величин задержек, которые могут не 0, 𝑥 < 𝛾. отражать в полной мере структуры задержек. В Функция распределения 3LN может быть ln(𝑥−⁡𝛾)−⁡𝜇 качестве альтернативы предлагается стохастическая записана в виде 𝐹(𝑥; 𝛾, 𝜇, 𝜎) ⁡ = Φ ( ), где σ модель, в которой неконтролируемые факторы Φ(𝑥) – функция распределения стандартного рассматриваются как скрытые параметры, а нормального закона [4]. Основные моментные задержки – как случайные величины с некоторыми характеристики распределения указаны в таблице 1. распределениями. Такая модель одновременно Набор параметров 𝛾, 𝜇, 𝜎⁡ будем обозначать 𝜃. описывает картину задержек более полно, чем набор Будем обозначать случайную выборку длины 𝑛 𝑋 𝑛 = статистик, и позволяет хранить информацию в (𝑋1 , … , 𝑋𝑛 ), её реализацию – 𝑥 𝑛 ⁡ = ⁡ (𝑥1 , … , 𝑥𝑛 ),⁡ 𝑘-ю сильно сжатом виде – всего несколько чисел – порядковую статистику и её реализацию – 𝑋(𝑘) и 𝑥(𝑘) параметров модели вместо выборки. соответственно. Проведенные ранее исследования задержек в локальных сетях и интернете [5, 10, 11] показали, что 3 Метод максимума правдоподобия и его величины задержек хорошо описываются модификации трёхпараметрическим гамма- или логнормальным распределением. В коммуникационных средах Наиболее популярным подходом к вычислительных кластеров, однако, наблюдаются параметрической оценке плотности распределения следующие особенности [6]: является метод максимального правдоподобия • распределение задержек является (ММП). В качестве меры адекватности многомодальным; распределения 𝐹(∙, 𝜃) данным 𝑥 𝑛 используется • в данных много повторов и мало уникальных функция правдоподобия 𝐿(𝜃) = ⁡𝑝(𝑥 𝑛 ; ⁡𝜃) – значений. совместная плотность вероятности объектов На Рис. 1 приведена картина задержек в выборки. Полагается, что чем больше значение коммуникационной среде суперкомпьютера функции правдоподобия, тем лучше модель BlueGene/P, на которой явно видны указанные описывает данные. Оценки максимального особенности. Исходя из этого, в работе [6] в качестве правдоподобия для многих задач оказываются модели задержек предложено использовать смесь состоятельными, асимптотически нормальными и трёхпараметрических логнормальных асимптотически эффективными. 94 𝑛 Для семейства 3LN распределений логарифм функции правдоподобия имеет вид 1 ln(𝑥𝑖 − 𝛾) − 𝜇(𝛾) 𝑛 𝜆(𝛾) = ∑ (1 + ) = 0. 𝑛 𝑥𝑖 − 𝛾 𝜎 2 (𝛾) ln⁡𝐿(𝜃) = − ln⁡2𝜋 − 𝑛ln⁡𝜎 − ∑ ln⁡(𝑥𝑖 − 𝛾) 𝑖=1 2 𝑛 𝑖=1 4 Общий метод моментов (ln⁡(𝑥𝑖 − 𝛾) − 𝜇)2 При оценке параметров с использованием метода −∑( ), 2𝜎 2 моментов на распределение 𝐹(⋅; 𝜃) накладывается 𝑖=1 последовательность ограничений типа равенства, причём выражение имеет смысл только при 𝛾 < 𝑥(1). образующая систему уравнений вида 𝑔𝑖 (𝜃) = Для неё можно выписать необходимые условия ℎ𝑖 (𝑋 𝑛 ), 𝑖 = 1, 𝑘, где функции 𝑔𝑖 (𝜃) характеризуют экстремума: 𝑛 теоретическое распределение, а ℎ𝑖 (𝑋 𝑛 ) являются их ⎧ ∂ln⁡𝐿 1 ln⁡(𝑥𝑖 − 𝛾) − 𝜇 выборочными оценками, как правило, ⎪ ∂𝛾 = ∑ (1 + ) = 0, несмещёнными или хотя бы асимптотически 𝑥𝑖 − 𝛾 𝜎2 ⎪ 𝑖=1 несмещёнными. ⎪ 𝑛 ⎪ ∂ln⁡𝐿 ln⁡(𝑥𝑖 − 𝛾) − 𝜇 Таблица 1 Основные моменты 3LN распределения = ∑ = 0, с параметрами 𝜸, 𝝁 и 𝝈 (𝜷⁡ = 𝐞𝐱𝐩 𝝁 , 𝝎⁡ = 𝐞𝐱𝐩 𝝈𝟐 ) ⎨ ∂𝜇 𝜎2 Математическое ⎪ 𝑖=1 γ + ⁡β√ω 𝑛 ожидание 𝔼 ⎪ 2 ⎪ ∂ln⁡𝐿 = ∑ 1 (−1 + (ln⁡(𝑥𝑖 − 𝛾) − 𝜇) ) = 0. Дисперсия 𝔻 β2 ω(ω − ⁡1) ⎪ ∂𝜎 𝜎 𝜎 2 ⎩ 𝑖=1 Коэффициент Метод максимального правдоподобия с успехом асимметрии 𝛼3 √ω − ⁡1(ω + ⁡2) используется во многих задачах статистики, однако Коэффициент его применимость для оценки параметров 3LN ω4 + ⁡2ω3 + ⁡3ω2 − ⁡6 эксцесса 𝛼4 распределения оказывается под вопросом. Показано [8], что для любой выборки 𝑥 𝑛 функция Общий метод моментов применялся для оценки правдоподобия 𝐿(𝜃) не ограничена, и существуют параметров 3LN распределения в связи с указанными траектории в пространстве параметров (𝛾, 𝜇, 𝜎), выше проблемами, возникающими при сходящиеся к (𝑥(1) , −∞, +∞), при движении вдоль использовании метода максимума правдоподобия которых 𝐿(𝜃) сходится к +∞, при этом в точке [4]. В качестве функций 𝑔𝑖 (𝜃), 𝑖 = 1,2,3, (𝑥(1) , −∞, +∞) 𝐿(𝜃) принимает значение 0. Таким использовались математическое ожидание, образом, возникает потребность в использовании дисперсия и коэффициент асимметрии (таблица 1), в иных методов оценки параметров 3LN качестве ℎ𝑖 (𝑋 𝑛 ), 𝑖 = 1,2,3, – их выборочные оценки распределения. [4]. Итогом является система уравнений 𝑛 Несмотря на общую неограниченность функции ⎧ 1 ⎪ 𝛾 + 𝛽√𝜔 = ⁡ ∑ 𝑥𝑖 , правдоподобия 𝐿(𝜃), если элементы выборки 𝑛 принимают достаточно много различных значений, ⎪ 𝑖=1 𝑛 «вблизи» истинных значений параметров функция ⎪ 1 2 ∑(𝑥𝑖 − 𝑥)2 , 𝛽 𝜔(𝜔 − 1) = ⁡ правдоподобия имеет локальный максимум [8]. Это 𝑛 − 1 ⎨ 𝑖=1 приводит к идее использования так называемых 𝑛 ⎪ 𝑛 ∑ (𝑥 − 𝑥)3 локальных оценок максимального правдоподобия. В ⎪ (𝑛 − 1)(𝑛 − 2) 𝑖=1 𝑖 работе [7] показано, что такие оценки для 3LN ⎪ √𝜔 − 1(𝜔 + 2) = ⁡ 1 𝑛 3 2 )2 . распределения обладают хорошими ⎩ ( ∑ (𝑥 − 𝑥) 𝑛 − 1 𝑖=1 𝑖 асимптотическими свойствами. Третье уравнение не содержит переменных 𝛾 и 𝛽 Для поиска оценок локального максимума и имеет вид 𝜔3 + 3𝜔2 − (4 + 𝑎2 ) = 0. Если 𝑎2 > 0, предлагается использовать необходимые условия уравнение имеет единственное решение, большее 1, экстремума логарифмической функции которое вычисляется по формуле правдоподобия [3]. Параметры 𝜇 и 𝜎 2 выражаются 2 как функции параметра 𝛾: (𝑎3 + 4)2 + 𝑎3 3 (𝑎3 + 4)2 − 𝑎3 3 1 𝑛 𝜔 = 1 + (√ −√ ) . ⎧ 2 2 ⎪ 𝜇(𝛾) = ∑ ln⁡(𝑥𝑖 − 𝛾) , 𝑛 𝑛 𝑖=1 Оценки для 𝜎 = √ln 𝜔, 𝜇 = ln 𝛽 и 𝛾 получаются ⎨ 1 аналитически. ⎪ 𝜎 2 (𝛾) = ∑(ln⁡(𝑥𝑖 − 𝛾) − 𝜇)2 , В работе [2] для оценки параметров 3LN ⎩ 𝑛 𝑖=1 распределения предложено использовать метод L- после чего оценка параметра 𝛾 получается из моментов. Теоретическим L-моментом порядка 𝑟 для уравнения распределения 𝐹(𝑥) называется величина 95 𝑟−1 𝜃0 ⁡ = argmin ⁡𝑑[𝐹(𝑥; 𝜃), 𝐹𝑛 (𝑥)]. Одним из наиболее 1 𝑟−1 𝜃∈Θ 𝜆𝑟 = ∑(−1)𝑘 ( ) 𝔼𝑋(𝑟−𝑘) , привлекательных свойств оценок минимального 𝑟 𝑘 𝑘=0 расстояния является их робастность, то есть то есть L-момент представляет собой линейную устойчивость к возмущениям в данных [1]. комбинацию математических ожиданий порядковых Применительно к задаче оценки параметров 3LN статистик распределения специального вида. распределения в работе [6] отмечалось, что методы Выборочный L-момент порядка 𝑟 ≤ 𝑛 определяется минимизации расстояния, как правило, оказываются как предпочтительнее других методов: они дают более 𝑟−1 точные оценки параметров, чем другие методы, в 𝑛 −1 1 𝑟−1 частности, метод максимального правдоподобия, и 𝑙𝑟 = ( ) ∑ ⁡ ∑(−1)𝑘 ( )𝑥(𝑖𝑟−𝑘) . они не страдают от проблем со сходимостью 𝑟 𝑟 𝑘 1≤𝑖1 ≤𝑖2 ≤⋯≤𝑖𝑟 ≤𝑛 𝑘=0 оптимизационной процедуры. Несмотря на эти Эти статистики являются несмещёнными оценками положительные свойства, до нас никто подробно не теоретических L-моментов. Метод L-моментов исследовал применение методов минимизации имеет ряд преимуществ по сравнению с «обычным» расстояния к задаче оценки параметров 3LN методом моментов: L-моменты однозначно распределения. определяют параметры, устойчивы к выбросам в В работе рассматриваются расстояния данных, а при малых размерах выборки зачастую Колмогорова – Смирнова, Крамера – фон Мизеса и дают более качественные оценки, чем метод Андерсона – Дарлинга [14]. максимального правдоподобия [9]. Для 3LN распределения можно выписать 6 Модельные и реальные данные следующую систему уравнений [9]: Ниже нам предстоит настраивать и сравнивать ⎧ 𝜎2 отобранные методы оценивания параметров. Для 𝛾 + exp (𝜇 + ) = 𝑙1 , ⎪ 2 этого мы использовали модельные и реальные ⎪ 𝜎 2 𝜎 данные из рассматриваемой предметной области. ⎪ exp (𝜇 + ) erf ( ) = 𝑙2 , 2 2 Таблица 2 Параметры модельных распределений ⎨ 𝜎 𝜃1 𝜃2 𝜃3 𝜃4 𝜃5 𝜃6 𝜃7 ⎪ 2 𝑥 ∫ erf ( ) exp(−𝑥 2 ) 𝑑𝑥 𝛾 3 10 16 10 10 10 10 ⎪ 6 0 √3 𝑙3 ⎪ 𝜎 = , 𝜇 3 3 3 2 4 3 3 ⎩ √ 𝜋 erf (2 ) 𝑙2 𝜎 0.23 0.23 0.23 0.23 0.23 0.1 0.35 где erf – функция ошибок. Для этой системы можно найти приближённое решение [2]: В качестве модельных данных использовались 1 + 𝑙3 /𝑙2 выборки из 3LN распределения с известными 𝑧 = √(8/3)Φ−1 ( ), параметрами 𝜃. По результатам анализа задержек 2 𝜎 ≈ 0,999281𝑧 − 0,006118𝑧 3 + 0,000127𝑧 5 , при передаче сообщений в локальной сети и интернете [10] мы выбрали 7 наборов параметров 𝑙2 𝜎2 𝜇 = ln ( ) − , 𝛾, 𝜇, 𝜎, для каждого из них генерировали несколько erf(𝜎2) 2 выборок. Значения параметров модельных данных 𝜎2 приведены в таблице 2. Поскольку для модельных 𝛾 = 𝑙1 − exp (𝜇 + ) . данных параметры известны, можно сравнивать 2 полученные оценки с истинным значением 5 Метод минимизации расстояния параметра и исследовать их статистические свойства. Следует отметить, однако, что такие В методе минимизации расстояний мерой модельные данные относятся к иной, хотя и смежной соответствия модели данным служит некоторым предметной области и не обладают особенностями образом выбранное расстояние 𝑑[⋅,⋅] между рассматриваемой задачи (см. введение). теоретическим и эмпирическим распределениями Также мы проанализировали работу методов на данных. Полагается, что чем меньше расстояние, тем реальных данных о задержках в коммуникационной лучше модель описывает данные. Для непрерывных сети вычислительной системы BlueGene/P. Эти распределений расстояние обычно берётся между данные отвечают предметной области и имеют функцией распределения модели 𝐹(𝑥; 𝜃) и особенности, указанные в разделе 1. Для сбора эмпирической функцией распределения 𝐹𝑛 (𝑥) = данных использовалась утилита network_test2 1 𝑛 ⁡ ∑𝑛𝑖⁡=⁡1 𝕀[𝑥 > 𝑥(𝑖) ] [1]. Следует отметить, что термин из пакета PARUS [12]. В силу многомодальности «расстояние» используется условно: функционал 𝑑 данные для анализа выделялись из выборки может быть даже несимметричен, обычно от него вручную. требуются только неотрицательность и равенство нулю только в случае равенства распределений. 7 Сравнение методов оценки параметров Оценкой минимального расстояния 𝜃0 ⁡ называется С целью сравнения описанных выше методов оценки параметров распределения мы провели 96 тестирование на модельных данных. Для каждого 𝜃6 0.0084 0.0177 0.0103 набора параметров, указанных в таблице 2, было 𝜃7 0.0020 0.0018 0.0010 сгенерировано по 100 выборок длиной 10000 каждая. Для каждой выборки производилось оценивание Таблица 5 Среднеквадратичная ошибка оценок параметров всеми описанными выше методами. параметра 𝝈 Таким образом, для каждого модельного набора ММП моменты L-моменты параметров и каждого метода оценивания мы 𝜃1 6.80 ⋅ 10−5 11.19 ⋅ 10−5 9.19 ⋅ 10−5 получили по 100 оценок этих параметров. Для 𝜃2 6.43 ⋅ 10−5 11.12 ⋅ 10−5 7.96 ⋅ 10−5 сравнения методов мы использовали следующие 𝜃3 5.22 ⋅ 10−5 9.12 ⋅ 10−5 6.65 ⋅ 10−5 характеристики: 𝜃4 6.55 ⋅ 10−5 13.33 ⋅ 10 −5 9.07 ⋅ 10−5 • среднеквадратичная ошибка для каждого из 𝜃5 7.06 ⋅ 10−5 16.73 ⋅ 10−5 10.47 ⋅ 10−5 1 параметров 𝛾, 𝜇 и 𝜎: ∑𝑛𝑖=1(𝜃𝑖 − ⁡𝜃)2, где 𝑛 – 𝜃6 6.80 ⋅ 10−5 8.10 ⋅ 10−5 7.42 ⋅ 10−5 𝑛 −5 −5 число оценок (𝑛 = 100), 𝜃𝑖 – оценка параметра 𝛾, 𝜃7 6.18 ⋅ 10 23.30 ⋅ 10 10.54 ⋅ 10−5 𝜇 или 𝜎 по выборке, 𝜃 – истинное значение этого ММР К-С К-фон М А-Д параметра; 𝜃1 10.85 ⋅ 10−5 19.81 ⋅ 10−5 11.23 ⋅ 10−5 • среднее время работы метода на выборках (в 𝜃2 10.84 ⋅ 10−5 18.51 ⋅ 10−5 10.50 ⋅ 10−5 секундах). 𝜃3 9.09 ⋅ 10−5 19.50 ⋅ 10−5 9.23 ⋅ 10−5 Результаты тестирования методов на модельных 𝜃4 12.79 ⋅ 10−5 22.43 ⋅ 10−5 11.61 ⋅ 10−5 данных приводятся в таблицах 3–6. Используемые 𝜃5 16.18 ⋅ 10−5 17.52 ⋅ 10−5 10.50 ⋅ 10−5 сокращения: К-С, К-фон М, А-Д – расстояния 𝜃6 7.87 ⋅ 10−5 15.63 ⋅ 10−5 9.46 ⋅ 10−5 Колмогорова – Смирнова, Крамера – фон Мизеса и 𝜃7 26.08 ⋅ 10−5 22.64 ⋅ 10−5 12.05 ⋅ 10−5 Андерсона – Дарлинга. Таблица 6 Среднее время работы методов (в Таблица 3 Среднеквадратичная ошибка оценок секундах) параметра 𝜸 ММП моменты L-моменты ММП моменты L-моменты 𝜃1 0.032 0.002 0.002 𝜃1 0.47 0.83 0.66 𝜃2 0.032 0.002 0.002 𝜃2 0.48 0.86 0.63 𝜃3 0.031 0.002 0.002 𝜃3 0.37 0.69 0.51 𝜃4 0.031 0.002 0.002 𝜃4 0.61 0.13 0.09 𝜃5 0.035 0.002 0.002 𝜃5 3.89 9.10 6.00 𝜃6 0.036 0.002 0.002 𝜃6 2.99 3.58 3.46 𝜃7 0.031 0.002 0.002 𝜃7 0.17 0.76 0.32 ММР К-С К-фон М А-Д ММР К-С К-фон М А-Д 𝜃1 0.416 0.211 0.200 𝜃1 0.85 1.44 0.78 𝜃2 0.375 0.225 0.234 𝜃2 0.88 1.45 0.80 𝜃3 0.359 0.229 0.224 𝜃3 0.70 1.58 0.70 𝜃4 0.411 0.221 0.206 𝜃4 0.13 0.22 0.11 𝜃5 0.392 0.275 0.282 𝜃5 9.33 10.11 6.10 𝜃6 0.422 0.269 0.270 𝜃6 3.58 8.70 4.56 𝜃7 0.426 0.175 0.175 𝜃7 0.78 0.68 0.35 По результатам тестирования методов оценки Таблица 4 Среднеквадратичная ошибка оценок параметров на модельных данных можно сделать параметра 𝝁 следующие выводы: ММП моменты L-моменты 1. Для каждого метода качество оценки 𝜃1 0.0012 0.0021 0.0017 относительно других методов в целом 𝜃2 0.0012 0.0022 0.0016 одинаково для всех параметров. Нет метода, 𝜃3 0.0009 0.0018 0.0013 который давал бы значительно лучшую, чем 𝜃4 0.0012 0.0026 0.0017 у другого метода, оценку одного параметра и при этом серьёзно проигрывал по другому 𝜃5 0.0013 0.0032 0.0020 параметру. Это значит, что можно провести 𝜃6 0.0071 0.0084 0.0080 ранжирование методов, одинаковое для всех 𝜃7 0.0005 0.0021 0.0009 параметров. ММР К-С К-фон М А-Д 2. С точки зрения точности оценки самым 𝜃1 0.0022 0.0036 0.0020 лучшим можно признать метод 𝜃2 0.0022 0.0036 0.0020 максимального правдоподобия. За ним идёт 𝜃3 0.0018 0.0038 0.0018 метод L-моментов, далее – метод моментов 𝜃4 0.0026 0.0042 0.0021 и метод минимизации расстояния 𝜃5 0.0032 0.0035 0.0021 Андерсона-Дарлинга, затем – ММР 97 Колмогорова–Смирнова и, наконец, ММР Крамера–фон Мизеса. 3. Следует отметить, что, хотя метод моментов и метод L-моментов уступают ММП, они всё же дают оценки очень высокой точности и при этом работают на порядок быстрее ММП. Поскольку для моделирования задержек предлагается использовать смесь 3LN распределений, метод L-моментов может быть использован в качестве промежуточного шага в задаче разделения смеси с целью ускорения работы. 8 Запуск на реальных данных Мы провели несколько запусков рассмотренных выше методов оценки параметров на реальных данных о задержках в коммуникационной среде суперкомпьютера BlueGene/P. Поскольку для реальных данных на данном этапе работы не представляется возможным ввести объективный численный критерий качества, нашей основной целью было визуальное наблюдение полученных функций плотности. Результат можно видеть на рис. 2. Видно, что рассмотренные методы применимы в условиях реальных данных, и полученные распределения хорошо описывают картину задержек. 9 Заключение В работе обоснована потребность в построении стохастической модели задержек. На основании анализа смежной предметной области (локальные сети и интернет), а также особенностей, присущих коммуникационным средам, предложена стохастическая модель задержек – смесь 3LN распределений. Поскольку задача параметрического восстановления даже одного компонента смеси оказалась нетривиальной, мы провели обзор существующих методов, а также предложили ранее не применявшийся методы минимизации расстояния. Проведённый нами анализ методов на Рисунок 2 Работа методов оценки параметров на модельных данных показал, что ММП даёт оценки реальных данных о задержках для суперкомпьютера наибольшей точности, однако метод L-моментов BlueGene/P. Линиями показаны восстановленные даёт хорошие оценки и при этом работает на порядок плотности распределений, светлая столбчатая быстрее. диаграмма на фоне показывает реальные данные В дальнейшем результаты работы предполагается использовать для решения задачи разделения смеси Литература 3LN распределений с целью построения точной и [1] Basu, A., Shioya, H., Park, C.: Statistical Inference: при этом компактной модели задержек для использования в задачах динамического the Minimum Distance Approach. CRC Press (2011) планирования выполнения и диагностики кластера. [2] Bílková, D.: Three-parametric Lognormal Distribution and Estimating its Parameters using the Благодарности Method of L-moments. Reprodukce Lidského Kapitálu (2011) Работа выполнена при частичной поддержке РФФИ, проекты 15-07-09214, 16-57-45054, 16-01- [3] Calitz, F.: Maximum Likelihood Estimation of the 00196. Parameters of the three Parameter Lognormal Distribution – a Reconsideration. Australian J. of Statistics, 15 (3), pp. 185-190 (1973) 98 [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 99