BC/NW 2006, №2, (9) :4.1
РАСПРЕДЕЛЕННЫЕ СИСТЕМЫ: СТРАТЕГИИ
ПЛАНИРОВАНИЯ И МАСШТАБИРОВАНИЯ РЕСУРСОВ *
В.В. Топорков
(Москва, Московский энергетический институт (ТУ),
Россия)
Методы и средства для
согласованного распределения ресурсов (resource co-allocation)
при организации параллельных вычислений в замкнутых конфигурациях хорошо
известны [1]. Например, система пакетной обработки Load Leveler
(LL) реализует назначение многопроцессорных заданий на множество
однотипных ресурсов (процессоров) и применяется, в частности, в
суперкомпьютерах IBM SP. Системы Net Queueing Env (NQE) и Portable Batch System (PBS) допускают согласованное
выделение разнородных ресурсов – процессоров и памяти. Такие системы как CODINE (Computing in Distributed Networked Environments), LSF (Load Sharing Facility) и mpC (Институт системного
программирования РАН) позволяют управлять ресурсами или выбирать их
конфигурацию в неоднородных распределенных средах. Однако при этом
предполагается полный контроль над всеми ресурсами, что не осуществимо в Грид.
Динамичность и гетерогенность состава, а также автономность узлов Грид [2]
серьезно усложняют задачу согласованного выделения ресурсов для выполнения
заданий с соответствующим качеством обслуживания. Решение этой проблемы, по
мнению ряда специалистов [3-5], связывается с управлением заданиями на основе
стратегий – семейств возможных сценариев развития вычислений, конкретный
вариант (опорный план) которых должен выбираться в зависимости от событий,
наступающих в глобальной среде и связанных, прежде всего, с занятием,
освобождением и предварительным резервированием ресурсов.
Структура системы управления
заданиями в Грид является иерархической. Роль посредников между пользователями
и узлами могут выполнять брокеры (агенты уровня приложений) либо глобальный,
внешний планировщик, именуемый иногда метапланировщиком, метадиспетчером,
Грид-диспетчером [2] и т.п. Эти подходы концептуально различны. Первый из них
предполагает временное отчуждение ресурсов от владельцев и централизованное
управление ими. В этом направлении, ассоциируемом часто с планированием на
уровне приложений (application-level scheduling),
выполнен ряд проектов: AppLeS, Legion, APST, Condor-G, Nimrod-G, DRM, GRB и др. Порядок и время
завершения выполнения заданий здесь иногда не важны для пользователя. Пример
реализации этой концепции – обработка экспериментальных данных с Большого
адронного коллайдера (проект LHC Computing Grid).
Другой подход учитывает коллективный характер использования ресурсов Грид и
ориентирован на образование виртуальных организаций. Это ограничивает его
масштабируемость, однако позволяет повысить качество планирования.
Метапланировщик поддерживает глобальную очередь заданий, выполняя роль
промежуточного звена между пользователями и локальными системами управления
заданиями на отдельных узлах, которые могут представлять собой кластеры,
многопроцессорные системы и т.д. Такой способ организации ресурсов и управления
заданиями рассчитан на открытую архитектуру Грид-служб (OGSA) и
инструментарий Globus Toolkit. Известно, что Globus Toolkit поддерживает программный интерфейс с уже
упоминавшимися системами LL, PBS, LSF, а также Condor и
рядом других. Нужно заметить, что альтернативной является такая организация
ресурсов, при которой не используются локальные системы пакетной обработки,
узлы очень просты (чаще всего, это отдельные компьютеры), причем управляются
они централизованно. Известные реализации этого подхода – проекты SETI@home и Distributed.net.
Сюда же можно отнести коммерческие платформы для глобально распределенных
вычислений DCGrid, LiveCluster, GridMP, Frontier, разработанные компаниями Entropia,
DataSynapse, Parabon Computation,
United Devices. Однако в рамках этого
направления вряд ли уместно ставить задачу согласованного распределения просто
организованных, управляемых централизовано и однородных ресурсов.
В данной работе в качестве
базовой принимается схема "метапланировщик – локальные системы пакетной
обработки (локальные планировщики)", реализуемая в рамках виртуальной
организации. Метапланировщик может иметь многоуровневую, например, древовидную
структуру и состоять из множества менеджеров ресурсов, каждому из которых
подконтролен домен вычислительных узлов либо подмножество менеджеров более
низкого уровня в иерархии управления заданиями [6]. Разнородность, динамичность
и автономность узлов Грид обуславливают необходимость в стратегии планирования
заданий. Фактическое выделение ресурсов осуществляется локальной системой
пакетной обработки на основе ресурсного запроса, содержащего требования к
типам, характеристикам ресурсов (памяти, процессорам), системному программному
обеспечению и оформляемого скриптом команды ввода задания qsub. Поэтому функции поддержки
стратегий планирования должен выполнять метапланировщик. Предполагается, что задание
состоит из информационно и/или логически связанных задач, для выполнения
которых необходимо согласованное выделение, в общем случае, разнородных
ресурсов на нескольких узлах в автономных доменах. Чаще всего за единицу
обработки в Грид и локальных системах принимается задание (исполняемые, входные
и выходные файлы данных). При этом структура задания не принимается во
внимание. Одно из немногих исключений – планировщик Maui [1], который допускает, что
задание (job) может состоять из параллельных задач (tasks),
однако все задачи считаются однотипными в смысле требуемого вычислительного
ресурса. При согласованном назначении задач на ресурсы необходимо учитывать и
структуру задания, и разнотипность составляющих его задач.
Новизна предлагаемого
подхода к организации вычислений в Грид заключается в использовании семейства
стратегий распределения ресурсов, состоящего из опорных планов в действиях
метапланировщика, причем конкретный план выбирается им в зависимости от
наступающих событий, информация о которых передается из локальных систем
управления ресурсами. Наличие заранее подготовленных опорных планов позволит
существенно снизить затраты времени на составление расписания запуска заданий и
реализовать адаптивное управление глобальной очередью заданий со стороны
метапланировщика. Стратегия согласованного выделения ресурсов может быть
сформирована с использованием метода критических работ [1, 7-9], который
позволяет строить стратегии распределенных вычислений, условно оптимальные по
частным критериям эффективности, на основе двухэтапной процедуры. Она включает
планирование ранжированных по длительности критических работ
(последовательностей задач) и разрешение конфликтов между задачами различных
работ, конкурирующими за один и тот же ресурс. Планирование реализуется на
основе аппарата динамического программирования, а для разрешения коллизий
применяются жадные алгоритмы.
Оригинальность и новизна
предлагаемого решения заключается в реализации адаптивного управления
заданиями, которое сочетает в себе использование опорных планов выделения
ресурсов и прогнозирование их освобождения на основе имитационного
моделирования действий локальных планировщиков.
Важным моментом является
формирование многоуровневых стратегий, состоящих из семейств опорных планов
выделения ресурсов для структурно различных, с неодинаковым уровнем
параллелизма моделей одного и того же задания, экономичными по сложности
процедурами. Для этого могут быть использованы декомпозиционные схемы синтеза
стратегий планирования на основе аппарата динамического программирования [9].
Регулярность схем синтеза стратегий позволяет с единых методологических позиций
ставить вопрос об их компактной инструментальной реализации
программами-планировщиками на верхнем уровне управления заданиями.
Л И Т Е Р А Т У Р А
1. Топорков В.В. Модели
распределенных вычислений. – М.: ФИЗМАТЛИТ. 2004. – 320 с.
2. Коваленко В.Н., Корягин Д.А.
Организация ресурсов грид. Препринт №63. – М.: ИПМ РАН им. М.В. Келдыша. 2004.
– 25 с.
3. Kurowski K., Nabrzyski J., Oleksiak A. et al. Multicriteria aspects of
Grid resource management // In: Grid resource management. State of the art and
future trends / Eds. J. Nabrzyski, J.M. Schopf, J. Weglarz. Kluwer Academic
Publishers. 2003. P. 271-293.
4. Natrajan A., Humphrey M.A., Grimshaw A.S. Grid resource management in
Legion // In: Grid resource management. State of the art and future trends /
Eds. J. Nabrzyski, J.M. Schopf, J. Weglarz. Kluwer Academic Publishers. 2003.
P. 145-160.
5. Коваленко В.Н., Семячкин
Д.А. Использование алгоритма Backfill в грид // Тр. междунар.
конф. "Распределенные вычисления и Грид-технологии в науке и
образовании" (Дубна, 29 июня - 2 июля
6. Киселев А., Корнеев В.,
Семенов Д. и др. Управление метакомпьютерными системами // Открытые системы.
2005. 32. С. 11-16.
7. Топорков В.В. Оптимизация
распределения ресурсов в системах жесткого реального времени // Известия РАН.
Теория и системы управления. 2004. №3. С. 61-71.
8. Топорков В.В. Выбор состава
и распределение ресурсов вычислительных систем реального времени // Автоматика
и телемеханика. 2005. №1. С. 171-189.
9. Топорков В.В.
Декомпозиционные схемы синтеза стратегий планирования в масштабируемых системах
// Известия РАН. Теория и системы управления. 2006. №1. С. 82-93.