22 февраля 2016г.
Аннотация
В данной работе представлено описание метода решения проблемы распределения пользовательских заданий по узлам распределенной вычислительной системы, использующего принципы машинного обучения. В основе предлагаемого метода лежит использование искусственной нейронной сети для прогнозирования рабочей нагрузки, представляющей собой инициализированные пользовательские задания, вычислительной системы. Полученные прогнозные данные затем используются для построения расписания и распределения заданий по вычислительным узлам распределенной системы.
Ключевые слова
Машинное обучение, нейронные сети, прогнозирование нагрузки, распределение заданий, распределенные вычислительные системы.
Введение
Область высокопроизводительных вычислений сегодня представлена обширным классом распределенных вычислительных систем под управлением систем, планирующих выполнение инициализированных пользователями заданий на их ресурсах. Основным показателем производительности вычислительного системы является количество задач, выполненных за определенный период времени. Данный показатель напрямую зависит от эффективности составленного расписания и тесно связан с другими критериями оценки качества работы систем планирования: использование вычислительных ресурсов и своевременность выполнения заданий [1,2]. Выбор превалирующего показателя, под который будет оптимизироваться составляемое планировщиком расписание, зависит от заданий, для выполнения которых проектировалась и используется вычислительная система. Вычислительные системы академической направленности с большим процентом учащихся среди пользователей служат примером систем, для которых характерно использование показателя своевременности выполнения заданий в качестве основной оценки производительности работы планировщика. Системы распределения ресурсов подобных вычислительных систем должны обеспечивать качество обслуживания – гарантировать окончание выполнения заданий в приемлемое для пользователя время.
Постановка проблемы и существующие решения
Очевидным решением повышения эффективности процесса распределения пользовательских заданий по узлам вычислительной системы с точки зрения снижения времени ожидания является заблаговременное резервирование ресурсов, необходимых для выполнения заданий. Такой подход позволит выполнять задания сразу после их инициализации пользователями, т.к. в данном случае нет необходимости дожидаться освобождения требуемых ресурсов.
С другой стороны, для целесообразного резервирования необходимо знать, когда и какие именно ресурсы вычислительной системы могут потребоваться. Другими словами, возникает задача прогнозирования рабочей нагрузки распределенной вычислительной системы. Сложность осуществления данного процесса заключается в высокой неоднородности потока инициализированных пользовательских заданий [3]. Определенные попытки решения проблемы прогнозирования рабочей нагрузки вычислительной распределенной системы предпринимались различными исследователями [4, 5, 6], однако, ни одно решение не получило широкого распространения. Более того, ни одно из предлагаемых решений не затрагивало вопрос о том, как использовать полученные прогнозы для повышения эффективности процесса составления расписаний.
Описание предлагаемого метода
Предлагаемый метод решения задачи распределения пользовательских заданий по вычислительным узлам распределенной системы состоит из трех этапов.
На первом этапе производится декомпозиционный анализ [7] с целью выявления паттернов повторяющихся заданий, инициализированных пользователями распределенной системы. Предварительный анализ показал, что поток пользовательских заданий вычислительных распределенных систем академической направленности содержит наборы повторяющихся заданий, причем задания, принадлежащие одному набору, характеризуются близкими по значения параметрами инициализации, такими как, количество запрашиваемых ресурсов: процессоров, памяти, процессорного времени и другие. Было сделано предположение, что подобные наборы можно использовать в качестве объектов прогнозирования, т.е. предсказывать, как долго в будущем будут появляться задания из набора.
Изначально, для задачи прогнозирования были использованы некоторые известные методики прогнозирования, в частности методы ARIMAи SSA, а также оболочка GMDH. Однако, учитывая высокую неоднородность входных данных, данные методы показали низкую эффективность прогнозирования. В связи с этим, было предложено использовать метод прогнозирования, основанный на применении машинного обучения, при этом в качестве обучаемого элемента была использована нейронная сеть. В качестве входных данных, помимо параметров инициализации заданий (используемые ресурсы), были также использованы такие параметры заданий, как местонахождение задания в паттерне и длина соответствующего паттерна [7]. Из графика сравнения (Рисунок 1) эффективности прогнозирования предложенного подхода (DA&P–decomposition analysis and prediction) и стандартных методов, очевидно, что DA&P заметно превосходит остальные методы прогнозирования.
Заключительным этапом предлагаемого метода является использование полученного прогноза в процессе составления расписания выполнения заданий [8]. Основная идея данного этапа заключается в резервировании ресурсов для заданий,
которые были спрогнозированы на предыдущем этапе. Высокая
точность прогнозирования позволяет исключить
простой ресурсов, т.е. те ситуации, когда ресурсы
были зарезервированы, но задание
не было инициализировано.
Заключение
В заключение необходимо отметить, что предложенный метод позволяет применять его совместно с парадигмой онлайн
обучения, когда входные данные
постоянно пополняются новыми элементами. Ограничением данного метода является невозможность предсказать появление тех пользовательских заданий, которые не являются частью ни одного
паттерна, обнаруженного на этапе декомпозиционного анализа.
Список литературы
1.
ArndtO., FreislebenB., Kielmann
T., Thilo F. A comparative study of online scheduling algorithms for networks of workstations. Cluster
Computing. Volume
3, Issue 2, pp 95-112. 2000.
2.
Xhafa F., Abraham A. Meta-heuristics for grid scheduling
problems. In Metaheuristics for Scheduling in Distributed Computing Environments, volume
146 of Studies in Computational Intelligence, pages 1–37.
Springer, 2008.
3.
Klusáček D., Rudová H. Complex real-life data
sets in grid simulations.
In Cracow Grid Workshop 2009 (CGW'09) Abstracts, 2009.
4.
GrudenicI., BakarcicI., BogunovicN. Computer
cluster workload analysis. In proceeding of MIPRO, 2010. Proceedings of the 33rd International Convention.
5.
JannJ., PattnaikP., Franke H., Wang F., SkoviraJ., Riordan J.Modeling of Workload in MPPs. Job Scheduling Strategies
for Parallel Processing, IPPS'97 Workshop,
Geneva, Switzerland, April 5, 1997.
6.
Wang K., Ma Z., Raicu I. Modeling
Many-Task Computing Workloads
on a Petaflop IBM Blue Gene/P Supercomputer. IPDPSW,
pp.2111-2120, 2013 IEEE International Symposium on Parallel & Distributed Processing. 2013.
7.
Gritsenko A. Prediction of DRMS workload by identification of patterns in job
submission processes. // Journal
of International Scientific Publications: Materials,
Methods and Technologies, Vol. 6, part 1, pp. 93-100. Bulgaria. 2012.
8.
Gritsenko A. A workflow-forecast approach
to the task scheduling problem in distributed computing systems.
// International Journal of Advanced
Studies in Computer
Science and Engineering, Vol. 2, Issue 2, pp. 1-7. 2013.
