В статье рассматриваются аспекты планирования задач в системах распределенных вычислений.
Ключевые слова: распределенные вычисления, стратегия планирования, GRID.
В общем случае запускаемые в вычислительной системе приложения имеют разные требования к вычислительным узлам. К примеру, в случае виртуализации сетей, запрос на создание виртуальной сети может быть описан с учётом ограничений, накладываемых на узлы сети (напр. процессор и физическое расположение) и на связи (например задержка, пропускная способность и джиттер).
Традиционные требования, которые предъявляются со стороны приложений:
- Сетевые требования (пропускная способность и задержка);
- Конфигурационные требования (процессор и память);
- Права доступа к определённым программным ресурсам.
Информационный сервис, который предоставляет данные о состоянии ресурсов, опирается на модель ресурсов, о которой будет сказано ниже.
Таким образом, на вход метода выделения ресурсов подаются следующие данные:
- Физические и виртуальные ресурсы;
- Требования приложений;
- Модели ресурсов.
При моделировании ресурсов производится разбивка доступных аппаратных ресурсов (памяти, процессора, пропускной способности сети и т. п.) на части, которые могут быть ассоциированы с конкретной задачей. К примеру, доступную задачам память можно делить на блоки по 16, 32, 64 и т. д. мегабайт, а пропускную способность сети — по 10 мегабит/с, а процессора можно предоставлять как эксклюзивно, так и предоставляя ядра одного процессора для планирования работы нескольких прикладных приложений. Здесь важно соблюсти баланс между наиболее точным выделением ресурсов и накладными расходами на планирование их использования: распределение ресурсов при очень мелком их дроблении само по себе становится сложной задачей, что усложняет работу на стадии планирования ресурсов и оптимизации [3].
Привлекаемые распределенные ресурсы почти всегда гетерогенны: различные архитектуры, программное и аппаратное обеспечение. В связи с этим, разработка адекватной ресурсной модели является первой задачей, которую необходимо решить при разработке системы выделения ресурсов [3].
Важно учитывать, что моделирование ресурсов не обязано привязываться к формам и способам, какими они предоставляются конечным пользователям. К примеру, провайдер может моделировать каждый ресурс индивидуально по мелкогранулированной шкале (количество гигагерц процессора или гигабайт памяти), но предоставлять их в определённой комплектации в качестве классов (виртуальные машины с большим объёмом памяти или высокопроизводительные — с мощным процессором).
Оптимальным представляется подход, когда на этапе создания системы строятся модели ресурсов исходя из типов предоставляемых сервисов.
К примеру в решении Elastic Computing Cloud от Amazon выделяются классы арендуемых машин (instance families): общего назначения, оптимизированные по производительности процессора, с большим объёмом основной памяти (RAM), c большим объёмом внешней памяти и оптимизированные под графическую обработку. Кроме того, в каждом классе машин идёт разделение по мощности (instance types): малые, средние, большие, сверхбольшие и т. п.
Среди стратегий выбора ресурсов можно выделить апостериорные и априорные [3].
Для апостериорных стратегий после того, как было выполнено изначальное назначение ресурсов (возможно — неоптимальное), управление назначением ресурсов продолжается с целью улучшения первичного решения. При необходимости принимаются такие меры по добавлению или переназначению ресурсов для выхода на требуемые показатели функционирования. Например, в приложениях, разворачиваемых в кластерах Kubernetes, на основе анализа загруженности узлов балансировщиком может быть принято решение о добавлении в работу дополнительного узла. Масштабирование может осуществляться на основе и иных метрик, собираемых управляющим центром кластера.
Априорные стратегии находят оптимальное решение на основе заранее определенных переменных, влияющих на распределение ресурсов. К таким переменным можно отнести и архитектурные ограничения представления ресурсов (например, память будет выделяться блоками, размер которых задается на уровне реестра ресурсов, даже если приложением она не будет задействована полностью), и особенности самой задачи.
Большинство существующих алгоритмов планирования задач исходит из предположения, что время выполнения приложения (задачи) известно заранее, ещё до реального выполнения [2]. Это упрощает сопоставление задач и ресурсов, но слабо применимо к реальным задачам. Более обоснованный подход — мониторинг прикладных приложений с целью выяснения характеристик выполнения. Это позволяет на основе предположения о корреляции между состоянием выполнения задачи и общим временем её выполнения прогнозировать время, оставшееся до завершения задачи.
Многие из алгоритмов, оценивающие время выполнения и прогнозирующие загрузку ресурсов, основаны на статистических моделях [4]. Статистика предыдущих запусков успешно применяется в кластерных и облачных платформах. Решения о масштабировании на практике базируется на множестве критериев, среди которых накладные расходы на выделение ресурсов, на миграцию заданий, оценку ожидаемого эффекта от масштабирования и перепланирования.
Наряду с методами управления ресурсами выделяют два различных типа планирования задач: статический и динамический. Статические стратегии предполагают принятие решения о запуске на основе информации о доступных узлах обработки и очереди ожидания заданий. Целью планирования выступает минимизация ожидаемой продолжительности выполнения задач.
Динамические стратегии применяются в тех случаях, когда система назначает ресурсы по мере поступления задач. Здесь можно минимизировать время обработки пакета или иную метрику, отражающую качество предоставляемого сервиса. Динамический подход к планированию предполагает возможность планировщика менять стратегию планирования при появлении новых задач и освобождении ресурсов. В этом случае планирование становится уже не единовременным отвлечением ресурсов на внутренние нужды, а систематической работой, влияние которой на общее время выполнения задачи нужно также минимизировать [5].
Методы динамического планирования базируются на сочетании стратегии и алгоритма планирования [6, 7]. Стратегия планирования описывает ситуации, в которых выполняется алгоритм планирования, алгоритм планирования составляет план на основе информации о задаче — очереди заданий, сведений о ресурсах. В динамическом планировании можно выделить стратегии немедленной обработки и пакетной обработки. В первом случае планировщиком рассматривается только поступающие задачи, в пакетном режиме планировщик дополнительно управляет очередью ожидающих задач.
Алгоритмы планирования опираются на различные допущения, в силу чего различаются по возможностям и целевым сценариям применения. С попытками систематизации существующих алгоритмов можно ознакомиться в [5]. Представление задачи для алгоритма планирования можно разделить на два направления:
- Планирование независимых задач;
- Планирование задач с зависимостями (описание на основе DAG).
Например, в статье [2] производится оценка производительности и оптимизация для существующего алгоритма адаптивного планирования в грид-системах. Алгоритм обрабатывает задачи, имеющие перекрестные зависимости, которые можно описать направленным ацикличным графом, для которых отсутствует информация об общем времени выполнения. Авторы в статье [5] также исследуют вопрос планирования задач с зависимостями.
Как уже отмечалось, все указанные методы планирования, как правило, реализуются на уровне промежуточного программного обеспечения. В [1] предлагается эвристика для повышения эффективности (минимизации времени решения задач и оптимизации использования ресурсов) промежуточного программного обеспечения на основе технологии GridRPC, которое служит для планирования клиентских запросов. Предложенная модель позволяет выполнить оценку длительности всех задач системы. Помимо клиентов и серверов авторы выделяют компонент называемый реестром, что соответствует планировщику в работах других авторов. Реестр отвечает за отображение пользовательских запросов на узлы в соответствии с определёнными критериями.
В указанной работе предлагается подход на основе модели разделения времени (time sharing), который позволяет прогнозировать длительность выполнения отдельно выбранной задачи на выбранном сервере и влияние на длительность задач уже запущенных на данном узле обработки.
Некоторые методы также учитывают возможность выхода из строя компонентов системы. Здесь необходим баланс резервирования ресурсов для обеспечения живучести расписания выполнения задачи и возможным снижением общей производительности системы за счет вынужденного простоя резервных узлов.
Авторы в статье [8] отмечают, что установление соответствия между приложениями и вычислительными ресурсами в грид-системах является трудоёмкой задачей ввиду гетерогенности ресурсов и динамичности изменения их состояния. Для преодоления этих проблем предлагается использовать искусственную нейронную сеть для прогнозирования состояния узлов обработки. В работе сравниваются два алгоритма прогнозирования на основе нейронных сетей. Авторы используют статический подход к планированию: делается допущение о том, что время выполнения задач может быть оценено на стадии планирования.
Идея о том, что для повышения качества планирования длительные по прогнозируемому времени задачи [2] назначаются на более производительные ресурсы, чем короткие по времени задачи, для которых достаточно низкопроизводительных ресурсов, может быть обобщена следующим образом: чем более точно выделенные для задачи ресурсы соответствуют её ресурсным требованиям тем выше эффективность использования ресурсов и ниже среднее время обработки заявок.
Литература:
- Caniou, Y. Experimental study of multi-criteria Scheduling Heuristics for GridRPC Systems / Y. Caniou, E. Jeannot // Euro-Par. — 2004. — P. 1048–1055.
- Chtepen, M. Performance evaluation and optimization of an adaptive scheduling approach for dependent grid jobs with unknown execution time / M. Chtepen, F. Claeys, B. Dhoedt // 18th World IMACS Congress and MODSIM09 International Congress on Modelling and Simulation, Proceedings. — 2009. — P. 1003–1009.
- Endo, P. Resource allocation for distributed cloud: concepts and research challenges / P. Endo, A. D. A. Palhares, N. Pereira // Ieee Network. — 2011. — Vol. 25 — № 4. — P. 42–46.
- Imam, M. T., Neural network and regression based processor load prediction for efficient scaling of Grid and Cloud resources / M. T. Imam, S. F. Miskhat, R. M. Rahman, M. A. Amin // 14th International Conference on Computer and Information Technology (ICCIT). — IEEE — 2011.
- Kwok, Y.-K. Static scheduling algorithms for allocating directed task graphs to multiprocessors / Y.-K. Kwok, I. Ahmad // ACM Computing Survey. — 1999. — Vol. 31. — № 4. — P. 406–471.
- Kim, J.-K. Dynamically mapping tasks with priorities and multiple deadlines in a heterogeneous environment / J.-K. Kim, S. Shivle, H. J. Siegel // Journal of Parallel and Distributed Computing. — 2007. — Vol. 67. — № 2. — P. 154–169.
- Sun, W. Dynamic task flow scheduling for heterogeneous distributed computing: Algorithm and Strategy / W. Sun, Y. Zhang, Y. Inoguchi // IEICE Transactions on Information and Systems. — 2007. — Vol. E90-D, № 4. — P. 736–744.
- Xue. S. Resource state prediction in the grid based on neural network / S. Xue, L. Chen, G. Liu // Proceedings of the 5th international conference on Natural computation. ICNC’09. Piscataway, NJ, USA: IEEE Press, 2009. — P. 294–298.
