Автор: С.В. Минухин, С.В. Знахур
Эксплуатация современных Грид-систем связана с необходимостью повышения их производительности. Она определяется такими характеристиками, как загруженность ресурсов, время выполнения всех заданий на имеющихся ресурсах, время завершения выполнения наиболее поздних заданий и т.д. Поскольку существует тенденция к увеличению количества гетерогенных вычислительных кластеров и заданий с дифференцированной сложностью решения, то является актуальным использование более тонкая настройка процедуры планирования, которая позволит эффективно «упаковать» задания на ресурсы с одной стороны, а с другой – обеспечить высокую загрузку всех ресурсов. Это может быть достигнуто путем использования эвристических алгоритмов планирования и дополнительных компонент(модулей) в самом механизме планирования ресурсов Грид.
Существующие планировщики Грид-систем представляют собой встроенные компоненты в сложной и взаимосвязанной информационно-коммуникационной системе Грид. Поэтому процедура оценки эффективности планирования является нетривиальной задачей в случае необходимости сравнения результатов работы разных планировщиков, которые не интегрированы в одну и туже среду (инфраструктуру распределенной системы). Как показали предварительные исследования, выигрыш (эффективность) от использования процедуры планирования возможно получить не только за счет выбора лучших алгоритмов планирования, но и за счет выбора соответствующей архитектуры планировщика и механизма его работы. В данной работе анализируются особенности механизма и метода планирования для распределенных систем для обоснования их преимуществ в случае изменения свойств входного потока заданий. В качестве основной рассматривается проблема формализации правил выбора оптимальных параметров компонент предлагаемого механизма планирования, позволяющих обеспечить минимальное время выполнения всех заданий и среднее время решения одного задания (время ответа), максимально эффективное использование ресурсов и лучшую балансировку их загрузки.
Целью работы является анализ статистических закономерностей, выявленных в процессе использования предлагаемого механизма планирования заданий для гетерогенной Грид-системы при изменении характеристик потока поступающих заданий, и обоснование выбора оптимальных значений параметров компонент механизма для повышения эффективности его работы.
Основной задачей исследования является следующая: на основе результатов статистического анализа работы Грид-системы сформулировать определенную систему правил, позволяющую для любых характеристик заданий и ресурсов определить области оптимальных значений параметров (настроек) компонент механизма планирования и тем самым повысить производительность работы Грид-системы.
Для планирования загрузки ресурсов в данной работе предлагается использовать механизм, компоненты которого приведены на рис. 1. Согласно приведенной схеме, задания из глобальной очереди с определенной периодичностью и интенсивностью поступают в пул. Размер пула определяется в зависимости от максимальной интенсивности поступающих заданий (если размер пула меньше количества поступающих заданий, то будет создана дополнительная очередь уже на входе самой системы). Задания из пула выгружаются через определенные промежутки времени, задаваемые периодичностью планирования, в блок планирования, в котором реализован алгоритм планирования (в данном случае быстрый эвристический алгоритм решения задачи о наименьшем покрытии [1]). Время планирования (время работы алгоритма решения задачи о наименьшем покрытии) зависит от размера пула, т.е. от количества поступивших на блок планирования заданий и количества доступных и свободных на момент планирования ресурсов. Эвристический алгоритм планирования обеспечивает решение задачи за полиномиальное время [1]), поэтому периодичность планирования должна быть больше времени решения задачи планирования. В результате планирования задания назначаются на свободные элементы блоков пакета заданий соответствующих ресурсов, т.е. те, которые на момент планирования не заполнены полностью(см. рис. 1).
Отметим, что задания поступают с задержкой, определяющей коммуникационную задержку и передачу данных с блока планирования на ресурсы для их выполнения.
Наличие пакета заданий в данном механизме обусловлено необходимостью решения двух задач:
В
данном исследовании
используется
последовательный режим для решения заданий на каждом
ресурсе, т.е., задания для решения на ресурсе последовательно
выбираются из пакета
заданий по мере
освобождения ресурса.
Рисунок 1. Общая архитектура механизма планирования
Для оценки эффективности механизма планирования использованы следующие показатели (индикаторы): время выполнения всех заданий – время решения всех заданий глобальной очереди, начиная с момента поступления первого задания в очередь и заканчивая временем завершения последнего задания; время ответа – среднее время решения одного задания; коэффициент использования ресурсов – средняя загрузка ресурсов за время решения всех заданий.
Для проведения вычислительных экспериментов использована программа, разработанная для имитационного моделирования механизма планирования, интерфейс которой приведен на рис. 2. В качестве единицы времени работы механизма планирования и расчетов в программе используется 1 такт – внутреннее время имитационной модели, которое соответствует времени решения одного задания, имеющего сложность 1000 MI на ресурсе, производительность которого 1000 MIPS [2].
Рисунок 2. Интерфейс настройки параметров имитационной модели механизма планирования
В качестве параметров для имитационного моделирования были выбраны следующие: для заданий – законы распределения входного потока (нормальный и экспоненциальный), интенсивность (среднее количество заданий, поступающих за один такт), общее количество заданий глобальной очереди (в исследовании – 2100), сложность задания (трудоемкость решения, среднее значение- 30, дисперсия – 5 тактов), универсальность – 50 % (процент имеющихся ресурсов, на которых может решаться задание); длина пула – 100 (максимальное количество заданий, загружаемых в него одновременно или по мере их поступления в систему на обработку); для планирования– периодичность(изменяется от 1 до 40 тактов); для пакета заданий на ресурсы – количество элементов – 5; количество ресурсов – 10, производительность одного ресурса – 5 тактов; задержка – 1 такт.
Для имитационного моделирования были сгенерированы потоки заданий, имеющие различную интенсивность (от 5 до 40 заданий с шагом 5) и законы распределения данных: для нормального и экспоненциального законов – среднее значение принималось равной величине интенсивности, среднеквадратическое отклонение – 2. На рис. 3 показаны гистограммы распределения сгенерированных данных, при этом для обеспечения адекватности проводимых экспериментов суммарная сложность заданий и их количество для сгенерированных выборок выбиралось одинаковым.
Рисунок 3. Гистограммы распределения входных потоков заданий (экспоненциальный и нормальный законы)
В результате планирования были получены следующие результаты. Эффективное планирование на основе использования эвристического алгоритма позволяет равномерно назначать задания на ресурсы, а эффект от планирования – увеличение загрузки ресурсов – увеличивается с уменьшением периодичности планирования. В данном случае задания, поступающие на вход ресурсов, независимо от их первоначального закона распределения, имеют экспоненциальный закон. Это означает, что для любого входного потока заданий с помощью выбора оптимального размера пула осуществляется его преобразование в n потоков заданий на ресурсы (кластеры), закон распределения которых будет экспоненциальным, что на практике позволит использовать унифицированный подход к планированию выполнения заданий на ресурсах (рис. 4).
Максимальное значение интенсивности на каждом такте планирования для пакетов заданий на ресурсы можно рассчитать по формуле:
(размер_пула)/(количество_ресурсов) (1)
Чем больше периодичность планирования, тем большее количество заданий поступает в пул, а затем назначается в пакеты заданий на каждом такте планирования. В случае высокой входной интенсивности заданий или большой периодичности планирования пул заполняется полностью и таким образом ограничивает размерность заданий, участвующих в процедуре планирования. При оптимальной организации процедуры планирования интенсивность (количество поступающих после планирования заданий) для пакета заданий должна быть равной 1, что обеспечивает минимальное время простоя заданий в системе и равномерную загрузку ресурсов за счет того, что на освободившейся ресурс всегда будет поступать хотя бы одно задание.
Проведенные эксперименты по оптимизации механизма распределения заданий на ресурсы, результаты которых показаны на рис. 5, свидетельствуют о высоком уровне балансировки загрузки гетерогенных ресурсов. Для выбранных исходных данных среднее количество поступающих на каждом такте планирования заданий на ресурс соответствует 1.1, минимальное значение равно 0, максимальное значение равно 5. Среднее количество заданий, поступивших на каждый ресурс за все время планирования, равно 203, что весьма близко к идеальному значению 210 = 2100 заданий/10 ресурсов.
Статистический анализ результатов планирования в зависимости от изменения интенсивности потока заданий и периодичности планирования приведен на рис. 6–8. Как показывают диаграммы, время выполнения линейно зависит от периодичности планирования. Исследования показывают, что при прочих равных характеристиках минимальная периодичность планирования, которая равна одному такту, позволяет получить наименьшее значение времени выполнения. Эта зависимость справедлива в случае, когда сложность (трудоемкость) заданий больше 1.
Рисунок 4. Закон распределения заданий после оптимального планирования на каждый ресурс (в пакете заданий)
(результат показан для ресурса P1 и P2)
Рисунок 5. Результаты загрузки пакета заданий на такте планирования на ресурсы
При увеличении интенсивности потока заданий линейная зависимость сохраняется, однако выигрыш от изменения периодичности планирования уменьшается. При увеличении интенсивности больше 100 изменение периодичности планирования не влияет на время выполнения заданий, что объясняется тем, что пул ограничивает количество поступающих на планирование заданий.
Для получения положительного эффекта от изменения периодичности планирования, предлагается следующая формула, которая позволяет определить верхнюю границу периодичности планирования:
(среднее_количество_заданий_в_пуле*средняя_сложность_заданий)/
/(количество_ресурсов*универсальность_задания* (2)
*средняя_производительность_ресурсов).
При увеличении входной интенсивности заданий среднее количество заданий в пуле также увеличивается, что приводит, при фиксированных значениях других характеристик, к возможности увеличения периодичности планирования без ухудшения времени выполнения всех заданий.
В отличии от времени выполнения всех заданий, среднее время ответа(среднее время выполнения одного задания) имеет нелинейную зависимость (рис. 7). В тех случаях, когда периодичность планирования меньше среднего времени освобождения ресурса (в данном случае – 5 тактов, что меньше отношения (30 тактов сложность задания)/(5 тактов производительности ресурса)), в системе формируется очередь из поступивших, спланированных заданий, которые ждут освобождения соответствующего ресурса, что приводит к резкому увеличению времени ответа.
При увеличении периодичности планирования время ожидания заданий в очереди уменьшается, поскольку за это время большая часть предыдущих заданий из пула успевает уже решиться. При больших значениях периодичности (больше 20 тактов на рис. 7) время ответа включает только время нахождения в пуле+ время транспортировки (коммуникационной задержки) + время решения на ресурсе (рис. 1), что и определяет его минимальное значение.
Рисунок 6. Зависимость времени выполнения заданий от периодичности планирования и интенсивности заданий
Рисунок 7. Зависимость времени ответа от периодичности планирования и интенсивности заданий
Максимальное значение коэффициента использования ресурсов возможно в случае постоянной загрузки ресурсов (минимизации времени их простоя). Это достигается или увеличением интенсивности, или уменьшением периодичности планирования. Так, при низкой интенсивности 5 (меньшей, чем количество ресурсов), периодичность планирования должна быть равна 1 такту, при интенсивности 20 - периодичность планирования должна быть не более 5 тактов, при высокой интенсивности 40 – периодичность планирования, которая обеспечивает высокую загрузку ресурсов, равняется 10 тактам.
Для определения значения коэффициента использования ресурсов предлагается следующая эмпирическая формула (3), в основе которой лежит использование значения показателя времени выполнения всех заданий, т.е. характеристики, которую достаточно легко измерить. Формула получена на основе статистического анализа данных экспериментов и позволяет прогнозировать значение коэффициента использования с ошибкой меньше 5%:
((общее_количество_заданий*средняя_сложность_заданий)/
(количество_ресурсов*средняя_производительность_ресурсов))/ (3)
время_выполнения_всех_заданий
Следует отметить, что периодичность планирования влияет как на время выполнения, так и на коэффициент использования ресурсов. Но, так как рассчитанные коэффициент использования ресурсов и время выполнения заданий имеют обратную линейную зависимость, то уменьшение коэффициента использования приводит к увеличению времени выполнения при условии, что планируемое время решения заданий (общее количество заданий * среднюю сложность заданий)/(количество ресурсов*среднюю производительность ресурса) остается неизменным.
Следовательно, если известно значение коэффициента использования, то на основе вышеприведенной формулы возможно также рассчитать ожидаемое время выполнения заданий.
На практике важным является выбор такой политики, которая учитывает интересы владельцев ресурсов (стратегия минимизации времени выполнения всех заданий) и пользователей (стратегия минимизации среднего времени выполнения одного задания).
Для определения компромиссной для двух стратегий периодичности планирования необходимо найти точку пересечения для индикаторов– времени выполнения и времени ответа (рис. 9). На рис. 9 приведена аппроксимация времени выполнения и времени ответа с помощью полинома 4-ого порядка, для сравнения используется диаграмма с двойной шкалой измерений для одного (левая) и другого (правая) показателей, соответственно.
Рисунок 8. Зависимость коэффициента использования от периодичности планирования и интенсивности заданий
Как следует из рис. 9, наиболее приемлемой периодичностью является периодичность равная 10 (12) тактам, поскольку в данном случае время выполнения и время ответа имеют незначительные отклонения относительно их оптимальных значений.
Для анализа влияния изменения характеристик заданий на процедуру планирования в исследовании отдельно проведен анализ влияния роста сложности (трудоемкости) заданий на результаты (эффективность) планирования. Следует отметить, что, так как сложность измеряется в тактах, то в исследовании использовался диапазон сложности задания от 5 до 350 тактов (при фиксированной интенсивности 5, производительности – 5 и количестве ресурсов – 10). Результаты эксперимента приведены на рис. 10–12. На рис. 10 видно, что увеличение времени выполнения практически линейно зависит от увеличения сложности задания, это характерно для всех выбранных периодичностей планирования.
Однако, при увеличении сложности задания время ответа начинает экспоненциально зависеть от периодичности планирования даже при низкой интенсивности заданий (рис. 11). Так, при сложности задания 160 и 320 (рис. 11–12) имеет место максимальное время ответа и загрузка ресурсов (коэффициент использования близок к 1), что приводит к тому, что задание ожидает освобождение ресурса.
На основе результатов проведенных экспериментов, для расчета нижней границы величины периодичности планирования при известной минимальной сложности задания, была найдена следующая эвристика, которую можно описать формулой:
(средняя_интенсивность_заданий*минимальная_сложность_заданий)/ (4)
(количество_ресурсов*максимальная_производительность_ресурса)
Рисунок 9. Величина периодичности планирования для компромисса для двух стратегий
Рисунок 10. Зависимость изменения времени выполнения от сложности задания для различных периодичностей планирования
Приведенная формула (4) справедлива при условии, что размер пула (или интенсивность) меньше или равен количеству ресурсов. В данном случае периодичность планирования определяется в большей степени минимальным временем освобождения ресурса, т.е. отношением (минимальная_сложность_задания/максимальная_производительность_ресурса).
Поскольку размер пула можно изменять и устанавливать равным количеству ресурсов, то в предлагаемом механизме планирования всегда можно обеспечить минимальное время выполнения всех заданий и максимальный коэффициент использования ресурсов.
Рисунок 11. Зависимость времени ответа от периодичности планирования для заданий различной сложности
Рисунок 12. Зависимость коэффициента использования от периодичности планирования для заданий различной сложности