BC/NW 2017 № 2 (31):4.1

МЕТОД ПЛАНИРОВАНИЯ ЗАДАНИЙ В ГРИД-СИСТЕМАХ

Арутюнян Ш.Ш., Абросимов Л.И,

Введение

В современном обществе существует необходимость в повышении качества и скорости обработки больших данных. В связи с этим возрастает значение grid-систем (ГС), как средства решения этой проблемы. Особенностью ГС является использование географически распределенных гетерогенных компьютеров, соединенные с помощью сети передачи данных.

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

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

1. Алгоритмы планирования заданий в Грид-системах

На сегодняшний день существует два класса алгоритмов планирования заданий в Грид-системах: планирование с наискорейшим выполнением заданий, целью которого является минимизация времени выполнения задания (best-effort scheduling) и планирование с оптимизацией качества обслуживания (QoS constrained scheduling), целью которого является соблюдение временных или финансовых ограничений для заданий, а также оптимизация других характеристик выполнения задания.

1.1. Best-effort планирование

Существует несколько алгоритмов, основанных на best-effort концепции, рассмотрим и выделим особенности основных:

 Планирование индивидуальных задач

Самый простой подход к планированию — выполнять каждую задачу на наилучшем для нее ресурсе, не учитывая структуру приложения.

Такой подход реализуется в эвристике MCT (Minimum Completion Time). На каждом шаге алгоритм запускается для одной готовой к выполнению задачи и планирует выполнение на ресурсе, с целью минимизации времени завершения выполнения алгоритма.

Несмотря на то, что задачи планируются независимо, алгоритм MCT может неявно учитывать структуру композитного приложения за счет вычисления оценки МCT, включающей в себя время передачи данных. Если планировщик обладает актуальной информацией о состоянии вычислительной сети, этого достаточно чтобы эффективно планировать выполнения алгоритмов с несложной структурой, избегая использования перегруженных ресурсов или ресурсов в плохой сетевой доступности.

1.1.1Пакетное планирование

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

Авторами эвристики было предложено 3 критерия: MinMin — первыми планируются задачи с минимальным оценочным временем выполнения на наилучшем ресурсе, MaxMin — первыми планируются задачи с максимальным оценочным временем выполнения на наилучшем ресурсе, Sufferage — первыми планируются задачи с максимальной разницей оценок времени выполнения между двумя наилучшими ресурсами.

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

1.1.2 Кластерное планирование

Кластерное планирование – класс эвристических методов планирования, основанных на разбиении задач на группы, выполняемые на одном ресурсе. Так как время передачи данных в пределах ресурса обычно полагают нулевым, эффективная группировка задач позволяет сократить время ожидания данных во время выполнения, и, таким образом, общее время выполнения заявки.

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

1.1.3. Планирование с дублированием задач

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

Однако, дублирование задач создает дополнительную нагрузку на ресурсы, что ограничивает применимость таких методов в загруженных вычислительных средах.

Алгоритмы с дублированием задач, как правило, построены на одном из уже рассмотренных эвристических подходов — приоритетном или кластерном. Однако именно дублирование задач принято выделять как основную особенность алгоритма.

Сравнение с алгоритмами приоритетного планирования показывает преимущество методов с дублированием задач при условии достаточно высокой доли обмена данными в общем времени выполнения.

1.2 QoS-constrained планирование

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

В [1] автор предлагает алгоритм планирования, основанный на базисном Min-min алгоритме. Предложенный QOS управляемый min-min алгоритм, в первую очередь планирует задачи требующие повышенной пропускной способности. Таким образом, если задачи требуют различных параметров пропускной способности, то результат планирования будет лучше чем у min-min алгоритма, если задачи требуют одинаковой пропускной способности, то результат двух алгоритмов будет одинаковым.

В [2] автор предлагает алгоритм RASA. Он строит матрицу C, где элементы  представляют собой время выполнения заявки  на  ресурсе . Если количество доступных ресурсов нечетное, применяется стратегия min-min для назначения первой задачи, в противном случае применяется алгоритм max-min. Остальные задачи назначаются соответствующим ресурсам, используя попеременно данные стратегии. Например, если первая задача назначена ресурсу по стратегии Min-min, следующая задача будет назначена стратегией Max-min. В следующем раунде назначение задания начинается со стратегии, отличной от последнего раунда. Например, если первый раунд начинается со стратегии Max-min, второй раунд начнется со стратегии Min-min.

Алгоритм Back-tracking представлен в работе [3], который выполняет следующие шаги:

1. Происходит назначение подзадач на наименее дорогие ресурсы.

2. Вычисляется время выполнение задания.

3. Если значение времени на шаге 2 меньше заданного ограничения, алгоритм заканчивает свою работу, иначе выполняется переход на шаг 1 и назначение происходит на набор ресурсов, из которого удаляется наиболее дешевый.

В [4] предложены два алгоритма для планирования задач с бюджетными ограничениями. Первый алгоритм изначально распределяет все задачи на более быстрые узлы и затем переназначает некоторые задачи для удовлетворения заданных ограничений. Аналогично, второй алгоритм назначает каждую задачу на свой самый дешевый узел и затем переназначает задачи на более быстрые и более дорогие узлы, при этом соблюдая бюджетные ограничения.

Был так же предложен алгоритм планирования DBL (Dead Bottom Level) в работе [5]. В основе данного алгоритма лежит принцип разделения заявок на группы на основании нижнего предела срока выполнения заявок, используя неявный метод Эйлера. После разделения, на каждую заявку распределяется общий срок выполнения всех задач группы. Первым обрабатываются заявки из группы с наименьшим крайним сроком выполнения, причем время начала  выполнения каждой задачи определяется последним временем окончания ее ближайшего предшественника.

1.3Предлагаемый метод планирования

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

Основные затраты при обработке запросов на узлах грид-систем, в соответствии с моделью ЭМВОС, происходят не только за счет прикладной программы, но и на транспортном и сетевом уровне[6]. Протоколы сетевого и транспортного уровня реализованы в виде программных функций ядра ОС. Учитывая вышесказанное, c помощью программных и аппаратных средств ОС можно достичь поставленную цель, для этого следует решить следующие  задачи: 

· определение функций участвующих в обработке заявок;

· определение адресов вызовов выделенных функций;

· установка динамических зондов на адреса вызовов подпрограмм используют средство SystemTap;

· измерение интервалов времени выполнения подпрограмм в тиках;

· расчет вышеуказанных показателей эффективности на основе полученных интервалов;

Используя вышеописанные измерительные средства (ИС), можно получить оценку эффективности узла, используя методы систем массового обслуживания.

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

1) на первом шаге – равномерно распределить заявки по ресурсам;

2) с помощью зондов и комплекса измерительных средств определить коэффициент загрузки и пропускную способность каждого узла;

3) определить задержки на каналах связи до каждого узла;

4) собрать все полученные параметры в базу данных;

5) сравнивая параметры полученные от пользователей и собранные параметры узлов, распределять заявки, учитывая QOS-стратегию.