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

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

ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 2, с. 109-119

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

УДК 519.6

ПОТОКОВЫЕ И ЖАДНЫЕ АЛГОРИТМЫ СОГЛАСОВАННОГО ВЫДЕЛЕНИЯ РЕСУРСОВ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ*

© 2007 г. В. В. Топорков

Москва, МЭИ (технический ун-т) Поступила в редакцию 14.03.06 г., после доработки 06.07.06 г.

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

Введение. Необходимость в особых механизмах управления ресурсами в распределенных системах обработки данных давно и хорошо осознана [1]. В ряде случаев сложные наборы взаимосвязанных задач (задания) требуют согласованного выделения ресурсов (resource co-allocation) на нескольких обрабатывающих узлах [2]. Каждый из узлов может находиться в автономном административном домене и представлять собой многомашинный или многопроцессорный комплекс, прохождением заданий в котором управляет своя локальная система пакетной обработки, например, CODINE, LL, LSF, NQE, Condor, СУШ 13 [3]. Так, LL реализует назначение многопроцессорных заданий на множество однотипных ресурсов (процессоров). Системы NQE и PBS допускают согласованное выделение разнородных ресурсов (процессоров и памяти), а CODINE, LSF, mpC позволяют конфигурировать неоднородные распределенные среды под конкретные задания. В локальных системах предполагается полный контроль над всеми ресурсами, что, например, не осуществимо в среде Грид. Здесь распределение ресурсов имеет множество существенных отличий, обусловленных автономностью, разнородностью и динамичностью состава обрабатывающих узлов [4].

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

* Работа выполнена при финансовой поддержке РФФИ (проекты < 04-01-00072, 06-01-00027).

тегий. Однако на практике чаще всего используется один из возможных вариантов распределения ресурсов, а множество критериев "сворачивается" в скалярную функцию полезности [6, 8].

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

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

Рис. 1. Граф задания.

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

Состав ресурсов и разбиение исходной совокупности задач на кластеры являются входными параметрами в алгоритмах планирования распределенных вычислений, что составляет наиболее трудоемкую часть работы менеджеров ресурсов, метапланировщиков, Грид-диспетчеров и т.п. [1-11]. Принципиально важно, чтобы затраты на подготовку исходных данных не доминировали над сложностью планирования. В задачах реальной размерности при крупноблочном распределении заданий на число узлов не более десятка [2, 4-6, 8, 11] предлагаемые алгоритмы позволяют подобрать состав ресурсов за время порядка нескольких сотен шагов, что несоизмеримо меньше затрат на планирование в известных подходах [1, 2, 4, 7, 8, 10, 11] и свидетельствует об эффективности этих алгоритмов.

1. Формальная постановка задачи согласованного выделения ресурсов. Пусть T - совокупность задач, составляющих задание, которые частично упорядочены в соответствии с информационно-логическими связями. Обозначим через Р = F2, ..., FK) последовательность необязательно непересекающихся множеств таких, что любой элемент ^ е Fk, к = 1, ..., К, определяет некоторый способ реализации кластера Tl с T в разбиении P = = {Тх, ..., TL} множества Т, 1 < / < Ь, Ь < К. Положим, разбиение осуществляется в соответствии с заданной метрикой dij связности кластеров Т, Т) е Р, использование которой делает возможной минимизацию пересылки данных между обрабатывающими узлами, передачу управлений между задачами и т.п. Назовем /к признаком, а совокупность Fк признаков - свойством ресурсов для выполнения задач кластера Т/. Формально описание свойств ресурсов

зададим как трансверсаль / = (/!, ...,семейства Р признаков. Будем считать состав ресурсов выбранным, если найдено его описание / и соответствующее ему разбиение задания Т на кластеры Р = {Тх, ...,

ТЬ}, причем определено отображение Т —Р.

Приведем пример описания ресурсов. Положим, последовательность Р = (Н, FD) свойств некоторой системы образована признаками, устанавливающими способы организации потоков команд и данных: FI = ^1, М1}, FD = MD}, где SI, М1 - одиночный и множественный потоки команд, а SD, MD - соответственно одиночный и множественный потоки данных. Тогда классификация архитектур вычислительных систем по Флинну формально может быть выражена описаниями ^1, SD), ^1, MD), (М1, SD) и (М1, MD), каждое из которых суть трансверсаль последовательности (И, FD). Таким образом, представление ресурсов включает один и только один признак из соответствующего свойства. Как правило, такой подход опирается на экспертные знания и на практике не всякая комбинация признаков является допустимой [3].

Согласованное выделение ресурсов в общем случае не сводится к отысканию отображения Т —► Р, поскольку при этом возможны различные разбиения задания на Ь < К кластеров в соответствии со свойствами ресурсов. Поясним это на примере. Положим, имеется задание Т, структуру которого иллюстрирует граф на рис. 1: каждая из вершин графа соответствует одной из 12 задач, а дуга - информационной связи. Необходимо в этом задании выделить кластеры, используя следующую метрику связности задач по данным:

= 2 ¥сот/(V, + V,),

(1.1)

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

По сути метрика (1.1) позволяет объединить в один кластер задачи, связанные по общим переменным, и может быть использована для минимизации трафика обмена данными в распределенных системах. На рис. 2, а приведена матрица 12 х 12 со значениями метрики (1.1). Для каждой из задач определяется множество задач-соседей с наибольшим значением метрики. Рассматриваемая задача и ее соседи включаются в один кластер, что можно представить в виде дерева (рис. 3, а). Так, пары задач 3, 5; 4, 6; 9, 10 и 11, 12 входят в кластеры I, II, III и IV соответственно. На второй стадии разбиения формируются кластеры А, В, С и D согласно значениям метрики (1.1), приведенным в матрице на рис. 2, б. По аналогии на третьей и четвертой стадиях разбиения можно выделить еще более крупные блоки задач Е, F, G, Н, а также I, J, которые имеют вид деревьев на рис. 3, б и в. Эти кластеры образуются в соответствии с матрицами значений (1.1), показанными на рис. 2, в-д.

Используем следующие разбиения исходного задания (см. рис. 1):

Л =

(1.2)

>

(1.3)

= {{ 1, 3, 5}, {2, 4, 6}, {7, 9, 10}, {8, 11, 12}},

Р2 = {{ 1,{ 3, 5 }},{ 2, { 4, 6 }},{ 7, { 9, 10 }}, {8, { 11, 12}}}.

Разбиения (1.2), (1.3) отвечают одному и тому же отображению Т —► Р, где Р - набор FB, FC, FD) свойств, связанных с выполнением кластеров А, В, С, D (см. рис. 3, а). Однако степень детализации кластеров в Р1 и Р2 различна и, следовательно, наборы признаков в описании соответствующих ресурсов также должны различаться.

Таким образом, при согласованном выделении ресурсов приходится рассматривать различные варианты разбиения задания. С целью локализации области поиска описания ресурсов с каждым из разбиений может ассоциироваться свое семейство признаков, которое чаще всего формируется на базе экспертных знаний о предметной области. Так, для реализации кластеров А, В, С, D в упомянутом задании (см. рис. 1 и рис. 3, а) ресурсы должны обладать следующими свойствами: FA =

= {/л1, /лг}, Fв = {/е1, /вг}, FC = {/е1, ¡с2, ¡с3 }, FD = {/в,, /в,, /в,}. Здесь признаки Д , Д означают испо

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

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