Возможности по улучшению механизма выявления дисбалансов загрузки в подсистеме балансировки TriadBalance

Размещено на http://www.allbest.ru/

УДК 004.032.26

Возможности по улучшению механизма выявления дисбалансов загрузки в подсистеме балансировки TriadBalance

C.А. Кирилловых

Пермский государственный университет, Россия, 614990, Пермь, ул. Букирева, 15

newserg88@mail.ru; 89026313552

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

В системе имитационного моделирования Triad.Net за эффективную загрузку вычислительных узлов и соединительных каналов отвечает подсистема балансировки TriadBalance и ее ключевое звено - агент анализа. Выбор схемы работы агента анализа приведен в [1, 2]. В данной статье предлагается ряд подходов к улучшению работы агента анализа, а также описываются результаты пробного внедрения этих подходов.

Ключевые слова: балансировка нагрузки; генетический алгоритм; нейронная сеть; TriadBalance.

вычислительный мощность имитационный балансировка

Capabilities of improving disbalance recognizing method in load-balancing subsystem TriadBalance

S. A. Kirillovykh

Perm State University, Russia, 614990, Perm, Bukireva st., 15

newserg88@mail.ru; 89026313552

In imitation modeling experiment the importance of execution speed and load-balancing efficiency is growing more because in contrast to real systems resources in imitation modeling systems are virtual and access speed is insignificant. In the imitation modeling system Triad.Net a balancing subsystem and its key part - analysis agent - are responsible for effective load of computational nodes and connection cables. The selection of working scheme for analysis agent is listed in previous works of the author. In this report some approaches to improving its work are discussed and results of its introduction into working scheme are disclosed.

Key words: genetic algorithm; load balancing; neural network; TriadBalance.

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

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

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

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

В системе проведения имитационного эксперимента Triad.Net подсистема балансировки действует на мультиагентной основе, а непосредственно за выявление момента возникновения дисбаланса отвечает агент анализа.

В работе [1] приводится обоснование выбора связки нейронной сети по типу персептрона и генетического алгоритма, построенного для определения оптимальной конфигурации нейронной сети, в качестве основы для реализации агента анализа.

Рис. 1. Декомпозиция задачи агента анализа

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

Общая схема работы агента анализа

Принципиальная схема работы агента анализа приведена на рис. 1. Курсивом выделен передаваемый промежуточный результат между компонентами рабочей части агента. Решателем, или рабочим звеном назовем главную часть агента анализа - искусственную нейронную сеть (ИНС) с конфигурацией, выбранной в результате работы генетического алгоритма (ГА).

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

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

Подробнее о работе агентов и принципе организации системы Triad.Net можно прочесть в [3, 4, 5, 6].

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

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

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

Объединение в качестве решателя нескольких нейронных сетей

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

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

Данный подход был проверен на практике. В первом варианте работы ГА оставалась только одна нейронная сеть из исходного пула особей. Во втором варианте все 9 нейронных сетей, оставшихся на последнем этапе, объявлялись победителями и все 9 сетей участвовали в рабочем режиме работы, мнения сетей объединялись по принципу большинства голосов. Проверка осуществлялась по всей обучающей выборке. Результаты сравнения двух подходов приведены на рис. 2. Ошибка измеряется в относительных единицах.

Рис. 2. Использование объединения решателей

Как можно видеть, особого улучшения качества распознавания дисбалансов добиться не удалось. Следовательно, можно заключить, что к последнему этапу работы ГА выживают примерно одинаковые по своей успешности особи. Однако в результате проведенных экспериментов можно также сделать вывод о более стабильной работе объединения лучших сетей. Это значит, что в тех случаях, когда важнее не допустить ошибку либо же когда перемещение вычислительных ресурсов слишком дорого стоит, предпочтительнее использовать второй вариант.

Механизмы контроля за обучением

Обучение нейронной сети представляет собой сложную задачу. Наибольшие трудности доставляет определение обучающей выборки и порядка ее "прогона", т.е. порядка подачи на вход ИНС с целью обучения. Также ИНС может заучивать выборку до состояния, когда она теряет способность дообучаться, но при этом необходимо "прогонять" обучающую выборку достаточное число раз, чтобы сеть обучилась, и избегать тем самым ситуации недообучения, когда ИНС может давать разные ответы на сходные входные векторы [7, 8, 9].

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

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

В качестве других алгоритмов были предложены и опробованы bagging (bootstrap and aggregation) для контроля за переобучением и boosting для контроля за недообучением.

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

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

Проблема переобучения может также решаться с помощью регуляризации (сокращения весов, pruning), раннего останова и оптимизации структуры сети [12].

Сам алгоритм bagging (bootstraping and aggregating) достаточно прост для понимания. Приведем алгоритм непосредственно для нейронной сети, хотя он универсален [10], т.е. может применяться для любого обучающегося классификатора (под классификатором можно понимать и наше рабочее звено - персептрон, по сути, он относит входной вектор к одному из трех классов: нет дисбаланса, есть дисбаланс перегрузки каналов, есть дисбаланс перегруженности узлов).

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

Затем на основе каждой из полученных выборок строится ИНС. Выходы комбинируются (агрегируются) путем голосования или простого усреднения.

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

Однако существуют и ограничения в применении метода. Как изложено в работе [11], в случае больших по объему выборок алгоритм становится неэффективным ввиду сближения классификаторов, получаемых для разных выборок по механизму, описанному выше. Но там же отмечено, что сильные стороны алгоритма bagging проявляются именно на "нестабильных" классификаторах, к которым относят нейронные сети и деревья решений. Под нестабильностью здесь понимается чувствительность к малым отклонениям в данных, подаваемых для обучения. Этот механизм предназначен для исключения ситуации, когда ИНС "недообучилась", то есть недостаточное число раз была подана обучающая выборка, в результате чего ИНС "недоучила" данные примеры и не приобрела способность выявлять схожие с заключенными в этих примерах ситуации.

Ключевые отличия boosting от предыдущего алгоритма приведены в работе [11]:

bagging базируется на случайных и независимых изменениях, которые порождаются разбиением примеров выборки с их последующим распределением по нескольким выборкам;

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

Механизм кросс-валидации относится к числу стандартных механизмов контроля обучения, поэтому при обучении ИНС не было смысла от него отказываться. Были испробованы три варианта контроля обучения с использованием: только кросс-валидации, кросс-валидации вместе с bagging и кросс-валидации с boosting.

Однако существенного улучшения качества распознавания дисбалансов получить не удалось (см. рис. 3). Ошибка сети с применением boosting, например, оказалась между ошибкой лучшей из ИНС в пуле сетей и средней ошибкой по всем сетям в пуле.

Рис. 3. Применение алгоритма boosting

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

Сокращение нейронной сети

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

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

Более простой подход состоит в сокращении нейронной сети (pruning). То есть предпринимается попытка максимально сжать ИНС за счет удаления менее значимых, по сравнению с остальными, синаптических связей и нейронов. Значимость в случае удаления связи определяется по ее весу, а в случае удаления нейрона - по суммарному весу всех входящих в нейрон связей.

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

Один из путей проведения сокращения вычислений - использование алгоритма Оptimal Brain Surgery (OBS) [12]. В нем выбор удаляемой связи определяется исходя из минимума функции, связанной с градиентом распространения ошибки. Однако можно производить сокращение и простым удалением слишком маленьких весов (меньше определенного порога), а также нескольких наименьших входящих весов для каждого нейрона. Конкретное число или даже стратегия удаляемых весов и нейронов - настроечный параметр, который также может подбираться в том же генетическом алгоритме.

Используемый вариант предполагал удаление двух самых маленьких весов для каждого нейрона и двух нейронов с меньшей суммой входных весов на каждом слое.

Суммарная ошибка ИНС после проведения сокращений меньше, чем ИНС до их проведения (см. рис. 4).

Рис. 4. Изменение суммарной ошибки в зависимости от проведения сокращений сети

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

Заключение

В этой статье были рассмотрены пути повышения эффективности работы механизма выявления дисбалансов загрузки в подсистеме балансировки TriadBalance. Они позволили на четверть уменьшить суммарную ошибку рабочего звена агента анализа (скомпилированной в виде исполняемого файла нейронной сети). Выбор конкретных механизмов был продиктован их применимостью к данной задаче либо конкретно к нейронным сетям, поскольку именно ИНС были выбраны в качестве рабочего звена.

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

В целом можно считать, что агент анализа построен и готов к работе в качестве компонента подсистемы балансировки TriadBalance.

Из приведенных в статье и опробованных практически механизмов, улучшающих качество распознавания дисбалансов, лучшим следует признать механизм сокращения ИНС.

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

1. Кирилловых С.А., Юрков К.А. Нейросетевой подход к реализации агента анализа подсистемы балансировки TriadBalance // Вестник Перм. ун-та. Пермь, 2010. № 1(1). С. 98_105.

2. Кирилловых С.А. Нейросетевой подход для выявления дисбалансов в распределенной вычислительной системе // Современные проблемы математики и ее прикладные аспекты: сб. ст. / Перм. ун-т, Пермь, 2010. С.64_69.

3. Замятина Е.Б., Стаценко Н.А., Юрков К.Б. Мультиагентная балансировка с использованием агентов, обученных на нейронных сетях // Математика программных систем: межвуз. сб. науч. тр. / Перм. ун-т. Пермь, 2008. С.21-27.

4. Замятина Е.Б., Ефимов А.Ю., Козлов А.А. Архитектура подсистемы мультиагентной балансировки в Triad.Net // Математика программных систем: межвуз. сб. науч. тр. / Перм. ун-т. Пермь, 2008. С.4-13.

5. Миков А.И., Замятина Е.Б., Козлов А.А. Оптимизация параллельных вычислений с применением мультиагентной балансировки // Параллельные вычислительные технологии (ПаВТ'2009): тр. междунар. науч. конф. / Челябинск: Изд-во ЮУрГУ, 2009. С.599-604.

6. Садыхов Р.К., Отвагин А.В. Оптимизация параллельных вычислений на базе многоагентной архитектуры // Математика программных систем: межвуз. сб. науч. тр. / Перм. ун-т. Пермь, 2008. С.42-59.

7. Круглов В.В., Борисов В.В. Искусственные нейронные сети. Теория и практика. М., 2002. 382 с.

8. Осовский С. Нейронные сети для обработки информации. М.: Финансы и статистика, 2002. 344 с.

9. Рутковская Д., Пилинский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы / пер. с польск. И.Д.Рудинского. М., 2006. 452 с.

10. Breiman, L. Bagging predictors. Machine Learning, 1996. 24(2). P.123-140.

11. Kuncheva L.I., Skurichina M. An experimental study on diversity for bagging and boosting with linear classifiers: [Электронный документ]. (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.3377) Проверено 17.03.2011.

12. Воронцов К.В. Лекции по искусственным нейронным сетям: [Электронный документ]. (http://www.machinelearning.ru/wiki/images/c/cc/Voron-ML-NeuralNets.pdf) Проверено 17.03.2011.

13. Федяев О.И., Соломка Ю.И. Применение генетических алгоритмов для обучения нейронных сетей: [Электронный документ]. (http://www.uran.donetsk.ua/~masters/2004/fvti/solomka/library/article2.htm) Проверено 17.03.2011.

14. Lazarevic A. Feature bagging for outlier detection: [Электронный документ]. (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.80.1204) Проверено 17.03.2011.

Размещено на Allbest.ru