Предлагается схема сбора и анализа задержек пересылки данных от одного процесса программной модели MPI к другому. Предлагаемый подход абстрагируется от конкретной реализации сетевого взаимодействия между узлами вычислительного кластера, он опирается на специальные программные системы, собирающие данные о коммуникационной среде. Предложена адекватная информационная модель задержек и специальный способ её настройки. Показано, как использовать эту модель в задачах диагностики коммуникационной среды вычислительного кластера. Все этапы предлагаемой схемы проиллюстрированы на реальных данных о задержках, собранных на суперкомпьютерных системах МГУ имени М. В. Ломоносова.
marks) являются некоторые стандартные числовые показатели (статистики) полученной в ходе тестов выборки задержек. Например, на основании выборки задержек передачи сообщений фиксированной длины из одного узла в другой узел вычисляется эжмпирическое среднее, медиана, стандартное отклонение, максимум и минимум. При этом выбор вычисляемых статистик не основывается на свойствах и природе описываемых распределений, а значит, их набор, возможно, не является удачным описанием нужных распределений. Соответственно, в данной работе рассматривается проблема построения модели задержек при фиксированных контролируемых пользователем параметрах: длине сообщения, узлеотправителе и узле-получателе. Такая модель должна по компактности соответствовать набору числовых характеристик, а по информативности— хранению выборки задержек.
На основе модели задержек предложен метод диагностики вычислительного кластера на основании коммуникационных свойств задержек. Все предложенные методы будут проиллюстрированы реальными задержками сообщений в суперкомпьютерных системах МГУ им. М. В. Ломоносова. В целом, исследование проводится с целью обеспечить системы динамического планирования информацией о задержках. Метод агрегирования отдельных конкретных задержек для повышения эффективности их использования уже разработан и реализован, однако в данной работе из-за ограничений по размеру не рассматривается. 2. Трёхмерное аналитическое пространство задержек Опишем общую модель вычислительной системы, используя терминологию по [8]. Класс систем со множественным потоком команд и множественным потоком данных (MIMD) предполагает, что в вычислительной системе есть несколько устройств обработки команд (процессоров), объединённых в единый комплекс и работающих каждое со своим потоком команд и данных. Вычислительные системы класса MIMD по организации памяти делятся на два подкласса: с общей памятью и с распределённой памятью. В системах второго подкласса память (в смысле адресного пространства) некоторым образом распределена между процессорами системы. Таким образом, все процессоры вычислительной системы с распределённой памятью можно разбить на группы процессоров, работающих в одном адресном пространстве. Такие группы называются вычислительными узлами. Для обмена информацией узлы объединяются друг с другом некоторой коммуникационной средой. Процессоры имеют доступ к памяти только своего узла, и получение информации с других узлов возможно только через коммуникационную среду данной системы. Если рассматривать узлы как вершины, а соединения в рамках коммуникационной среды между ними как рёбра, мы получим коммуникационную сеть вычислительной системы. Вычислительный кластер— объединённый коммуникационной сетью набор узлов, выполняющий вычисления и представляемый пользователю как единая система.
На каждом узле вычислительного кластера операционная система управляет работой
процессов. Процесс— это такой контейнер для ресурсов (адресное пространство, стек и т. д.),
который включает хотя бы один поток команд. С точки зрения адресного пространства
процесс не может выйти за рамки своего узла. При распараллеливании задачи для систем с
распределённой памятью она разбивается на несколько подзадач, выполняющихся в виде
процессов на отдельных узлах. Необходима передача данных между процессами.
Существует много программных интерфейсов для коммуникации процессов, самая распространённая
из таких технологий — MPI [
MPI рассматривает все коммуникации между процессами на узлах как сообщения некоторой структуры. В нашей работе мы не будем исследовать влияние содержания MPIсообщений на их передачу через коммуникационную сеть. Будем варьировать только размер сообщений, процесс-отправитель и процесс-получатель. Таким образом, для нас сообщение— это последовательность произвольных байтов определённой длины с определённым узлом-отправителем и определённым узлом-получателем 1. Получается, что каждое сообщение характеризуется тремя параметрами, которые в анализе данных принято называть измерениями. Таким образом, вводится трёхмерное аналитическое пространство. В каждой ячейке этого пространства хранится и анализируется информация о задержках передачи сообщений с фиксированным набором значений параметров.
В данном исследовании сначала будет предложена модель задержек для одного элемента аналитического пространства. Агрегирование элементов аналитического пространства (понижение его размерности, кластеризация) не описывается в данной публикации. когда оно было проведено, оказалось, что число таких кластеров для реальных систем составляет единицы, т. е. удаётся информацию о задержках представить компактно. 3. Модель задержек
Задержка передачи сообщения в коммуникационной сети — это интервал времени с
момента принятия заявки на отправку сообщения узлом-отправителем до момента полного
получения сообщения узлом-получателем. В конкретных вычислительных системах с
помощью специальных программных продуктов можно измерять задержки при фиксированных
контролируемых параметрах. В нашем исследовании сбор исходных данных о задержках
производился с помощью модифицированной программной системы Network Test из пакета
Parus [
В результате работы системы тестирования в каждой ячейке трёхмерного аналитического пространства мы получаем некоторую выборку задержек. В данной разделе нашей задачей является построение удачного описания набора задержек независимо в каждой ячейке аналитического пространства, то есть при фиксированных контролируемых параметрах сообщения. Разумеется, задержки зависят не только от контролируемых нами параметров сообщения, но и от многих других характеристик состояния сети. Будем считать, что в каждой ячейке аналитического пространства задержка является случайной величиной. Тогда для стохастического моделирования задержки требуется выбрать семейство распределений и оценить параметры распределения по выборке.
В некоторых работах уже предпринимались попытки создания моделей задержек при
передаче информации. В [
Изучение собранных нами данных позволяет заметить некоторые особенности изучаемых задержек. Во-первых, «мультимодальность» распределений задержек: на крупномасштабных гистограммах можно визуально выделить от одного до трёх унимодальных сгущений («горбов»). Во-вторых, «атомарность» распределений задержек: большинство задержек имеют значения из небольшого множества значений. Иными словами, задержки разбиваются на довольно большие группы равных между собой. Например, для суперкомпьютера Blue Gene/P в выборке получается 6% уникальных значений. Однако следует от1Напомним, что в теоретической части под узлом мы понимаем узел сети передачи сообщений. Для MPI это процесс. Таблица 1: Показатели качества работы стандартного и предложенного методов на одном наборе данных. Предложенный метод по всем показателям превосходит стандартный. Суперкомпьютер Blue Gene/P.
стандартный
минимизация алгоритм расстояния Время работы, с, меньше — лучше Правдоподобие (для станд.), больше — лучше Расстояние (для предл.), меньше — лучше метить нерегулярность интервалов между уникальными значениями задержек, т. е. атомы распределения не получается объяснить дискретностью времени в системе. В-третьих, имеются выбросы, отстоящие далеко от сгущений в обе стороны.
Из анализа данных, подкреплённого существующими публикациями, получилось, что распределение задержек в ячейке аналитического пространства в крупном масштабе допустимо описывать смесью трёхпараметрических логнормальных распределений. Другие смеси, например смесь нормальных распределений, хуже согласуются с наблюдениями.
Серьёзным теоретическим вызовом оказалась разработка метода оценки параметров
такой смеси (метода разделения). В [
Blue Gene/P
Regatta Монотонность 4. Анализ задержек на маршрутах
Пусть ts,a\rightaow b — задержка передачи сообщения длины s от узла a узлу b. Основываясь на интерпретации задержек, логично потребовать для качественно настроенной коммуникационной среды выполнения следующих трёх условий.
1. ts1,a\rightaow b \geq ts2,a\rightaow b при s1 \geq s2 (свойство монотонности) — длинное сообщение идёт не быстрее короткого; 2. ts,a\rightaow b \leq ts,a\rightaow c + ts,c\rightaow b (неравенство треугольника) — лучше посылать сообщение сразу в конечный пункт, чем явно указывать промежуточные пункты; 3. ts1+s2,a\rightaow b \leq ts1,a\rightaow b + ts2,a\rightaow b (свойство неделимости) — лучше посылать сообщение целиком, чем явно разбивать на части.
Эти свойства можно назвать обобщёнными метрическими требованиями. Напомним, что речь идёт о сравнении случайных величин, т. е. о стохастическом доминировании. Показано, что все три рассматриваемые свойства независимы.
Провести тестирование указанных требований только по числовым показателям эмпирических распределений не получается, посколько требования содержат арифметические операции, в статистике известно, для таких ситуаций мощных критериев нет. Сравним результаты тестирование по большой выборке и по предложенному компактному представлению. Результаты диагностики вычислительных систем Regatta, BlueGene/P и Ломоносов, установленных в МГУ имени М. В. Ломоносова, показаны в табл. 2. Видно, что системы работают не идеально. Результаты сравнения методов диагностики представлены в табл. 3. Видно, что компактное представление даёт результаты, практически неотличимые от результатов на богатом представлении. 5. Заключение
Предложена схема сбора и анализа задержек передачи сообщений в коммуникационной среде вычислительного кластера. Предложена вероятностная модель задержек и способ её настройки, что позволяет компактно описать взаимодействие между узлами. Предложен метод диагностики коммуникационной среды. Показано, что предложенное описание задержек позволяет решать указанные задачи предметной области с достаточным качеством. Реализованы система сбора информации и система анализа собранной информации. Рассматриваемые методы прошли апробацию на реальных данных с суперкомпьютерных систем МГУ имени М. В. Ломоносова. Оказалось, что для реальных систем не всегда выполняются естественные требования к задержкам. Литература Delay structure mining in computing cluster Alexey Gorelov, Archil Maysuradze and Alexey Salnikov Keywords: communication environment of computing cluster, MPI programming model, message passing delays, information model of delays, communication environment diagnostics, delay data aggregation We propose a new scheme for the collection and analysis of message passing delays from one MPI process to another. The proposed approach is abstracted from a specific implementation of network interaction between computing cluster nodes. It is argued that it is possible to collect data with special software systems and build adequate information model of delays. It is shown how to use this model in the communication environment diagnostics and the dynamic scheduling problems. All stages of the proposed scheme are illustrated with real data collected at Lomonosov Moscow State University supercomputer systems.