Прогнозирование загрузки ЭВМ, входящих в корпоративные вычислительные сети
ХАЛИМОН В.И., СМИРНОВ А.В.
The paper proposes algorithm for making long-term forecasts of CPU load for computers belonging to the corporate computer networks. The algorithm is designed for use in distributed computing, but can be applied to solve other problems. The basis of the algorithm is the identification of typical CPU usage patterns, and the regularity of their alternation.
В настоящий момент наблюдается активное развитие сетей ЭВМ и повышение их пропускной способности. Это дает возможность отдельным независимым исследователям использовать распределенные вычислительные системы в локальных и корпоративных сетях ЭВМ. Такие сети обладают следующими особенностями:
- состоят из сравнительно небольшого числа ЭВМ (до нескольких сотен);
- сегменты сети могут являться как частью локальной сети, так и быть удаленными друг от друга территориально и связанными через internet-среду;
- ЭВМ, входящие в такие сети, могут существенно отличаться своими характеристиками, видом сетевого подключения и режимами использования;
- ЭВМ являются неотчуждаемыми, т.е. на них также могут выполняться задачи пользователей, имеющие более высокий приоритет.
Принципы организации распределенных вычислений для таких сетей в данный момент не проработаны достаточно глубоко.
Суть идеи распределенных вычислений в описанных сетях заключается в разбиении исходной вычислительной задачи на фрагменты, называемые подзадачами. Каждая такая подзадача состоит из набора данных и алгоритма их обработки, реализованного в виде программного модуля [1].
Все ЭВМ, доступные для проведения вычислений, поддерживают активное сетевое подключение с компьютером - координатором, и называются вычислительными элементами (ВЭ). Координатор осуществляет выделение ЭВМ для решения вычислительных задач путем передачи списка вычислительных элементов программе, осуществляющей общее управление ходом вычислений - диспетчеру вычислений. Диспетчер рассылает подзадачи на доступные ЭВМ, и затем собирает и сохраняет результаты вычислений.
Одним из важнейших аспектов организации таких вычислений является прогнозирование загрузки ЭВМ задачами пользователя на заданном временном интервале [6, 7]. Такой прогноз позволяет произвести оценку ключевых характеристик, описывающих процесс вычислений:
- оценка времени решения подзадачи на конкретном вычислительном элементе, начиная с заданного момента времени;
- оценка общего времени проведения расчетов по задаче.
Помимо прогнозирования процессорной загрузки ВЭ также существуют близкие по смыслу задачи: прогнозирование доступности и надежности вычислительных элементов на заданном интервале времени. На основе построенных прогнозов становится возможной реализация эффективных политик назначения фрагментов (подзадач) вычислительной задачи на отдельные ЭВМ, учитывающие характер использования ЭВМ.
Перед тем как перейти к описанию алгоритма построения прогнозов, рассмотрим способ представления состояния вычислительного элемента во времени.
В каждый момент времени t вычислительный элемент характеризуется вектором состояния Vt.
Вектор состояния V состоит из трех компонент:
- загрузка ВЭ задачами пользователя, описывается вещественным числом L (load), L[0,1]. При этом L=0 означает, что ЭВМ не выполняет никаких задач пользователя, а L=1 значит, что все процессорное время ЭВМ отведено под эти задачи;
- доступность ВЭ (наличие сетевого подключения к координатору), описывается вещественным числом A (availability), A[0,1]. Смысл значений параметра раскрыт ниже;
- загрузка ВЭ подзадачами, описывается вещественным числом S (subtask load), S[0,1]. При S=0 ВЭ не производит расчетов по подзадачам, при S=1 все процессорное время отведено решению подзадач.
Таким образом, Vt = {Lt,At,St}. Очевидно, что (L + S) ? 1.
Фиксация вектора состояния производится через дискретные интервалы времени Дt. Состояние, когда ВЭ не функционирует (т.е. физически выключен), описывается вектором V = {0,0,0} и определяется как интервал, на котором сбор данных не проводился. В дальнейшем это состояние именуется сбоем ВЭ, т.к. оно приводит к потере прогресса в решении текущей подзадачи.
Состояние ВЭ в течение интервала времени [t1,t2] будет описываться набором пар (Vt,t), таких, что t[t1,t2]; Количество таких пар определяется интервалом Дt. Интервал Дt должен быть достаточно небольшим, чтобы уменьшить влияние попаданий на кратковременные "скачки" загрузки процессора, связанные с работой операционной системы и других приложений. В дальнейшем эти скачки устраняются с помощью фильтров.
Сбор данных о недоступности ВЭ выполняется путем измерения количества потерь (A=0 соответствует 100% потерь, A=1 - полному отсутствию потерь) при отправке пробных пакетов с ВЭ координатору и обратно (так называемый Heartbeat - сердцебиение).
Теперь мы можем сформулировать формальную постановку задач построения прогноза.
Задача прогнозирования загрузки ВЭ формулируется следующим образом:
Необходимо спрогнозировать загрузку ВЭ задачами пользователя на заданном интервале времени [t1,t2], с шагом Дt, т.е. получить набор пар (L,t). На основе этого прогноза можно будет в дальнейшем рассчитать предполагаемое время решения подзадачи на заданном интервале.
Задача прогнозирования доступности ВЭ формулируется следующим образом:
Необходимо оценить вероятности доступности ВЭ A1 и A2 на границах интервала времени [t1,t2]. Необходимым требованием является доступность ВЭ на момент начала и окончания вычислений для передачи исходных данных и результатов расчетов.
Задача прогнозирования надежности ВЭ формулируется следующим образом:
Необходимо оценить вероятность сбоя ВЭ E на интервале времени [t1,t2]. При этом верхняя граница t2 определяется в ходе оценки времени решения, т.е. фактически прогнозирование доступности и загрузки ВЭ осуществляется одновременно с оценкой времени решения подзадачи. Это обусловлено тем, что сама загрузка L влияет на время решения подзадачи.
В данной работе рассматривается алгоритм, позволяющий строить долгосрочные прогнозы загрузки ЭВМ задачами её владельца. Решение задач прогнозирования доступности и оценки вероятности сбоя оставлены за рамками работы, так как они основаны на широко известных подходах (см. например [3]).
Под долгосрочным прогнозом понимается оценка значений загрузки ЭВМ в дискретные моменты времени на интервале от нескольких часов до нескольких суток. Разработка алгоритма была мотивирована тем, что обычные виды прогнозирования, в том числе на основе рядов Фурье [2], при построении долгосрочных прогнозов дают большую ошибку и требуют ресурсоемких расчетов.
В основе алгоритма лежит обнаруженная авторами в ходе исследования выраженная суточная периодичность изменений загрузки ВЭ. При этом можно выделить несколько типовых циклов, в дальнейшем называемых паттернами загрузки, и рассматривать непрерывный временной ряд значений загрузки ЭВМ Lt как последовательность этих паттернов. Набор паттернов будет меняться в зависимости от конкретного предназначения ЭВМ. Другим базовым фактом, лежащим в основе алгоритма, является наличие статистических закономерностей в цепочке паттернов.
Цикличность может быть вызвана различными причинами, однако в большинстве изученных случаев она привязана к 24-часовым периодам. Для случаев, когда выраженной цикличности не наблюдается, необходимо использовать другие методы прогнозирования.
Поясним вышесказанное на примере. Для ЭВМ, применяемой в домашних условиях, можно выделить несколько паттернов загрузки, условно соответствующих дням недели: будний день, пятница, суббота, воскресенье. Эти паттерны представлены на рисунке 1. Изображение A соответствует будним дням, B - концу рабочей недели, C - выходным дням. Как можно заметить, будние дни характеризуются практически полным отсутствием загрузки в дневное время и сравнительно невысокой загрузкой в вечернее время. Пятница отличается высокой степенью загрузки, начиная с раннего вечера, и до ночи субботы. Выходные дни характеризуются средней загрузкой днем и высокой - вечером.
Рисунок 1 - Паттерны загрузки типового домашнего компьютера
Наличие статистических закономерностей в цепочке паттернов обуславливается сменой дней недели.
Алгоритм прогнозирования состоит из следующих шагов:
- получение статистических данных из файла;
- фильтрация данных методом скользящего среднего;
- поиск наилучшего разбиения на суточные периоды;
- разбиение данных на суточные периодограммы;
- вычисление корреляции периодов методом квадратичного отклонения;
- построение кластеров;
- получение суточных паттернов путем усреднения значений загрузки суточных периодов, входящих в соответствующий паттерну кластер;
- сопоставление паттернам символьных имен;
- кодирование начального набора данных в последовательность символов;
- генерация таблиц для построения цепей Маркова;
- составление прогноза в виде последовательности символов;
- декодирование сгенерированной последовательности с помощью паттернов;
- вычисление запрошенных оценок.
Рассмотрим части алгоритма и их реализацию подробнее.
Получение статистических данных из хранилища подразумевает получение сохраненной ранее последовательности значений Vt. В данном алгоритме используется только компонента L вектора, которая будет обозначатся Lt. Для анализа может быть выбрана только часть данных. Обозначим количество полных суток в выбранном диапазоне как D.
Фильтрация значений загрузки производится с помощью фильтра скользящего среднего [5], окно усреднения выбрано равным 15 минутам.
Затем осуществляется поиск наилучшего начального сдвига, начиная с которого производится разбиение исходных данных на суточные периодограммы. Под наилучшим начальным сдвигом понимается такой сдвиг, при котором суммарное значение загрузки в моменты времени, разделяющие суточные периоды, будет минимальным, т.е.
,
где k соответствует количеству измерений за 24 часа. Иными словами, мы стремимся подобрать точку разбиения так, чтобы она попадала на моменты продолжительного отсутствия загрузки.
После получения T производится разбиение исходной периодограммы на D отдельных суточных периодограмм DLd.
Следующим этапом вычисляется корреляция всех полученных периодограмм между собой. Строго говоря, вычисляется не корреляция, как таковая, а некоторая функция расстояния между периодограммами. Всего таких расстояний будет D(D-1)/2. Расстояние между парой периодограмм DLi и DLj вычисляется по формуле:
.
После этого осуществляется кластеризация, то есть разбиение исходного множества периодограмм на несколько непересекающихся множеств, объединяющих схожие периодограммы. Каждому найденному кластеру присваивается символьное имя. Обозначим количество выделенных кластеров, как C, длину i-того кластера, как si, а множество входящих в него периодограмм, как P(ci), где i[0,C].
Далее, для каждого кластера составляется паттерн суточной загрузки. Для этого вычисляется усредненная периодограмма, каждый элемент которой является средним значением между соответствующими элементами всех периодограмм, входящих в данный кластер:
,
где - элемент, соответствующий времени t j-ой периодограммы, входящей в кластер ci.
После этого происходит кодирование начального набора данных. В процессе кодирования составляется цепочка символов , каждый из которых соответствует кластеру, к которому был отнесен данный суточный период:
На основе полученной цепочки составляется таблица вероятностей перехода из некоторого заданного состояния системы в другие [4]. Состояние системы определяется, как последовательность из символов, соответствующих состоянию, в котором находится система в данный момент, и нескольких предыдущих состояний. В данный момент длина последовательности SL составляет 4 элемента, то есть, используется таблица вероятностей переходов 4-го порядка. Вероятности вычисляются путем подсчета количества переходов из текущего состояния в каждое возможное новое с последующим переходом от статистических вероятностей к математическим (нормализацией).
Построение прогноза осуществляется следующим образом:
- выбирается участок периодограммы, включающий в себя SL полных суток и интервал с окончания последнего суточного периода до текущего момента;
- последовательность из целых суточных периодограмм кодируется путем поиска наиболее близкого паттерна для каждого периода;
- для текущего суточного периода составляется прогноз на основе цепей Маркова и вычисляется значение функции расстояния между текущим периодом и спрогнозированным шаблоном;
- для текущего периода ищется наиболее близкий паттерн и вычисляется значение функции расстояния;
- из двух полученных таким образом символов выбирается тот, отклонение от которого наименьшее, и подставляется в цепочку;
- цепочка дополняется на заданное количество периодов;
- сгенерированная последовательность символов декодируется на основе паттернов;