Постановка задачи выбора оптимальной комбинации слотов

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

Пусть  – множество наборов слотов, подходящих для выполнения -го задания пакета, . Набор слотов  является подходящим для -го задания, если он удовлетворяет требованиям ресурсного запроса, цене  и времени , . Ресурсный запрос содержит тип, количество и характеристики необходимых узлов (тактовую частоту процессора, емкость оперативной памяти, дисковое пространство, операционную систему и т.д.). При этом  не обязательно не пересекаются. К началу каждого цикла планирования локальные расписания обновляются и известны. При этом требуется решение двух задач. Во-первых, нужно отобрать набор подходящих слотов для каждого задания  пакета. Во-вторых, необходимо найти комбинацию слотов, оптимальную с позиции прохождения всего пакета заданий в текущем цикле планирования. Комбинация представляет собой -элементную последовательность  не обязательно различных наборов слотов. Любое из заданий может использовать один и только один набор слотов. В то же время некоторые из наборов могут разделяться по времени или ресурсу несколькими заданиями одного и того же пакета. Обозначим через  множество комбинаций слотов для пакета заданий. Если для какого-либо из заданий подходящего набора слотов не существует, то его планирование переносится в следующий цикл и задание занимает место в очереди цикла планирования в соответствии с некоторым приоритетом. После просмотра слотов для всех  заданий пакета отыскиваются альтернативные наборы слотов, поскольку при отборе слотов для -го задания не весь исходный список может быть просмотрен. Эта процедура итеративно реализуется для всех заданий, планирование которых не перенесено в следующий цикл.

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

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

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

, .              (3.2.1)

Примером временно́го показателя, который отражает интересы пользователей и политику администрирования, является суммарное время прохождения пакета:

, .           (3.2.2)

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

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

, ,       (3.2.3)

в частности (3.2.1) или (3.2.2).

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

Ограничение  формируется динамично к началу текущего цикла планирования таким образом, что

,                                     (3.2.4)

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

Формальная постановка задачи выбора оптимальной комбинации слотов  заключается в отыскании экстремума (3.2.3) при ограничении

,                                     (3.2.5)

где  определяется в соответствии с (3.2.4).

Еще раз отметим, что ограничение (3.2.5) формируется для каждого пакета в текущем цикле планирования. Рассмотрим пример ограничения (3.2.4), фигурирующего в правой части неравенства (3.2.5).

Функция уровня временны́х затрат может иметь следующий вид:

,                                   (3.2.6)

где  – число подходящих (альтернативных) наборов слотов для -го задания;  – ближайшее не большее целое число.

Ограничение (3.2.4) с учетом (3.2.6) задается следующим образом:

.                                               (3.2.7)

В (3.2.7)  – сумма усредненных значений длительности слотов по всем альтернативным наборам в пакете.

В задачах однокритериальной оптимизации каждая из сторон, представленная в виртуальной организации, – пользователь, собственник, администратор – заинтересована в минимизации или максимизации критериев типа (3.2.1), (3.2.2) при заданных ограничениях путем выбора оптимальной комбинации  слотов. Например, пользователи стремятся минимизировать стоимость  (3.2.1) при ограничении на суммарное время  занятия слотов (3.2.7) либо минимизировать время  (3.2.2) прохождения пакета заданий при фиксированном бюджете  виртуальной организации. С позиций собственников ресурсов целесообразно минимизировать потери доходов (максимизировать ) или простой ресурсов (максимизировать ) при ограничении на время использования слотов внешними заданиями. Конкретные задачи поиска оптимальной комбинации слотов рассматриваются в разделе 3.3 настоящего пособия.

3.3. Решение задачи и примеры выбора оптимальной комбинации слотов

В данном разделе рассматривается отыскание экстремума (3.2.3) при ограничении (3.2.5). Приводится ряд примеров, имеющих важное практическое значение.

Схема выбора

Пакет состоит из  независимых заданий, что допускает естественную декомпозицию решения задачи (3.2.3)-(3.2.5) на  этапов с использованием методов динамического программирования, основанных на рекуррентных соотношениях.

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

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

Подчеркнем, что  в отличие от  обозначает затраты на выполнение -го задания на наборе  слотов - цену  или время  (раздел 3.2).

Тогда рекуррентные соотношения для отыскания экстремума (3.2.3) при ограничении (3.2.5) и использовании набора слотов ,  по схеме обратной прогонки имеют следующий вид:

, , , ; (3.3.1)

, , , , (3.3.2)

где  – суммарные затраты при использовании наборов слотов заданиями  пакета.

Соответствующие уравнения для схемы прямой прогонки:

, , , ;   (3.3.3)

, , , , (3.3.4)

где  – суммарные затраты на выполнение заданий  пакета.

Оптимальные затраты в схемах (3.3.1), (3.3.2) и (3.3.3), (3.3.4) определяются из уравнения

, .                            (3.3.5)

Оптимальный набор слотов для выполнения -го задания будем обозначать через .

В обеих схемах (3.3.1), (3.3.2) и (3.3.3), (3.3.4) он задается соотношением

, .                       (3.3.6)

На основе функциональных уравнений (3.3.1)-(3.3.6) отыскивается решение задачи (2.2.3) при ограничении (2.2.5), позволяющее получить оптимальную комбинацию слотов  для пакета заданий.

 

Отбор подходящих слотов

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

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

1°. Доступные слоты (см. рис. 3.1, а) упорядочиваются по неубыванию времени старта  (рис. 3.1, б и в).

2°. Из полученного на шаге 1° списка выбирается очередной подходящий по ресурсу, цене и длительности слот .

3°. Из списка ранее просмотренных подходящих слотов от 1 до  удаляются слоты с временем окончания , где .

4°. Шаги 2°, 3° повторяются до тех пор, пока не наберется заданное число  слотов.

 

а

б

в

Рис. 3.1. Отбор слотов для выполнения задания

 

Заметим, что в этой схеме на шаге 2° фигурирует не только время, но и требования к ресурсу и цене.

В примерах, иллюстрируемых рис. 3.1, =3. Время запуска задания определяется временем начала последнего из отобранных подходящих слотов (на рис. 3.1 это слот 6). Время окончания выполнения задания зависит от , это - максимум длительности выполнения задачи соответствующего задания по всем отобранным слотам (на рис. 3.1, в ему соответствует слот 4).

Рассмотренная выше схема применяется для каждого из заданий пакета. Сначала делается попытка найти комбинацию подходящих слотов для всех заданий пакета. Если для какого-либо из заданий такого набора не существует, его планирование переносится в следующий цикл и задание занимает место в очереди в соответствии с заданным приоритетом, например в начале очереди. При успешном отборе слотов для -го задания список просматриваемых слотов для -го задания модифицируется. Из соответствующих временных отрезков исключаются периоды, занятые выполнением -го задания. Отбор слотов для -го задания осуществляется на модифицированном списке по вышерассмотренной схеме. После просмотра слотов для всех  заданий пакета отыскиваются альтернативные наборы, поскольку при отборе слотов для каких-либо заданий не весь исходный список может быть просмотрен. Эта процедура итеративно повторяется для всех заданий, планирование которых не перенесено в следующий цикл. В очередном цикле совокупность доступных слотов (см. рис. 3.1, а) обновляется в соответствии с динамикой загрузки локальных узлов распределенной среды.

В табл. 3.1 приведен пример числовых характеристик наборов слотов для пакета из трех заданий. Параметр  связан с временем , которое указывает пользователь в ресурсном запросе, при этом  на условиях соответствующей оплаты . Вопросы ценообразования и пересчета  в  выходят за рамки данного пособия. Параметры ,  – исходные данные для выбора оптимальной или эффективной комбинации слотов. Согласно обозначениям, введенным в разделе 3.2, ,  и . Так, для задания 1 существует три альтернативных набора слотов, для заданий 2 и 3 – соответственно два и четыре набора подходящих слотов. Каждое из заданий использует один и только один набор слотов. Наборы слотов  и  могут разделяться всеми тремя заданиями, набор  – заданиями 1 и 3, набор  может быть выделен лишь заданию 3.

 

Таблица 3.1

Номер  набора	Задание 1		Задание 2		Задание 3
слотов
1	7	7	3	3	5	5
2	10	5	2	1	8	4
3	9	3	-	-	6	2
4	-	-	-	-	4	1

 

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