Проект Templet

Перевод статьи: An Architecture for Resource Behavior Prediction to Improve Scheduling Systems Performance on Enterprise Desktop Grids, Advances in New Technologies, Interactive Interfaces and Communicability, Lecture Notes in Computer Science Volume 7547, 186-196 (2012)

Авторы: Sergio Ariel Salinas¹, Carlos García Garino^1,2, and Alejandro Zunino³

1. Instituto para las Tecnologías de la Información y las Comunicaciones (ITIC), UNCuyo, Mendoza, Argentina
2. Facultad de Ingeniería, UNCuyo, Mendoza, Argentina
3. ISISTAN, Facultad de Ciencias Exactas, UNICEN, Tandil, Argentina

Перевод: Артамонов Юрий

Промышленные настольные Грид-системы - это дешёвая платформа, которая использует простаивающие настольные компьютеры для запуска Грид-приложений. Поскольку ПНГС ¹⁾ используют компьютеры во время простоя, важно оценить ожидаемое время доступности. На основании этой оценки, система планирования может выбрать компьютеры с большей ожидаемой доступностью для запуска приложений. Как следствие, достигается большая совокупная производительность. Различные методики прогнозирования предлагались для предсказания состояния компьютера на момент времени, но этой информации недостаточно. Модель прогнозирования предоставляет последовательность состояний компьютера для различных моментов времени. Проблема в том, как определить поведение компьютера имея последовательность состояний. Мы выявляем необходимость создания архитектуры для моделирования и оценки поведения настольных компьютеров. Таким образом, система планирования может сравнить и выбрать ресурсы, которые позволят выполнить вычисления быстрее. Эксперименты показали, что программы работают до 8 раз быстрее, когда планировщик выбирает компьютер, предложенный нашим методом.

Ключевые слова: промышленные настольные Грид-системы, система обнаружения ресурсов, предсказание поведения компьютера, система планирования, алгоритмы классификации.

В прошлые годы, промышленные настольные Грид-системы (ПНГС) стали более дешёвой альтернативой традиционным вычислительным Грид-системам. Эта технология объединяет настольные компьютеры в различных учреждениях по всему миру, таких как: университеты, школы и предприятия. ПНГС используют время простоя настольных компьютеров для запуска ресурсоёмких вычислительных задач с независимыми задачами. Затраты на обслуживание платформы сильно распределены между участниками-учреждениями. По этой причине учёт технологической инфраструктуры может представлять интерес для латиноамериканских учреждений.

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

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

Методики предсказания доступности компьютеров применялись для различных целей: для улучшения балансировки нагрузки, для предотвращения отказов или для предсказания доступности компьютеров. Эти методики работают лучше, если события анализируются в соответствии с определёнными шаблонами. Эту ситуацию можно наблюдать в ПНГС, где большинство ресурсов участников расположено в различных офисах или учебных лабораториях. Компьютеры в офисах остаются включены в те же интервалы времени, например, с 8:00 утра и до 6:00 вечера. С другой стороны использование компьютеров в учебных лабораториях организовано в соответствии с учебным планом. По этой причине мы считаем, что можно с высокой точностью состояние компьютеров в ПНГС.

Различные методы предсказания оценивают ожидаемое состояние компьютера на момент времени. Возможные состояния: доступен, занят, включен, выключен и т.д. Для каждого компьютера можно рассчитать последовательность ожидаемых состояний для временного интервала. Мы используем понятие поведения ресурса для обозначения изменений состояний компьютера. Рассмотрим компьютер, который постоянно переходит из состояния доступен в состояние занят в интервале времени i. Его поведение является неустойчивым и не подходит для запуска приложений в интервале i. Возможные поведения ресурса полезны для процесса выбора компьютеров планировщиком.

В этой статье мы предлагаем архитектуру для предсказания, вычисления и оценки поведения настольных компьютеров в ПНГС. Архитектура улучшает процесс выбора компьютеров планировщиком. Как следствие, снижается время выполнения приложений, что приводит к общему увеличению производительности. Для проверки архитектуры, мы проводили мониторинг набора компьютеров в университете UNCyou в течение месяца. После этого мы смоделировали выполнение распределённых приложений на разных компьютерах. Мы рассмотрели две ситуации: 1) планировщик выбирает компьютеры случайно 2) планировщик выбирает компьютеры на основе информации, предоставленной нашей архитектурой. Результаты эксперимента показали улучшение до 8 раз быстрее выполнение приложений в различных сценариях. Вклад этой работы: 1) архитектура для вычисления информации, необходимой для системы планирования для быстрого выполнения приложений 2) эвристические модели поведения компьютера для сравнения поведения компьютеров простым способом.

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

Сетевая служба погоды (ССП) предоставляет точные прогнозы динамического изменения характеристик производительности для распределённого набора метавычислительных ресурсов. Механизм предсказания использует смесь экспертных оценок, каждая из которых имеет свои параметры. Опираясь на историю производительности, каждая модель выполняет прогноз для серии измерений. Система использует набор датчиков для сбора наблюдаемых измерений, которые сохраняются в постоянной памяти. Собранные данные: доли процессорного времени для новых процессов, время соединения TCP, пропускная способность и значения задержки на пути от точки до точки и обратно. Процесс прогноза запрашивает релевантную историю измерений из постоянной памяти для генерации предсказания.

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

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

Методы прогнозирования также были использованы в планировании систем. Планировщик реального времени (ПРВ) - система пользовательского уровня, которая советует, как планировать задачи реального времени. Цель ПРВ - помочь клиентским приложениям уложиться в сроки и сообщить, если сроки не могут быть удовлетворены. Предсказание ресурсов основанное на статистическом анализе описано в (..). Система предлагает ресурс из набора компьютеров, таких, что задача с номинальным временем исполнения T_nom, при запуске сейчас, будет исполнена во время (1+SF)T_nom или менее с уверенностью CONF, где SF - фактор слабости.

Децентрализованный подход для систем добровольных вычислений на базе предсказания наличия ресурсов представлен в (..). Предсказание наличия ресурсов основывается на 3 входных коэффициентах: 1) доступность ресурса 2) доступность группы 3) текущая доступность группы. Первый коэффициент вычисляется из зарегистрированной истории активности ресурса. Он показывает вероятность того, доступна ли данная машина в данное время недели. Второй коэффициент учитывает количество ресурсов доступных в данное время. Наконец, третий коэффициент вычисляется на основе количества занятых и простаивающих компьютеров. Эта модель сокращает количество прерванных работ в распределённой системе с невыделенными настольными компьютерами.

В отличие от существующих работ, наше предложение выполняет оценку эволюции различных состояний компьютера за временной интервал. Хотя можно использовать любой метод прогнозирования, упомянутый ранее, мы предлагаем использовать алгоритмы классификации из области искусственного интеллекта. Эти алгоритмы выбраны потому, что статистические модели дают низкую точность в сценариях с периодическими событиями. Например, настольные компьютеры включают/выключают каждый день или они находятся в автономном режиме из-за неполадок. Алгоритмы классификации показали высокую точность во время предварительных испытаний при прогнозировании будущих состояний компьютера. На основе выполненного предсказания мы предлагаем эвристику для моделирования поведения компьютера через набор метрик. Таким образом можно сравнить различное поведение компьютеров. Эта архитектура, как ожидается, будет частью системы обнаружения ресурсов для предоставления исчерпывающей информации о ресурсе для улучшения общей производительности настольной Грид-системы. По этой причине, эта архитектура объединяет компоненты для управления информацией о возможностях компьютеров. В следующем разделе мы рассмотрим предлагаемую архитектуру и подробно изучим её компоненты.

Главная цель предлагаемой архитектуры - предоставление исчерпывающей информации о настольных компьютерах в ПНГС. Эта информация включает в себя: 1) мощность вычислительных возможностей 2) установленные приложения 3) предсказание доступности компьютера 4) набор метрик, определяющих ожидаемое поведение ресурса для заданного интервала времени. Архитектура действует на каждом компьютере и состоит из следующих модулей: 1) датчик активности ресурса 2) предварительный обработчик 3) предсказатель 4) анализатор 5) описатель 6) реестр. Взаимодействие между модулями показано на рисунке (..). Датчик активности ресурса отслеживает и записывает данные об активности компьютера. Модуль предварительной обработки создаёт обучающий набор данных на основе данных, сгенерированных датчиком. Модуль предсказания использует этот набор для оценки шаблона поведения ресурса в прошлом. На основе этой информации, он предсказывает ожидаемое поведение интервала времени в будущем. Модуль анализа принимает на вход ранее сделанное предсказание и рассчитывает набор метрик, определяющих ожидаемое поведение компьютера. Модуль описателя сканирует возможности аппаратного и программного обеспечения. Наконец, информация, полученная с помощью анализатора и дескрипторов направляется в модуль реестра. Реестр отвечает за информацию об управлении ресурсами. Далее рассмотрим более детальное описание архитектуры и компонентов.

Датчик активности ресурса - это программный компонент, который периодически собирает информацию об активности компьютера. Записываются данные: 1) дата и время 2) процент свободной оперативной памяти 3) загрузка процессора. Для сохранения консистентной информации время и дата компьютера синхронизируется с центральным сервером. Датчик с настраиваемой частотой записывает активность ресурса. Затем он хранит эту информацию для дальнейшего анализа. Процесс мониторинга ресурсов является неинвазивным и полностью прозрачен для пользователя. В общем, место для хранения записываемой информации не превышает 1 мегабайта в день. Регулярно, старые записи стираются для ограничения объёма хранимой информации.

Алгоритмы классификации из области искусственного интеллекта требуют обучающий набор данных с мечеными данными для классификации новых экземпляров данных. Модуль предварительной обработки отвечает за создание этого набора данных. Он имеет следующую информацию: 1) месяц 2) день 3) час 4) минута 5) состояние процессора 6) ОЗУ 7) состояние компьютера. Обучающий набор данных вычисляется на основе данных, собранных с помощью датчика активности. Метки для процессора, ОЗУ и состояния компьютера определяются на основе различных порогов. Например, если процент свободной оперативной памяти больше 90% используется метка «свободный». Возможные режимы для оперативной памяти: «свободный» или «полный». Метки, используемые для процессора: «занят» или «простой». Состояние компьютера определяется на основе состояния процессора и ОЗУ. Возможные значения: «доступный», «занято» или «выключен». Например, если процессор находится в состоянии простоя и оперативная память свободна, то компьютер доступен для приложений Грид. Для каждой записи, созданной датчиком активности, вычисляется набор данных. Этот процесс занимает несколько секунд и срабатывает с определённой настраиваемой частотой.

Набор данных представляет изменения в состоянии компьютера за период времени. В каждый момент времени t₁, t₂, … t_N есть запись о наборе данных, который вычисляется на основе сигнала датчика активности. Для моментов времени без данных от датчика активности состояние считается равным «выключен». Обучающий набор данных используется модулем предсказания для оценки состояния компьютера на определённый момент времени. Каждый компьютер хранит свой набор данных и записей активности. В процессе тестирования использовались обучающие данные результатов мониторинга информации с настольных компьютеров университета UNCuyo. Алгоритм C4.5 показал самую высокую среднюю точность, около 90%. По этой причине был использован в процессе тестирования.

Модуль предсказания направлен на оценку возможных состояний компьютера для интервала времени. Мы предлагаем использовать алгоритмы классификации из области искусственного интеллекта, поскольку они показали точность 90% в предварительных испытаниях. Тем не менее, можно использовать любую модель прогнозирования, представленную ранее. Фреймворк Weka позволяет тестировать различные алгоритмы классификации, для дальнейшего анализа смотри (..). Прогноз состояния представляется как массив предсказания поведения ресурса (МППР). Какждый МППР ассоциируется с заголовком предсказания поведения ресурса (ЗППР). МППР ³⁾ - это последовательность состояний компьютера state₁, state₂, …, state_n, которые были предсказаны для интервала времени между t₁ и t_n. Возможные состояния вычисляются модулем предварительной обработки. ЗППР ⁴⁾ предоставляет информацию о массиве предсказания поведения ресурса. Это информация важна модулю оценки для обработки МППР и включает: 1) временную зону компьютера 2) дата и время, когда предсказание было получено 3) дата начала 4) дата окончания 5) частота дискретизации 6) метод предсказания 7) точность метода предсказания.

Модуль анализа отвечает за вычисление набора показателей, моделирующих ожидаемое поведение компьютера за интервал времени. Этот модуль - главный компонент предлагаемой архитектуры. Он реализует эвристическую модель для предсказания поведения компьютера на базе массива предсказания поведения ресурса. Эта эвристическая модель характеризует поведение компьютера, что облегчает сравнение разных компьютеров. Таким образом система планирования может выбрать эти компьютеры с более высокой вероятностью успешного завершения программы. Набор меток включает следующие:

• Счётчик состояний: количество экземпляров определённого состояния в МППР
• Кластеризация: количество кластеров выбранного состояния в МППР
• Связность: значение, которое представляет, как связаны кластеры состояния, анализируемого в МППР. Этот показатель рассчитывается по следующей формуле: Cohesion = StateCount/Clustering
• Область состояний: это значение считает количество экземпляров t_i с первого до последнего вхождения
• Стабильность: это значение предоставляет измерение, которое представляет насколько изменчиво состояние, анализируемое в соответствии с МППР. Компьютеры, которые показывают более высокие значение, скорее всего выполнят программу быстрее. Этот показатель вычисляется следующим образом: Stability = Cohesion/Statescope

Далее, мы вводим пример, который представляет, как этот модуль работает. Рассмотрим следующую ситуацию. Система планирования требует два настольных компьютера для запуска приложения, которое требует 4 единицы времени исполнения. Есть семь компьютеров, которые удовлетворяют требованиям приложений. МППР для каждого компьютера показан в таблице (..).

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

Модуль описания - самостоятельный компонент, который сканирует и автоматически собирает возможности аппаратного и программного обеспечения компьютера. Основной целью данного модуля является публикация вычислительных возможностей. Эта информация находится под управлением системного модуля реестра и может включать: частоту процессора, ОЗУ, возможности жёсткого диска, установленную сетевую карту, операционную систему, установленные приложения. Вычислительные возможности необходимы системе планирования для выбора ресурсов, которые удовлетворяют программным и аппаратным требованиям для работы приложений. Любые изменения в возможностях компьютера периодически обновляются и отправляются в модуль реестра.

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

Процесс тестирования предлагаемой архитектуры ставит своей целью оценить улучшение производительности системы. С этой целью были смоделированы 2 сценария: 1) система планирования выбирает компьютер для запуска процесса случайным образом 2) система планирования выбирает компьютер в соответствии с нашим предложением. Показатель используемый для оценки производительности - среднее время для обоих сценариев. Модуль предсказания использует алгоритм классификации C4.5 из области искусственного интеллекта.

Процесс моделирования использует информацию, собранную с 30 компьютеров в университете UNCyou. В течение 20 дней, приложение отслеживало и записывало каждые 10 секунд загрузку процессора и доступный объём ОЗУ. Эта информация была включена в главную базу данных для дальнейшего анализа. В соответствии с полученными данными, компьютеры доступны в 8:00 утра и до 4:00 вечера. Из собранных данных можно заметить, что компьютеры используются более интенсивно утром, чем в послеобеденное время. По этой причине эксперименты были разделены на 2 периода времени: 1) с 8:00 утра до 12:00 вечера и 2) с 12:01 утра и до 4:00 вечера.

Для упрощения процесса имитационного моделирования мы принимаем следующие допущения:

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

Количество приложений, работающих одновременно, было рассчитано, как процент от участвующих компьютеров. Проценты включали: 30%, 60%, 100% и 120%. В последнем случае количество приложений на 20% больше, чем количество компьютеров. Этот вариант делает возможным моделирование различной нагрузки. Выполнение вычисляется как разница между начальной и конечной меткой времени, независимо от того, сколько раз компьютер был выключен.

Моделирование включало 8607 экземпляров приложений со случайным исполнением, генерируемые между 600 и 3600 секундами. Время старта приложения также выбиралось случайно из интервалов времени, упомянутых выше. Процесс моделирования выполнял следующие шаги. Время запуска и время исполнения необходимые для приложения выбирались случайно. Процесс выполнения приложения моделировался на случайно отобранном компьютере. Затем то же приложение было смоделировано на компьютере, выбранном в соответствии с предложенной методикой. Наконец, время, необходимое для запуска приложения рассчитывалось для обоих сценариев.

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

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

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

Чтобы проверить наше предложение, мы провели мониторинг 30 настольных компьютеров в университете UNCuyo в течение 20 дней. Программный компонент записывал каждые 10 секунд загрузку процессора и доступный объём ОЗУ. Эта информация использовалась для тестирования нашего предположения и для оценки различных алгоритмов классификации. Предложенная архитектура может использовать любую методику предсказания, описанную в работе. В предварительном этапе мы оценивали различные алгоритмы из области искусственного интеллекта с использованием фреймворка Weka. Алгоритм C4.5 был выбран потому, что предсказание состояний компьютера показало 90% точность.

Процесс моделирования был использован для оценки того, как информация, предоставленная нашим предложением повышает производительность системы планирования. С этой целью мы сравнили две стратегии выбора компьютера: 1) случайный выбор 2) отбор, основанный на нашем предложении. Процесс моделирует 8607 экземпляров приложений в рамках различных сценариев нагрузки, в том числе: 30%, 60%, 100% и 120%. В последнем случае количество приложений на 20% больше, чем количество компьютеров. Время выполнения необходимое для различных экземпляров приложений варьировалась от 600 до 3600 секунд. Наше предложение сработало лучше чем случайный выбор на более чем 57% приложений и даёт возможность выполнения в среднем в 8 раз быстрее.

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