научная статья по теме ПАКЕТНАЯ ОБРАБОТКА ЗАДАНИЙ В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СРЕДАХ С НЕОТЧУЖДАЕМЫМИ РЕСУРСАМИ Автоматика. Вычислительная техника

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

Автоматика и телемеханика, № 10, 2012

© 2012 г. В.В. ТОПОРКОВ, д-р техн. наук (Национальный исследовательский университет "МЭИ", Москва)

ПАКЕТНАЯ ОБРАБОТКА ЗАДАНИЙ В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СРЕДАХ С НЕОТЧУЖДАЕМЫМИ РЕСУРСАМИ1

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

1. Введение

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

1 Работа выполнена при частичном содействии Совета по грантам Президента Российской Федерации для поддержки ведущих научных школ (шифр НШ-316.2012.9), Российского фонда фундаментальных исследований (проект № 12-07-00042), Министерства образования и науки Российской Федерации в рамках федеральной целевой программы "Научные и научно-педагогические кадры инновационной России" на 2009-2013 гг. (государственные контракты № 16.740.11.0038 и 16.740.11.0516).

Серьезная проблема связана с ценообразованием в зависимости от уровня качества обслуживания [1—3]. Обзор различных подходов к ее решению, а также к формированию различных стратегий планирования при наличии ограничений на время и бюджет выполнения задания приводится в [4]. В [5] рассматриваются эвристические алгоритмы подбора ресурсов на основе задаваемых пользователем функций полезности. Пользователь, запускающий задание, должен иметь возможность управлять временем его старта, оперируя платой, которую он вносит за выполнение задания в течение некоторого времени [1—5]. Цена устанавливается собственником на основе соображений балансирования глобальных и локальных потоков заданий, получения соответствующего дохода и т.п.

В одних моделях распределенной обработки данных на неотчуждаемых ресурсах в зависимости от состояния среды отыскивается лишь подходящий набор ресурсов [6] и не поддерживаются оптимизационные механизмы планирования заданий. В других [7] - не представлены аспекты, весьма характерные для распределенных сред с неотчуждаемыми ресурсами и связанные с динамикой изменения загрузки узлов, конкуренцией независимых пользователей, а также глобальных и локальных потоков заданий [1-5,8,9]. При реализации той или иной экономической политики брокерами вычислительных ресурсов [4,5], как правило, проводится оптимизация выполнения конкретного приложения [8,9]. Здесь ключевые игроки - владельцы и брокеры, представляющие интересы независимых пользователей, конкурирующих за использование вычислительных ресурсов. Другая тенденция связана с образованием виртуальных организаций [6,8,9]. При этом осуществляется оптимизация планирования на уровне потоков заданий. В рамках первого из направлений системы управления ресурсами являются хорошо масштабируемыми и адаптируемыми к особенностям приложений. Однако использование независимыми пользователями различных критериев для оптимизации планов выполнения своих заданий в условиях возможной конкуренции с другими заданиями может ухудшать такие интегральные характеристики, как время выполнения пакета заданий и загрузка ресурсов. Образование виртуальных организаций естественным образом ограничивает масштабируемость систем управления заданиями. Тем не менее наличие определенных правил предоставления и потребления ресурсов позволяет повысить эффективность планирования на уровне потоков заданий.

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

лельного задания требует выделения определенного числа слотов, так чтобы составные части задания (задачи) могли стартовать одновременно. План выполнения задания представляет собой набор отобранных слотов, а план выполнения пакета - комбинацию слотов. Списки доступных слотов передаются из локальных систем пакетной обработки заданий [7,10] метапланировщику. В отличие от известных подходов стратегии планирования и ограничения [11,12] модифицируются в соответствии с обновляемыми расписаниями локальных вычислительных узлов.

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

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

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

Пусть Si - множество наборов слотов, подходящих для выполнения г-го задания пакета, г = 1,...,и. Набор слотов в^ € Si является подходящим для г-го задания, если он удовлетворяет требованиям ресурсного запроса, цене с(в^)

и времени ti(вj), ] = 1,... NN =

. Ресурсный запрос содержит тип,

из

i=1

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

п

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

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

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

п

(2.1) = Ес,(в3), в3 е Бг, з е{1,...,М}, в е Б.

г=1

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

п

(2.2) Щ = ), в3 е Б,, з е{1,...,Щ, в е Б.

г=1

Пусть /г(в3) - функция, определяющая эффекти

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

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