ВЕСТНИК ЮЖНОГО НАУЧНОГО ЦЕНТРА РАН Том 4, № 3,2008, стр. 23-34
ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
УДК 519.68
МЕТОДЫ И АЛГОРИТМЫ УПРАВЛЕНИЯ ПАРАЛЛЕЛЬНЫМИ ЗАДАНИЯМИ В ГРИДЕ С РЕСУРСАМИ В ФОРМЕ КЛАСТЕРОВ
© 2008 г. В.Н. Коваленко1, Д.А. Семячкин1
Задача управления параллельными заданиями много раз решалась для ближайшего аналога вычислительного грида - кластерных систем, однако в условиях грида она усложняется и для ее решения требуются новые подходы. Основная трудность состоит в необходимости накопления и затем гарантированного синхронного выделения ресурсов в нескольких кластерах (коаллокация ресурсов). В настоящей работе предлагается решение этой задачи с помощью метода опережающего планирования, разработанного для практически важной формы организации грида с неотчуждаемыми ресурсами, когда они не выделяются в грид полностью, а используются в режиме разделения с их владельцами.
Ключевые слова: грид, параллельное задание, метод обратного заполнения, резервирование ресурсов, коаллокация, неотчуждаемые ресурсы.
Параллельное (или многопроцессорное) задание относится к базовым понятиям теории параллельных вычислений и представляет собой программу, реализованную в виде нескольких компонент, каждая из которых запускается на отдельном процессорном узле и в ходе своего выполнения может взаимодействовать с остальными компонентами с помощью стандартных средств передачи сообщений (MPI, PVM и др.).
Параллельные задания могут обрабатываться на массивно-параллельных компьютерах (МРР) и кластерах, которые, как правило, используются коллективно и для которых характерна множественность заданий и ресурсов. Процесс управления, называемый диспетчеризацией, заключается в автоматической обработке множества заданий и включает определение для каждого из них времени запуска и доступных исполнительных ресурсов (планирование), доставку входных файлов на исполнительный узел, мониторинг выполнения задания и доставку результата его выполнения. Одним из основных требований к управлению заданиями является гарантирование запуска, которое обеспечивается планированием.
В сравнении с обычными однопроцессорными заданиями управление параллельными заданиями значительно сложнее: необходимо под-
1 Институт прикладной математики им. М.В. Келдыша Российской академии наук, 125047, Москва, Миусская пл., 4; тел. (495) 250-79-82, (495) 250-79-01. e-mail: kvn@keldysh.ru, dms@keldysh.ru.
бирать исполнительные ресурсы так, чтобы все компоненты задания стартовали одновременно -это так называемая задача коаллокации ресурсов [1, 2]. К настоящему времени для современных параллельных архитектур и кластерных систем разработаны методы, решающие эту задачу, Их обзору посвящен первый раздел. Рассматриваемая нами постановка задачи коаллокации в гриде и наиболее значимые, усложняющие ее свойства грида приводятся во втором разделе.
В данной работе мы предлагаем решение задачи управления параллельными заданиями в гриде - инфраструктуре глобально распределенных вычислительных ресурсов, интегрирующей множество кластеров в единую операционную среду. Решение опирается на метод опережающего планирования [3], примененный нами ранее для управления однопроцессорными заданиями в программном комплексе GrAS (Grid Advanced Scheduler) [4]. Метод основан на построении плана распределения ресурсов на некоторый период времени вперед и гарантировании его выполнения за счет использования механизма предварительного резервирования, с помощью чего обеспечивается детерминированность планирования. Это позволяет применить его для обслуживания параллельных заданий в гриде.
Формальная постановка задачи планирования в гриде, предполагающая совместное использование ресурсов с их владельцами, приведена в заключительной части второго раздела. При планировании в гриде существенно, каким образом
учитываются задания, находящиеся в локальных очередях кластерных ресурсов. Предлагаемый способ учета основан на экономическом подходе, а формализация планирования опирается на представление плана в виде множества временных слотов, где каждый слот соответствует началу и концу некоторого кластерного задания. Планирование заключается в подборе слотов, удовлетворяющих его ресурсному запросу и подходящих по стоимости, которые можно синхронно выделить в количестве, необходимом заданию. В локальных системах для подбора слотов используется алгоритм коал локации метода Backfill [5], прямое применение которого в условиях грида, как показано в третьем разделе, не дает линейной оценки сложности, зависящей от количества слотов. Основной результат работы приведен в четвертом разделе и заключается в построении алгоритма коал-локации с такой сложностью.
1. МЕТОДЫ ПЛАНИРОВАНИЯ
ПАРАЛЛЕЛЬНЫХ ЗАДАНИЙ В ЛОКАЛЬНЫХ МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ
К настоящему времени для многопроцессорных компьютеров и кластеров разработан ряд методов, с помощью которых решается задача планирования параллельных заданий, большая часть которых описана в работах [5-9]. Эти методы принято разделять на две группы. Методы первой группы используют разделение времени процессоров (time-sharing) между несколькими заданиями. Это означает, что сразу несколько заданий в произвольный момент времени могут разделять одни и те же вычислительные ресурсы. Основная проблема методов этой группы состоит в том, что компоненты одного задания могут быть прерваны и перезапущены в различные моменты времени, что приводит к сильному снижению общей эффективности использования ресурсов. В локальных системах положение может быть улучшено применением метода комплектного планирования (Gang scheduling), подробно рассматриваемого в работе [9], тем не менее в условиях грида временное разделение ресурсов представляется мало перспективным.
Вторая группа методов планирования основана на идее разделения пространства ресурсов (space-sharing) между заданиями, согласно которой каждое задание получает необходимый объем ресурсов на требуемое время в эксклюзивном режиме.
Методы пространственного разделения ресурсов
Простейшим методом пространственного разделения ресурсов является метод FCFS (First Come First Served) [7], согласно которому задание, поступившее в очередь раньше других, имеет самый высокий приоритет и, следовательно, должно быть запущено первым. Если для его запуска ресурсов оказывается недостаточно, ожидается момент времени, когда накопится требуемый ему объем свободных ресурсов, затем оно будет запущено. Метод гарантирует запуск параллельного задания, однако неэффективно использует ресурсы: в период их накопления для запуска самого приоритетного задания часть из них простаивает. Согласно имеющейся статистике [10], загрузка ресурсов в этом случае составляет примерно 50-60%. По этой причине метод FCFS в чистом виде практически не используется, а применяются его модификации, способные лучше загружать ресурсы.
Модификация «первый подходящий» (First-Fit) метода FCFS допускает нарушение порядка очереди, позволяя низкоприоритетным заданиям занимать ресурсы, оставшиеся незагруженными. Это повышает эффективность их использования, однако приводит к тому, что большая часть процессоров занимается мелкими заданиями -возникает фрагментация ресурсов. Так, даже если задание имеет самый высокий приоритет, необходимый ему объем ресурсов может никогда не образоваться и, следовательно, задание может никогда не стартовать - возникнет эффект «зависания» (starvation). Типовой способ решения этой проблемы заключается в ограничении числа низкоприоритетных заданий, способных «обогнать» более приоритетные задания. Это позволяет достичь компромисса между предотвращением зависания заданий и эффективностью использования ресурсов, но требует в каждом конкретном случае подбирать число обгонов, которым необходимо ограничиваться для эффективной работы метода.
Более аккуратный способ решения предлагает метод обратного заполнения (Backfill), изначально разработанный для массивно-параллель-ных систем типа IBM SP2 [5], а в настоящее время достаточно широко применяющийся на практике, в том числе и в кластерных системах. В отличие от FCFS он требует от пользователей оценку времени выполнения их заданий, что позволяет выделять ресурсы заданиям не непосредственно в момент освобождения, а заблаговременно. Для этого строится план распределе-
ния ресурсов - расписание запусков заданий. При построении расписания ресурсы выделяются заданиям в порядке их приоритетов, причем задание могут получить некоторые ресурсы только при условии, что они уже не отведены более приоритетным заданиям (в консервативном варианте) или самому приоритетному заданию (в агрессивном варианте). Это обеспечивается тем, что в процессе планирования для высокоприоритетных заданий производится предварительное резервирование ресурсов - создаются объекты, состоящие:
- из множества зарезервированных ресурсов,
- времени действия резервирования;
- прав доступа, определяющих, для каких заданий доступны зарезервированные ресурсы.
Важно отметить, что в методе ВаскГШ достигается компромисс между двумя конфликтующими друг с другом целями: повышением эффективности использования ресурсов путем заполнения «дырою» в расписании мелкими заданиями и предотвращением зависания больших заданий - прогнозированием их запуска.
2. УПРАВЛЕНИЕ ПАРАЛЛЕЛЬНЫМИ ЗАДАНИЯМИ В ГРИДЕ
Как показано в предыдущем разделе, задача управления параллельными заданиями успешно решается для массивно-параллельных компьютеров (МРР) и кластерных систем, однако в условиях грида она усложняется и для ее решения требуются новые подходы.
2.1. Свойства грида
Среди наиболее значимых отличительных свойств грида, усложняющих задачу коал локации, можно выделить следующие.
Автономность ресурсов. Грид формируется из ресурсов, принадлежащих различным организациям, их подразделениям или отдельным пользователям, осуществляющим собственную политику управления этими ресурсами. Это предполагает возможность использования ресурсов их владельцами для собственных нужд, поэтому необходимо, чтобы выделение ресурсов для заданий грида не противоречило существующей политике управления этими ресурсами.
Гетерогенно
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.