Симулятор вычислительного кластера и его управляющей системы, используемый для исследования алгоритмов планирования задач

УДК 519.687

СИМУЛЯТОР ВЫЧИСЛИТЕЛЬНОГО КЛАСТЕРА И ЕГО УПРАВЛЯЮЩЕЙ СИСТЕМЫ, ИСПОЛЬЗУЕМЫЙ ДЛЯ ИССЛЕДОВАНИЯ АЛГОРИТМОВ ПЛАНИРОВАНИЯ ЗАДАЧ

17. if. Полежаев

SIMULATOR OF COMPUTER CLUSTER AND ITS MANAGEMENT SYSTEM USED FOR RESEARCH OF JOB SCHEDULING ALGORITHMS

P.N. Polezhaev

В данной работе описывается симулятор вычислительного кластера и его управляющей системы, учитывающий его топологию, коммуникационные задержки при передаче данных, а также многопроцессорность вычислительных узлов. Он применяется для исследования алгоритмов планирования параллельных задач на вычислительном кластере. Разработана имитационная схема и модель кластера, модель его вычислительной загрузки, приводятся исследуемые алгоритмы планирования, а также описывается система критериев и метрик их сравнения.

Ключевые слова: симулятор вычислительного кластера и его управляющей системы, планирование задач, высокопроизводительные вычисления, имитационное моделирование

In this work the simulator of computer cluster and its management system which considers its topology, communication latency in data transmition and multiprocessor nodes is described. It is used for investigation of parallel jobs scheduling algorithms on computer cluster. The simulating scheme and model of cluster, its computational load model were developed, job scheduling algorithms were presented, and also the system of criteria and metrics for their comparison is described.

Keywords: a simulator of computer cluster and its management system, jobs scheduling, high performance computings, a simulation modeling

Введение

В настоящее время весьма актуальной является проблема эффективного планирования параллельных задач, поступающих в очередь управляющей системы вычислительного кластера, т.к. современные алгоритмы планирования не обеспечивают должного качества составляемых расписаний запуска задач. Весьма часто возникает ситуация, при которой в расписании остается значительное число окон, в то время, когда в очереди имеется большое количество ожидающих своего исполнения задач. Это приводит к снижению производительности всей вычислительной системы.

Другим существенным недостатком современных управляющих систем вычислительного кластера является использование алгоритмов планирования, не учитывающих топологию при размещении процессов задач на вычислительных узлах, а также их многопроцессорность. Учет данных факторов позволит увеличить эффективность работы алгоритмов планиров ания.

Рис. 1. Имитационная схема управляющей системы вычислительного кластера

В связи с этим возникает необходимость исследования существующих алгоритмов планирования и разработка их новых более эффективных вариантов. Для этой цели в настоящей работе создается симулятор вычислительного кластера и его управляющей системы, учитывающий ее топологию, коммуникационные задержки при передаче данных, а также многопроцессорность вычислительных узлов.

Использование симулятора для исследования алгоритмов планирования перед применением реальной управляющей системы, исполняющейся на настоящем кластере, имеет ряд преимуществ. Во-первых, имеется возможность обеспечения контролируемой вычислительной среды - не надо учитывать возможные проблемы, связанные с необходимостью обеспечения отказоустойчивости или безопасности. Во-вторых, при использовании симулятора обеспечивается гибкость и простота модификации аппаратной конфигурации и режимов работы вычислительного кластера. И, в-третьих, в случае применения реального кластера и управляющей системы имела бы место проблема формирования потоков реальных параллельных задач, отвечающих заданным характеристикам, что, напротив, делается очень просто при использовании имитационного моделирования.

1. Имитационная схема и модель вычислительного кластера

Имитационная схема управляющей системы вычислительного кластера приведена на рис. 1. Источник I генерирует поток параллельных задач, отправляемых пользователями в очередь <3 управляющего узла ро. Канал 8 представляет собой планировщик, который в

соответствии с заложенным в него алгоритмом осуществляет извлечение задач из очереди Q и назначение их на свободные вычислительные ядра подходящих по конфигурации узлов.

Множество Р = {pi,p2,    iPn} содержит все вычислительные узлы кластера, связанные с выделенным узлом Ро с помощью отдельной управляющей сети. Пусть Xj = {Хг,1, Хг,2,   , Xifii) ~ множество вычислительных ядер узла pi- Они могут относиться как к отдельным процессорам узла (по одному ядру на каждом), так и к нескольким многоядерным процессорам. С целью упрощения модели они рассматриваются, как единое множество Хг. Обозначим X = X¿ — множество вычислительных ядер всех узлов кластера.

Конфигурация узлов вычислительного кластера и соединяющей их высокопроизводительной сети может быть описана с помощью следующего взвешенного ориентированного графа:

GT =

где К = {к\, /гг-... ; kz) - множество коммутаторов, Е - множество направленных сетевых связей между ними, b: Е —> Z+ U {о} - отображение, характеризующее пропускную способность каждой сетевой связи в байтах в секунду. Функции с, т, d: Р Z+ определяют для каждого вычислительного узла pi соответственно количество его вычислительных ядер с(рг) = Ci, объемы оперативной m(pi) = Mi и дисковой памяти d,{p.¡) = Z?¿ в килобайтах. Отображение s: Р —> R+ для узла задает относительную производительность s(pi) = каждого его вычислительного ядра, которая определяет, во сколько раз ядра данного узла работают быстрее вычислительных ядер самого непроизводительного узла кластера.

Заметим, что орграф (1) позволяет моделировать статические и динамические сети с полнодуплексными и полудуплексными связями. Настоящая модель также позволяет рассматривать однородные и неоднородные вычислительные системы, как по составу вычислительных узлов, так и по конфигурации высокопроизводительной сети. В рамках проводимого исследования будут рассматриваться только однородные вычислительные сети с полнодуплексными связями.

Статические параметры C¿, Мг, D, и 8г описывают конфигурацию вычислительного узла Pi, а динамические параметры характеризуют его состояние в произвольный момент времени t G [0;+оо): u¿(í) - загруженность вычислительных ядер, m¿(í) и di(t) - объемы доступной оперативной и дисковой памяти.

Имитационная схема вычислительного узла приведена на рис. 2. соединен с другими узлами и коммутаторами вычислительной сети с помощью дуплексных связей. Все входящие пакеты, а также пакеты сообщений, генерируемых процессами, выполняющимися на вычислительных ядрах, сначала поступают в очередь Qinp.i, а затем маршрутизируются каналом обслуживания R{. Если соответствующий пакет предназначен для локального вычислительного ядра, то он передается ему непосредственно, иначе - помещается в одну из очередей Qout.i,ii Qout.i,2i  • • i Qout.i,rii соответствующую выбранной алгоритмом маршрутизации исходящей связи. Предполагается использование алгоритмов статической и динамической маршрутизации, характерных для конкретных топологий вычислительной системы, в том числе алгоритмы кратчайших коммуникационных путей и покоординатной маршрутизации.

При выполнении маршрутизации каналом 11г моделируется временная задержка величиной Irouting Заметим, если два процесса одной задачи выполняются на соседних ядрах узла, то обмен пакетами между ними также осуществляется через очередь Qinp.i и канал Ri.

Имитационная схема коммутатора, приведенная на рис. 3, представляет собой урезанный вариант имитационной схемы узла. Отличие только в том, что коммутатор не может выполнять вычисления, и поэтому у него отсутствуют вычислительные ядра.

От планировщика

Вычислительный узел р.

Рис. 2. Имитационная схема вычислительного узла Рі

Коммутатор

сб

Ч

й

Р-

О

£

£

О

и

к

Е-1

&

Рис. 3. Имитационная схема коммутатора кі

К другим узлам и коммутаторам

Г 1 Е„ Г 1

Л А

/ н—К )—1* \

Ел

\ а— м—/

I______1 I_______I

Рис. 4. Схема работы дуплексной связи Ь

Обозначим в качестве И = Р{)К множество всех сетевых устройств системы. На рис. 4 приведена схема работы дуплексной связи = {Е^,Е^}, соединяющей сетевые устройства (¿¡- € К и ^ £ Д. Каналы обслуживания Ег] и Е]г добавляют к времени передачи пакета задержку величиной Ь(Е^) = Ь(Е

Настоящая модель вычислительной системы предполагает использование принципа коммутации пакетов при передаче данных. Пусть д задает стандартный фиксированный размер одного пакета, а к < д - размер его заголовочной части, тогда для передачи сообщения размера д потребуется р

пакетов.

д-Н

Время передачи сообщения от сетевого устройства ¿¿0 к (11н вдоль пути а = (с?г0, С?г1 , . . . , ¿¿д) может быть вычислено по формуле:

Я. 1 /

р) = 'у 'у 7 / г-1 Г Н : Т7т? Т ^гоиНпд ’

ЫЕи ) тш ЫЕи й. )

к=О ' а‘гка'-к + 1> к=0 д_х ' гк гк-\-1

Заметим, данная формула не учитывает возможные задержки, связанные с сетевой конкуренцией пакетов.

Настоящая работа предполагает проведение исследования алгоритмов планирования параллельных задач для случаев однородных и неоднородных вычислительных узлов, связанных гомогенной сетью. Рассматриваются следующие топологии современных кластерных вычислительных систем: двухуровневые толстые деревья, 21) и 31) торы, А;-арные п-кубы, &-арные п-деревья и звезды с единственным коммутатором в центре. Все они могут быть описаны с помощью ориентированного графа (1).

2. Модель вычислительной загрузки кластера

Вычислительная загрузка кластера формируется потоком задач 3 = {3\,Згп). помещаемых пользователями в очередь его управляющей системы. Каждая задача представляет собой параллельную неинтерактивную программу, способную работать в пакетном режиме. Ее процессы запускаются планировщиком одновременно на всех выделенных вычислительных ядрах, во время работы они обмениваются сообщениями между собой. Ресурсы, выделенные задаче, освобождаются при завершении всех ее процессов.

Каждая задача 3$ характеризуется следующим набором параметров:

¿з =

где nj .количество необходимых вычислительных ядер, тг? и (1гу - соответственно объе-

мы оперативной и дисковой памяти в килобайтах, запрашиваемые для исполнения каждого

процесса задачи. Величина ^ задает оценку пользователя в секундах времени выполнения программы на узлах с единичной относительной производительностью. Параметр определяет время поступления задачи в очередь, а Tj € (0; Ц] - время, затрачиваемое задачей только на вычисления (без сетевых коммуникаций) при условии единичной относительной производительности всех назначенных ей вычислительных узлов. Множество СРу задает набор коммуникационных паттернов задачи

Следующая формула позволяет вычислить tj - оценку времени выполнения задачи с учетом производительности выделенных ей планировщиком вычислительных узлов:

где Ij - множество номеров узлов, ядра которых были отданы задаче. Аналогичная формула применяется для корректировки значения параметра Tj.

В рамках данной модели предполагается, что пользователь, делая оценку времени выполнения задачи, возможно, допускает ошибку, переоценивая ее по сравнению с реальным временем выполнения. Противоположный случай ошибок не рассматривается, т.к. управляющая система будет принудительно завершать задачи, превысившие лимит выделенного им времени.

Структура программы каждой параллельной задачи Jj может быть представлена следующей SPMD-моделью:

Process и:

for г = 1 to qj do

Выполнение каждого процесса параллельной задачи представляет собой чередование фаз коммуникации и вычислений.

Коммуникационная часть каждой итерации может быть описана с помощью коммуникационного паттерна - ориентированного взвешенного графа следующего вида:

где П? = {7гх, 7Г2,..., 7ГП} - множество процессов задачи, ру : П? х П? —> и{0} - функ-

ция, определяющая вес каждой дуги, равный размеру в пакетах передаваемого сообщения. Рц(и,ь) определяет количество пакетов сообщения, передаваемого от процесса и к процессу V на %-ж итерации ЭРМБ.

Тогда С'Р] = {CPlj,CP2j,..  ,СРд^} - множество всех коммуникационных паттернов задачи .

Пусть рге<1ц{и) = {у € 11^ : р^(у,и) > 0} - множество предшественников процесса и в орграфе (5), виссц{и) = {у 6 П? : рг](и, у) > 0} - множество его последователей. Выполнение фазы СоттишсаМоп(г, ]) для каждого процесса и заключается в том, что сначала происходит неблокируемая рассылка сообщений всем процессам множества зисс^(и), а затем выполняется блокируемый прием всех сообщений от процессов ргейц (и).

Можно выделить два основных способа задания множества СР3: случайная генерация и моделирование реальных программ, например, эталонных тестов, реализации быстрого

{

Communication^, j); Computation (г, j);

}

СРц — (П^iPij)-,

преобразования Фурье, алгоритма параллельного умножения матриц и др. Типичные коммуникационные паттерны, встречаемые в научной литературе [1, 2]: Random, Pairs, Ring, One-to-all и All-to-all.

Заметим, что в рамках настоящей модели рассматриваются только коммуникации вида «точка-точка». Моделировать коллективные операции достаточно сложно, т.к. способ их выполнения в виде совокупности точечных операций зависит от нескольких факторов: используемых алгоритмов, характеристик вычислительной системы и передаваемых сообщений. В частности, коллективные операции MPI по-разному реализованы в библиотеках разных производителей, а также в разных версиях библиотеки одного производителя. В будущем планируется расширение данной модели за счет учета коллективных операций.

Пусть функция jj : II? —> Р позволяет определить для каждого процесса задачи J? вычислительный узел, на ядро которого он был назначен планировщиком. Для простоты положим, что каждый процесс тратит одинаковое время на выполнение вычислительной части каждой итерации SPMD-модели задачи. Тогда время выполнения вычислительной фазы Computation^, j) процессом и можно вычислить по формуле:

7~ ‘

Tcomp.ij

qjS

Пусть Тсоттщ(и) - время выполнения коммуникационной фазы Communication^, j) процессом и задачи J3, тогда реальное время выполнения данной задачи Т3 может быть вычислено по формуле:

Ч] Чз

Tj — мах ^^j

liÇiii îtÇll7 5 \ ^{UI )

J г=1 г=1 4

Величина Tcomm.ij(u) зависит от сетевой конкуренции и от физического расположения процессов на вычислительных узлах, ее значение может быть вычислено в процессе симуляции работы вычислительного кластера и его управляющей системы. Заметим, что в рамках данной модели мы, в силу незначительности, пренебрегаем временем, которое тратится на разбиение сообщения на пакеты и его сборку из них.

Симуляция работы вычислительного кластера и его управляющей системы предполагает формирование потока задач. Все описанные выше количественные параметры генерируются на основе определенных законов распределений случайных величин, подобранных в результате анализа реальных трасс, собираемых на кластерных вычислительных системах (см. таблицу). Более подробную информацию можно найти в статье [3].

Таблица

Законы распределений параметров модели

Параметр Используемый закон распределения

log rij двухэтапное равномерное распределение с выделением классов последовательных и 2^-задач

log Tj гипер-гамма распределение, параметр р которого линейно зависит от по-

ь равномернее распределение на отрезке \fj\2fj]

a3+l ~ a] экспоненциальное распределение

mr3, dr3 равномерное распределение

Pij(u,v) экспоненциальное распределение для всех дуг, существующих в СРгз

3. Алгоритм работы симулятора

В основе симулятора вычислительного кластера и его управляющей системы лежит алгоритм моделирования по принципу особых состояний.

В рамках рассматриваемой модели выделены следующие особые состояния (события):

1. Поступление новой задачи в очередь.

2. Окончание передачи пакета по сетевой связи.

3. Окончание маршрутизации пакета на сетевом устройстве.

4. Окончание вычислительной фазы процесса задачи.

5. Запуск спланированной задачи.

Для работы алгоритма моделирования по принципу особых состояний используется очередь Qevent, содержащая события перечисленных выше типов. Они сортируются по неубыванию времени наступления, а при равных значениях времени - в порядке приоритетности событий согласно данному списку. Это необходимо во избежание возможных конфликтов.

Обобщенная блоксхема работы алгоритма моделирования приведена на рис. 5. После

Инициализация симулятора. Поместить в Q event события прибытия всех задач потока

Нет

Извлечь событие е из Ое, Установить модельное время согласно событию е

Вычислить метрики

Реакция на Реакция на

событие ... событие

1-го типа 5-го типа

Обновить значения вычисляемых метрик

Рис. 5. Обобщенный алгоритм работы симулятора ввода параметров модели выполняется инициализация симулятора. Затем, пока очередь

Qevent не пуста, происходит извлечение очередного события и его обработка, в процессе которой в Qevent могут добавляться новые события. Например, при обработке события окончания передачи пакета по сетевой связи может создаваться событие окончания маршрутизации этого пакета на сетевом устройстве-получателе.

При наступлении событий поступления новой задачи или окончания вычислительной фазы процесса задачи происходит запуск алгоритма планирования. Значения количественных метрик обновляются в конце каждой итерации цикла моделирования и окончательно вычисляются по его завершению.

4. Система критериев и метрик сравнения алгоритмов планирования

С целью учета всех аспектов эффективности работы алгоритмов планирования задач для кластерных вычислительных систем была построена система критериев и метрик их сравнения. Она включает следующие критерии:

1. Производительность расписаний. Содержит метрики: средняя загруженность вычислительных ядер узлов кластера Ucores, потеря производительности кластера CL, максимальное время завершения задачи Стах, среднее время ожидания задач в очереди twait и среднее ограниченное замедление задач snm. Метрики Ucores, CL vi Стах характеризуют непосредственно производительность расписания, поэтому они более важны для исследования, чем twait и $1гт- которые имеют косвенный характер.

2. Используемость оперативной и дисковой памяти. Включает метрики Ш и d, определяющие соответственно средние загруженности оперативной и дисковой памяти вычислительных узлов. Позволяет выявить процент неиспользованных ресурсов.

3. Сбалансированность загрузки узлов. Определяет метрики Du, Dm и Dd, обозначающие соответственно дисперсии загруженности ядер, оперативной и дисковой памяти вычислительных узлов. Демонстрирует честность алгоритма планирования по отношению к узлам.

4. Гарантированность обслуживания задач. Включает метрики максимального времени ожидания задач в очереди twait.max и максимального ограниченного замедления задач sum.max- Данный критерий имеет особую важность в случае, если кластер используется в рамках системы реального времени.

5. Честность по отношению к задачам. Содержит метрику Dtwan - дисперсию времени ожидания задач в очереди. Позволяет оценить степень равноправности задач с точки зрения алгоритма планирования.

6. Коммуникационный критерий. Включает следующие метрики: среднее суммарное расстояние SD между вычислительными ядрами, назначенными процессам параллельных задач, средняя дисперсность задач JD и среднее время блокировки сообщений MB. Данный критерий позволяет оценить сетевую конкуренцию и степень фрагментации параллельных задач.

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

Анализ алгоритмов планирования по определенному критерию представляет собой сравнение для различных алгоритмов графиков зависимостей метрик этого критерия от величины системной загрузки Ь и выбор лучшего варианта для того или иного случая. При этом используются усредненные значения метрик на 100-1000 различных сгенерированных потоках параллельных задач.

Системная загрузка определяется как отношение суммарного объема вычислительной работы всех задач к объему работы, который кластер может потенциально выполнить (при полной загруженности) за время до появления в управляющей системе последней задачи:

т

Е км

—------------100%.

п

Е вгСг • шах {а,,}

г=1 3=1,т

Данная величина позволяет характеризовать вычислительную насыщенность потока работ, поступающих в управляющую систему вычислительного кластера.

Приведем формулы для вычисления основных метрик критерия производительности. Обозначим в качестве I количество моментов времени, когда в процессе моделирования наступают определенные события, ¿1, ¿2,..., ¿; _ сами моменты времени. При этом гарантируется, что никакие параметры модели и метрики не меняются на интервале времени (¿^,¿^+1) Ук = 1,1 — 1. Будем также считать, что если мы вычисляем параметр модели или метрику в момент времени ¿&, то это выполняется после того, как все события модели, назначенные на это время, были обработаны и выполнен цикл планирования задач. Обозначим ~

множество задач, находящихся в очереди планировщика в момент времени ¿&.

Средняя загруженность вычислительных ядер узлов кластера может быть вычислена по формуле:

71

ис0Гез = • 100%,

п

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

г-1

У) щ(^к)^к-\-1 Ък)$к

щ = к-^Т-1----------------,

{^к+1 %к)$к к= 1

где

5 [1, |««1#0,

10, иначе.

Величина потери производительности вычислительного кластера может быть вычислена следующим образом:

(—1 п

Е Ху 8гРгк^к-\-1 — 1к)&к СЬ = |*=1*=1--------------------100%,

/—1 п

Т, {¿к+1 — *к)сГк ' Ё ¿¿С*

к=1 г=1

где Рц. - количество свободных ядер на узле Рг в момент времени ¿¿, а сг к определяется по формуле:

°к = < г=1

I 0, иначе.

Заметим, что формулы (9) и (12) соответственно не учитывают отсутствие загруженности ресурсов вычислительных узлов и потерю производительности в случае пустой очереди задач планировщика. Это позволяет более объективно судить о состоянии вычислительной системы.

5. Исследуемые алгоритмы планирования

К числу алгоритмов планирования, которые будут экспериментально исследованы с помощью симулятора вычислительного кластера и его управляющей системы, относятся сочетания алгоритмов выбора задачи из очереди Most Processors First Served Scan и Backfill со следующими методами назначения, учитывающими топологию вычислительной системы [1, 2, 4, 5, 6]:

1. Paging, Multiple Buddy System, Adaptive None-Contiguous Allocation, Greedy Available Busy List, Minimizing Contention, Minimizing Contention Incrémental, Manhattan Médian, NEP (для топологий торов);

2. Contiguous Allocation, Quasi-Contiguous Allocation (/:;-арные п-деревья);

3. алгоритмы сортировки узлов (толстые деревья, звезды);

4. модифицированный вариант алгоритма Minimizing Contention (для произвольных топологий) .

А также со следующими методами назначения, не принимающими ее во внимание [3]: First Fit, Best Fit, Fastest Node Fist, Random First.

Заключение

В данной работе описывается симулятор вычислительного кластера, учитывающий его топологию, коммуникационные задержки при передаче данных, а также многопроцессорность вычислительных узлов. Он будет использован для исследования алгоритмов планирования задач.

Приведена имитационная схема и модель кластера, описывается модель его вычислительной загрузки, сформирована система критериев и метрик сравнения алгоритмов планирования. Также определен набор алгоритмов планирования, которые будут исследованы с помощью данного симулятора.

Статья рекомендована к публикации программным комитетом международной научной конференции «Параллельные вычислительные технологии 201СЬ>.

Работа проводилась при финансовой поддержке Федерального агентства по образованию в рамках реализации ФЦП сНаучные и научно-педагогические кадры инновационной России» на 2009-2013 гг, (государственный контракт № П2039).

Литература

1. Moore, S.Q. The Effects of Network Contention on Processor Allocation Stratégies /

S.Q. Moore, M.N. Lionel // Proceedings of the lOth International Parallel Processing

Symposium. - Washington, DC: EEE Computer Society, 1996. - P. 268 - 273.

2. Bani-Mohammad, S. An efficient processor allocation strategy that maintains a high degree

of contiguity among processors in 2D mesh connected multicomputers / S. Bani-Mohammad,

М. Ould-Khaoua, I. Abaneh // Proceedings of ACS/IEEE International Conference on Computer Systems and Applications, AICCSA. - 2007. - P. 934 - 941.

3. Полежаев, П.Н. Исследование алгоритмов планирования параллельных задач для кластерных вычислительных систем с помощью симулятора / Полежаев, П.Н. // Параллельные вычислительные технологии (ПАВТ’2010): тр. междунар. конф. - Челябинск, 2010. - С. 287 - 298.

4. Bender, М.A. Communication-Aware Processor Allocation for Supercomputers / M.A. Bender, D.P. Bunde, E.D. Demaine // Lecture Notes in Computer Science. - 2005.

- V. 3608/2005. - P. 169 - 181.

5. Cheng, C. Improving Performance of Mesh-connected Multicomputers by Reducing Fragmentation / C. Cheng, P. Mohapatra // J. of Parallel and Distributed Computing. -1998. - V. 52(1). - P. 40 - 68.

6. Pascual, J.A. Effects of Topology-Aware Allocation Policies on Scheduling Performance / J.A. Pascual, J. Navaridas, J. Miguel-Alonso // Lecture Notes in Computer Science. - 2009.

- V. 5798/2009. - P. 138 - 156.

Полежаев Петр Николаевич, аспирант, кафедра математического обеспечения информационных систем, Оренбургский государственный университет, peter.polezhaev@mail.ru.

Поступила в редакцию 20 мая 2010 г.