научная статья по теме УПРАВЛЕНИЕ РЕСУРСОЕМКИМИ ВЫЧИСЛЕНИЯМИ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ. III. ДИНАМИЧЕСКОЕ КОНКУРЕНТНОЕ РАСПРЕДЕЛЕНИЕ РЕСУРСОВ Кибернетика

Текст научной статьи на тему «УПРАВЛЕНИЕ РЕСУРСОЕМКИМИ ВЫЧИСЛЕНИЯМИ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ. III. ДИНАМИЧЕСКОЕ КОНКУРЕНТНОЕ РАСПРЕДЕЛЕНИЕ РЕСУРСОВ»

ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2015, № 1, с. 50-60

= КОМПЬЮТЕРНЫЕ МЕТОДЫ =

УДК 519.85

УПРАВЛЕНИЕ РЕСУРСОЕМКИМИ ВЫЧИСЛЕНИЯМИ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ. III. ДИНАМИЧЕСКОЕ КОНКУРЕНТНОЕ РАСПРЕДЕЛЕНИЕ РЕСУРСОВ

© 2015 г. Ю. Е. Малашенко, И. А. Назарова

Москва, ВЦ РАН Поступила в редакцию 23.07.14 г., после доработки 25.08.14 г.

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

DOI: 10.7868/S0002338815010102

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

В [1, 2] была предложена и реализована на макете многопараметрическая модель (МП-модель) планирования разнородных вычислительных работ для неизвестного состава потока заявок [3, 4]. Система диспетчеризации, разработанная на основе МП-модели, поддерживает режим скользящего планирования, производит распараллеливание по данным и оптимизирует состав пакета текущих работ, что дает возможность завершать задания к назначенному сроку [5, 6] и минимизировать производственные потери [7].

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

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

Предложенная схема планирования позволяет производить декомпозицию входного потока по видам заданий в зависимости от состояния вычислительных ресурсов. Далее в статье показано, как соответствующие конструктивные построения могут быть использованы для распределения квоты, выделенной для заявок одного вида. Применение динамической схемы суперконкурентного [8] распределения квоты реализует дисциплину обслуживания SWAP (от английского Short — Work — Ahead — Performance) [3, 4, 9].

1. Постановка задачи. Рассмотрим гетерогенную высокопроизводительную вычислительную систему, выполняющую ресурсоемкие задания, которые относятся к специальному классу, определенному в [7] как citu-задания, citu-задачи (от английского термина computationally intensive task (under) uncertainty, который можно перевести как ресурсоемкие вычислительные задания, выполняемые в условиях неопределенности). Решение каждой такой задачи (выполнение задания) сводится к поиску уникального фрагмента в большом массиве исходных данных. Поиск осуществляется переборными алгоритмами. Задача считается решенной, как только в предъявленном наборе данных удается выявить уникальный фрагмент, характеристики, свойства или параметры которого задаются заранее. В противном случае необходимо убедиться, что искомый фрагмент в массиве отсутствует, и тем самым завершить задание [10]. Заявки на решение citu-за-дач различных видов поступают в систему в произвольные моменты времени без каких-либо особых признаков, отношений предпочтения или предписанного порядка обслуживания. Для получения решения каждой citu-задачи достаточно найти хотя бы один уникальный фрагмент. Все задания выполняются в режиме реального времени, их содержательные решения одинаково важны и должны быть получены все в совокупности и каждое в отдельности как можно быстрее.

Для описания функционирования СВС далее используется модель, подробно описанная в [1, 2]. При математическом описании системы будем говорить об абстрактной гетерогенной СВС, выполняющей разнородные вычислительные работы по поиску уникальных фрагментов. Считается, что СВС состоит из центрального управляющего устройства и набора независимых исполняющих единичных вычислительных модулей (ЕВ-модулей) различных конструктивных типов. ЕВ-модуль может выполнять по крайней мере один вид работ. Произведенная работа измеряется числом специализированных элементарных вычислительных операций (СЭВ-операций). СЭВ-операция состоит в просмотре отдельного фрагмента данных и проверке его уникальности соответствующим переборным алгоритмом. При выполнении конкретного citu-задания число фрагментов данных, которые будут в действительности просмотрены до его завершения, априори неизвестно, т.е. объем необходимой работы для обнаружения уникального фрагмента определить заранее невозможно.

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

A(t) — длительность планового периода (операционного окна, интервала планирования), который начинается в момент t;

еm — отдельный ЕВ-модуль (устройство) m-го типа, m = 1, M, где М — общее число типов ЕВ-модулей, из которых состоит рассматриваемая СВС;

pm (t) — в момент времени t производительность ЕВ-модуля m-го типа при обработке задания k-го вида, k = 1, K, где K — общее число различных видов работ (заданий), которые могут выполняться в данной СВС. Предполагается, что производительность p% (t) с течением времени может меняться, например, из-за перегрева оборудования и/или изменения тактовой частоты;

— общее число работоспособных ЕВ-модулей т-го типа на момент времени I; соответственно вектор R(í) = (Я1^), ^2(0, • ••, Ям({)) определяет все исправные ресурсы СВС в момент I.

Введем переменные г1 (I) — число ЕВ-модулей т-го типа, которые, начиная с момента I, должны в течение А(0 выполнять работу к-го вида. Тогда за плановый период А(0 может быть завершен следующий общий объем работ к-го вида:

м

¥к(А(0) = А(() £/)г1 (/), к = 1К. (1.1)

т = 1

Поскольку число ЕВ-модулей, распределяемых для выполнения работ, не может превышать общего числа работоспособных, то значения г1 (I) должны удовлетворять следующим ограничениям:

К

£ гтк (0< лт(Г), к = 1ТМ, (1.2)

к = 1

гк( 0, к = 1К, т = ЦМ. (1.3)

Условия (1.1)—(1.3) задают множество векторов выполнимых (достижимых) объемов работ V(А(í)) = (К1(А(!)), •.., УК(А(1))) при допустимых распределениях ресурсов в соответствии с ограничениями, заданными вектором R(í).

В рамках модели функционирования [1, 2] предполагается, что вся исходная и текущая информация о еки-заданиях, как вновь поступивших, так и находящихся в обработке, помещается и далее хранится в базе данных заданий (БД-заданий). В контрольной точке принятия решения I по команде администратора в программном комплексе планирования (ПК-плане) анализируются текущие данные о ходе выполнения всех заданий, находящихся в СВС. Здесь I — начальный момент очередного планового периода. Далее администратор (специалист и/или алгоритмическая процедура) выбирает длительность планового периода А(0, в ПК-плане формируется пакет текущих работ (ТР-пакет), который состоит из подмассивов (поднаборов) неделимых фрагментов данных тех заданий, которые будут обрабатываться в СВС в течение А(?). ПК-план помещает ТР-пакет в специальный буфер текущих работ (ТР-буфер) и, начиная с момента I, СВС выполняет плановую работу на всех работоспособных ЕВ-модулях. По завершении выполнения заданий ТР-пакета наступает следу

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком