Стратегия научно-технологического развития Российской Федерации предусматривает развитие и поддержку функционирования центров коллективного пользования (ЦКП) научно-технологическим оборудованием, к которым относятся суперкомпьютерные научные центры (СКЦ). Одной из устойчивых тенденций развития последних является объединение их вычислительных ресурсов в единую территориально распределенную систему (ТРС) с целью повышения эффективности использования вычислительных ресурсов СКЦ и увеличения значений индикаторных показателей (http:// government.ru/docs/23110/). Активные работы над проектом единой распределенной сети научных суперкомпьютерных центров в настоящее время ведутся в Межведомственном суперкомпьютерном центре РАН [1]. В качестве единицы ресурса, подключаемой к ТРС, в проекте рассматривается вычислительная установка (ВУ), представляющая собой, как правило, отдельный высокопроизводительный вычислительный кластер (суперкомпью- тер). Важно отметить, что обычно в состав ТРС входят ВУ различной вычислительной мощности, объединенные коммуникационными каналами различной пропускной способности.

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

Каждая ВУ из состава ТРС находится под управлением локальной системы управления ресурсами (ЛСУР), в качестве которой могут выступать такие распространенные системы, как PBS [2], SLURM [3], Moab [4], или отечественная Система управления прохождением параллельных заданий (СУППЗ) [5]. Основными функциями ЛСУР являются ведение очереди вычислительных заданий, их планирование, запуск и контроль процесса выполнения на вычислительных ресурсах отдельной ВУ.

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

Различные задания от разных пользователей образуют один или несколько потоков. В каждой ВУ присутствует как минимум один локальный поток заданий, которые допускают обработку только на локальных вычислительных ресурсах и не могут быть переданы на другие ВУ ТРС (рис. 1).

Задания глобального потока, напротив, могут быть переданы для обработки в любую из ВУ ТРС. Управлением на этом уровне занимается глобальная система управления ресурсами (ГСУР). В предшествующих работах авторы остановили выбор на децентрализованной схеме управления, предполагающей отсутствие единого центра управления и планирования вычислительных заданий. Децентрализованное управление основано на совместной согласованной работе коллектива равноправных диспетчеров (рис. 2), располагающихся локально на всех ВУ ТРС. В работе [6] авторы рассмотрели варианты организации глобальной очереди заданий ГСУР и остановили свой выбор на докумен- то-ориентированной распределенной СУБД Elas- ticsearch [7] – логически централизованном хра- нилище информации, обеспечивающим, с одной стороны, симметричный доступ к глобальной очереди от всех диспетчеров ТРС, с другой – надежное распределенное хранение информации в условиях динамически изменяющегося состава ТРС (ВУ могут отключаться или подключаться к ТРС в произвольные моменты времени).

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

Обратим внимание на тот факт, что в условиях абсолютных приоритетов заданий в глобальную очередь имеет смысл помещать задания с высоким приоритетом. В этом случае выбранные диспетчерами задания глобальной очереди, попадая в ЛСУР, должны либо сразу поступать на выполнение, либо занимать места в начале очереди. В такой постановке в качестве основного показателя качества планирования заданий глобальной очереди целесообразно рассматривать среднее время T обработки задания в соответствии с уровнем приоритета [8]. В этом контексте основными задачами, решаемыми авторами, являются исследование и разработка методов и алгоритмов планирования заданий глобальной очереди, обеспечивающих минимальное среднее время обработки высокоприоритетных заданий.

Применение метода английского аукциона при планировании заданий с абсолютными приоритетами в ТРС

Известно, что при планировании вычислительных заданий в грид-средах и ТРС могут быть эф- фективно применены аукционные методы [9, 10]. Обязательным требованием любого аукционного метода является наличие в системе предмета торгов (товара) и нескольких ролей: продавца и покупателя. В классическом случае продавцами выступают владельцы вычислительных ресурсов, а покупателями – пользователи, участвующие в аукционе с целью приобретения вычислительных ресурсов для выполнения своих заданий.

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

Все покупатели преследуют сложную цель: с одной стороны, они хотят минимизировать затраты на приобретение вычислительных ресурсов, с другой – обработать свои вычислительные задания как можно быстрее [11]. Стремясь найти компромис- сное решение из этих двух противоречивых требований, пользователь может как повышать свою ставку (цену, которую он готов заплатить за вычислительные ресурсы), так и понижать ее. Выгода пользователя определяется следующим образом. Для каждого вычислительного задания пользователь заранее определяет бюджет – максимальную цену, которую он готов заплатить за обработку за- дания. Увеличивая цену, пользователь может раз- местить задание на ВУ с более производительными вычислительными ресурсами или на менее производительной ВУ, но при этом продвинуть задание в очереди. Один и тот же вычислительный ресурс может представлять интерес для нескольких покупателей, поэтому между ними возникает конкуренция, которая позволяет обеспечить максимальную прибыль продавцу.

Аукционные методы эффективны, когда товар уникален, имеется в ограниченном количестве (всего несколько штук) или когда точно неизвестно число участников (потенциальных покупателей), готовых купить его. В этом случае допускается, что цена товара заранее может быть не установлена и будет определена в процессе проведения аукциона на основе ставок участников. Ставка – это цена, которую готов заплатить участник за товар. В процессе проведения аукциона ставки всех участников поступают аукционисту, который ранжирует их и выявляет победителя аукциона. Победитель определяется в зависимости от используемой модели аукциона. В рассматриваемой авторами децентрализованной схеме управления ТРС в роли поку- пателей, продавцов и аукционистов выступают диспетчеры ВУ, причем каждый диспетчер в зави- симости от текущей ситуации может выступать в любой из ролей.

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

Авторы предлагают новый подход, в котором предметом аукционных торгов становятся задания, а участники меняются ролями: владельцы ресурсов становятся покупателями, расплачивающимися за задания имеющимися в наличии свободными вычислительными ресурсами, а продавцы – пользователями, продающими свои задания. Так как в один и тот же момент времени в разных ВУ доступно разное число вычислительных ресурсов (ВУ различаются по производительности и интенсивности локального потока заданий), между покупателями вновь возникает конкуренция.

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

-     продолжительность аукциона должна быть достаточной для того, чтобы в нем успели принять участие не менее двух покупателей;

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

При этом загруженность вычислительных ресурсов ВУ в процессе проведения аукциона может измениться в силу следующих причин:

-     помимо глобального потока, на вычислительные ресурсы ВУ поступает локальный поток заданий;

-     часть заданий успевает завершиться;

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

Действительность ставки в течение длительного периода времени позволяют обеспечить многораундовые аукционы. В этом случае каждый участник поддерживает актуальность сделанной ставки, изменяя ее каждый раз, когда меняется загруженность вычислительных ресурсов ВУ. Авторами была выбрана модель английского аукциона как наиболее предпочтительная для планирования заданий в ТРС с абсолютными приоритетами [12]. Английский аукцион – это открытый многораундовый аукцион с повышением ставок, который начинается с установления минимальной цены.

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

В работе [12] рассмотрен разработанный авторами алгоритм проведения английского аукциона в ТРС с абсолютными приоритетами заданий. Последовательность шагов алгоритма повторяется до тех пор, пока все задания глобальной очереди не будут распределены по ВУ. В начале торгов диспетчер-аукционист устанавливает за это задание минимальную ставку, после чего начинает принимать ставки от других диспетчеров. Прием ставок может многократно повторяться в течение времени проведения аукциона, при этом диспетчеры-участники могут корректировать свои ставки, повышая цену задания. Предполагается, что в течение времени проведения аукциона ставка диспетчера может измениться при изменении доступного объема вычислительных ресурсов. По окончании аукциона задание получает диспетчер, предложивший максимальную цену.

Продолжительность английского аукциона

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

На продолжительность аукциона оказывают влияние характеристики входного потока заданий (интенсивность, закон распределения), а также продолжительность выполнения заданий.

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

Для определения продолжительности английского аукциона авторы провели серию экспериментов с использованием специально подготовленного на базе вычислительных ресурсов МСЦ РАН макета ТРС. В экспериментах моделировалась работа двух суперкомпьютерных центров (СКЦ1 и СКЦ2), каждый из которых содержал в своем составе две высокопроизводительные вычислительные установки. ВУ моделировались отдельными сегментами суперкомпьютера МВС-100К (см. рис. 3).

На каждом сегменте был развернут следующий набор программных компонентов:

-     сервер хранения глобальной очереди (ГО), организованной в соответствии с [6] на базе распределенной СУБД Elasticsearch;

-     диспетчер заданий, разработанный авторами на языке программирования Python;

-     ЛСУР (СУППЗ и SLURM).

В ходе эксперимента моделировалась работа ВУ с различной вычислительной мощностью от 4 до 8 вычислительных модулей МВС-100К. При этом на все ВУ поступали потоки заданий от локальных пользователей.

В качестве тестовых задач использовались MPI-программы из известного пакета NAS Parallel Benchmarks (NPB). Моделирование входного потока заданий проводилось следующим образом. В глобальную очередь поступал стационарный поток из M = 400 вычислительных заданий. В потоке заданий были выделены четыре уровня приорите- тов заданий, число заданий каждого уровня зада- валось равномерным распределением. При этом исходные данные задания были равномерно распределены по всем ВУ ТРС. Интенсивность поступления вычислительных заданий в глобальную очередь задавалась пуассоновским распределением исходя из следующих соображений [13].

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

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

Для выполнения условия стационарности вероятностные характеристики входного потока заданий не должны зависеть от времени. На практике поступающий в ТРС поток заданий может считаться стационарным только на непродолжительном интервале времени, например, с 13 до 18 часов, но этот же поток в течение суток уже не может считаться стационарным (ночью плотность поступления заданий значительно меньше, чем днем, то же относится к выходным и будним дням). Однако во многих задачах теории массового обслуживания представляет интерес анализ работы системы при постоянных условиях; тогда задача решается для стационарного потока заявок [13].

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

В качестве показателя эффективности алгоритма проведения аукциона рассматривалось среднее время T обработки задания в соответствии с уровнем приоритета [8].

В результате многочисленных запусков авторами было установлено, что результаты зависят не от абсолютных значений времен, а от соотношения продолжительности аукциона и среднего времени выполнения задания. По этой причине среднее время выполнения задания может быть представлено в некоторых условных единицах (у.е.). В этом контексте продолжительность аукциона, например в 0,5 у.е., означает, что аукцион проводится в течение времени, равного половине среднего времени выполнения задания. Для экспериментального определения зависимости среднего времени обработки задания от продолжительности аукциона последняя изменялась с шагом 0,1 у.е. Полученные результаты показаны на рисунке 4.

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

Особый интерес представляет определение зависимости числа участников аукциона от его продолжительности. Для исследования этой зависимости авторами была проведена серия экспериментов, результаты которых представлены на графике (см. рис. 5). График демонстрирует следующую зависимость: увеличение средней продолжительности выполнения заданий снижает интенсивность участия диспетчеров в аукционе. При оптимальной продолжительности аукциона в 0,3–0,4 у.е. число участников аукциона в среднем достигает 70 % от общего числа диспетчеров ГСУР.

Заключение

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

Для определения оптимальной продолжительности аукциона авторами проведена серия экспериментов на макете ТРС, построенном на базе нескольких сегментов суперкомпьютера МВС-100К. Анализ результатов экспериментов позволяет сделать два основных вывода.

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

Во-вторых, наибольшая эффективность планирования заданий обеспечивается при продолжительности английского аукциона от 0,3 до 0,4 от среднего времени обработки задания. При такой продолжительности число участников аукциона в среднем достигает 70 %.

Работа выполнена в МСЦ РАН в рамках государственного задания по теме 0065-2018-0409. При проведении исследований использовался суперкомпьютер МВС-100К, находящийся в МСЦ РАН.

Литература

1.     Шабанов Б.М., Овсянников А.П., Баранов А.В., Ле- щев С.А., Долгов Б.В., Дербышев Д.Ю. Проект распределенной сети суперкомпьютерных центров коллективного пользования // Программные системы: теория и приложения. 2017. № 4. С. 245–262. DOI: 10.25209/2079-3316-2017-8-4-245-262.

2.     Henderson R.L. Job scheduling under the Portable Batch System. In: Job scheduling strategies for parallel processing, Feitelson D.G., Rudolph L. (Eds.), LNCS, Springer, 1995, vol. 949, pp. 279–294. DOI: 10.1007/3-540-60153-8_34.

3.     Yoo A.B., Jette M.A., Grondona M. SLURM: simple linux utility for resource management. In: Job scheduling strategies for parallel processing, Feitelson D., Rudolph L., Schwiegelshohn U. (Eds.), LNCS, Springer, 2003, vol. 2862, pp. 44–60. DOI: 10.1007/10968987_3.

4.     Moab HPC Suite Enterprise Edition. URL: http://www. adaptivecomputing.com/products/hpc-products/moab-hpc-suite-enterprise-edition (дата обращения: 12.07.2018).

5.     СУППЗ. URL: http://suppz.jscc.ru/ (дата обращения: 03.07.2018).

6.     Баранов А.В., Тихомиров А.И. Методы и средства организации глобальной очереди заданий в территориально распределенной вычислительной системе // Вестн. Южно-Уральского гос. ун-та. Вычислительная математика и информатика. 2017. Т. 6. № 4. С. 28–42. DOI: 10.14529/cmse170403.

7.     Singh K.K., Kumar M., Singhal M., Dubey A. Elasticsearch. IJMTER, 2018, vol. 5, iss. 05. DOI: 10.21884/ijmter.2018. 5137.2jz19.

8.     Климов Г.П. Теория массового обслуживания. М.: Изд-во МГУ, 2011. 312 с.

9.     Buyya R., Abramson D., Giddy J., Stockinger H. Economic models for resource allocation and scheduling in grid computing. Concurrency Comput. Pract. Exp., 2002, vol. 14, pp. 1507–1542. DOI: 10.1002/cpe.690.

10.   Wolski R., Plank J.S., and Brevik J. Analyzing market-based resource allocation strategies for the computational grid. J. of High Performance Computing Applications, 2001, vol. 15, iss. 3, pp. 258–281. DOI: 10.1177/109434200101500305.

11.   Kale L.V., Kumar S., Potnuru M., DeSouza J., and Bandhakavi S. Faucets: efficient resource allocation on the computational grid. Proc. Intern. Conf. on Parallel Processing (ICPP 2004), 2004, pp. 396–405. DOI: 10.1109/ICPP.2004.1327948.

12.   Baranov A., Telegin P., Tikhomirov A. Comparison of auction methods for job scheduling with absolute priorities. LNCS, 2017, vol. 10421, pp. 387–395. DOI: 10.1007/978-3-319-62932-2_37.

13.   Вентцель Е.С. Теория вероятностей. М.: Юстиция, 2018. 658 с.

14.   Петухов О.А., Морозов А.В., Петухова Е.О. Моделирование: системное, имитационное, аналитическое. СПб: Изд-во СЗТУ, 2008. 288 с.

References

1. Shabanov B.M., Ovsyannikov A.P., Baranov A.V., Leshchev S.A., Dolgov B.V., Derbyshev D.Yu. A project of a supercomputer center distributed network for collaborative research. Program Systems: Theory and Applications. 2017, vol. 8, no. 4, pp. 245–262 (in Russ.).
2. Henderson R.L. Job scheduling under the Portable Batch System. Feitelson D.G., Rudolph L. (Eds.) JSSPP 2015. Lecture Notes in Computer Science. Springer Publ., Berlin, Heidelberg, 1995, vol. 949, pp. 279–294.
3. Yoo A.B., Jette M.A., Grondona M. SLURM: simple linux utility for resource management. Feitelson D., Rudolph L., Schwiegelshohn U. (Eds.). JSSPP 2003. Lecture Notes in Computer Science. Springer Publ., Berlin, Heidelberg, 2003,
   vol. 2862, pp. 44–60.
4. Moab HPC Suite Enterprise Edition. Available at: http://www.adaptivecomputing.com/products/hpc-products/moab-hpc-suite-enterprise-edition (accessed July 12, 2018).
5. SUPPZ. Available at: http://suppz.jscc.ru/ (accessed July 3, 2018).
6. Baranov A.V., Tikhomirov A.I. Methods and tools for organizing the global job queue in the geographically distributed computing system. Bulletin of the South Ural State Univ. Ser. Computational Mathematics and Software Engineering. 2017, vol. 6, no. 4, pp. 28–42 (in Russ.).
7. Singh K.K., Kumar M., Singhal M., Dubey A. Elasticsearch. IJMTER. 2018, vol. 5, iss. 05, pp. 23–28.
8. Klimov G.P. Queuing Theory. Moscow, Lomonosov MSU Publ., 2011, 312 p.
9. Buyya R., Abramson D., Giddy J., Stockinger H. Economic models for resource allocation and scheduling in grid computing. Concurrency Comput. Pract. Exp. 2002, vol. 14, pp. 1507–1542.
10. Wolski R., Plank J.S., Brevik J. Analyzing market-based resource allocation strategies for the computational grid.
    J. of High Performance Computing Applications. 2001, vol. 15, iss. 3, pp. 258–281.
11. Kale L.V., Kumar S., Potnuru M., DeSouza J., and Bandhakavi S. Faucets: efficient resource allocation on the computational grid. Proc. Int. Conf. on Parallel Processing (ICPP 2004). 2004, pp. 396–405.
12. Baranov A., Telegin P., Tikhomirov A. Comparison of Auction Methods for Job Scheduling with Absolute Priorities. Lecture Notes in Computer Science. 2017, vol. 10421, pp. 387–395.
13. Ventsel E.S. Probability Theory. 12th ed. Moscow, Yustitsiya Publ., 2018, 658 p.
14. Petukhov O.A., Morozov A.V., Petukhova E.O. Modeling: System, Simulation, Analytical. St. Petersburg, SZTU Publ., 2008, 288 p.