Содержание к диссертации
Введение
Глава 1. Особенности построения современных систем планирования задач в распределённых системах 8
1.1. Анализ предметной области и обзор научных публикаций 8
1.1.1. Основные типы распределённых систем обработки 8
1.1.2. Системы управления ресурсами и планировщики заданий 14
1.1.3. Свойства задач и ресурсов в распределённых системах 20
1.1.4. Методы планирования использования ресурсов и выполнения задач 21
1.2. Анализ распространённых промышленных планировщиков заданий и систем управления ресурсами 27
1.2.1. Система HTCondor 27
1.2.2. Система DIET 30
1.2.3. Программный стек ProActive 32
1.2.4. Системы управления ресурсами Slurm и Torque 34
1.2.5. Планировщик Moab 35
1.2.6. Планировщик Maui 38
1.3. Выводы 41
Глава 2. Использование метаданных для планирования в РСОД 42
2.1. Классификация метаданных 42
2.2. Создание и хранение мультимедийных метаданных 44
2.3. Связь между метаданными и ресурсными требованиями 48
2.4. Поиск близких задач 52
2.5. Выводы 58
Глава 3. Разработка теоретических основ планирования задач в РСОД 59
3.1. Математическая модель планирования задач в РСОД 60
3.2. Метод планирования задач в РСОД на основе метаданных и ресурсных метрик 65
3.2.1. Вычисление ресурсных затрат выполнения на основе ресурсных метрик 67
3.2.2. Оценка ресурсных затрат на выполнение на основе метаданных 69
3.2.3. Вычисление матрицы назначения 71
3.3. Модификация алгоритма поиска ближайших соседей на основе метода локализованного хэширования 72
3.4. Методика планирования задач на основе метаданных и ресурсных метрик 76
3.5. Выводы 80
Глава 4. Экспериментальная оценка эффективности предложенного метода 81
4.1. Архитектура программной системы 81
4.2. Задача декодирования видео данных 87
4.2.1. Описание задачи 87
4.2.2. Инфраструктура и метаданные 88
4.2.3. Жизненный цикл метаданных 93
4.2.4. Оценка вычислительных затрат 96
4.2.5. Обработка результатов эксперимента 99
4.3. Задача обработки гидрографических данных 114
4.3.1. Задача построения карт высот 114
4.3.2. Планирование задач обработки гидрографических данных 116
4.4. Выводы 123
Заключение 125
Литература 127
- Методы планирования использования ресурсов и выполнения задач
- Связь между метаданными и ресурсными требованиями
- Метод планирования задач в РСОД на основе метаданных и ресурсных метрик
- Жизненный цикл метаданных
Методы планирования использования ресурсов и выполнения задач
Под грид системой (от англ. grid - сетка) или метакомпьютером понимают сеть гетерогенных вычислительных ресурсов, географически распределённых, используемых для параллельной обработки вычислительных задач [1]. Грид представляет собой программно-аппаратную инфраструктуру для разделяемого использования вычислительных узлов, сетей, баз данных и других ресурсов, которые находятся в юрисдикции различных географически распределённых организаций [2]. Для управления ресурсами используется промежуточное ПО, причём управление как правило - децентрализованное.
Отличительными свойствами грид систем являются [3]:
1. Распределенность компонентов - узлы системы могут находиться в географически удалённых друг от друга регионах, что сказывается на оперативности взаимодействия;
2. Метакомпьютер может динамически менять конфигурацию - система поддержки прозрачно для пользователя производит распределение задач по компонентам системы с учётом динамического подключения/отключения удалённых ресурсов: 3. Неоднородность системы - в состав грид системы могут входить узлы с различным составом программно-аппаратных ресурсов;
4. Метакомпьютер объединяет ресурсы различных организаций, каждая из которых может иметь собственную политику доступа к ресурсам.
С точки зрения пользователя отличительной чертой таких систем является отсутствие контроля над множеством задач обрабатываемых на каждом конкретном узле. Кроме того заранее неизвестно, какими ресурсами будет располагать система в определённый момент. Также важной отличительной чертой является нацеленность грид систем на решение вычислительно трудоёмких научных задач.
Облачные вычисления - общий термин для целого ряда сетевых сервисов, предоставляемых по требованию, для которых наиболее характерными являются следующие свойства [4]:
1. Самообслуживание по-требованию - клиент имеет возможность получить доступ к вычислительным ресурсам в любой момент без необходимости человеческого вмешательства со стороны провайдера.
2. Сервисы предоставляются по сети стандартными механизмами и нацелены на использование на гетерогенных клиентских платформах (ноутбуках, мобильных устройствах, рабочих станциях).
3. Объединение физических ресурсов (серверов, устройств хранения данных, сетей и пр.) на стороне поставщика сервисов в единый пул, что позволяет их динамически перераспределять в условиях постоянно изменяющегося спроса.
4. Эластичность - услуги (или динамическая расширяемость) могут быть предоставлены, расширены или сужены по требованию в любой момент времени, зачастую в автоматическом режиме. Для конечных клиентов данное свойство позволяет получать сервисы с высоким уровнем доступности.
5. Оплата услуг выполняется исходя из учёта затраченных ресурсов. Облачные сервисы могут предоставляться в соответствии со следующими моделями обслуживания [5]:
1. Программное обеспечение как услуга оаао, англ. Software -as-a- Service) -модель в которой пользователь абстрагируется от всех деталей поддержки приложения: аппаратного обеспечения, распределенности данных, используемых программных средств и др., - и получает в качестве услуги готовое к использованию программное обеспечение, предоставляемое по сети. Наиболее характерным примером таких услуг могут выступать сервисы предоставления или обработки данных, которые доступны как SOAP или REST веб-сервисы, и могут использоваться программным способом.
2. Платформа как услуга (PaaS, англ. Platform-as-a-Service) - модель, в которой пользователь абстрагируется от аппаратной части поддержки приложения и получает возможность управлять заранее подготовленным набором информационно-технологических платформ: операционными системами, базами данных, средствами разработки и тестирования и др., - и имеет возможность устанавливать и использовать собственное прикладное программное обеспечение.
3. Инфраструктура как услуга ( laao, англ. IaaS or Infrastructure-as-a-Service) - модель, в которой клиент предоставляется возможность управлять виртуальными ресурсами - виртуальными машинами, виртуальными сетями, а также балансировкой нагрузки, межсетевыми экранами и пр. Поставщик услуги предоставляет гибкие механизмы доступа к пулу ресурсов, а также хранения и перенастройки заранее сконфигурированных виртуальных машин.
Связь между метаданными и ресурсными требованиями
Разработчики системы планирования Maui выделяют три основные области, для которых осуществляется принятие решений с использованием политик [23]:
1. Управление трафиком. Необходимо исключать ситуации соревнования задач за одни и те же ресурсы, поскольку это, как правило, снижает общую производительность кластера, увеличивает время выполнения таких задач, и может приводить к отказам.
2. Политики целевого использования. Кластеры и иные высокопроизводительные платформы создаются для выполнения определённых прикладных задач. В целях эффективности планирования планировщик должен позволять учитывать бизнес-правила по использованию системы в процессе планирования.
3. Любые оптимизации, которые можно применить в процессе планирования для повышения производительности в обработке задач.
Информация о задачах обработки поступает из таких систем управления ресурсами как Loadleveler, PBS, Wiki, или LSF, и содержит: 1. Атрибуты: владелец задачи, состояние задачи и пр. 2. Ресурсные требования: количество и временной интервал на который требуется тот или иной ресурс. Каждое требование на ресурс включает в себя также список условий, которые ВСЕ должны быть удовлетворены, чтобы узел-обработчик был выбран.
Под узлом-обработчиков в системе Maui подразумевается набор ресурсов, каждый с множеством связанных атрибутов. Как правило, узел-обработчик -это один или несколько процессоров, память, и, возможно, множество дополнительных ресурсов, таких как дисковое пространство, область подкачки, сетевые интерфейсы, программные лицензии и т.д. Дополнительно узел описывается такими атрибутами как тип архитектуры или операционная система.
Информацию об узлах, включая количество доступных ресурсов и состояние узлов, поступает к планировщику исключительно от системы управления ресурсами. Под ресурсами в системе Maui понимается тот же список что и в системе Moab (см. 1.2.5). Для применения политик планирования к задачам обработки используется понятие класса. Класс задачи задаётся с помощью системы выделения ресурсов и может быть ассоциирован с одним или несколькими атрибутами или ограничениями: 1. Атрибуты задачи (длительность задачи, её размер, ресурсные требования); 2. Ограничения на множество рабочих станций - класс задач может обрабатываться только на заранее заданном множестве узлов-обработчиков; 3. Ограничения на свойства поступающей задачи - минимальное количество процессоров, время поступления задачи и т.п. 4. Список доступа - в соответствующую очередь поступает лишь класс задач, для которых выполняются требования контроля доступа (поступают только задачи от определённых пользователей или групп).
Соответственно для каждого класса выделяется отдельная очередь обработки. Maui отслеживает использование классов как потребляемого ресурса, что даёт возможность проектировщикам системы создавать политики использования в зависимости от типов задач.
Пример политики выполнения задач: - не более 8 задач любого типа можно запускать одновременно, - не более 4 задач от группы административных пользователей могут одновременно выполняться в системе.
Шаги, которые планировщик Maui выполняет на каждой итерации планирования полностью эквивалентны тем, которые используются в планировщике Moab (см. 1.2.5).
Одним из достоинств системы для конечного пользователя является поддержка резервирования ресурсов с указанием интервалов времени и списка доступа, что особенно важно для предоставления гарантий качества обслуживания QoS.
Главные недостатки используемого в планировщике Maui подхода к планированию: 1. Необходимо знать ресурсные требования задачи априори, что не всегда возможно; 2. Как правило, требуется задать условия выбора узла-обработчика; 3. Задачи необходимо заранее разбить на классы в зависимости от значений их атрибутов, параметров контроля доступа и пр. 4. На основе заданных классов необходимо заранее определить политики выбора очереди запуска. Такая избыточность ручного конфигурирования приводит к существенным временным затратам на стадии проектирования системы.
Метод планирования задач в РСОД на основе метаданных и ресурсных метрик
Таким образом, метаданные, которые задают трудоёмкость операции декодирования, формируются исходя из свойств исходного видео файла, класса устройства воспроизведения (иными словами - его аппаратных возможностей) и пропускной способности сетевого соединения. К примеру, даже если устройство способно воспроизводить видео высокого разрешения, нет смысла предоставлять такой видео поток при низкой пропускной способности сети, поскольку это может привести к появлению джиттера (jitter).
После преобразования метаданных сервис добавляет новое задание в очередь планировщика: add_task( data ). Планировщик (Scheduler) выполняет назначение заданий на узлы-обработчики (Cluster node): assign_task(task_data). Узел-обработчик выполняет декодирование видео данных, а на клиентское устройство передаётся URL, по которому можно получить доступ к выходному видео потоку.
Далее рассмотрим подробнее процесс назначения вычислительных ресурсов на поступившие задачи обработки данных.
Анализ литературы в главе 1 показал, что наиболее распространённый метод распределения заданий по узлам-обработчикам заключается в использовании приоритетной очереди FIFO (First In First Out) и выделения наименее нагруженного узла под новые задания LLF (Least Loaded First).
Данный метод (FIFO_LLF) будет использован в качестве основы для сравнения, поскольку так же как и метод планирования на основе метаданных (метод Meta_Sched) он не требует априорных знаний о ресурсных требованиях. Кроме того, данный метод используется для накопления предыстории экспериментов для метода Meta_Sched.
Метод Meta_Sched требует построения модели, позволяющей прогнозировать оценку вычислительных затрат для новых заданий, на основе собранной статистики запуска. В результате выполнения заданий, помимо получения результатов декодирования, производится сбор метрик загрузки вычислительных ресурсов и их сохранение в базу данных. На Рисунке 4.7 приведён пример метрик (metrics), полученных в результате выполнения задания. Каждая запись также хранит метаданные задачи и свойства узла-обработчика.
Решаемая задача декодирования видео относится к вычислительно ёмким, то есть требовательна к процессору W\ = 1, в то время как потребление памяти остаётся незначительным W2 = 0.3. Функции cpu_cost и ram_cost оценивают затраты для отдельных ресурсов, при этом учитывается является ли ресурс не до конца загруженным или перегруженным.
Оценка ресурсных затрат для новых пар задач и вычислительных узлов (t, к) осуществляется следующим образом. Наличие метаданных позволяет найти в предыстории Ghist близкие пары G hist.near-est и оценить ресурсные затраты. Для этого используется алгоритм поиска предложенный в разделе 3.3.
При этом выбор корзины в хэш таблице основан на значениях значимых категориальных аттрибутов. Для задачи декодирования видео данных значимыми являются атрибуты ffrnpeg preset, 1і264 profile, 1і264 level, которые определяют качество выходного видео потока.
При вычислении расстояния до всех объектов-кандидатов из полученной корзины по-атрибутные расстояния взвешиваются исходя из значимости каждого численного атрибута.
В результате оценки ресурсных затрат для всех заданий и узлов обработчиков строится матрица ресурсных затрат. Полученная матрица ресурсных затрат позволяет решить задачу о назначениях и получить матрицу назначения, в соответствии с которой задачи обработки данных будут разосланы по узлам-обработчикам.
Для сравнения методов планирования задач распределённая система обработки данных тестируется в различных условиях. Сценарии, на которых проверяется производительность методов планирования отличаются распределением трудоёмкости входного потока заданий и степенью нагрузки на систему.
Построенная распределённая система обработки данных выполняет планирование и обработку задач декодирования видео в течение 10 минут для каждого сценария. Затем, по результатам собранной статистики качество работы методов планирования FIFO_LLF и Meta_Sched оценивается по следующим
Жизненный цикл метаданных
Поскольку для оценки стоимости использовалась только метрика, отражающая затраченное время (elapsed_seconds), в приведенной таблице ценность представляют лишь строки с этой независимой переменной. Как можно видеть повышение количества потоков обработки (threads) сопровождается понижением времени обработки (коэффициент корреляции -0.58), а увеличение разрешения (output_resolution) выходной карты высот сопровождается повышением времени обработки (коэффициент корреляции 0.68). Хотя значения коэффициентов корреляции не могут служить для установления причинно-следственной связи между явлениями, наличие высокой положительной или отрицательной корреляции является необходимым (но недостаточным) условием такой связи.
После того как выбраны атрибуты, необходимо определить способ поиска ближайших пар {thist, khist) из предыстории выполнения Gust к новой паре (t, к). Для эффективного поиска предлагается использовать структуру данных kdree [63], которая позволяет осуществлять поиск ближайших соседей в среднем за О{1од{п)) время. При этом, для вычисления расстояния D{ta,tb) между двумя точками структура данных kdree использует евклидово расстояние.
После того как для каждой задачи t найдены ближайшие соседи G hist.near-est (в данной реализации ищутся 3 ближайших соседа), ресурсные затраты выполнения задачи на заданном узле с находится как среднее значение ресурсных затрат ближайших пара (задача, вычислительный узел).
Повторив данную процедуру для всех новых задач получена матрица стоимости С, которая используется для решения задачи о назначениях одним из существующих алгоритмов комбинаторной оптимизации. В данной реализации используется алгоритм Джеймса Манкреса [52] решения задачи о назначениях.
В результате работы алгоритма строится матрица назначения W: на основе которой выполняется непосредственно сам запуск задач на выполнение на узлах обработчиках.
Для сравнения по производительности был проведён ряд экспериментов как при использовании предлагаемого метода планирования, который учитывает зависимость между атрибутами прикладных задач и загрузкой ресурсов, так и при использовании метода без учёта такой зависимости. Иными словами альтернативный метод в плане учёта атрибутов прикладных задач выполняет случайное назначение ресурсов на задачи обработки.
Результаты проведения экспериментов можно видеть на Рисунке 4.24.
По оси х отображается номер эксперимента, а по оси у время выполнения для обоих методов планирования в минутах: зеленым цветом обозначено затраченное время при использовании предложенного метода планирования, красным - при использовании метода без учета атрибутов задач. Кроме того на графике для каждого отдельного эксперимента приведён полученный при 121 10, 8 I I 179 2 13
Предложена программная архитектура системы планирования задач в РСОД, реализующая предложенный метод планирования на основе метаданных и ресурсных метрик.
На основе предложенной программной архитектуры реализована программная система планирования в РСОД для задач декодирования видео данных и задач обработки гидрографических данных. Проведён цикл экспериментов по планированию заданий декодирования видео данных при различных условиях распределения трудоёмкости заданий и интенсивности вычислительной нагрузки с использованием предлагаемого метода планирования и метода FIFO/Least Loaded First (FIFO_LLF). Анализ результатов эксперимента показывает следующее:
. Суммарное время нахождения заявок в системе при использовании метода планирования на основе метаданных сокращается на 20% по сравнению с методом FIFO_LLF при высокой интенсивности поступления задач в систему, но возрастает на 4.5% при средней интенсивности и на 10.7% при слабой интенсивности. . Среднее время ожидания обработки заявок при использовании метода планирования на основе метаданных сокращается на 7.58% по сравнению с методом FIFO_LLF при высокой интенсивности поступления задач в систему, но возрастает на 10.55% при средней интенсивности и на 70.6% при слабой интенсивности. Такие результаты объясняются следующими причинами:
Увеличение интенсивности поступления заявок также увеличивает объём данных предыстории, что оказывает влияние на качество прогнозирования. . При невысокой интенсивности поступления заявок значительная часть вычислительных ресурсов простаивает. Метод планирования FIFO_LLF отдаёт предпочтение наименее загруженным вычислительным узлам, в результате чего ресурсные требования задач оказываются удовлетворёнными. 4. Метод планирования на основе метаданных был применён к задаче обработки гидрографических данных и позволил сократить время выполнения задач в среднем на 10%.
