Конференции ИВТ СО РАН

Тезисы докладов

Информационные технологии

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

Генетический алгоритм (Genetic Algorithm) представляет собой вариант стохастического поиска, в котором особи-преемники формируются путем изменения или комбинирования двух и более родительских особей. Под особью в данном случае подразумевается расписание заданий в GRID. Работа генетического алгоритма начинается с генерирования множества сформированных случайным образом особей, называемых популяцией. Каждая особь представлена в виде строки символов и классифицируется с помощью функции оценки, или (в терминологии ГА) функции пригодности (fitness function). Функция пригодности должна возвращать более высокое значение для лучших особей-расписаний.

Была выбрана следующая форма представление расписания для алгоритма. Закодированное расписание (хромосома) делиться на две логические части: заголовок и тело хромосомы. Заголовок представляет описание тела хромосомы в формате перечисления количеств процессов, которые планируется запускать на процессорах. Заголовок и тело хромосомы разделено служебным символом. Тело хромосомы состоит из нескольких блоков, каждый из которых представляет собой описание выполнения задач на одном конкретном процессоре в формате пары последовательных ячеек <идентификатор задачи, процессорное время>. Если в расписании есть "окна", в которых тот или иной процессор должен простаивать, то такая задача простоя имеет id равный нулю. Генами в данном случае будут являться пары <идентификатор задачи, процессорное время>. Таким образом наименьшей единицей, которой должны оперировать генетические операторы будет пара неделимых числовых значений.

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

Для описанной задачи критерий отбора реализуется функцией пригодности (приспособленности). Эта функция позволяет оценить особи в популяции на каждой из итераций и выбрать "лучшие" из них, которые будут включены в следующую популяцию (новое поколение). Для описания работы функции пригодности рассмотрим одну хромосому. На каждом из ее участков, описывающих последовательность заданий на одном конкретном процессоре, возьмем сумму значений процессорного времени каждой из "присутствующих" на этом процессоре задач. Максимальное значение всех полученных сумм является тем временным интервалом, в котором хотя бы один из процессоров будет недоступен для нахождения следующего расписания, ввиду загруженности задачами из предыдущего расписания.

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

Базовая часть алгоритма реализована на языке C++ и представляет собой исполняемую программу с CUI интерфейсом. На стандартном входе исполняемый файл получает (помимо численных параметров алгоритма) путь к директории, в которой располагаются файлы описания задач. Каждый файл описывает одну задачу пользователя. Все задачи равнозначны и не имеют приоритетов, то есть задача, поставленная в очередь первой будет рассматриваться с таким же приоритетом, что и поставленная в очередь последней на определенный момент времени. Входными данными алгоритма является множество описаний заданий с параметрами, описывающими требуемые параметры процессора, операционной системы, оперативную и постоянную память, и так далее.

Базовая часть алгоритма не представляла бы большого практического значения без ее интеграции с инструментарием GRID. Для этих целей был написан web-сервис WS-Geneur, работающий в окружении контейнера Globus Toolkit 4.x и являющийся, своего рода, интерфейсом к базовому модулю алгоритма. Необходимая информация о состоянии и параметрах ресурсов GRID-сети WS-Geneur получает от стандартного web-сервиса Globus Toolkit WS-MDS (Monitoring and Discovery System). Последний в свою очередь может черпать информацию у таких систем мониторинга ресурсов, как Ganglia или Nagios. На основании данной информации строиться таблица описания ресурсов. Она используется как при генерировании первой популяции, так и при работе фильтрующей функции, которая не дает образоваться заведомо противоречивым особям в популяции.

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

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск