Планирование многопроцессорных заданий в грид Дмитрий Семячкин Институт прикладной математики им. М.В. Келдыша

Под многопроцессорным заданием понимается задание, состоящее из нескольких частей (подзаданий), которые в процессе выполнения могут взаимодействовать между собой, например, посредством сообщений Задача Необходимо планировать задания с синхронным выделением (коаллокация) для них ресурсов на нескольких узлах (кластерах) грид

Проблемы В условиях приоритетного обслуживания алгоритмы типа FCFS (FIFO) работают по принципу выделения освободившихся ресурсов самому приоритетному заданию из очереди, которое может на них разместиться. В условиях приоритетного обслуживания алгоритмы типа FCFS (FIFO) работают по принципу выделения освободившихся ресурсов самому приоритетному заданию из очереди, которое может на них разместиться. Даже если задание имеет самый высокий приоритет, необходимый ему объем ресурсов может никогда не образоваться и, следовательно, задание может никогда не стартовать, т.к. большая часть процессоров будет всегда занята мелкими заданиями (фрагментация ресурсов). Даже если задание имеет самый высокий приоритет, необходимый ему объем ресурсов может никогда не образоваться и, следовательно, задание может никогда не стартовать, т.к. большая часть процессоров будет всегда занята мелкими заданиями (фрагментация ресурсов). Как гарантировать запуск заданий?

Типовой способ Модификация алгоритма FCFS: при превышении некоторого времени ожидания необходимо блокировать все ресурсы, которые подходят для зависшего задания с высоким приоритетом => приводит к простою ресурсов Необходим более экономный способ

Локальные системы Используется алгоритм обратного заполнения Backfill, работающий по следующему принципу: Размещая наиболее приоритетное задание, он определяет момент времени, когда освободится достаточное количество ресурсов, занятых уже выполняющимися заданиями, и производит резервирование этих ресурсов. Задание с меньшим приоритетом может быть запущено вне очереди, но только в том случае, если оно не будет мешать запуску: всех более приоритетных заданий (в консервативном варианте алгоритма); всех более приоритетных заданий (в консервативном варианте алгоритма); самого приоритетного задания (в агрессивном варианте алгоритма). самого приоритетного задания (в агрессивном варианте алгоритма).

Текущая ситуация Как работает Backfill запущенные задания Очередь процессоры времятекущее время pr=25 pr=15 pr=9 pr=15

Подходы к коаллокации в грид EDG Resource Broker EDG Resource Broker Ориентирован на работу с однопроцессорными заданиями, в существующем варианте для решения задачи коаллокации ресурсов был бы вынужден блокировать часть ресурсов на неопределенное время, часть которого они будут простаивать Ориентирован на работу с однопроцессорными заданиями, в существующем варианте для решения задачи коаллокации ресурсов был бы вынужден блокировать часть ресурсов на неопределенное время, часть которого они будут простаивать Ursala Ursala Используется предварительное резервирование ресурсов, но реального механизма определения времени запуска заданий нет Используется предварительное резервирование ресурсов, но реального механизма определения времени запуска заданий нет Computing Center Software (CCS) Computing Center Software (CCS) Решается задача коаллокации для отчуждаемых ресурсов, (целиком отданных в грид) Решается задача коаллокации для отчуждаемых ресурсов, (целиком отданных в грид)

Грид-диспетчер (1) Через локальный менеджер ресурсов на ресурсы поступают два потока заданий: Через локальный менеджер ресурсов на ресурсы поступают два потока заданий: локальный локальный глобальный глобальный Соблюдение принципа автономии ресурсов: конкуренция локальных и глобальных заданий на основе сравнения их локальных приоритетов Соблюдение принципа автономии ресурсов: конкуренция локальных и глобальных заданий на основе сравнения их локальных приоритетов Локальный приоритет глобального задания может быть вычислен исходя из платы за задание или, например, времени его нахождения в очереди Локальный приоритет глобального задания может быть вычислен исходя из платы за задание или, например, времени его нахождения в очереди

Грид-диспетчер (2) Выделение ресурсов под глобальные задания должно быть заблаговременным, иначе ресурсы будут либо простаивать, либо будут заняты локальными заданиями Выделение ресурсов под глобальные задания должно быть заблаговременным, иначе ресурсы будут либо простаивать, либо будут заняты локальными заданиями Для этого необходимо, чтобы Грид-диспетчер располагал локальными расписаниями (план занятия ресурсов локальными заданиями на определенный период времени вперед, содержащий не только запущенные задания, но и задания из очереди) Для этого необходимо, чтобы Грид-диспетчер располагал локальными расписаниями (план занятия ресурсов локальными заданиями на определенный период времени вперед, содержащий не только запущенные задания, но и задания из очереди) Предложен способ построения локальных расписаний для каждого кластера путем моделирования Предложен способ построения локальных расписаний для каждого кластера путем моделирования

Глобальное расписание pr=21 Backfill для грид запущенные задания Глобальная очередь процессоры время pr=19 pr=12 pr=2 запланированные задания (стоящие в очереди) Плата: 202 pr=20 Плата: 110 pr=11 Плата: 57 pr=5

Шаги планирования Очередной шаг планирования происходит при фиксированном (на начало шага) множестве заданий в очереди и глобальном расписании Очередной шаг планирования происходит при фиксированном (на начало шага) множестве заданий в очереди и глобальном расписании Между шагами очередь перестраивается и обновляются локальные расписания кластеров Между шагами очередь перестраивается и обновляются локальные расписания кластеров На каждом шаге происходит: На каждом шаге происходит: построение глобального расписания для всех заданий из очереди построение глобального расписания для всех заданий из очереди резервирование ресурсов под задания, для которых пора начинать доставку файлов на исполнительные узлы резервирование ресурсов под задания, для которых пора начинать доставку файлов на исполнительные узлы инициирование доставки файлов на исполнительные кластеры для заданий, под которые зарезервированы ресурсы инициирование доставки файлов на исполнительные кластеры для заданий, под которые зарезервированы ресурсы

Состояние реализации Разработана модель данных для представления информации о состоянии кластеров грид и прогнозе их использования Разработана модель данных для представления информации о состоянии кластеров грид и прогнозе их использования Реализован алгоритм подбора ресурсов для задания (на одном шаге Backfill) Реализован алгоритм подбора ресурсов для задания (на одном шаге Backfill) Этот алгоритм протестирован с использованием модельной базы данных Этот алгоритм протестирован с использованием модельной базы данных

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

Контакты Институт прикладной математики им. М.В. Келдыша (ИПМ РАН) Коваленко Коваленко Шорин Шорин Березовский Березовский Семячкин Семячкин Россия, , Москва, Миусская пл. 4; тел. (095) Работы ИПМ в области грид доступны на: