Содержание к диссертации
Введение
Глава 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
Литература
- Свойства задач и ресурсов в распределённых системах
- Создание и хранение мультимедийных метаданных
- Метод планирования задач в РСОД на основе метаданных и ре сурсных метрик
- Инфраструктура и метаданные
Свойства задач и ресурсов в распределённых системах
Задание представляет собой сущность, которая поступает на вход системы планирования и состоит из набора задач (см. Рисунок 1.2). Поток задач поступает во входную очередь. Задачи являются атомарной единицей планирования и в рамках одного задания могут быть независимыми или организованы в дерево зависимостей.
Соответственно такие задачи или выполняются параллельно если они независимы, или последовательно при наличии зависимостей. Зависимости определяют порядок выполнения работ и потоки данных между задачами.
Поскольку в дальнейшем будут рассматриваться только независимые задачи, которые могут планироваться отдельно, между терминами задание и задача в данной работе не будет поставлено различий.
Проблема планирования задач обработки состоит из выделения ресурсов (узлов обработки) для задач и установления порядка в котором задачи из входной очереди будут выполняться на этих ресурсах [7].
Класс систем, в которых осуществляется централизованное управление ресурсами получил название системы управления ресурсами [8], который, как правило тесно интегрируется с системой планирования задач или планировщи-14
Система управления ресурсами и планировщик задач вместе представляют собой промежуточное программное обеспечение: с одной стороны оно должно управлять ресурсами (на низком уровне), а с другой - учитывать требования прикладных задач (описанных на высоком уровне). Для этого на этапе функционирования система выполняет мониторинг текущего состояния загруженности ресурсов и затем производит назначение свободных ресурсов на поступившую задачу [8].
Система управления ресурсами обычно включает в себя информационный сервис, отвечающий за сбор информации о состоянии выполнения задач и о состоянии ресурсов. Иногда данные функции на себя берёт сторонняя система мониторинга.
Для управления ресурсами и задачами планировщик, опираясь на данные, предоставляемые информационным сервисом, использует методы управления (планирования) задачами и ресурсами.
Метод или политика планирования задач (task scheduling policy) представляет собой набор правил, которые используются для определения когда и как выбирать новую задачу (процесс) на обработку [10]. В основе выбора задачи на исполнение лежит процедура сортировки задач в соответствии с их приоритетами.
Для планирования задач, как правило, используется та или иная дисциплина обслуживания. Выделяют дисциплины обслуживания, которые опираются на знания о ресурсных требованиях задачи и без априорных знаний, когда все задачи обрабатывают универсальным способом. Дисциплины обслуживания без априорных знаний [6]: 1. First in First Out, FIFO, - задачи обрабатываются в порядке поступления. 2. Last in First Out, LIFO, - задачи обрабатываются в обратном порядке. 3. Random Selection for Service (RSS), - задача выбирается случайным образом. 4. Time Sharing, с разделением времени - квант времени выделяется каждой задаче поочерёдно. 5. Least Attained Service - выбирается задача, получившая наименьшее время обслуживания. К недостаткам приведённых дисциплин обслуживания можно отнести следующее: 1. Они не стремятся подобрать узел соответствующий ресурсным требованиям; 2. Решают другую задачу: какую задачу из очереди выбрать первой для обработки в соответствии с приоритетом или другими критериями; 3. Предполагают однотипность задач в плане ресурсных требований (вычислительной и пространственной трудоёмкости); 4. Предполагают использование однотипных узлов-обработчиков (количество ресурсов на каждом узле одинаково). При использовании данных подходов ресурсы используются неэффективно в случаях, когда: 1. Узлы РСОД различаются по мощности (гетерогенность РСОД); 2. Задачи разнородны по вычислительной и пространственной (по памяти) сложности, и, следовательно имеют сильно отличающиеся ресурсные требования; 3. Узлы РСОД могут исполнять параллельно несколько задач. Если ресурсные требования заданы заранее, то могут применяться следу ющие дисциплины обслуживания [6]: 1. Shortest Job First (SJF), - выбирается задача с наименьшими ресурсными требованиями. 2. Shortest Remaining processing time, - выбирается задача, для которой оценённое время обслуживания минимально.
Данные дисциплины обслуживания учитывают разнородность задач, но требуют априорных знаний о ресурсных требованиях, которые не всегда доступны.
Другой аспект приведённых методов планирования задач – поддержка сохранения состояния выполнения задач, что позволяет прерывать выполнение текущей задачи и переключаться на выполнение другой (например более приоритетной). Такие методы как Time Sharing, Least Attained Service, Shortest Remaining Processing Time относятся к данному классу методов планирования задач, за счёт чего на каждом вычислительном узле могут находиться несколько задач на разных стадиях выполнения.
Реализация сохранения состояния задач широко применяется для планирования процессов в операционных системах, когда нескольким процессам выделяется последовательно квант процессорного времени для создания псевдопараллелизма. Вместе с тем такая стратегия привносит дополнительные накладные расходы и может быть неприемлема для прерывания вычислительно трудоёмких задач.
Создание и хранение мультимедийных метаданных
К примеру в статье [8] отмечается существование т.н. правил масштабирования, которые задают каким образом и в каких ситуациях приложение потребляет больше вычислительных ресурсов и требует масштабирования. Пользователи облачной среды имеют возможность задать правила, определяющие те действия, которые необходимо произвести (например запуск новой виртуальной машины) при превышении допустимых пороговых значений собираемых метрик.
Априорные же стратегии находят единственное решение о выделении ресурсов, которое считается оптимальным. Для достижения этого стратегия должна учитывать все переменные, которые могут влиять на способ выделения. К примеру, при выделении виртуальных машин, стратегия оптимизации должна предоставить решение (или множество возможных решений), которое удовлетворяет всем ограничениям и требованиям (минимизации времени или ресурсных затрат на выполнение) оптимальным способом.
Большинство существующих алгоритмов планирования задач исходит из предположения, что время выполнения приложения (задачи) известно заранее, ещё до выполнения [9]. Данное предположение существенно упрощает сопоставление задач и ресурсов, хотя и показало свою несостоятельность для многих реальных приложений. С другой стороны, существует целая группа прикладных приложений, для которых есть возможность мониторинга исполнения. Зачастую, когда существует корреляция между состоянием выполнения задачи и общим временем её выполнения, информация о текущем состоянии может выступать основой для прогнозирования оставшегося времени выполнения.
Многие из предложенных алгоритмов, которые выполняют оценку времени выполнения и прогнозирование загрузки ресурсов, основаны на статистических моделях [11].
Использование истории предыдущих запусков для построения моделей прогнозирования для кластерных и облачных платформ не является новой идеей [11]. Помимо автоматического масштабирования ресурсов, данные модели при-22 меняются совместно с генерацией синтезированной нагрузки для тестирования различных политик масштабирования.
Решения о масштабировании на практике безусловно не основываются лишь только на истории предыдущих запусков, т.к. необходимо принимать во внимание ресурсные затраты на выделение новых ресурсов, накладные расходы на миграцию задач и многие другие факторы.
Помимо методов управления ресурсами выделяют два различных типа планирования задач: статический и динамический. Статические стратегии определяют план на стадии планирования или выполняют запуск на основе информации о доступных узлах обработки и задач для запуска. В качестве цели статического планирования выступает минимизация ожидаемой длительности выполнения задач.
Динамические стратегии, с другой стороны, применяются в тех случаях, когда время прибытия неизвестно априори и потому система вынуждена назначать ресурсы по прибытию задач. В качестве цели динамического планирования может выступать как минимизация длительности обработки пакета задач, так и минимизация некоторой метрики производительности, отражающей качество предоставляемого сервиса (QoS).
Динамический подход к планированию означает, что планировщик способен менять стратегию планирования при появлении новых задач и освобождении узлов обработки.
При статическом планированиии, которое, как правило, выполняется на этапе подготовки запуска, характеристики параллельной программы (время обработки задач, зависимости данных, требования синхронизации и пр.) известны заранее. При динамическом планировании, решения о планировании принимаются на этапе выполнения на основании информации о состоянии системы (метрик), в связи с чем дополнительно появляется проблема минимизации накладных расходов на планирование [12].
Методы динамического планирования состоят из стратегии планирования и алгоритма планирования [13, 14]. Стратегия планирования описывает ситуации в которых вызывается алгоритм планирования. Алгоритм планирования составляет план на основе информации о состоянии машин, и информации об очереди задач в очереди ожидания на момент вызова.
Как указано в [15] стратегии динамического планирования делятся на две категории: немедленной обработки и пакетной обработки. В первом случае только вновь прибывшая задача рассматривается планировщиком, в то время как в пакетном режиме планировщик управляет как вновь прибывшей задачей, так и задачами из очереди ожидания обработки.
Используемые алгоритмы планирования основаны на различных допущениях, различаются по функциональности и, в следствие этого имеют различающиеся сценарии применения. В работе [12] проведена попытка систематизации 27 существующих алгоритмов. В целом к задаче планирования выполнения пакетов заданий для параллельной обработки выделяют два основных подхода: 1. Планирование независимых задач; 2. Планирование задач с зависимостями (описанных в виде направленного ацикличного графа). В работе [7] отмечается, что существующие наработки в области динамического планирования в гетерогенных кластерах рассматривают исключительно независимые задачи и назначают единственную задачу на каждый узел обработки. В связи с этим авторы отмечают актуальность исследования методов, которые учитывают зависимости между задачами в виде направленных ацикличных графов.
Метод планирования задач в РСОД на основе метаданных и ре сурсных метрик
Оценка ресурсных требований задачи по ресурсным требованиям наиболее близких задач в широком смысле представляет собой обучение на основе прецедентов (Instance-Based Learning). Прецедентное обучение основано на предположении что схожие объекты (точки) относятся к схожим классам [31].
Прецедентное, или иначе, ленивое обучение (lazy learning) характеризуется следующими свойствами [32]: 1. отложенность - данные обучения сохраняются, а вычисления откладываются до момента, когда поступают запросы, требующие ответа; 2. локальность - ответы на запросы получаются в результате объединения подмножества записей из обучающей выборки; при этом используется т.н. локальное обучение, когда для прогнозирования используется часть пространства обучающей выборки [33, 34]. Применительно к данной работе интерес представляют собой способы решения задачи регрессии методом поиска ближайших соседей (- регрессия).
Прогнозирование методом ближайшего соседа заключается в поиске наименее удалённых (другими словами, наиболее близких) точек и получении класса (или численного значения в случае регрессии) голосованием простым большинством. Качество прогнозирования методом - зависит от того, какие точки считаются менее удалёнными, то есть метод чувствителен к способу за-52 дания метрики расстояния.
Выходом алгоритма k-NN регрессии является прогнозируемый вектор ресурсных затрат, который оценивается как среднее значение векторов ресурсных затрат к ближайших соседей, где параметр к задаётся аналитиком.
Вес каждого атрибута отражает его значимость для определения прогнозируемых ресурсных требований: если один из атрибутов важнее других для классификации, то назначение ему большего веса позволяет повысить точность прогнозирования.
Схемы взвешивания по-атрибутных метрик схожести необходимы, поскольку в противном случае избыточные, незначимые или зашумлённые атрибуты будут оказывать тот же эффект на вычисление расстояния что и другие атрибуты [36]. В частности, для алгоритма поиска ближайшего соседа размер выборки, требуемый для получения классификатора с заданным уровнем точности прогнозирования, растёт экспоненциально с ростом количества избыточных атрибутов [31, 37].
Ряд исследований показал [38–40], что разновидности алгоритма -, осуществляющие взвешивание атрибутов позволили повысить точность прогнозирования в ряде прикладных областей.
Техники выбора атрибутов (feature selection) являются частным случаем назначения весов, когда для отсечения множества избыточных атрибутов им задаются нулевые веса = 0. Ранжирование и отсечение атрибутов потенциально позволяют получить целый ряд преимуществ: 1. Упростить визуализацию и понимание данных; 2. Уменьшить объём хранимых данных; 3. Сократить время обучения (построения модели); 4. Сократить эффект проклятия размерности; 5. Повысить точность прогнозирования. Стандартными способами получения вектора весов являются линейная ре грессия, вычисление коэффициентов корреляции и ковариации. Среди мето дов выбора атрибутов, широкое распространение получили методы фильтра ции (flter) [41], которые выполняются на стадии предъобработки данных вне зависимости от выбора классификатора. Вместе с тем, на данный момент не существует универсального метода получения атрибутных весов, оптимальных для всех прикладных областей, поскольку каждая задача требует предвзятости (bias) в выборе атрибутов [42]. Смещением оценок (bias), считается любая основа для предпочтения одних обобщений другим, в отличие от строгого соответствия оценкам полученным из обучающей выборки. Наличие знаний прикладной области, знание об источниках получения данных обучения, предпочтение простых обобщений приводят к смещению оценок, но при этом позволяют повысить точность прогнозирования [42]. В работе [32] в качестве одного из оснований классификации алгоритмов обучения выступает как раз наличие знаний прикладной области для коррекции весов. В методике выбора атрибутов, предложенной в работе [43], также предлагается составлять список выбранных атрибутов вручную ("ad hoc"feature selection method) при наличии знаний из прикладной области.
Что касается способа вычисления по-атрибутной меры схожести (расстояния), то он зависит, в первую очередь, от типа атрибута: численный или категориальный (т.е. дискретный и возможно неупорядоченный). Если для численных атрибутов наибольшее распространение носит мера Минковского, в частности при значении порядка р = 2 - евклидово расстояние, р = 1 - манхеттенское расстояние:
Инфраструктура и метаданные
Описательная статистика результатов экспериментов приведена в сводной Таблице 4.4. Как видно из полученных результатов, временные характеристики, - среднее время нахождения заявки в системе, средняя задержка и среднее время ожидания обработки заявки, - являются величинами одного порядка для обоих методов планирования.
Проанализируем эффективность использования вычислительных ресурсов для каждого экспериментального сценария.
На гистограммах 4.8, 4.9, 4.10 приведена характеристика эффективности загрузки процессорных ресурсов для постоянного распределения трудоёмкости, которое характеризуется тем, что на вход системы подаются задания средней трудоёмкости.
Как можно видеть из Рисунка 4.8, при слабой загрузке, метод FIFO_LLF имеет больше точек в диапазоне [0, 0.8), который говорит о недоиспользовании ресурсов, а также отличается наличием заданий, для которых было выделено недостаточно ресурсов (processor utilization 2). В диапазоне [0.8, 1] оба метода показали схожие результаты.
При средней загрузке (Рисунок 4.9) метод FIFO_LLF немного превосходит метод Meta_Sched, поскольку последний ошибочно назначил часть заданий таким образом, что ресурсы оказались перегружены. Кроме того, в оптимальном диапазоне [0.8, 1] метод Meta_Sched немного уступает (70 против 90) методу FIFO_LLF по количеству точек.
При высокой загрузке (Рисунок 4.10) видно значительное преимущество метода планирования на основе метаданных и ресурсных метрик (Meta_Sched), поскольку множество точек, попавших в диапазон [2, 6] было перенесено в диапазон [0, 2]. Иными словами была снижена перегрузка системы.
На гистограммах 4.11, 4.12, 4.13 приведена характеристика эффективности загрузки процессоров для равномерного дискретного распределения трудоёмкости, которое характеризуется тем, что на вход системы равновероятно подаются задания легкой, средней и высокой трудоёмкости.
При средней загрузке (Рисунок 4.12) метод планирования Meta_Sched показывает лучшие результаты на диапазоне [0, 0.8) (недоиспользованные ресурсы) и сравнимые результаты в диапазоне [0.8, 1] (оптимальная загрузка), однако проигрывает в диапазоне [1, 4], поскольку имеет больше заданий, для которых вычислительных ресурсов оказалось недостаточно. Впрочем в диапазоне [4, 5] оба метода ведут себя одинаково неэффективно.
При высокой загрузке (Рисунок 4.13) метод планирования Meta_Sched позволяет сократить количество случаев перегрузки ресурсов.
Также в работе приведены графики для взвешенного дискретного и случайного распределения трудоёмкости заданий. Взвешенное дискретное распределение является приближением гауссова распределения, при котором 72% заданий имеют среднюю трудоемкость, а задания с высокой и низкой трудоёмкостью получают по 14% соответственно. Случайное (псевдослучайное) распределение трудоёмкости определяется программным генератором случайных чисел.
Аналогично анализируя гистограммы для взвешенного дискретного и случайного распределения трудоёмкости можно сделать вывод о том, что при средней и слабой загрузке оба метода планирования (FIFO_LLF и Meta_Sched) сравнимы по эффективности, в то время как при высокой загрузке метод планирования на основе метаданных и ресурсных метрик (Meta_Sched) позволяет более эффективно использовать вычислительные ресурсы.
Для того чтобы сравнить два метода планирования в целом, целесообразно также вычислить процент задач для которых вычислительных ресурсов оказалось достаточно в каждом тестовом сценарии. Данная величина отражает эффективность работы планировщика.
Значение величины относительной эффективности планирования для всех экспериментальных сценариев приведено на Рисунке 4.20. Как показывает распределение, метод планирования на основе метаданных проигрывает методу FIFO_LLF при слабой и средней загрузке, но показывает свою эффективность при высокой интенсивности поступления заявок (86/мин.).
Такой результат объясняется тем, что при слабой интенсивности поступления заявок значительная часть вычислительных ресурсов простаивает. Метод планирования FIFO_LLF отдаёт предпочтение наименее загруженным вычислительным узлам, в результате чего ресурсные требования задач оказываются удовлетворёнными.
Планирование на основе метаданных и ресурсных метрик опирается на историю выполнения задач обработки данных. Как показывают результаты на Рисунке 4.20 в условиях высокой интенсивности поступления заявок такой подход позволяет повысить эффективность планирования за счёт более точного установления соответствия задач вычислительным узлам на основе собранной ранее статистики.
