Планировщики и алгоритмы планирования задач на многопроцессорных комплексах Князев Н. Студент 5го Курса, научный руководитель А.Н. Сальников Спецсеминар факультета ВМиК МГУ "Системы параллельной обработки экспериментальных данных с использованием нейросетей и генетических алгоритмов" под руководством Л. Н. Королева, Н. Н. Поповой и А. Н. Томилина.

Sheduler Планировщик задач (сервис)Планировщик задач (сервис) сервис операционной системы, позволяющий пользователям планировать задачи. Планировщик задач программа, которая запускает другие программы в зависимости от различных критериевпрограмма Scheduling is the process of deciding how to commit resources between a variety of possible tasks.

Схема Планирования Пользователи Система пакетной Обработки Задачи Ресурсы Суперкомпьютера Где и что запустить Результат

Планирование Определяет исполнительные ресурсы, на которых будет выполняться каждое задание, и Время, когда исполнительные ресурсы отводятся тому или иному заданию Цель планирования – обеспечить скоординированное разделение ресурсов, учитывающее интересы пользователей, и владельцев ресурсов. Задача планирования представляет интерес как самостоятельное исследовательское направление, которому посвящено большое количество публикаций

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

Проблема малых заданий Одна из наиболее трудных проблем планирования – коаллокация: синхронное выделение ресурсов в нескольких кластерах для многопроцессорных заданий Простые алгоритмы приоритетного планирования не способны обеспечить запуск заданий, требующих большого количества ресурсов, независимо от приоритета: Причина заключается в фрагментации ресурсного пула из-за того, что ресурсы постоянно выделяются более мелким заданиям. Для предотвращения зависания многопроцессорных заданий необходимо каким-то образом накапливать ресурсы для них. Лучший на сегодня алгоритм для планирования многопроцессорных заданий – алгоритм обратного заполнения BackFill

Схема опережающего планирования 1. Цикл планирования: { 2. Получение стоящих в очереди заданий; 3. Получение расписаний всех кластеров(ресурсов); 4. Цикл размещения заданий: { 5. Построение аллокации для задания; 6. Если время начала аллокации близко: 7. { резервирование; доставка задания в кластер(системе запуска);} }

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

Сравнение расписаний В общем случае функция полезности является линейной функций от N параметров вида: F = - (C1*x1 + C2*x CN*xN), где C1,...,CN - некоторые константы, играющие роль весовых коэффициентов. Наилучшее времени выполнения, пользователя может интересовать выполнение своего задания за наименьшую плату, тогда функция полезности может выглядеть следующим образом: F = - (2*FinishTime+5*JobCost). Обычно при использовании использующих алгоритма Backfill, функция полезности по умолчанию задана как F = - StartTime

Backfill в MAUI Maui работает итерационно, т.е. перемежая процесс планирования с ожиданием или выполнением внешних команд. Каждый цикл начинается при осуществлении одного из следующих событий: меняется состояние задания или ресурса достигнута граница резервирования получена внешняя команда с начала предыдущего цикла прошло время, определенное как максимальное.

Запуск заданий До тех пор, пока это возможно, упорядоченные по приоритетам задания берутся из очереди и запускаются (попутно создается job резервирование); как только очередное задание нельзя запустить из-за нехватки ресурсов для него, определяется ближайшее время, возможного запуска, и начиная с него создается job резервирование затребованных ресурсов на все время. Как только задание запускается, то сразу, на все время исполнения, создается job резервирование, закрывающее доступ к ресурсам, для этого задания, всем, кроме него самого. Эти ресурсы могут не использоваться, однако как только они потребуются заданию, оно их получает.

Алгоритм Backfill в MAUI 1. Получая сведения от СПО о машинах, стартовавших/закончившихся заданиях, конфигурации системы, Maui обновляет свою внутреннюю информацию о состоянии ресурсов. Корректируются сделанные резервирования, исходя из обновленной информации о занятости узлов. На этой же фазе запускаются те ожидающие задания, время действия job резервирований, при составлении которых в частности принимаются смотрится запрашиваемые ресурсы для которых уже наступило. ИЗ всего количества заданий, в очереди, отбираются те, которые готовы к запуску. При этом принимаются во внимание такие аспекты, как состояние задания (задержано оно или нет), достаточно ли ресурсов всего кластера для запуска этого задания и т.п. Отсеиваются задания в соответствии с политикой кластера. Задания сортируются по приоритетам Последовательно получая задания из списка, Maui запускает, пока это возможно (создавая job резервирования), Если текущее задание с наибольшим приоритетом не может быть запущено из-за недостатка свободных ресурсов на время walltime, то когда это сделать будет возможно, создается job резервирование. Задания под которые не сделано резервирований алгоритм backfill пытается пристроить на оставшиеся свободными ресурсы.

Планировщики задач Portable Batch System(PBS). Sun Grid Engine (SGE). LoadLeveler MAUI

Portable Batch System(PBS). Используется устанавливаемый по умолчанию планировщик FIFO. OpenPBS и PBSPro – открытая и коммерческая версия. penPBSPBSPro Terascale Open-source Resource and QUEue Manager – новая версия PBS, на основе OpenPBS. В TORQUE улучшена маштабируемость(до 2500 узлов), интерфейс, логгирование, устойчивость к сбоям, также имеется планировщик - pbs_sched Torque используется как система управления заданиями (resource manager) совместно с планировщиком, делающим запросы к нему, в качестве планировщика чаще всего используют MAUI. Как и в других СУПО планировщик PBS умеет выравнивать загрузку узлов (Loadleveling), опираясь на текущие полученные от ОС значения. Кроме того, в PBS отличается ориентацией в сторону распределения по текущему состоянию ресурсов.

Sun Grid Engine (SGE). Sun Grid Engine - свободно распространяемая версия, для управления ресурсами одного проекта или подразделения. Sun Grid Engine SGE имеет лучший планировщик чем старая OpenPBS, лучше относится к загрузке большим потоком малых задач. В отличие от PBS не имеет развитого API для запуска и управления процессами, поэтому "тесная интеграция" ее с MPI приложениями обычно невозможна. PBS может чистить все MPI-процессы после аварийного завершения задачи, а SGE -- нет, в ней запущенные mpirun дочерние процессы остаются неубитыми. Sun Grid Engine, Enterprise Edition (SGEEE) - коммерческая версия, предназначенная для управления ресурсами предприятий (campus grid) Включает модуль для определения политики разделения ресурсов между независимо работающими пользователями. Для каждого пользователя определяется квота от общего количества ресурсов, в соответствии с которой происходит их распределение между запущенными заданиями.

LoadLeveler Продукт компании IBM, предназначенный для пакетной обработки последовательных и параллельных заданий на кластерах и суперкомпьютерах Текущая версия дополнена рядом новых характеристик, таких как новые планировщики; механизм поддержки контрольных точек; Последняя версия планировщика содержит также улучшенное восстановление буфера заданий - эта функция используется для восстановления записей заданий из буфера, когда исходный управляющий процесс LoadL_schedd недоступен. Новая схема взаимодействия, разработанная для улучшения масштабируемости и производительности при запуске заданий, она включает поддержку нескольких главных заданий в планировщике BACKFILL. Планировщик определяет недостаток необходимых ресурсов для выполнения задания и рассчитывает ближайшее время освобождения этих ресурсов. Функция дополнительного планирования, которая позволяет TWS LoadLeveler дополнительно планировать выполнение нескольких шагов заданий, устанавливая минимальные ограничения на тип и число необходимых ресурсов.

MAUI Внешний планировщик, который может использоваться взамен штатных планировщиков для нескольких СПО: PBS, SGE, Loadleveler, LSF, Wiki. MAUI представляет большой интерес в связи с тем, что это единственная из свободно распространяемых СПО, способная обеспечивать автоматический запуск многопроцессорных заданий, избегая при этом неоправданного простоя ресурсов. Алгоритмы обратного заполнения (backfill) и справедливого распределения ресурсов (fairshare) Улучшенная диагностика проблем с заданиями, узлами и программными компонентами СПО. Расширенный спектр статистики.. В Maui есть возможность моделирования работы СПО Это позволяет подобрать конфигурацию системы, наиболее полно отвечающую требованиям/ Интерфейсы для внешнего или, так называемого, административного резервирования. В такой изолированности резервирования от остальной части СПО, есть недостатки – необходимо координировать действия по резервированию и управления заданиями, очередями и узлами, но это, наверное, дело будущего.

Сравнение ПараметрPBS+Maui+Torqu e SGELoadLevelerМВС-1000 ОткрытостьOpen SourceОтрытая и закрытая версия Коммерческий продукт Закрытая разработка APIЕстьесть Приоритеты у задач Есть для работНетЕстьЕсть по времени Политика запуска Предварительно е резервирование BackFill Назначение задачем необходимых производительн ости. Классы Работ и устройств- где что может запускаться 3 типа задач. Запуск с учетом расположени я ресурсов нет

Литература 1. ИССЛЕДОВАНИЕ ВОЗМОЖНОСТИ ИСПОЛЬЗОВАНИЯ ПЛАНИРОВЩИКА Maui В СОСТАВЕ СУПЗ МВС-1000 А.В. Баранов, Д.М. Голинка 2. Tivoli Workload Scheduler LoadLevelerUsing and Administering 3. Maui Administrator's Guide 4. Workload Management: SP and Other RS/6000 Servers Janakiraman Balasayee, Bruno Blanchard, Subramanian Kannan, Akihiko Tanishita (LoadLeveler) 5. Programming Interfaces Guide SunMicrosystems, Inc. (SGE) 6. System Interface Guide Sun Microsystems, Inc. (SGE) 7. Управление заданиями в распределенной среде и протокол резервирования ресурсов ИПМ им. М.В.Келдыша РАН Москва, TORQUE Administrator Manual 9. Руководство пользователя системы МВС-1000/RSC4. Авторы: А.В. Баранов О. Лацис С.В. Сажин М.Ю. Храмцов

Вопросы?