Статистическая оценка времени завершения вычислительного эксперимента в Desktop Grid

Аннотация. В статье представлен статистический подход к решению задачи оценивания времени завершения набора заданий в Desktop Grid. Представлены статистический подход, основанный на модели Хольта и результаты численного моделирования на основе статистики проекта добровольных вычислений RakeSeach.
Ключевые слова: BOINC, Desktop Grid, high-throughput computing, модель Хольта, доверительный интервал, оценка времени завершения.

Для выполнения высокопроизводительных расчётов, а также обработки больших массивов данных, как правило, используют суперкомпьютеры или вычислительные кластеры. Однако с развитием каналов связи сети Интернет и ростом производительности персональных компьютеров, становится все более популярным направление, связанное с организацией Desktop Grid [1; 53]. Desktop Grid – грид-система, состоящая из неспециализированных вычислителей и использующая их временно-свободные вычислительные ресурсы для вычислительноёмких расчётов. Преимущества технологии: практически неограниченные масштабируемость, устойчивость к сбоям, минимальная стоимость создания и сопровождения вычислительной сети [2; 184]. Наибольшей популярностью вычисления в рамках Desktop Grid используются в научной сфере (математика, биология, астрономия и т.п.). Эти системы подходят для выполнения научных высокопроизводительных расчётов. Одной из наиболее популярных платформ организации распределённых вычислений в Desktop Grid является BOINC.

Платформа BOINC имеет архитектуру «клиент-сервер», при этом клиентская часть может работать на произвольном количестве компьютеров с различными аппаратными и программными характеристиками. Сервер поддерживает одновременную работу большого числа независимых проектов. Ключевым понятием при организации BOINC является проект – автономная сущность, в рамках которой производятся распределённые вычисления [1; 54].

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

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

Рассмотрим процесс накопления выполненной работы, который задается временным рядом и является строго возрастающим: . Его значения фиксированы в моменты времени. Значение превысит заданный порог (см. рисунок 1 а) в момент времени , который необходимо оценить в момент прогноза .

Процесс отражает время завершения -ого задания Desktop Grid. Требуется оценить значение процесса на шаге – время упреждения, см. рисунок 1 b) на -ом шаге. Будем считать, что есть некоторая функциональная зависимость между прошлыми и будущими значениями ряда, имеющая кусочно-линейный вид с восходящим трендом: где - это случайная ошибка, имеющая нулевое математическое ожидание и постоянную дисперсию. Рисунок 1 – Прогнозируемый процесс

С точки зрения Desktop Grid наблюдаемый процесс является строго возрастающим (в один момент времени нельзя получить два результата), производительность вычислительной системы характеризуется углом наклона линии тренда, а производительность вычислительной системы может изменяться (возрастать или убывать), так как интерес к проекту тоже меняется и это изменение происходит линейно. В данной работе модель Хольта или двойного экспоненциального сглаживания была выбрана в качестве модели прогнозирования.

Модель Хольта или двойное экспоненциальное сглаживание применяется для моделирования процессов, имеющих тренд. В этом случае рассматривают две составляющие: уровень и тренд, сглаживание которых выполняется по отдельности [3; 28]:

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

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

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

Доверительный интервал, учитывающий неопределённость, связанную с положением тренда, и возможность отклонения от этого тренда, определяется в следующем виде [4; 162]:
Где – точечный прогноз на момент ,
где – это количество зафиксированных наблюдений временного ряда, а – период упреждения,
– значение статистики Стьюдента, – дисперсия отклонений расчётных наблюдений от фактических;
- порядковый номер уровней ряда,
– порядковый номер уровня, стоящего в середине ряда. Дисперсия отклонений фактических наблюдений от расчётных определяется выражением: - фактические значения уровней ряда, - расчётные значения уровней ряда, - длина временного ряда. Таким образом, ширина доверительного интервала зависит от уровня значимости, периода упреждения, среднего квадратического отклонения от тренда и числа фактических наблюдений.

В заключение, стоит отметить, что в работе представлен статистический подход к оценке времени завершения набора заданий в Desktop Grid. В качестве исходных данных была взята статистика расчёта проекта RakeSearch. Из исходного набора данных выделялись записи о времени завершения уникальных подзаданий. Для оценки времени завершения брались наборы заданий случайной продолжительности (от 100 до 1000 подзаданий) со случайным временем упреждения (от 10 до 50 подзаданий). В качестве статистической модели была выбрана модель Хольта экспоненциального сглаживания с учетом тренда. Результаты экспериментов изображены на рисунке 2. Были построены 2 доверительных интервала с вероятностями 0,95 и 0,8. Рисунок 2 – Прогнозирование и доверительные интервалы с вероятностью 0,95 и 0,8

При применении данного подхода на практике необходимо учитывать некоторые нюансы. Во-первых, от параметров коэффициентов сглаживания ряда и тренда зависит точность аппроксимации моделью Хольта. Во-вторых, при прогнозировании на большое число шагов вперед необходимо объединять в одно значение ряда результаты, которые поступили за какой-то период времени. Для построения доверительного интервала необходимо брать последних точек, которые формируют текущий тренд проекта. При поступлении новых результатов необходим пересчёт прогноза (расчеты дополняются новой точкой). Указанные аспекты планируется учесть при построения алгоритма оценки соответствующего ему модуля оценки, реализованного для платформы BOINC.

Список литературы

1. Ивашко Е. Е., Никитина Н. Н. Использование BOINC-ГРИД в вычислительноёмких научных исследованиях // Вестник Новосибирского Государственного Университета. Серия: Информационные технологии, 2013. - 53-57с.
2. Ивашко Е. Е. Desktop Grid корпоративного уровня // Программные системы: теория и приложения, 5:1, 2014. - 183-190с.
3. Чучуева И. А. Модель прогнозирования временных рядов по выборке максимального подобия, 2012. - 155с.
4. Четыркин Е. М. Статистические методы прогнозирования. - М.: Статистика, 1997. -198 с.

В. С. Литовченко