close

Вход

Забыли?

вход по аккаунту

Толпекин Артем Сергеевич. Разработка программной системы распределенной обработки данных с динамической адаптацией к нагрузке

код для вставки
АННОТАЦИЯ
ВКР 106 с., 28 рис., 3 табл., 98 источников, 1 прил.
ИНФОРМАЦИОННАЯ
МНОГОСЛОЙНЫЙ
СИСТЕМА,
ПЕРСЕПТРОН,
НЕЙРОННАЯ
РАСПРЕДЕЛЕННАЯ
СЕТЬ,
СИСТЕМА,
РЕГУЛИРОВАНИЕ НАГРУЗКИ, АРХИТЕКТУРА СИСТЕМЫ.
Выпускная квалификационная работа посвящена разработке программных
компонентов механизма оперативного регулирования распределенных систем.
В первой главе исследуются проблемы оперативного регулирования
распределенных систем, показывается актуальность работы.
Во второй главе производится анализ и разработка методов и алгоритмов
прогнозирования для оперативного регулирования распределенной системы.
В третьей главе показана программная реализация механизма оперативного
регулирования распределенной системы, а также реализация информационной
системы прогнозирования нагрузки.
Содержание
Введение ................................................................................................................ ..5
1. Исследование проблем оперативного регулирования распределенных
систем .................................................................................................................... ..9
1.1. Основные требования к архитектуре распределенных систем…………..9
1.2. Топология распределенных систем ............................................................ 12
1.3. Функциональные уровни распределенных систем .................................... 17
1.4. Обобщенная структура распределенных систем ....................................... 19
1.5. Обзор технологий разработки распределенных систем ........................... 24
1.6. Проблемы регулирования вычислительной нагрузки в
распределенных системах .................................................................................... 24
1.7. Постановка задачи исследования ................................................................ 29
2. Анализ и разработка методов и алгоритмов нейропрогнозирования для
оперативного регулирования распределенной централизованно-кольцевой
системы .................................................................................................................. 33
2.1. Анализ повышения эффективности распределенных
централизованно-кольцевых систем обработки информации ......................... 33
2.2. Разработка архитектуры распределенных систем с оперативным
регулированием вычислительной мощности .................................................... 35
2.3. Обоснование выбора типа нейронной сети для реализации
механизма оперативного прогнозирования ....................................................... 39
2.4. Разработка общего подхода к прогнозированию на основе аппарата
нейронных сетей................................................................................................... 46
2.5. Метод прогнозирования нагрузки на основе многослойного
перцептрона .......................................................................................................... 50
3. Программная реализация механизма оперативного регулирования
распределенной централизованно-кольцевой системы ..................................... 58
3.1. Архитектура и состав библиотеки компонентов....................................... 58
3.2. Программная реализация механизма обучения многослойного
перцептрона ..................................................................................................... …. 60
3.3 Реализация программы прогнозирования количества пользователей ....... 65
Заключение ............................................................................................................ 71
Список использованных источников .................................................................. 72
Приложение 1…………………………………………………………………….80
5
ВВЕДЕНИЕ
Пользовательские компьютеры (далее ПК) с каждым годом становятся все
популярнее. Их число неизменно растет. Наметилась тенденция объединения ПК в
сети с выходом в Интернет не только в организациях и на предприятиях, но и в
домах частных пользователей. Такое положение дел создает основания для
активного развития коммуникационных и информационных технологий в
интернет-среде. Все чаще внедряются глобальные системы, обладающие
способностью
обслуживать
пользовательские
запросы
различного
уровня
сложности. Яркий пример подобных глобальных систем представляют собой
интернет-магазины, интернет порталы и системы управления предприятиями. В
большинстве случаев созданные и эксплуатируемые в настоящее время системы
являются распределенными. При этом применяется компьютер или программаклиент
(тонкий
клиент)
с
терминальной
или
серверной
архитектурой,
использующий сервер приложений и функции презентационного слоя, который
построен по кольцевой схеме. Основная нагрузка, образующаяся за счет обработки
данных, ложится на серверную часть системы.
Многие системы обрабатывают с точки зрения нагрузки внушительный
объем заявок. Часто случается так, что обработка поступившей в конкретную
систему заявки осуществляется посредством формирования потока заявок,
обращенных к другим, стоящим выше на иерархических ступенях системам. Время
обработки одной подобной заявки может выполняться в течение нескольких минут,
что является достаточно критичным в условиях большой загрузки. Помимо этого,
для обработки подобных заявок необходимо задействовать значительные ресурсы
вычислительной
системы.
Зачастую
сервер
немотивированно
отказывает
обработать заявку, что свидетельствует о наличии перегрузки.
Факторы критичности, важности, работоспособности и доступности
вычислительных ресурсов приводят к размещению серверной части системы на
базе более мощного оборудования, что увеличивает стоимость системы. Во многих
случаях на одних и тех же мощностях располагаются несколько серверов. В таких
ситуациях наиболее оптимально настроить каждый сервер на работу и при этом
6
затратить минимальное количество ресурсов очень сложно. Серьезной проблемой
при настройке сервера на оптимальное функционирование является определение
вычислительной мощности.
Большая часть крупных и средних современных распределенных систем
создается по централизованно-кольцевой схеме, в которой сервер – это кольцо
однотипных вычислительных узлов. Для оптимизации управления серверным
кольцом редко применяются какие-либо программные средства. Чаще всего число
серверных узлов жестко регламентируется при установке настроек и не меняется в
зависимости от нагрузки. Гораздо реже используется вариант, при котором
функционирующая система вычисляет среднюю величину нагрузки на основе
статистических данных, и использует полученный результат как эталон для
выявления нужного количества вычислительных узлов. При этом основную часть
времени ресурсы, занятые системой, простаивают, потому что ситуация
равномерности и постоянности потока пользовательских заявок складывается
очень редко.
О необходимости совершенствования существующих и развитии новых
механизмов оперативного и автономного управления подсистемами крупных
распределенных сетей свидетельствует перспективность автономных вычислений,
концепция компании IBM, которая выдвинута в качестве ключевой инициативы
самоуправляющихся вычислительных систем.
Таким
образом,
разработка
централизованно-кольцевой
алгоритма
системы
оперативного
масштабирования
программной
реализации,
для
крупных
может
стать
оперативного
регулирования
эффективного
решения
распределенных
систем
общим
решением
для
задач
и
его
любой
распределенной системы.
Теоретическая
основа распределенных и
параллельных
вычислений
рассматривается в трудах Воеводина В.В. [12], Барского А.Б. [4], Воеводина Вл.В.
[12,13], Топоркова В.В. [85], Ван Стеена М. [83], Крюкова В.А. [53,54], Таненбаума
Э. [82,83] и других исследователей. Работа Гоффа М.К. [31] содержит анализ
основных аспектов разработки распределенного ПО, демонстрацию основных
7
перспективных направлений и проблем. Исследования Буча Г. [10], Эммериха В.
[94], Брауде Э. [9], Дейтела Х.М. [34], Грегори Р. Эндрюса [95], Фаулера М. [87,88]
освещают практические вопросы проектирования и разработки распределенных
систем.
В результате аналитики исследований, которые посвящены решению задач
оперативного регулирования централизованно-кольцевых систем, можно сделать
вывод об отсутствии в современных технологиях разработки распределенного ПО
аппарата для реализации задач оперативного регулирования. Это обусловлено
отсутствием практики в решении данных проблем и недостаточностью
проработанностью теории для синтеза универсального прогностического метода.
Исследования, направленные на создание алгоритмов оперативного регулирования
распределенных систем обработки информации, являются чрезвычайно важными.
Они имеют большое значение для эффективного решения задач оперативного
масштабирования крупных распределенных систем на основе математического
аппарата нейронных сетей.
Целью работы является разработка алгоритмов и программных компонентов
механизма
оперативного
регулирования
распределенных
централизованно-
кольцевых систем, которые позволят обеспечить повышение производительности
серверного программного обеспечения и уменьшение числа вычислительных
ресурсов,
использующихся
в
системах
для
эффективности
увеличения
распределенных
централизованно-кольцевых
решения
задач
оперативного
масштабирования крупных распределенных систем.
Поставленной цели можно будет достичь посредством интеграции
подсистемы оперативного регулирования распределенной системы на базе
нейропрогнозирования нагрузки в схему распределенной централизованнокольцевой системы.
Задачи работы заключаются в:
– изучении способов построения распределенных систем на базе послойного
деления функциональности;
8
– определении особенных черт организации взаимодействия узлов в
распределенных системах и создание на их основе новых алгоритмов
нейропрогнозирования
– разработке архитектуры и программной реализации нейропрогностических
средств для оперативного регулирования.
В ходе выполнения исследований применялся математический аппарат
теории графов, теории нейронных сетей и массового обслуживания, методики
имитационного моделирования сложных сетей.
Использование
вышеобозначенных
технических
инструментов
даст
возможность сократить число задействованных ресурсов, увеличить уровень
производительности
в
централизованно-кольцевой
системе
обработки
информации в период пиковой нагрузки посредством наиболее оптимального
распределения вычислительных ресурсов.
Созданный комплекс взаимодействующих программ для оперативного
регулирования дает возможность разрабатывать распределенные серверные ОС
для корпоративных ИС, систем управления предприятием и производством,
которые будут самонастраиваться и адаптироваться к вычислительной нагрузке.
Полученные программные компоненты – это законченная программная
реализация, представленная в виде библиотеки классов, применяемой в
большинстве разрабатываемых или уже внедренных крупных централизованнокольцевых системах с минимумом доработок по взаимодействию.
Результаты разработки достоверны по причине научной обоснованности и
подтвержденности
положений работы.
экспериментами
основных
теоретических
выводов
и
9
1 ИССЛЕДОВАНИЕ ПРОБЛЕМ ОПЕРАТИВНОГО РЕГУЛИРОВАНИЯ
РАСПРЕДЕЛЕННЫХ СИСТЕМ
Об увеличении скорости вычислений специалисты задумывались на
протяжении
всего
периода
развития
электронно-вычислительных
машин.
Потребность в создании высокопроизводительных вычислительных комплексов
обусловлена стремительным ростом популярности глобальной интернет-сети,
увеличением масштабов существующих систем, появлением новых, все более
сложных задач. Учитывая ежегодный рост производительности процессоров
(согласно закону Мура [38] число транзисторов, которые располагаются на
кристалле интегральной схемы, увеличивается в два раза каждые 24 месяца)
главной становится проблема оптимально организованных вычислений. Данная
проблема вызвана постоянно увеличивающимся масштабом ИС, ростом объемов
информации, которую необходимо обработать.
Усовершенствование технологий распределенных вычислений является
наиболее
перспективным
Распределенная
система
направлением
представляет
развития
собой
исследуемой
набор
области.
индивидуально-
вычислительных компонентов, способных осуществлять обмен информацией [31].
Распределенные системы – это логическое развитие локальных вычислений
и параллельных алгоритмов многопроцессорных систем. Подробное рассмотрение
теоретических вопросов распараллеливания алгоритмов между процессорами
выполняется в [4,13,51,12].
1.1 Основные требования к архитектуре распределенных систем
Новые разработки в сфере распределенных вычислений находится в тесной
взаимосвязи с топовыми тенденциями в технологической области. Здесь имеются
в виду мобильные и беспроводные вычисления, робототехника, web-службы,
нанотехнологии, биотехнология и расшифровка геномов. Помимо этого, есть
стандарт «де-факто» архитектуры, который сформировался за годы исследований
10
в области распределенных систем. В соответствии с ним для архитектуры
распределенной системы необходимо реализовать требования [87]:
– масштабируемости;
– открытости;
– неоднородности;
– ресурсного разделения;
– отказоустойчивости;
– прозрачности.
Реализация всех нефункциональных требований должна быть выполнена в
системе еще до начала этапа бизнес-логики. Кроме того, нефункциональные
требования должны работать независимо от алгоритмов, которые будут
программироваться позже. Общая сумма реализованных нефункциональных
требований образует систему управления распределенной системой. Необходимо
рассмотреть суть каждого требования в отдельности.
Масштабируемой
является
такая
архитектура,
которая
обладает
способностью адаптации к любому типу увеличения нагрузки. Это обеспечивается
посредством выделения системе нужных вычислительных ресурсов. Архитектура
должна давать возможность осуществлять ввод и вывод вычислительных ресурсов
без больших задержек и остановки функционирования системы. Крупные
распределенные системы обладают классами однотипных вычислительных
элементов, число которых определяет уровень способности системы осуществлять
функции, реализуемые данными элементами. Как правило, данные элементы – это
наиболее загруженные части системы. Общая вычислительная способность
определяется по сумме вычислительной мощности каждого компонента. Если
присутствует условие однотипности вычислительных компонентов, совокупная
вычислительная мощность равна их количеству.
Одна из необходимых характеристик ПО в целом и архитектуры системы в
частности – открытость. Она дает возможность быстро выполнять расширение и
модифицирование [3]. Для выполнения данного условия компонентам системы
необходимо иметь подробно описанные и заранее определенные интерфейсы.
11
Система должна разрешать интеграцию новых компонентов, которые отвечают
вновь сформировавшимся функциональным требованиям. Открытость – это полная
формализация большого числа операций, которые реализуются компонентом.
Формализацию допустимо представить как текстовую информацию, например,
документации или справочников [94], или в бинарном виде [33].
Неоднородность компонентов обусловлена применением разных технологий
для реализации услуг, управления данными и выполнения команд на аппаратной
платформе [3]. Причин возникновения неоднородности несколько. Зачастую
происходит так, что компоненты приобретаются в готовом виде. Для вновь
появляющихся компонентов необходимо взаимодействие с уже существующими
составляющими.
Кроме
того,
компоненты
могут
писаться
разными
разработчиками, что также вызовет неоднородность в большинстве случаев.
Причины неоднородности кроются в независимости разработчиков, различные
временные рамки создания компонентов, совместимости конкретного компонента
и конкретной технологии.
Ресурсами
считается
программное
обеспечение,
оборудование
и
информационные данные. Для более эффективного применения дорогостоящих
ресурсов зачастую требуется ресурсное разделение. Право на доступ к ресурсам,
как правило, имеет менеджер ресурсов [72].
Программы, оборудование и сеть не всегда функционируют бесперебойно.
Сбои в работе возникают из-за неисправности вспомогательного оборудования,
программных ошибок, неправильных пользовательских действий, старения
аппаратуры. Например, жесткий диск может служить от 2 до 5 лет, что значительно
короче, чем средний срок службы всей системы [82].
Отказоустойчивость – это способность системы функционировать при
появлении
неисправностей.
Выбор
архитектуры
часто
обусловлен
отказоустойчивостью. Отказоустойчивости систем удается достигать посредством
избыточности.
С
применением
репликации
производится
удвоение
функционирующих компонентов с актуальными данными. Если отказывает
основной элемент, начинает функционировать его копия, поэтому остановки
12
обработки запросов клиентов не происходит. В работе [83] приводится ряд
подходов к отказоустойчивости программного обеспечения, часть из которых
можно использовать в отношении распределенных систем. Одной из самой
распространенной
методикой
увеличения
степени
отказоустойчивости
неверсионного ПО является checkpoint-restart – механизм перезапуска контрольной
точки. В отношении гетерогенных и многоверсионных систем наиболее
целесообразно использовать recovery-blocks – метод восстанавливающих блоков.
Архитектура крупной распределенной системы, которая бы удовлетворяла
всем или большей части перечисленных выше требований, характеризуется
сложностью. Пользователь должен воспринимать подобную систему в виде
единого интегрированного вычислительного средства. То, что система является
многокомпонентной, должно быть скрыто от пользователя, то есть, система должна
быть прозрачной. Стандарт 180/1ЕС 107463:1996 “Информационные технологии.
Открытая распределенная обработка. Эталонная модель. Архитектура” описывает
основные концепции прозрачности программного обеспечения [45].
1.2 Топология распределенных систем
Эффективность системы вычисления находится в прямой зависимости от
эффективности функционирования отдельных узлов. По закону Меткалфа
потенциальная ценность сети исчисляется количеством узлов в квадрате. Это
доказывается эффективность распределенных сетей, но максимум эффективности
может быть получен только в случае объединения всех подсистем в глобальную
распределенную вычислительную сеть. Постоянное увеличение числа узлов
увеличивает важность топологии – принципов и правил формирования
межузловых связей.
На сегодняшний момент крупнейшей распределенной системой является
Интернет.
Данная
сеть
с
точки
зрения
топологии
децентрализованной структурой.
Основные принципы формирования распределенных сетей:
– централизованность;
характеризуется
13
– децентрализованность;
– иерархичность;
– кольцо.
Данные топологии применяются в чистом и смешанном виде.
Самыми распространенными являются системы с единым центром.
Большинство простых клиент-серверных приложений – это централизованные
системы, например, СУБД и веб-серверы. Топология системы с единым центром
показана на рис. 1.1. В такой системе вся информация и функции имеют
сосредоточение на одном сервере, который осуществляет обслуживание множества
пользователей.
Рисунок 1.1 – Топология централизованной системы
Основное преимущество показанной типологии заключается в простоте ее
исполнения. Код и данные находятся в одном месте, поэтому больших проблем в
ходе поддержания работоспособного состояния комплекса, не возникает.
Распределенные системы, существующие в реальности, часто не относятся к
вышеописанным технологиям. В любой современной системе скомпановано
несколько способов узлового соединения. Подобные способы носят наименование
14
гибридных.
Наиболее
популярными
гибридными
технологиями
являются
централизованно-децентрализованная и централизованно-кольцевая.
Стоит отметить, что большая часть современных крупных централизованных
систем только на первый взгляд являются такими, а на самом деле представляют
собой централизованно-кольцевыми. Их серверная часть – это кольцо серверов.
Данные способ используется для того, чтобы предотвратить перегрузки системы и
равномерно распределить нагрузку. На рис. 1.2. представлена серверная
подсистема
централизованно-кольцевой
системы,
построенная
на
основе
классической кольцевой топологии. Тем не менее, в целом система представляет
собой гибридную, потому что соединение серверной подсистемы с клиентами
централизованно. При этом не возникает конфликта с принципом прозрачности,
потому
что
для
клиентов
нет
разницы
между
централизованной
и
централизованно-кольцевой системой. Можно сделать вывод о простоте
централизованно-кольцевой схемы с точки зрения клиентской части, но при этом
она обладает характеристиками, которые присущи системам кольцевой топологии.
Рисунок 1.2 – Топология централизованно-кольцевой системы
15
Популярность подобной топологии при создании крупных информационновычислительных комплексов объясняется сочетанием лучших свойств кольцевых
и централизованных систем.
Перекрытие нескольких централизованных систем – это ядро многозвенных
систем, которые получили распространение в последние годы. В качестве примера
можно привести организацию большинства web-серверов. В этом случае задача
web-сервера заключается в формировании разметки и содержания страниц на
основе информации, которая получена с других системных серверов, хранящих
логику и или данные. Таким образом, основное направление применения
представленной технологии состоит в декомпозиции крупных систем по
функциональной составляющей. На рис. 1.3. показан самый ранний метод
формирования распределенной системы. Это комбинированная централизованнодецентрализованная топология. Узлы такой системы делятся на группы. В каждой
группе присутствует свой сервер. Получается, что для ряда компонентов система
централизованна, а для другого ряда – сеть является децентрализованной.
Рисунок 1.3 – Топология централизованно-децентрализованной системы
16
Централизованно-децентрализованная
топология
соединяет
в
себе
достоинства систем с объединенным центром и без него. В качестве примера
можно привести систему электронной почты или пиринговые сети [32].
Комбинировать разные способы узлового соединения можно посредством
многих вариантов. В централизованной системе может иметься иерархия из
нескольких
узлов
в
центре,
которые
играют
роль
единого
сервера.
Децентрализованная архитектура может выглядеть как несколько колец или
иерархий. Зачастую крупные системы формируются с помощью использования
разных типовых топологий.
централизованная
децентрализованная
иерархическая
-
прозрачность
отказоустойчивость
управление ресурсами
неоднородность
открытость
масштабируемость
Таблица 1.1 - Характеристики топологий распределенных систем
?
-
+
-
+
+
+
+
+
-
+
+
+
кольцевая
+
-
-
-
+
+
централизованно-кольцевая
централизованно-
+
-
-
+
+
+
?
+
+
-
+
-
децентрализованная
Таблица 1.1 показывает свойства описанных топологий с точки зрения
реализации главных нефункциональных требований к их архитектурам. Знак «+»
поставлен напротив характеристик, которые реализовываются без затруднений и
помех, знак «–» стоит при изначального незапланированного или слабо
реализуемого свойства, знаком «?» отмечены характеристики, выполнение
17
которых полностью зависит от нюансов реализации механизма конкретной
системы данной типологии.
Аналитика
существующих
топологий
показывает
перспективность
использования распределенных систем гибридного типа. Комбинирование
различных простых топологий дает возможность сочетать достоинства каждой из
них и минимизировать недостатки примененных топологий. Строить крупные
информационные и управляющие системы, которые ориентированы на работу с
большим объемом пользовательских запросов, наиболее целесообразно с
применением гибридной централизованно-кольцевой топологии. Основное ее
преимущество заключается в идеальной приспособленности к масштабированию
системы за счет использования узлов-обработчиков однотипного плана. С ростом
нагрузки по причине введения в кластер дополнительных вычислительных узлов и
перераспределения
данной
нагрузки
между
узлами
можно
обеспечить
равномерную загруженность каждого узла, что позволит избежать коллапса всей
системы.
1.3 Функциональные уровни распределенных систем
Современная
отрасль
разработки
программного
обеспечения
характеризуется тремя функциональными составляющими:
– уровнем данных;
– уровнем логики системы;
– уровнем представления (см. рис. 1.4).
Каждая информационная система предназначается для ввода, вывода,
хранения и анализа данных. За предоставление, хранения и поддержание
актуальности данных отвечает слой данных. На современном этапе самым
эффективным способом реализации слоя данных являются СУБД – реляционные
системы управления базами данных.
18
Рисунок 1.4 – Функциональные уровни распределенных систем
За объединение частей системы, реализующих логику функционирования, а
также за полноту работоспособности системы отвечает слой логики. Он является
посредником между слоем данных и слоем представления. Слой логики
осуществляет управление всеми изменениями, которым подвергаются данные в
зависимости от логики решения задач.
Моделирование рабочих мест операторов системы или субъектов, которые
имеют доступ к системе, выполняет слой представления. По сути, им является
интерфейсная часть, осуществляющая взаимодействие с пользователями. Задача
слоя заключается в получении и отображении данных, редактировании и проверки
корректности их ввода.
Естественно, что не существует абсолютного разделения системных узлов по
выполнению функций одного или другого слоя. Это вызвано тем, что такой подход
сложен в реализации, а также тем, что не всегда подобное разделение считается
оптимальным в аспекте быстродействия. Как правила, ограничения касаются двух
19
слоев: данных и представления, потому что их код не может быть очищен от слоя
логики. Слой логики, в свою очередь, может выделиться в отдельные блоки и
реализоваться в виде независимых узлов.
Из всего вышесказанного можно сделать вывод о том, что основная нагрузка
в распределенных системах приходится на компоненты слоя логики. Надежность и
качество функционирования распределенной системы полностью зависит от
реализации слоя логики. Именно в отношении его компонентов необходимо
оперативное регулирование, в первую очередь для предотвращения избыточной
нагрузки.
1.4 Обобщенная структура распределенных систем
В виде формального исчисления распределенная система представляется так:
 = < {}, {}, {}, {}, {}, {} > ,
(1.1)
где {} – множество узлов распределенной системы;
{} – множество узлов, которые реализуют функциональность слоя
представления,  ∈ ;
{} – множество узлов, которые реализуют логику работы системы,  ∈ ;
{} – множество узлов хранения данных,  ∈ ;
{} – множество аппаратных вычислителей, используемых системой;
{} – аппаратные ресурсы системы.
Вычислителями в структуре такой распределенной системы являются
электронно-вычислительные машины, объединенные единой сетью.
выражены
программной
абстракцией,
которая
реализует
Узлы
работу
запрограммированной логики, делая это независимо от других узлов. В
многозадачных операционных системах реализация узлов представлена в виде
многопоточных процессов. Основную роль, согласно идеологии распределенных
вычислений, играет межузловое взаимодействие.
На сегодняшний день существует достаточно много средств, которые
призваны обеспечивать взаимодействие между процессами. Первая группа данных
20
средств необходима для
поддержки
взаимодействия между процессами,
протекающими в рамках одной ЭВМ.
Shared memory или разделяемая память представляет собой непрямой способ
взаимодействия посредством технологии отображения файлов на оперативную
память File Mapping. Данный механизм выполняет доступ к памяти по принципу
работы с фалом. Такой подход дает возможность сразу нескольким процессорам
производить действия с файлом. В процессе работы с памятью потокам
необходимо
согласовывать
собственные
действия
посредством
объектов
синхронизации.
DLL – библиотеки динамической подготовки характеризуются тем, что
объявленную в рамках переменную можно сделать разделяемой (shared). Все
действия, которые обращаются к библиотеке, для shared будут использовать одно
и то же место в физической памяти.
Dynamic Data Exchange, DDE – протокол динамического обмена данными
широко применялся до тех пор, пока не стали с этой целью применять OLE
(впоследствии ActiveX). Сейчас DDE используется, как правило, только для
обратной совместимости. Данный проток оптимален для решения задач, которые
не требуют продолжительного взаимодействия с пользователем. В некоторых
случаях пользователю нужно установить межпрограммное соединение, а обмен
данными будет протекать без его участия.
Вторая группа средств взаимодействия между процессами представляет
собой технологии, которые равнозначно функционируют и в рамках одной
электронно-вычислительной машины, и сети. Строятся средства на семиуровневой
сетевой модели OSI, являясь надстройкой транспортного уровня.
Pipes или каналы представляют собой стандартную технологию обмена
данными. Pipes поддерживаются в системах Windows и Unix. Наиболее часто они
применяются для передачи непрерывного потока данных. Различают anonymous
pipes – анонимные каналы и named pipes – именованные. Первые используются
нечасто для передачи потока вывода одного процесса на поток ввода другого.
Именные каналы применяют для передачи произвольных данных.
21
Sockets или сокеты – это технология обмена данными в Интернет. Sockets
часто можно встретить в крупных локальных вычислительных сетях. Они
представляют собой абстракцию конечных точек коммуникационной линии,
которая соединяет два приложения.
Вышеописанные механизмы необходимы для обеспечения связи между
узлами распределенной системы на системном уровне. Алгоритмический уровень
включает три модели, являющиеся основными. Данные модели различны по
степени обобщенности и синхронизации.
Модель синхронной передачи сообщений. Сюда относятся Remote Procedure
Call – RPC-подобные методы удаленного вызова процедур.
Модель асинхронной передачи сообщений. Ее представляет Java Messaging
Service (JMS) – платформа, реализующая веб-службы на Java. Здесь же можно
привести в пример IBM MQSeries и Microsoft Message Queue (MSMQ) –
коммерческие системы очередей.
Модель с асинхронным совместным использованием памяти. В основном
данная модель используется в распределенных вычислениях с сильными связями,
например, кластерные концепции и grid-вычисления.
Необходимо
подробнее
рассмотреть
самые
востребованные
схемы
организации ИС.
Наиболее простая и старая по времени – это архитектура настольного
приложения. Она имеет такую структуру, в которой все узлы даже при их
разделении расположены на одной машине. Данная архитектура получила название
локального сервера. Взаимодействие между узлами выполняется посредством
программных вызовов методов. Помимо этого, есть возможность взаимодействия
средствами разделяемых областей памяти pipes, shared memory или sockets.
Реализовываться система данного типа может только на многозадачных
операционных системах.
Самая распространенная на современном этапе архитектура – традиционная
клиент-серверная схема, показанная на рис. 1.5.
22
Рисунок 1.5 – Клиент-серверная система
В подобных системах слои логики и представления тесно связаны. Логически
и физически отделен от всех остальных уровень хранения данных.
Отличительная особенность подхода заключается в передаче большого
объема «сырой» информации. В результате у пользователя оказывается
внушительное количество необработанных данных, требующих окончательной
обработки.
Самая перспективная на сегодняшний день система – это трехзвенная
архитектура, показанная на рис. 1.6.
Рисунок 1.6 – Трехзвенная архитектура
23
Учитывая то, что на слое логики лежит основная вычислительная нагрузка,
крупные комплексы создаются посредством поддержки масштабирования за счет
увеличения числа однотипных вычислительных узлов. Данный подход используют
в централизованно-кольцевых распределенных системах, где в качестве узлов
кольца функционируют однотипные вычислительные узлы, реализующие логику.
Это демонстрируется на рис. 1.7.
Рисунок 1.7 – Централизованно-кольцевая трехзвенная система
Описанный подход дает возможность осуществлять масштабирование
системы под нагрузку с изменением числа обработчиков согласно ее значениям.
Здесь может использоваться метод работы каждого узла логики на отдельном
вычислительном устройства. Это позволяет выполнить распараллеливание
реализацию заявок.
Учитывая все вышесказанное можно сделать вывод о самом эффективном
архитектурном решении – им является архитектура трехзвенной централизованнокольцевой системы. При этом переход уже работающих трехзвенных систем может
быть выполнен с минимальным числом доработок.
24
1.5 Обзор технологий разработки распределенных систем
Платформа .NET Framework – одна из самых современных технологий
разработки распределенных систем. Ее можно описать как виртуальную машину,
которая исполняет команды языка CIL (common intermediate language).
Посредством CIL-совместимых компиляторов выполняется компиляция кода, если
он написан на стандартных языках программирования C++, С#, Delphi и Basic.
.NET Framework представляет собой абсолютно объективно-ориентированную
среду. Любая абстракция представляется в виде объекта. Подсистема .NET
Framework применяется для разработки распределенных систем. .NET Remoting по
сравнению с DCOM характеризуется более широкими настройками форматов
межсетевого взаимодействия объектов, включая открытые форматы WSDL, XML.
Это дает возможность создавать гетерогенные системы. .NET Framework по
сравнению с CORBA и DCOM не требует описывать базовые типы объектов,
находящихся во взаимодействии. Кроме этого, в .NET Framework значительно
упрощено управление распределенными объектами (на основе спонсоров и
лицензий), если вести сравнение с подсчетом ссылок в DCOM.
RMI (remote method invocation) – технология используется для создания
распределенных систем на Java. .NET Framework и Java во многом схожи. но имеют
различия в кроссплатформенности Java и определенных выполнениях некоторых
алгоритмов.
Ни одна из рассматриваемых технологий не предусматривает встроенный
механизм оперативного регулирования вычислительной мощности.
1.6 Проблемы регулирования вычислительной нагрузки в распределенных
системах
Использование централизованно-кольцевой архитектуры затрудняется по
ряду причин. Данные проблемы делятся по характеру появления. Одни проблемы
свойственны только для кольцевых систем, другие характерны только для
централизованных систем. Разработчикам приходится решать задачу по выбору
25
наиболее оптимального числа узлов и вычислителей слоя логики, балансировке
нагрузки и распределению узлов по вычислителям.
Некоторые из обозначенных проблем могут быть решены посредством
внедрения специальных систем, которые поддерживают параллельные программы
[53,54], или с помощью коммуникационных библиотек PVM, MPI, Router.
Промышленная эксплуатация подобных систем неэффективна по причине узкой
ориентированности на решение вычислительных задач, поэтому их использование
может оправдано только, если необходимо решить сложные вычислительные
задачи. Далее следует рассмотреть варианты, которые применяются в настоящее
время для решения вышеобозначенных задач при разработке промышленного
программного обеспечения.
В крупных и особо крупных распределенных системах проблема
распределения узлов по вычислителям стоит очень остро. Это обусловлено тем, что
число вовлеченных в них узлов исчисляется сотнями и тысячами. Оптимальное
распределение узлов позволит минимизировать сетевой трафик, обеспечить
эффективную загрузку и ускорить обработку запросов. В работах [83,85]
рассказывается о наиболее известных решениях данной проблемы. Выделяются
алгоритмы децентрализованные и с единым центром управления. Последние
представляют собой алгоритмы на основе Graph-Theoretic Determenistic Algorithm
– «графовое представление» и алгоритм на основе применения таблицы «Вверхвниз».
Проблемы
децентрализованных
систем
решаются
посредством
“распределенного эвристического алгоритма по получателю или по отправителю”
или “иерархического алгоритма”.
Балансировка нагрузки между однотипными узлами необходима для
предотвращения перегрузки одних узлов при простое других. Еще эта проблема
обозначается как Token Distribution Problem [28] и заключается в распределении
заданий по вычислителям. Балансировка нагрузки может быть как статической
[40,43,46] так и динамической [46,38,54]. Наиболее интересна динамическая
балансировка нагрузки. Характерная особенность способа заключается в контроле
и распределении нагрузки непосредственно в ходе функционирования системы.
26
Балансировочные механизмы делят на распределенные и централизованные. В
централизованных алгоритмах распределения нагрузки и вся информация о ней
сосредоточена на одном управляющем узле. Распределенная балансировка
выполняется узлами, обменивающимися между собой данными о нагрузке.
Балансировка бывает явной и неявной. Явная предоставляет пользователю
возможность самостоятельно принять решение, какое действие и где должно
выполняться. Неявную балансировку система осуществляет самостоятельно.
Примеры явной балансировке представлены в [55,47], неявной – в работах
[45,24,29].
Теперь
необходимо
рассмотреть
наиболее
популярные
стратегии
балансировки нагрузки. Балансировка Diffusion Based Load Ballancing – основана
на распространении [50,10]. В соответствии с алгоритмом каждый узел
согласовывает собственную нагрузку с узлами-соседями. Процесс осуществляется
последовательно в отношении каждого узла. В рамках крупных систем применение
метода занимает некоторое время. В [57] представлено усовершенствование
данного алгоритма для лучше сходимости при помощи применения информации
предыдущей интеграции. Развитие распределенных систем привело к активизации
разработки алгоритмов управления нагрузкой в системах без единого центра и
пиринговых сетях [21,36]. Главным образом, это алгоритмы управления distrubuted
hash table – распределенной хэш-таблицей, которые являются основами идеологии
пиринговых файлообменных сетей.
Самые простые алгоритмы балансировки нагрузки – централизованные.
Здесь можно указать Gradient Model [22] – Градиентную модель, Central Job
Dispatcher [25] – модель центрального диспетчера. Механизмы обеспечены единым
управляющим узлом, поэтому могут получить полную информацию о нагрузке на
отдельные части системы.
Реализация
переключения
потока
заданий
между
узлами
может
осуществляться средствами системы и или на уровне сетевых протоколов. В [44]
дает подробное описание методов динамического перераспределения нагрузки по
27
нескольким однотипным серверам на уровне сетевого транспортного слоя путем
подмены ip-адресов серверов.
Кроме того, есть методы управления распределенной системой на базе
нейронных сетей. В виде нейронной сети представляется граф распределенной
системы. В нейронной сети нейроны играют роль вычислительных узлов, синапсы
являются имитаторами каналов связи. В труде [96] в пример приводится подход на
основе нейронной сети под названием WTA – “Победитель получает все”. Показана
реализация механизмов двух правил: определение задачи и исполнителя.
Выбор оптимального количества вычислителей и узлов слоя логики
распределенной системы тесно связан с задачей балансировки нагрузки. По сути,
задача сводится к выбору необходимого количества вычисляющих узлов, т.к.
количество вычислителей регулируется алгоритмами распределения узлов по
вычислителям.
Характер взаимодействия между частями клиент-серверной системы
позволяет использовать для описания их работы аппарат систем массового
обслуживания (СМО) [76]. В работе [78] рассматриваются способы выравнивания
нагрузки на узлы с помощью разделения крупных вычислительных задач на
подзадачи небольшого размера. При этом выравнивание нагрузки происходит за
счет количества участков, просматриваемых каждым узлом. В [79,59] подробно
рассмотрена задача наилучшего выбора разбиения задачи на подзадачи, в
зависимости от различных критериев. Также, в работе [69], предложены критерии
осуществимости
решения
сложных
вычислительных
задач
с
помощью
распределенных систем.
В контексте рассмотрения централизованно-кольцевых распределенных
систем, линией считают вычислительный узел слоя логики. Вызов – это заявка на
обслуживание от узлов слоя представления, отправка ответа на полученный вызов
– завершение операции обслуживания.
В общем смысле централизованно-кольцевую систему представляют как
систему с ожиданием. Отличительная особенность такой системы заключается в
том, что вызов, которому не нашлась линия, не исчезает, а становится очередным
28
на обслуживание и ждут освобождения линии. Если вести сравнение с системами
с потерями, увеличивается только время обслуживания при сохранении вызова.
Время ожидания обработки заявки () – важная характеристика систем
массового обслуживания с очередью. В [76] показана формула:
=
1 
,
−
(1.2)
где  – является средним временем обслуживания заявки,
 – вероятностью полной занятости линий,
 – количеством очередных заявок,

 = , где  – обозначает число требований, которое поступает в систему за

временную единицу.
Основная цель заключается в минимизации времени обработки заявки при
необходимом минимуме обработчиков. Очевидно, что основной целью является
минимизация времени ожиданий обработки заявки () при минимально
необходимом количестве обработчиков. 1.1 показывает, что можно обеспечить
снижение времени обработки заявки за счет уменьшения времени на ее обработку.
Эта задача решается программистом в процессе реализации системных
компонентов. Рекомендации по практике использования данной методики даны в
[94].
Еще одним вариантом уменьшения затрат времени является снижение
вероятности полной занятости линий. Данную задачу можно решить, определив
оптимальное
число
линий
(обработчиков).
Оптимальные
количественные
характеристики для каждого узла обработки определяются в ходе проектирования
системы. Определить среднюю нагрузку в течение всего времени работы узла
позволяет имитационное моделирование вместе с использованием подходящих
методов теории массового обслуживания [75]. Оптимальное число линий
обрабатывающего узла подбирается в зависимости от средней нагрузки.
У
всех
рассмотренных
выше
методов
функциональный
характер.
Наибольший интерес вызывает технология, позволяющая встроить возможность
масштабирования в архитектуру системы. Все более актуальным становится поиск
29
работоспособного и приемлемого по стоимости решения. Это обусловлено
активным внедрением компьютерных разработок на основе трехзвенной
архитектуры. Ее решение возможно посредством разработки механизма, который
дал бы возможность не заботиться о масштабировании системы. Данное решение
должно давать возможность масштабирование в автоматическом режиме на уровне
узлов автономно.
Необходимость
развития
механизмов
автономного
регулирования
вычислениями обусловлена появлением концепции автономных вычислений.
Впервые об автономных вычислениях заговорила компания IВМ. Разработчики
выдвинули свою концепцию самоуправляющихся вычислительных систем,
которые требуют минимума вмешательства со стороны человека. Таким образом,
можно
сделать
об
актуальности
разработки
механизма
оперативного
регулирования распределенной централизованно-кольцевой системы.
1.7 Постановка задачи исследования
Увеличение производительности узлов, которые отвечают за реализацию
логики – один из методов масштабирования крупной распределенной системы. Он
представляется наиболее перспективным. Увеличения производительности можно
добиться посредством увеличения числа узлов слоя логики. Данный метод
ограничивается только возможностями серверного ПО по подключению и
использованию дополнительных узлов-обработчиков. Весьма нетривиальной
задачей представляется определение нужного числа узлов-разработчиков. Для того
чтобы ее решить необходимо получить функцию аналитического вида, которая
обеспечит вычисление оптимального для нормального функционирования системы
числа узлов. Возможность рассчитать количество узлов даст возможность
разработать механизм оперативного регулирования количества вычислительных
узлов для того чтобы минимизировать время простаивания запроса.
Применение
рассмотренного
метода
даст
возможность
увеличить
эффективность функционирования системы, если брать во внимание высокую
30
стоимость вычислительных ресурсов и нестационарность нагрузки в крупных
системах.
Эффективность
системы
определяют
числом
незадействованных
обработчиков и временем, которое тратится на обработку запроса. Наибольший
интерес в этом плане представляют такие характеристики:
Среднее время, которое проходит от поступления запросов в очередь

входящих до помещения ответов в исходящую (
). Его высчитывают по
формуле:



∑
=1 
=
,

(1.3)
где  – время выполнения запроса, которое определяется выражением:
 = _ − _ ,
(1.4)
где _ – время поступления заявки;
_ – время помещения результата в очередь отправки;
 – количество заявок.
Еще одна формула подсчета времени выполнения запроса:

 = 

где 



+ 
,
(1.5)
– время нахождения запроса в очереди;
– время обработки запроса.
Формула определения среднего времени простоя обработчика:
ℎ

ℎ
∑
=1 
=
,

(1.6)
где  – количество обработчиков;
ℎ – время простоя i-го обработчика.
Операции затрат на продвижение заявки в очереди, передачи обработчику, а
также помещения результата обработчиком в очередь отправки представляют
собой операции с фиксированным временем выполнения. Данные операции
практически нецелостны и время на их выполнение уходит очень мало. Отсюда
следует:
31
ℎ = _ℎ − _ℎ −
∑


,
(1.7)
∈ℎ
где _ℎ – время запуска обработчика;
_ℎ – время остановки обработчика;
ℎ – множество запросов, выполненных обработчиком.
Наиболее
вычислительной
целесообразно
мощности,
разработать
который
позволит
механизм
регулирования
сократить
время
простоя
обработчиков и время обработки заявок, без ущерба для производительности
системы. Данный механизм даст возможность прогнозировать нагрузки и менять с
опорой на него конфигурацию и параметры системы. Прогнозирование нагрузки
возможно
выполнить
посредством
созданных
алгоритмов
оперативного
прогнозирования. Применение такого алгоритма даст возможность создать
механизм, не зависящий от системных изменений и нагрузки. Таким образом
предмет исследования определяется как диспетчер управления слоя логики. Это
базовый модуль системы, который регулирует вычислительную мощность системы
в зависимости от степени нагрузки. Функции данного модуля включают создание
и ликвидацию компонентов обработчиков.
К функциям этого модуля относится прием заявок, их распределение по
обработчикам, создание и уничтожение компонентов обработчиков.
Основная
цель
нейропрогнозирования
работы
с
заключается
целью
в
оперативного
создании
алгоритмов
регулирования
числа
вычислительных компонентов серверного узла. Ее успешное достижение требует
решения таких задач:
– исследовать способы построения распределенных систем на базе
разделения функциональности на слои;
– определить особенности организации взаимодействия между узлами в
распределенных системах и создание на их основе новых алгоритмов
нейропрогнозирования
для
оперативного
централизованно-кольцевых систем;
регулирования
распределенных
32
– разработать архитектуру и выполнить программную реализацию
нейропрогностических средств для оперативного регулирования распределенных
централизованно-кольцевых систем;
–
экспериментально
механизма для
проверить
оперативного
реализацию
регулирования
нейропрогностического
в
распределенной
централизованно-кольцевой системе.
Следующие главы посвящены детальному рассмотрению решений каждой из
перечня задач.
Выводы по Главе 1:
1. Установлено одно из главных требований при создании распределенных
систем обработки информации. Данным ключевым требованием является
масштабируемость.
2. Показана необходимость оперативного регулирования вычислительной
нагрузки для выполнения масштабирования распределенных централизованнокольцевых систем в автоматическом режиме.
3. Выявлены достоинства централизованно-кольцевой топологии создания
распределенных систем, которое заключается в возможности масштабирования
посредством регулирования числа узлов серверного кольца слоя логики.
4. Доказано отсутствие готовых, испытанных на практике механизмов,
которые
смогли
бы
вычислительных узлов.
реализовывать
оперативное
регулирование
числа
33
2 АНАЛИЗ И РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ
НЕЙРОПРОГНОЗИРОВАНИЯ ДЛЯ ОПЕРАТИВНОГО РЕГУЛИРОВАНИЯ
РАСПРЕДЕЛЕННОЙ ЦЕНТРАЛИЗОВАННО-КОЛЬЦЕВОЙ СИСТЕМЫ
Предыдущая глава состоит из рассмотрения основных подходов к проблеме
увеличения эффективности управления распределительными системами. В рамках
данной части работы был выполнен анализ целесообразности применения
централизованно-кольцевой схемы в системах подобного вида. Была также
отмечена важность регулирования вычислительной мощности в повышении
эффективности системы обслуживания пользовательских запросов. В текущей
главе предложены алгоритмы и методы для оперативного регулирования
производительности системы посредством прогнозирования нагрузки.
2.1 Анализ повышения эффективности распределенных централизованнокольцевых систем обработки информации
Основной показатель эффективности любой ИС – это время реакции, которое
представляет собой промежуток времени с момента регистрации запроса до
момента отправки ответа на него [76]. Рис. 2.1. демонстрирует диаграмму
пребывания запроса на обработке от момента поступления в систему до момента
отправки ответа.
Рисунок 2.1 – Диаграмма пребывания запроса в системе обработки
34
Время обработки запроса (  ) складывается из следующих временных
составляющих:
– время пересылки запроса от клиента на сервер (  );
– время обработки поступившего запроса в центральном узле системы
( _ );
– время, необходимое для создания обработчика ( _ );
– время выполнения запроса компонентом (  );
– время, затраченное на отправку ответа i-м компонентом ( _ );
– время ожидания в очереди в условиях ограниченного числа обработчиков
(  ).
Отсюда:
  =   +  _ +  _ +   +  _ +   . (2.1)
Наглядно видно, что уменьшение времени обработки запроса следует из
уменьшения значений любого из слагаемых. Теперь необходимо провести
аналитику возможных путей уменьшения временных затрат.
Менеджер транзакций в распределенной системе, который одновременно
является центральным узлом, координирует взаимодействие серверной части с
клиентами. Через данный узел проходит любой взаимодействие частей системы.
Время прохождения заявки через центральный узел ( _ ) вносит свой
вклад в общее время обработки. Снижение нагрузки на центральный узел до
минимума можно получить за счет упрощения алгоритма обработки заявок и
ответов. Идеальный случай – это выполнение менеджером транзакций только
транспортных функций. Время обработки поступившего и отправляемого пакета
находится в прямой зависимости от числа выполняемых в отношении него
операций. Повышению эффективности работы узла способствует примитивность
обработчиков. Однако даже транспортные функции характеризует конечная
пропускная способность. Способы решения проблемы масштабирования на
транспортном уровне, оптимизация транспортных задержек рассматривается в
исследовании [44].
35
Реализация алгоритма обработки запроса выполняется в теле обработчика.
Снижение до минимума затрат на выполнение обработки запроса существенно и с
оценкой «плюс» влияет на производительность системы. Рекомендации по
оптимизации кода обработчика с целью ускорения обработки даны в [78,48],
однако стоит учитывать, что универсального подхода к решению данной проблемы
до сих пор не найдено.
Зачастую, обработчикам необходимо зарегистрировать большое число
ресурсов при инициализации. Сюда входит инициализация обработчика,
считывание кода с информационных носителей, выделение внушительного объема
памяти и так далее. Может также занять некоторое время деструктуризация
обработчика по окончанию формирования ответа. В [94] продемонстрировано, что
время, которое тратится на создание компонента-обработчика, во многих случаях
в несколько раз превышает время, потраченное на обработку.
2.2 Разработка архитектуры распределенных систем с оперативным
регулированием вычислительной мощности
Как было отмечено ранее, увеличение производительности распределенной
системы нуждается в минимизации кода, который выполняется центральным
звеном. Такого результата можно достичь, наделив его исключительно
транспортными функциями. При выполнении только приема, расшифровки
запроса и отправке ответа дальнейшую работу по обработке запроса предлагается
предоставить удаленным компонентам системы. Данный подход открывает путь к
разработке динамически масштабируемых систем. С увеличением нагрузки на
систему менеджером транзакций происходит создание и инициализация
дополнительных компонентов для обработки запросов.
В таких случаях в момент запуска системы нужно создать кольцо, состоящее
из нескольких узлов-обработчиков, и в дальнейшем использовать механизм:
– закрепление запроса за одним из свободных узлов при поступлении в
систему;
36
– в условиях занятости всех обработчиков помещение поступившего запроса
в очередь и его отправка на обработку при появлении свободного узла.
Со снижением числа поступающих запросов может уменьшиться число
вычислительных ресурсов для освобождения мощностей под реализацию других
задач. При выполнении упреждающего регулирования числа обработчиков
диаграмма пребывания запроса в системе имеет вид, показанный на рис. 2.2.
Рисунок 2.2 – Диаграмма пребывания запроса в системе обработки при
упреждающем регулировании количества обработчиков
Таким образом, время обработки запроса (  ) определяется по формуле:
  =   +   +  _ .
(2.2)
Рассматриваемый механизм даст возможность значительно сэкономить
время, если произойдут серьезные временные траты на формирование и
ликвидацию обработчика. Налицо эффективность представленного механизма,
если
есть
ресурсоемкие
обработчики,
при
нежелательном
постоянном
удерживании вычислительных мощностей электронно-вычислительной машины,
на которой располагается системный компонент. Стоит отметить, что 2.1. имеет
справедливость только пока, если число занятых обработчиков не станет меньше
числа поступивших заявок.
37
Из вышесказанного можно сделать вывод о необходимости получения
аналитического вида функции зависимости вычислительной мощности от
состояния системы.
В случае, если заранее известен закон распределения и распределение
длительности обслуживания запроса, на поставленный вопрос дает ответ теория
массового обслуживания [75,49,44,18]. В реальности условия жесткого задания
необходимых потоков практически никогда не реализуется. Чаще присутствует
нестационарность процесса, то есть, изменение интенсивности потока в
зависимости от дней месяца или времени суток. Ни одну из зависимостей нельзя
получить в общем случае.
Решение поставленной задачи требует разработки метода оперативного
прогнозирования числа вычислительных ресурсов, который позволит в процессе
работы системы получать показатели функции для состояния системы,
соответствующее следующему моменту времени на основе состояния в настоящий
момент времени.
На рис. 2.3. показана традиционная схема распределенной централизованнокольцевой системы с использованием статичного пула обработчиков.
Рисунок 2.3 – Схема централизованно-кольцевой распределенной системы
38
Пул обработчиков слоя логики  содержит обработчики 1 , … ,  ,
объединенные в кольцо. Подобная организация слоя логики открывает путь к
изменению мощности системы, останавливая или добавляя обработчики.
Предложено
интегрировать
в
схему
централизованно-кольцевой
распределенной системы механизм оперативного регулирования. На рис. 2.4.
приведена схема функционирования полученной системы с применением
оперативного регулятора нагрузки.
Рисунок 2.4 – Схема распределенной системы с подсистемой оперативного
регулирования
На основе статистических данных о работе системы за предыдущие периоды
времени, а также в зависимости от текущей нагрузки, подсистема регулирования
должна производить инициализацию дополнительных обработчиков, либо
освобождение простаивающих. Такой подход позволит высвободить максимально
возможное количество ресурсов без ущерба для общей производительности
системы.
Регулятор включает модули: сбора статистики, прогнозирования нагрузки,
настройки. Модуль сбора статистики фиксирует изменение нагрузки на
39
протяжении всего функционирования системы для того чтобы посредством модуля
настройки можно было выявить зависимость нагрузки от внешних факторов и
задать
оптимальный
режим
работы
модуля
прогнозирования.
Модуль
прогнозирования изменяет число обработчиков на основе прогностических
показателей нагрузки.
2.3 Обоснование выбора типа нейронной сети для реализации механизма
оперативного прогнозирования
Структуру, состоящую из связанных между собой нейронов, называют
нейронной сетью. Нейрон представляет собой простейший элемент вычисления,
включающий разнотипные элементы:
– умножители (синапсы);
– нелинейный преобразователь;
– сумматор.
Умножители выполняют функцию связующего звена между нейронами,
умножают входной сигнал на вес синапса (число, характеризующее силу связи).
Сумматор складывает сигналы, которые поступают от других нейронов по
синаптическим связям. Посредством нелинейного преобразователя реализуется
нелинейная функция выхода сумматора. Данная функция именуется функцией
активации или передаточной функцией нейрона. В целом нейрон реализует
скалярную функцию векторного аргумента.
Математическую модель нейрона выражается формулой [62]:

 = ∑   + ,
=1
где  – вес синапса (weight), ( = 1,2, . . . ,  );
 – значение смещения;
 – результат суммирования;
 , – компонента входного вектора (входной сигнал), ( = 1,2, . . . ,  );
 – число входов нейрона.
(2.3)
40
В общем случае весовые коэффициенты, входной сигнал, и значения
смещения могут принимать действительные значения. Выход определяют видом
функции активации. Он может быть и действительным, и целым. Во многих
практических задачах весовые коэффициенты, входной сигнал, и значения
смещения могут принимать только определенные фиксированные значения.
Функции активации подразделяются на линейные и нелинейные. При
введении нелинейностей в структуру нейросети повышается ее мощность, т.к.
любая комбинация линейных функций также дает линейную функцию. В самой
структуре сетей с линейными функциями активации имеют место значительные
ограничения. Их снятие осуществляется посредством использования нелинейных
функций.
В работах [62,42,31,43,19,20,84] рассматриваются общие вопросы работы
нейронных сетей. Нейронные сети используются для решения широкого класса
задач. В исследованиях [53,37,55,39,72] рассматриваются вопросы использования
нейронных сетей в задачах распознавания образов. Нейронные сети также находят
применение
в
приложениях
моделирования
[63],
ассоциативной
памяти
[76,23,46,86], классификации данных [39,99,65], сжатия данных [54,56,39,67],
поиска информации [74], построения адаптивных систем [5,17,56].
В табл. 2.1 показана аналитика применимости разных нейросетевых
парадигм к решению тех или иных задач.
Наглядно видно, что для прогностических задач подходит многослойный
перцептрон и сети радиального базиса, потому что данные технологии могут
обеспечить возможность оперативного прогнозирования нагрузки.
Теперь
необходимо
более
подробно
остановиться
на
механизме
многослойного перцептрона (сеть обратного распространения, back propagation
network, MLP). Подробно о структуре и принципах работы данной технологии
рассказывается в [34,49,52,66].
41
Таблица 2.1 – Анализ возможностей нейросетевых парадигм
АссоциаСжатие
тивная информац
память
ИИ
Сеть
Хопфилда
Сеть
встречного
распростра
нения
Класте- Оптим Классиф Прогно
ризаци изация
икация
зирова
я
ние
+
+
+
+
Сеть
радиального
базиса
1
+
Карта
Кохонена
Многослой
ный
перцептрон
(MLP)
Двунаправленная ассоциативная
память
Сеть
Хэмминга
+
+
+
+
+
+
+
+
+
+
Вероятностная
сеть
PNN
Сеть
адаптивного
резонанса
ART2
+
+
+
+
Изучаемая сеть относится к классу сетей с последовательными связями.
Схему сети демонстрирует рис. 2.5. Все нейроны сети обратного распространения
подразделяются на слои. На вход каждого нейрона подаются выходы всех нейронов
предыдущего слоя. Входной слой используется для подачи входных сигналов.
Выходной сигнал формируется на выходном слое. Все остальные уровни скрыты.
Число нейронов входного и выходного слоев соответствует числу входных
параметров и выходных значений.
42
Рисунок 2.5 – Строение многослойного перцептрона
Сеть функционирует путем прямого прохода. В обучении сети применяется
специальный алгоритм, который сочетает процедуру обратного хода с изменением
коэффициентов веса на основе значения функции ошибки.
Обучающий алгоритм многослойного перцептрона, который показан на рис.
2.6, подробно описывается
в работе
[16,66].
Основа обучения – это
последовательное предъявление сети примеров обучения с известными входными
и выходными значениями. Выходной сигнал сети определяется по известным
входам. После этого вычисляется новый коэффициент связи. Вычисление
производится на основе показателя ошибки выхода каждого нейрона. Процесс
характеризуется рекурсивностью. Он повторяется до тех пор, пока значение общей
ошибки не станет достаточно минимальным.
43
Рисунок 2.6 – Схема алгоритма обратного распространения ошибки
Нейронные сети радиального базиса (RBF-сетей) в своей основе опираются
на подход, который основывается на разбиении пространства на гиперсферы,
44
задающиеся радиусом и центром. Поверхность отклика радиального элемента – это
гауссова функция, вершина которой находится в центре, по краям – понижение.
Наклон гауссова радиального элемента изменяем.
В RBF-сети нейроны слоя Кохонена работают с реальными выходными
значениями,
определяемыми
функцией
Гаусса
с
нормальным
законом
распределения.
Обучение нейронной сети с радиально-базисной функцией осуществляется в
два последовательных этапа. Первый этап заключается в обучении слоя Кохонена,
которое выполняется в соответствии с правилом «победитель забирает все» с
применением конкурентного обучающего метода. Далее выполняется группировка
входных образцов в кластеры, после этого определяется ширина радиальнобазисной функции для каждого нейрона слоя Кохонена. Второй этап – обучение с
учителем. Осуществляется настройка весовых коэффициентов в соответствии с
алгоритмом обратного распространения ошибки.
Рисунок 2.7 – Строение сети RBF
Сравнительная аналитика двух нейросетевых парадигм (многослойный
перцептрон и сеть радиального базиса), которые применимы к прогнозированию,
выявил следующие факты:
45
– При решении одной и той же задачи размер сети RBF превышает размер
MLP. Это обусловлено различными способами кодирования информации на
скрытых слоях, для MLP - гиперплоскости, для RBF - гиперсферы. Применение
гиперсфер ведет к неэффективности сети RBF, которая связана с тем, что при
работе сети в каждом конкретном случае применяется только часть нейронов.
– Число слоев для обоих вариантов равняется трем – входной, выходной,
скрытый. В [26] говорится о том, что любая функция может быть
аппроксимирована трехслойной сетью MLP с одним скрытым слоем с любой
степенью точности.
– MLP может работать с разными функциями активации. Это открывает
более широки возможности для экспериментов в ходе создания нейросетевой
модели. Сети RBF пользуются только гауссовой функцией активации.
– Сеть RBF не способна к экстраполяции данных при увеличении ширины
диапазона значений входных данных. Отклик сети быстро затухает при удалении
от сформированных на обучающей выборке центров классов.
– Недостатки сетей MLP заключаются в сложном обучающем процессе. Это
связано с необходимостью прохода по всем нейронам при обучении методом
обратного
распространения.
Однако
при
использовании
в
качестве
вычислительного устройства ЭВМ влияние этого негативного фактора ничтожно
мало.
Результаты сравнительного анализа сведены в таблицу 2.2.
Таблица 2.2 – Сравнение двух нейросетевых парадигм, применимых к
прогнозированию
Виды кодирования информации
Участвуют в аппроксимации
Многослойный перцептрон (MLP)
Гиперплоскости
Все нейроны
Сеть радиального базиса
(RBF)
Гиперсферы
Ближайшие нейроны
Чувствительность к размерности
входных данных
Выражается в росте сложности
обучения
Выражается в росте размеров
сети
Количество скрытых слоев
Несколько
Сигмоида, гиперболический
тангенс, биполярная сигмоида
Да
Одновременное (более медленное)
Один
Гауссова функция
Характеристика
Функция активации
Способность экстраполировать
Форма обучения слоев
Нет
Раздельное (более быстрое)
46
В связи с более широкими возможностями многослойного перцептрона в
сравнении с сетями радиального базиса целесообразно использовать в качестве
механизма прогнозирования сеть на основе многослойного перцептрона.
2.4 Разработка общего подхода к прогнозированию на основе аппарата
нейронных сетей
С учетом применения в качестве механизма прогнозирования нейронных
сетей схему функционирования распределенной централизованно-кольцевой
системы (см. рис. 2.4) необходимо дополнить подсистемой генерации нейросети,
подсистемой обслуживания нейросети и подсистемой обучения нейросети (рис.
2.8).
Далее необходимо рассмотреть механизм работы оперативного регулятора.
До накопления достаточного объема статистической информации система может
работать только в режиме статичного пула. Выделения или освобождения внешних
ресурсов при этом не происходит. После получения достаточного для настройки
регулятора количества статистики выполняется генерация прогнозирующей
нейронной сети прогностического модуля и ее обучение. Генерация нейронной
сети осуществляется по итогам определения влиятельных факторов внешней
среды. К числу таких факторов можно отнести точное время, час, день недели, флаг
“выходной день” и т.д. Большую роль играют знания настройщика в области
работы системы в силу того, что дальнейшая эффективность работы регулятора
основана исключительно на умении выделить существенные факторы. После
определения всех переменных работы регулятора производится генерация
нейронной сети. Затем созданная сеть подвергается обучению. По окончании
тестирования принимается решение об удачности обучения. При недостаточных
значениях показателей качества обучения производится повторное обучение сети.
После того, как сеть обучена, возможен запуск модуля прогнозирования в активном
режиме. Значения предоставляются сети, после чего на выходе формируется
значение прогноза, которое после преобразования можно использовать для
корректировки числа активных обработчиков. При такой организации работы
47
механизм нуждается в услугах эксперта лишь раз, для определения переменных и
их форматов.
Рисунок 2.8 – Схема оперативного регулятора на основе нейросетевого
прогнозирования
Далее необходимо боле подробно рассмотреть задачи, которые решают
подсистемы обслуживания и генерации. Прогнозирование нужного количества
ресурса требует:
1. Выявить зависимость количества прогнозируемого ресурса от внешних
факторов и внутренних состояний системы.
2. Создать средства быстрого вычисления выходных значений зависимости
на основе входных данных.
Нейросеть способна рассчитывать вектор  для любого входного вектора 
[66], т.е. давать значение некоторой векторной функции  = ().
48
Задача выбора смысла (формализации) характеристик, которыми наделены
компоненты входного и выходного векторов, может решаться только человеком на
основе имеющегося у него практического опыта. В настоящее время отсутствуют
жесткие рецепты формализации для нейронных сетей.
Существуют предполагаемые возможности недостаточного числа нейронов
и слоев. Это может быть необучаемость сети, в этом случае возникнет большая
ошибка в работе сети, на ее входе не будет осуществляться передача резких
колебаний аппроксимируемой функции. Негативно может сказаться и превышение
необходимого числа нейронов и слоев. В этом случае может появиться
переобучаемость сети (выходной вектор будет передавать незначительные и
несущественные детали в изучаемой зависимости, например шум или ошибочные
данные). В такой ситуации резко нелинейной окажется зависимость выхода от
входа, это значит резкие, существенные, непредсказуемые изменения вектора при
малом изменении входного вектора. Сеть потеряет способность к обобщению.
Выходной вектор будет непредсказуем и случаен, неадекватен решаемой задаче.
Данные, которые подаются на вход сети и снимаются с выхода, должны быть
подготовлены. Данная подготовка состоит в изменении шкалы, ее стандартизации
и нормализации [39,66].
Изменение шкалы – это вычитание или прибавление константы с
дальнейшим умножением на определенный коэффициент. Как правило, это
применяется при переходе от одних измерительных единиц к другим.
Нормализация – это деление показателей на норму вектора. Стандартизация
– вычитание меры расположения с дальнейшим вычитанием меры шкалы.
Предварительная подготовка данных путем их изменения выполняется для
максимизации энтропии входов и выходов. Вся информация обучения находится в
обучающих данных. Получается, что, чем больше хват области обучения, тем
качественнее пройдет обучающий процесс. Идеально, если значения равномерно
распределятся на области обучения [19].
Все действия, которые связаны с изменением входных и выходных данных,
будут носить название масштабирования.
49
Универсальных
методических
рекомендаций
по
предварительному
преобразованию входных и выходных данных нет. Стоит отметить, что на скорость
обучения значительное влияние оказывает способ предоставления данных.
Многослойный перцептрон требует расположения значений в диапазоне [0; 1].
Однако некоторые источники утверждают, что оптимальной является группировка
значений у ноля. Причем, это касается и положительной и отрицательной
окрестности [19]. Кроме того, нужно грамотно выбрать функцию активации.
Диапазон значений подбирается в зависимости от диапазона определения функции.
Зачастую скорость сходимости можно увеличить посредством небольшого
сужения диапазона определения функции активации. К примеру, вместо
конкретного диапазона [0; 1] применять для кодирования значений диапазон [0,1;
0,9].
Способы масштабирования для разнотипных сетей могут быть различны. Это
вызвано разными способами образования входных сигналов с предыдущего
уровня. Для сетей, у которых способ основан на функции расстояния (евклидово
расстояние, например), масштабирование необходимо. Примером такой сети
является сеть RBF. Необходимость масштабирования вызвана тем, что вклад
каждой переменной зависит от диапазона ее определения в сравнении с другими
переменными. В случае, если одна переменная определена на промежутке [0;0,1],
а другая на [0; 100000] вклад второй переменной будет ничтожно мал. Таким
образом, для переменных одинаково важных необходимо приводить значения к
одному диапазону.
В случае формирования входов последующего уровня с помощью линейной
комбинации
входов
предыдущего
уровня
(этот
способ
характерен
для
многослойного перцептрона) может показаться, что масштабирование не имеет
значения. При линейной комбинации выходов предыдущего слоя теоретически
любое масштабирование может быть реализовано подбором соответствующих
весовых коэффициентов. Однако подбор таких коэффициентов на практике в
процессе обучения сети практически невозможен. Это вызвано проблемой
определения начальных значений весовых коэффициентов. Перед началом
50
обучения выбираются малые значения коэффициентов, чтобы избежать выхода на
уровень насыщения. Стоит отметить, что при этом нельзя выделить коэффициенты,
которые
необходимо
масштабирования
подвергнуть
определенных
значительным
переменных.
изменениям
Данная
проблема
для
решаема
посредством проведения масштабирования значений перед обучением.
2.5 Метод прогнозирования нагрузки на основе многослойного перцептрона
Разработанный метод прогнозирования нагрузки состоит из четырех этапов.
На первом этапе, представленном на рис. 2.9, на основе оценки экспертов
выделяется набор факторов внешнего мира и внутренних состояний системы,
влияющих
на
прогноз.
Например,
применительно
к
решению
задачи
прогнозирования серверной нагрузки факторами могут быть значения номера дня
недели, времени суток, часы работы и т.д. Также на первом этапе нужно
осуществить сбор значений выбранных факторов путем сбора статистики на
работающей системе.
Рисунок 2.9 – Этап 1. Выбор набора входных переменных и их масштабирование
51
Второй этап, показанный на рис.2.10 – это бинаризация (преобразование всех
входных и выходных векторов к двоичному виду) переменных на основе
сформированных экспертом диапазонов изменения их значений и числа квантов.
Формирование сети выполняется на основе полученных результатов обработки
данных.
Рисунок 2.10 – Этап 2. Формирование сети
Задание параметров для определения структуры нейронной сети:
I – число входов сети;
О – число выходов сети;
L – число скрытых слоев сети;
1 , … ,  – число нейронов в каждом из скрытых слоев.
52
В ходе операций настройки параметров нейронной сети число скрытых
нейронов может варьироваться для увеличения точности прогноза. Порядок
количества нейронов скрытого слоя оценивают посредством теоремы Колмогорова
и следствий из нее. В соответствии с изложенными в [52] теоретическими
результатами непрерывную функцию можно аппроксимировать с любой
точностью при помощи трехслойной нейронной сети, которая имеет  входных,
(2 + 1) скрытых и один выходной нейрон. Следовательно, число (2 + 1)
теоретически можно считать верхней границей количества нейронов на скрытых
уровнях. Данная оценка справедлива для сети, соответствующей глобальному
минимуму адаптивного рельефа ошибки в пространстве весов. На практике создать
такую наилучшую сеть обычно не удается. Кроме того, имея (2 + 1) скрытых
нейронов, велика вероятность, что сеть просто запомнит обучающие примеры,
когда на самом деле от нее требуется обобщение и выявление скрытых
закономерностей. Таким образом, оценка Колмогорова служит лишь ориентиром.
Выбор количества скрытых слоев и количества нейронов каждого скрытого слоя
целесообразно сделать настроечными параметрами прогнозирующей системы и в
каждом конкретном случае экспериментально подобрать нужное количество.
В качестве функции активации нейронов предлагается использовать
сигмоиду. Сигмоидная функция традиционно применяется в сетях типа
многослойный перцептрон, потому что она гладкая, дифференцируемая, а ее
производная выражается через саму функцию, что важно для обучения сети.
Формирование сети для решения задачи определяет набор векторов,
характеризующие факторы, диапазон их изменения и квантование. Проблема
выбора и подготовки параметров для прогнозирования включает в себя экспертную
задачу для специалиста предметной области, для которой создается система
прогнозирования ресурса. При
определении
экспертом данных
входных
параметров существует возможность динамического построения нейронной сети.
53
Рисунок 2.11 – Этап 3. Обучение сети
Нейронная сеть, которая синтезируется посредством метода, описанного
выше, перед началом применения нуждается в обучении. Обучение выполняется
по методу обратного распространения ошибки.
В качестве обучающих используются данные, полученные заранее, при
работе системы без прогнозирования. Перед обучением данные нуждаются в
подготовке.
Необходимо
привести
значения
в
соответствие
выбранным
диапазонам и произвести квантование и бинаризацию как входных значений, так и
54
значений прогнозируемого ресурса в соответствии с описанными выше
алгоритмами.
Обучение методом обратного распространения ошибки производится до тех
пор, пока изменение усредненной квадратичной ошибки не окажется меньше
некоторого допустимого значения при переходе от одной эпохи к следующей,
говорят, что наблюдается сходимость. Другим критерием окончания обучения
можно считать наступление момента, когда выход для каждого учебного образца
оказывается в рамках допустимого отклонения от соответствующего целевого
выходного образца.
Использование сети для прогнозирования ресурса осуществляется по
правилам идентичным обучению, с той лишь разницей, что не производится
обратный проход.
Четвертый этап (см. рис. 2.12) – функционирование прогностического
модуля в штатном режиме. Сети предъявляются значения факторов, при которых
необходимо получение величины прогноза. Здесь нужна дебинаризация и
преобразование обратное масштабированию выхода для определения абсолютного
числового промежутка значений прогноза.
В режиме прогнозирования постоянно ведется оценка качества прогноза.
Если выявлено большое количество неточностей в прогнозе, необходимо
выполнить переобучение сети.
Эффективность работы регулятора характеризуется выражениями (1.3), (1.6).
Метод оперативного прогнозирования даст возможность сократить среднее время
от постановки запросов во входящую очередь до помещения ответов в исходящую
(1.3) до среднего времени обработки запроса компонентом-обработчиком.
55
Рисунок 2.13 – Этап 4. Работа сети в режиме прогнозирования
Кроме того, использование метода оперативного регулирования даст
возможность сократить время простоя обработчиков (1.4) до ноля.
Перечень ограничений метода:
1. Нейронная сеть не способна сгенерировать правильный прогноз, если
отсутствует обучение на данных о факторах, которые серьезно влияют на прогноз.
То есть, сеть не может сделать прогноз того, чему ее не учили.
2. При общем изменении характера нагрузки сеть нуждается в переобучении.
3. Число скрытых слоев и нейронов сети определяют вычислительные
ресурсы ЭВМ.
56
4. Число примеров обучения должно во много раз превышать число скрытых
нейронов сети.
5. Существует необходимость в первоначальном задании состава входных
факторов с помощью эксперта.
С учетом перечисленных ограничений можно сделать вывод о том, что сеть
нуждается в достаточно большем объеме обучающих данных, охватывающем все
характерные периоды работы системы, однако, такой объем информации не
должен привести к переобучению сети. Кроме того, необходим постоянный
мониторинг качества прогнозирования, в случае ухудшения предоставляемого
сетью прогноза необходимо производить переобучение на свежих входных
данных. Процесс переобучения не должен происходить часто, т.к. он
характеризуется достаточно ресурсоемкими вычислениями. Первоначальная
настройка
сети
производится
экспертом,
обладающим
исчерпывающей
информацией о влиянии тех или иных параметров внешней среды на нагрузку. В
отличие от других методов прогнозирования, при использовании нейросети услуги
эксперта требуются лишь раз для выбора влияющих параметров.
Выводы по Главе 2:
1.
системы
Создана
с
архитектура
интегрированным
централизованно-кольцевой
механизмом
оперативного
распределенной
регулирования
вычислительной мощности.
2. Выполнен анализ основных методов краткосрочного прогнозирования. В
ходе аналитики выявлено условие наиболее эффективного использования
нейронных сетей. Им является краткосрочное прогнозирование серверной
нагрузки, потому что оно не налагает ограничений на характер прогнозируемого
процесса.
3. Выполнена сравнительная аналитика самых распространенных типов
нейронных сетей относительно задачи краткосрочного прогнозирования. В
процессе анализа установлено, что наиболее подходящим является многослойный
перцептрон из-за своей простоты, эффективности обучения и внутренней
параллельности вычислений.
57
4. Разработан метод прогнозирования нагрузки на основе многослойного
перцептрона, который дает возможность учитывать и эффективно применять
влияние на прогнозируемую величину большого числа разнородных факторов.
58
3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕХАНИЗМА ОПЕРАТИВНОГО
РЕГУЛИРОВАНИЯ РАСПРЕДЕЛЕННОЙ ЦЕНТРАЛИЗОВАННОКОЛЬЦЕВОЙ СИСТЕМЫ
Созданный
механизм
оперативного
регулирования
вычислительной
мощности централизованно-кольцевой системы реализован в программном
исполнении в виде объектно-ориентированной библиотеки классов на языке
Borland Delphi.
Объектно-ориентированная реализация библиотеки на основе языкового
стандарта Borland Delphi является востребованной и приемлемой в современных
условиях разработки ПО.
Язык Borland Delphi для этих целей был выбран из-за удобства
использования памяти (автоматическое освобождение неиспользуемой памяти “сборка мусора”) и объектной ориентацией данного языка.
3.1 Архитектура и состав библиотеки компонентов
В этом подпункте будет показан состав библиотеки оперативного
регулирования распределенной централизованно-кольцевой системы на основе
нейропрогнозирования нагрузки с указанием блоков алгоритма, реализация логики
которого осуществлена в том или ином классе.
TNeuron – класс, который инкапсулирует главные характеристики нейрона,
открывает доступ к получению выходного значения в зависимости от значений на
входах и активационной функции.
TNeuronBP – класс, потомок TNeuron. Он расширен свойствами и методами,
которые присущи нейрону сети обратного распространения ошибок, в качестве
функции активации реализована сигмоида.
TLayer – базовый класс слоя.
TLayerВР – класс слоя сети обратного распространения ошибки.
TNeuralNet – класс, который инкапсулирует работу нейронной сети.
59
TNeuralNetBP – класс, который реализует работу сети обратного
распространения ошибок.
TVariable – класс, который реализует функциональность работы с
переменными алгоритма.
TNNVariable – базовый класс, который реализует работу с переменными
сети.
TNNBinVariable – класс, представляющий собой наследника TNNVariable,
который отвечает за работу с двоичным преобразованием переменных.
TNNGrayVariable – класс, представляющий собой наследника TNNVariable,
для работы с преобразованием переменных по коду Грея.
TNNConfiguration – класс, который реализует работу с конфигурациями сети
(применяется для разработки структуры сети по заданным параметрам).
TNNData – класс для работы с выборками данных обучения (применяется в
Блоке 3.1).
TNNManager
–
класс,
который
реализует
функциональность
прогностического модуля.
Общая
структура
библиотеки
реализации
механизма
оперативного
регулирования приведена на рис.3.1.
Взаимодействие данных классов и ряда вспомогательных структур дает
возможность преобразовать статистические данные, а потом провести их анализ в
соответствии с прогностическим алгоритмом.
60
Рисунок 3.1 – Структура библиотеки механизма оперативного регулирования
Далее приводятся отдельные фрагменты, которые описывают выполнение
того или иного метода или преобразования. Исходный код классов разделен на два
модуля. Первый включает классы, которые реализуют функциональность работы с
нейронными сетями (TNeuron, TLayer, TNeuralNet, TNeuronBP, TLayerBP,
TNeuralNetBP), второй объединяет классы, которые участвуют в реализации
прогностического метода, описанного в Главе 2 (TVariable, TNNVariable,
TNNBinVariable, TNNGrayVariable, TNNConfiguration, TNNData, TNNManager),
исходный код модуля представлен в приложении 1.
3.2 Программная реализация механизма обучения многослойного
перцептрона
В рамках данного подпункта необходимо рассмотрение реализации
обучающего механизма сети обратным распространением ошибки в методе
TeachOffLine. Рис. 3.2 отражает схему алгоритма TeachOffLine.
Первое обучение – это инициализация весовых коэффициентов случайными
значениями (InitWeights). Далее следует инициализация генератора случайных
61
чисел (Randomize) и установка длины последовательности случайных чисел в
числе обучающих наборов и запуск цикла обучения. Условие выхода из
обучающего цикла заключается в прохождении числа эпох, которое равно
значению EpochCount.
Шаги обучения на протяжении эпохи:
Шаг 1: Инициализация переменных. FTeachError - значение ошибки
обучения, FMaxTeachResidual - значение максимальной ошибки на обучающем
множестве, FRecognizedTeachCount - количество распознанных примеров на
обучающем множестве, xNewEpoch - флаг новой эпохи обучения.
Шаг 2: Перемешивание данных обучения. Это необходимо для улучшения
обобщающих свойств будущей сети. В отдельный метод выносится реализация.
Шаг 3: Перечень действий:
1.
Предъявление
сети
на
вход
значении
входных
переменных
(LoadPattemsInput). Предъявление сети на выход значении выходных переменных
(LoadPattemsOutput).
2. Распространение сигнала в прямом направлении (Propagate).
3. При условии того, что предъявленный сети пример был распознан,
увеличивается
значение
счетчика
распознанных
примеров
(FRecognizedTeachCount). Также увеличивается значение ошибки обучения на
значение квадратичной ошибки.
62
Рисунок 3.2 – Схема алгоритма обучения нейронной сети
63
4. В случае обработки первого набора в эпохе, значению переменной,
характеризующей
максимальную
ошибку
на
обучающем
множестве,
присваивается значение квадратичной ошибки. Если набор не первый в эпохе, то
перед присваиванием производится сравнение. Присваивание, в этом случае,
производится, только если значение квадратичной ошибки оказывается больше,
чем значение переменной MaxTeachResidual.
5. Вычисление занчения локальной ошибки (CalcLocalError).
6. Подстройка весовых коэффициентов (AdjustWeights).
Шаг 4: Вычисление значения средней ошибки (FMidTeachResidual) на
обработанном обучающем множестве.
Шаг 5: Увеличение значения счетчика эпох (FEpochCurrent).
Выход из обучающей процедуры сопровождается вызовом события (перед
выходом из процедуры), который означает окончание обучения – OnAfterTeach.
Отдельно необходимо уделить внимание методу реализации прямого
прохода сигнала по нейронной сети. Рис. 3.3. демонстрирует схему алгоритма
методики TNeuralNetBP.Propagate, которая осуществляет прямой проход сигнала.
Обработка сигнала в прямом направлении выполняется в цикле по всем
слоям сети. Она начинается с нейронов второго слоя, так как эти нейроны являются
входами сети. После выполнения операций настройки массива значений выходов
предыдущего слоя (хАггау), он заполняется значениями свойства Output нейронов
предыдущего слоя. После этого последовательным вызовом метода ComputeOut с
входным параметром (хАггау) для всех нейронов обрабатываемого слоя
определяется значение их выхода. Перед завершением работы подпрограммы
производится ликвидация временного массива хАггау.
64
Рисунок 3.3 – Схема алгоритма метода TNeuralNetBP.Propagate
Метод AdjustWeights применяется для корректировки весов, схема алгоритма
данного метода показана на рис.3.4
65
Рисунок 3.4 – Схема алгоритма метода TNeuralNetBP.AdjustWeights
3.3 Реализация программы прогнозирования количества пользователей
средствами разработанной библиотеки
Во второй главе было произведено теоретическое обоснование возможности
оптимизации функционирования распределенных централизованно-кольцевых
систем с помощью регулирования числа обработчиков заявок на основе
нейропрогнозирования. Чтобы подтвердить эффективность и адекватность
предложенного метода, была разработана нейронная сеть, предсказывающая
среднее количество пользователей  системы на следующий день.
Чтобы,
регулирование
используя
пулом
данную
обработчиков,
нейросеть,
достаточно
организовать
ввести
оперативное
коэффициент
,
отражающий количество заявок, способных одновременно обрабатываться на
66
одном вычислителе. Тогда необходимое количество обработчиков  вычисляется
по формуле:
=
1
.

(3.1)
Стоит отметить, что коэффициент  будет уникальным для каждой
распределенной системы. Его величина зависит от качества реализации
распределенной системы, её сложности, а также используемых при реализации
технологий.
В качестве исходных послужили данные о количестве одновременных
пользователей одной популярной в сети Интернет распределенной системы за
промежуток в 10 лет.
Рисунок 3.5 – График средней нагрузки на распределенную систему
Всего данных имеется за 3273 дня. По оси абсцисс единичным отрезком
является 1 день, по оси ординат – тысяча пользователей.
67
Для нормализации данных использовалось процентное изменение величины
нагрузки за день.
Рисунок 3.6 – Нормализованные исходные данные
Выборка поделена на окна по 30 дней. Архитектура нейронной сети включает
в себя 30 входов, 64 нейрона на скрытом слое и один выходной нейрон. Задача
нейронной сети во время одной итерации алгоритма получить значения,
соответствующие процентному изменению нагрузки в каждый из 30 дней, и
предсказать её изменение в тридцать первый.
Для разделения на обучающую и тестовую выборки исходные данные были
поделены в соотношении 85/15.
На рисунке 3.7 изображены графики точности предсказаний нейросети в
режиме обучения и в режиме тестирования.
68
Рисунок 3.7 – График точности модели во время обучения
Как видно из графика на рис. 3.7 точность предсказаний на тестовой выборке
стабильна, в то время как точность для обучающей выборки растёт, что
свидетельствует о начале эффекта переобучения.
Величина ошибки  предсказания варьируется в пределах 22-30%. Такой
результат
нельзя
назвать
идеальным,
однако,
данную
ошибку
можно
компенсировать, уменьшив коэффициент k следующим образом:
 =  (1 −

).
100%
(3.2)
Такой подход предотвращает перегрузку обработчиков, но уменьшает
величину экономии электроэнергии пропорционально величине ошибки.
Стоит также отметить, что в данном эксперименте не учитывались никакие
из характеристик, указываемые экспертом, в виду их отсутствия в открытом
доступе.
69
Для прогона в рабочем режиме по исходным данным сеть обучилась за 300
эпох (величина, после которой началось переобучение). После преобразования
выходного массива значений в абсолютные величины был построен график,
изображенный на рисунке 3.8, для наглядного представления результата.
Рисунок 3.8 – Графики исходных данных и предсказанных
Выводы по Главе 3:
1. Выполнена разработка объектной архитектуры библиотеки механизма
оперативного регулирования централизованно-кольцевых распределенных систем,
которая
дает
возможность
внедрять
в
библиотеку
новые
способы
нейропрогнозирования и кодирования.
2. Разработана программная реализация методов, выполняющих работу
многослойного
перцептрона
с
использованием
основных
требований
рефакторинга, чем обеспечивается простота и прозрачность программного кода.
70
3.
Реализован
обучающий
механизм
многослойного
перцептрона
посредством метода обратного распространения ошибки с учетом разработанной
объектной структуры нейронной сети.
4. Создана программная реализация механизма оперативного регулирования
распределенной централизованно-кольцевой системы.
71
ЗАКЛЮЧЕНИЕ
В процессе выполнения исследовательской работы удалось получить
следующие результаты:
– Сформулирована и предоставлена формальная постановка задачи
разработки
средств
регулирования
вычислительной
мощности
кольца
централизованно-кольцевой системы на базе нейропрогнозирования нагрузки.
Выявлены параметры и показатели увеличения эффективности работы алгоритма
на стороне сервера.
– Выполнена аналитика существующих прогностических методов и научное
обоснование необходимости применения многослойного перцептрона. Простой,
эффективный в обучении и внутренней параллельности вычислений механизм дает
возможность достоверное прогнозировать нагрузку при минимальных затратах на
вычисления.
–
Разработан
нейропрогностический
алгоритм
для
оперативного
регулирования вычислительной мощности распределенной централизованнокольцевой системы.
–
Создана
объектно-ориентированная
архитектура
и
программная
реализация механизма оперативного регулирования централизованно-кольцевыми
распределенными системами на базе нейропрогнозирования нагрузки.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1.
Айвазян C.A., Бежаева З.И., Староверов О.В. Классификация
многомерных наблюдений. - М.: Статистика, 1974. - 240 с.
2.
Андерсон Т. Статистический анализ временных рядов. - М.: Мир,
1976.755 с.
3.
Арсено Ж. и др. Переносимость программного обеспечения. //
Открытые системы, 1993 г., №2, стр. 29-35
4.
Барский А.Б. Параллельные процессы в вычислительных системах. -
М.:Радио и связь, 1990. - 256 с.
5.
Басканова
Т.Ф.,
Ланкин
Ю.П.
Нейросетевые
алгоритмы
самостоятельной адаптации. // Всероссийская научно-техническая конференция Нейроинформатика-99. Научная сессия МИФИ-99. Сборник научных трудов, В 3 ч.
- М.: МИФИ, 1999. - ч. 2. - с. 17-24
6.
Бокс Дж, Джеккинс Г. Анализ временных рядов. Прогноз и управление.
- М.: Мир, 1974. - 406 с.
7.
Боровков A.A. Математическая статистика. - М.: Наука, 1984. - 219 с.
8.
Браверман Э.М., Мучник И.Б. Структурные методы обработки
эмпирических данных. - М.: Наука. Гл. Ред. Физ.-мат. лит., 1983. - 467 с.
9.
Брауде Э. Технология разработки программного обеспечения. - СПб.
Литер, 2004, - 655 с.
10.
Буч Г. Объектно-ориентированный анализ и проектирование: с
примерами приложений на C++. - СПб.:Издательство Бином, 1998. - 560 с.
11.
Васкевич Д. Стратегии клиент-сервер. - Киев:Диалектика, 1996, - 384 с.
12.
Воеводин
В.В.
Воеводин
Вл.В.
Параллельные
вычисления.
-
СПб.:БХВПетербург, 2002, - 600 с.
13.Воеводин В.В. Математические модели и методы в параллельных
процессах. - М.:Наука, 1986, - 296 с.
14.
Гагарина Л.Г., Городилов A.B. К вопросу о реализации механизма
множественного наследования при программировании на Borland Delphi.
//Оборонный комплекс- научно-техническому прогрессу России: Межотр.
науч.техн. журнал/ВИМИ.-М., 2003, №3, с.22-24
15.
Гагарина Л.Г., Городилов A.B. Особенности разработки программных
компонентов взаимодействия с монитором производительности. // Оборонный
комплекс- научно-техническому прогрессу России:Межотр. науч.-техн. журнал/В
ИМИ.-М., 2004, №3, с.20-24
16.
Галушкин А.И. Нейрокомпьютеры. Книга 3. Учебное пособие для
ВУЗов. - М.:ИПРЖР, 2000г. - 528 с.
17.
Глаз А.Б. Применение принципов самоорганизации для построения
решающих правил на недостаточных обучающих выборках. // Автоматика. :Киев,
1984. - № 3. - С. 3 - 12.
18.
Гнеденко Б.В., Коваленко И.Н.. Введение в теорию массового
обслуживания. - М.:Наука.Гл.ред.физ.-мат.лит, 1987., 336 с.
19.
Головко В.А. Нейронные сети: обучение, организация и применение.
М.: Радиотехника, 2001.-256 с.
20.
Горбань
А.Н.,
Россиев
Д.А.,
Коченов
Д.А.
Применение
самообучающихся нейросетевых программ. - Красноярск: СПИ, 1994. -169 с.
21.
Городилов A.B. Алгоритм оперативного управления диспетчеризацией
ресурсов распределенной системы. //Техника и технология: СпутникПлюсМ.,2006, №2.-С.37-41
22.
Городилов A.B. К вопросу о методологиях разработки программного
обеспечения // X всероссийская межвузовская научно-техническая конференция
студентов и аспирантов. Тез. докл. - М.:МИЭТ 2003.-с.243
23.
Городилов A.B. К вопросу о реализации механизма множественного
наследования при программировании на Borland Delphi// IX Международная науч.-
практическая
конференция
студентов,
аспирантов
и
молодых
ученых
“Современные техника и технологии”. Тез. докл. В 2-х томах, Т.2 -Томск.:ТПУ,
2003.-е.124-125
24.
Городилов A.B. К вопросу об организации взаимодействия между
узлами в гетерогенной среде с оперативным распределением нагрузки. //
Актуальные проблемы современной науки: СпутникПлюс-М., 2006г, №2.-С.151152
25.
Городилов A.B. Механизм динамического распределения ресурсов
сервера между обработчиками запросов на основе прогнозирования нагрузки //
Известия ВУЗов. Электроника.-М., 2005 №3, с.88-89
26.
Городилов A.B. Особенности реализации механизма асинхронного
взаимодействия в гетерогенных системах с применением алгоритмов оперативного
регулирования. // Естественные и технические науки: СпутникПлюс-М., 2006,
№1.С. 192-196
27.
Городилов A.B. Разработка компонентов взаимодействия с монитором
производительности//
XI
всероссийская
межвузовская
научно-техническая
конференция студентов и аспирантов. Тез. докл. -М.:МИЭТ 2004.-c.273
28.
серверной
Городилов A.B. Разработка однопроходного метода прогнозирования
нагрузки
вычислительной
системы
//
Журнал
агентства
электронного
архива
научнотехнической информации SciTecLibrary, май 2005
29.
Городилов
A.B.
Разработка
нормативно¬правовой документации “НПДок”// IV Всероссийская научнотехническая конференция “Новые информационные технологии”. Тез. докл. В 2-х
томах, Т.2 -М.: МГАПИ 2003.-С.93-95
30.
Городилов A.B., Крагин А.Н. Организация электронного архива
документов// IX всероссийская межвузовская научно-техническая конференция
студентов и аспирантов. Тез. докл. - М.:МИЭТ 2002.- с.169
31.
Гофф М.К. “Сетевые распределенные вычисления. Достижения и
проблемы”, М.: Кудиц-образ, 2005.-320с.
32.
Громов А. Каменова М. Особенности реализации больших проектов. //
Computerworld. - 1996. №22 - С. 33-36.
33.
Дарвин Ян Ф. Java. Сборник рецептов для профессионалов. - СПб.:
Питер, 2002. - 768с.
34. Дейтел X. М., Дейтел П. Дж., Сантри С. И., Технология
программирования на Java 2. Книга 2. Распределенные приложения. - М.:
БиномПресс, 2003, - 464 с.
35.
Демиденко Е.З. Линейная и нелинейная регрессия. - М.: Финансы и
статистика, 1981. - 302 с.
36.
Долгов К.А. Исследование и разработка методов адаптивного
управления ресурсами сети коммутации пакетов. Автореф. дис. ... канд. техн. наук.
М., 1997.-29с.
37.
Дуда Р., Харт П. Распознавание образов и анализ сцен. - М.: Мир,
1976.512 с.
38.
Дьяконов В.П. «Закон Мура» и компьютерная математика. // Научно-
практический журнал ExponentaPro, 2003 г, №1, - с. 82-86
39.
Ежов А.А., Шумский С.А. Нейрокомпьютинг и его применения в
экономике и бизнесе. - М.: МИФИ, 1998. - 224 с.
40.
Емельянов
А.А.,
Е.А.
Власова,
Р.В.
Дума.
Имитационное
моделирование экономических процессов. - М.: Финансы и статистика, 2002 - 364
с.
41.
3аенцев И.В. Нейронные сети: основные модели. - Воронеж: ВГУ,
1999.157 с.
42.
Иванова Е. Вершинин М. Java 2 Enterprise Edition. - СПб.:БХВ-
Петербург, 2003 - 1088 с.
43.
Ивахненко А.Г. Перцептроны. - Киев: Наукова Думка, 1974. - 179 с.
44.
Ивченко Г.И., Каштанов Г.И., Коваленко И.Н. Теория массового
обслуживания. - М.: Высшая школа, 1982., 256 с.
45.
Информационные технологии. Открытая распределенная обработка
данных. Эталонная модель. Основы : Интернет-сайт.http://www.iso.org/iso/en/CatalogueDetailPage.CatalogueDetail7CSNUM
BER=20697&ICS 1 =35&1CS2=80&ICS3=
46.
Искусственный интеллект. Справочник, В 3-х кн. - Под ред.
Д.А.Поспелова. - М.: Радио и связь, 1990. - Кн.2: Модели и методы. - -304 с.
47. Казаков С.И. Основы сетевых технологий. М.: “Микроинформ”, 1995
48.
Касперски
К.
Техника
оптимизации
программ.
Эффективное
использование памяти. - СПб.:БХВ-Петербург, 2003. - 464 с.
49.
Кениг Д., Штойян Д.. Методы теории массового обслуживания: Пер. с
нем. Под. ред. Г.П.Климова. М.:Радио и связь, 1981.
50.
Керимов А.К. Методы анализа и прогнозирования ценовых данных:
Технический анализ: Учебное пособие. - М:РУДН, 2003 - 107 с.
51.
Ковалев И.В. Моделирование и оптимизация параллельных процессов
в информационно управляющих системах. Учебное пособие. - Красноярск: ИПЦ
КГТУ, 2003, 111 с.
52.
Колмогоров А.Н. Представление непрерывных функций многих
переменных суперпозицией функций одной переменной и сложением. Докл. АН
СССР, № 5, вып. 114 - С.953-956.
53.
Коновалов H.A., Крюков В.А. Параллельные программы для
вычислительных кластеров и сетей.//’’Открытые системы”, 2002, №3 (Интернет
адрес: http://www.osp.ru/os/2002/03/012.htrn)
54.
Крюков
В.А. Удовиченко
Р.В. Отладка
программ.//Программирование, 2001, №3, стр. 19-29
DVM-
65.
Мостеллер Ф., Тьюки Дж. Анализ данных и регрессия. - М.: Финансы
и статистика, 1982. - 239 с.
66.
Назаров
A.B., Лоскутов
А.И. Нейросетевые
алгоритмы
прогнозирования и оптимизации систем. - СПб.:Наука и Техника, 2003.-384 с.
67.
Нейроинформатика и нейрокомпьютеры // Тез. докл. рабочего
семинара / Гилев С.Е., Горбань А.Н., Галушкин А.И. и др. - Красноярск, 1993. - с.
83-85.
68.
сервер.
Орфали Роберт, Дэн Харки, Java и CORBA в приложениях клиент-
- М.:Издательство Лори, 2000 - 712 с.
69.
Павский
К.В.
Разработка
средств
анализа
функционирования
распределенных вычислительных систем. Автореф. дис. канд. техн. наук.
Новосибирск 2004 - 156 с.
70. Пол Киммел Создание приложений в Delphi. - М.:Вильямс, - 2003. - 631
с.
71.
Прицкер А. Введение в имитационное моделирование и язык SLAM- II.
-М.:Мир, 1987.-544 с.
72.
Прохоров В.В. Технология компонентных моделей представления
знаний и ее приложения к построению гетерогенных компьютерных сред: Дис.
докт. физ.-мат. наук, Челябинск, 2003, - 297 с.
73.
Растригин Л.А. Экстраполяционные методы проектирования и
управления. - М.: Машиностроение, 1986. - 120 с.
74.
Родионов
П.Е.
Решение
проблем
поиска
информации
путем
использования самообучающихся адаптирующихся систем на базе нейронных
сетей // Интеллектуальные технологии и системы. - М., 2001.-Вып.З. -С.60-61.
75.
Саати Т.Л. Элементы теории массового обслуживания и ее
приложения. - М.: Изд-во Советское радио, 1971. - 520 с.
76.
Саульев
В.К.
Математические
модели
теории
массового
обслуживания.-М. :Статистика, 1979, 96 с.
77.
Скурихин А.Н. Нейронные сети: определения, концепции, применение.
М.: ЦНИИ управления экономики и информатики, 1991. -274 с.
78.
Смирнов А.Н. Исследование методов организации и выполнения
параллельных вычислений в сети: Дис. ... канд. техн. наук, СПб, 2003,. 142 с.
79.
Смирнов Д. В. Разработка моделей иерархических описаний для
эффективного решения сложных задач в многомашинных многопроцессорных
комплексах. Дис. ... канд. техн. наук, Екатеринбург, 2002 - 130с.
80.
Советов Б.Я., Яковлев С.А. Моделирование систем. - М.: Высшая
школа, 1998. - 320 с.
81.
Суровцев И.С., Клюкин В.И., Пивоварова Р.П. Нейронные сети. -
Воронеж: ВГУ, 1994.-215 с.
82.
Таненбаум Э. Архитектура компьютера. 4-е издание. - СПб. Литер, -
2003.-704 с.
83.
Таненбаум Э., Ван Стеен М. Распределенные системы: Принципы и
парадигмы, - С-Петербург, Питер, 2003, 877 с.
84.
Терехов В.А., Ефимов Д.В., Тюкин И.Ю. Нейросетевые системы
управления. Книга 8: Учебное пособие для вузов. - М.ЛПРЖР, - 2002. -480 с.
85.
Топорков В.В. Модели распределенных вычислений: Монография. -
М:Физматлит, 2004г - 320 с.
86.
Уоссермен Ф. Нейрокомпьютерная техника. - М.: Мир, 1992. - 226 с.
87.
Фаулер М. Архитектура корпоративных программных приложений. -
М.: Вильямс, 2004, -544 с.
88.
Фаулер М. Рефакторинг: Улучшение существующего кода. - Пер. с
англ.
- СПб: Символ-Плюс, 2004. - 432 с.
89.
Харман Г. Современный факторный анализ. - М.: Статистика, 1972. -
90.
Цимбал А. Технология CORBA для профессионалов. - СПб.:
486 с.
Издательство Питер. 2001 - 624 с.
91.
Черепанов А.В. Модели и метод интеллектуальной поддержки
построения многокомпонентной технической системы: Дис. ... канд. техн. наук,
СПб., - 2003
92.
Шрайбер Т. Дж. Моделирование на GPSS. - М.Машиностроение, 1979.-
93.
Эккель Б. Философия Java, 3-е издание. - М.: Издательство Питер,
592 с.
2003472 с.
94.
средства
Эммерих В. Конструирование распределенных объектов. Методы и
программирования
интероперабельных
объектов
в
архитектурах
OMG\CORBA MicrosofiACOM Java\RMI. Перевод с англ. - М.:Мир, 2002 - 510 с.
95.
Эндрюс Р. Грегори Основы многопоточного, параллельного и
распределенного программирования. М.:Вильямс, 2003, 512 с.
96.
Alu Е., Mohamed I. “A Neural Network Approach for Dynamic Load
Balancing In Homogenius Distributed Systems”// 13th Annual Hawwaii International
Conf. System Sciences, 1997
97. Barker R. CASE Method. Entity-Relationship Modeling. - Oracle
Corporation UK Limited: Addison-Wesley Publishing Co., 1990. 231 p.
98.
Bernard Widrow, Michael A. Lehr, 30 Years of Adaptive NeuralNetworks:
Perceptron, Madaline, and Backpropagation. Artificial Neural Networks: Concepts and
Theory // IEEE Computer Society Press, 1992, pp.327-354.
Приложение 1
Программный код реализации механизма оперативного регулирования
централизованно-кольцевых распределенных систем
unit Variable;
interface
uses SysUtils, Contnrs, NeuralBaseComp, DBCiient;
type
DigPos = array of smaliint;
VarCl = class
private
RightEdge: extended;
LeftEdge: extended;
RightLimit: extended;
LeftLimit: extended;
AmountOfPoints: integer;
VarInput: boolean;
Title: string;
procedure SetPoint(const Value: integer);
function GetPoint: integer;
public
property VarLLim:extended read LeftLimit write LeftLimit;
property PointCount:integer read AmountOfPoints write AmountOfPoints;
property LeftLimit:extended read LeftEdge write LeftEdge;
property VarRLim:extended read RightLimit write RightLimit;
property VariablePoint:integer read GetPoint write SetPoint;
property RightLimit:extended read RightEdge write RightEdge;
property InputVariable:boolean read VarInput write VarInput;
property Title:string read Title write Title;
end;
NeuralVar = class
private
Title: string;
VarVal: integer;
NumberOfBinaryDigits: integer;
function GetMax: integer;virtual;abstract;
public
property Variableiinteger read VarVal write VarVal;
property MaxVar:integer read GetMax;
function DigPosCount(AVal:integer):integer;virtual;abstract;
property NumOfBinaryDigits:integer read
NumberOfBinaryDigits
NumberOfBinaryDigits;
function GetVar:integer;
property Title:string read Title write Title;
procedure SetVar(FirstLayerVar:integer);
procedure Clear;
procedure SetDigPos(ADigPos:DigPos);virtual;abstract;
function GetDigPos:DigPos;virtual;abstract;
function AsString:string;virtual;
write
end;
BinVar = class(NeuralVar)
private
function GetMax: integer;override;
public
procedure SetDigPos(ADigPos:DigPos);override;
function GetDigPos:DigPos;override;
function DigPosCount(AVal:integer):lnteger;override;
end;
GrayBinVar = class(NeuralVar)
private
function GetMax: integer;override;
public
function DigPosCount(AVal:integer):integer;override;
procedure SetDigPos(ADigPos:DigPos);override;
function GetDigPos:DigPos;override;
end;
CounterVar = class(NeuralVar)
private
function GetMax: integer;override;
public
function DigPosCount(AVal:integer):integer;override;
function GetDigPos:DigPos;override;
procedure SetDigPos(ADigPos:DigPos);override;
end;
ConfigCl = class
private
InVars:TObjectList;
OutVars:TObjectList;
NNetworkF: NNetworkCh;
function BinInputs: integer;
function BinOutputs: integer;
private
function InNeurons:integer;
function OutNeurons: integer;
public
constructor Create;
function AddInVar(FirstLayerVar:FirstLayerVar):integer;
property OutVars:TObjectList read OutVars;
function AddOutVar(FirstLayerVar:NeuralVar):integer;
property BinInputs:integer read BinInputs;
property InVars:TObjed;List read InVars;
property NNetwork:NNetworkCh read NNetworkF write NNetworkF;
property BinOutputs:integer read BinOutputs;
procedure Clear; procedure ConfigureNN;
end;
NeuralData = class(ConfigCl)
public
function InVarByName(Title:string):NeuralVar;
function OutVarByName(Title:string):NeuralVar;
procedure InsData;
end;
Mgr = class
private
NNetworkF: NNetworkCh;
NeuralNetworkData: NeuralData;
SetOfData: TClientDataSet;
DescOfVar: TObjectList;
FIOType: smallint;
function VarByName(Title:string):VarCl;
public
procedure Teach;
property IOType:smaiiint read ROType write FIOType;
procedure Calculate;
property NNetwork:NNetworkCh read FNeuraiNet write FNeuraiNet;
property SetOfData:TCIientDataSet read SetOfData write SetOfData;
property Description:TObjectList read FVariabieDescr write FVariabieDescr;
property
NNData:NeuralData
NeuralNetworkData;
end;
implementation
uses NeuralBaseTypes, DB, Math;
read
NeuralNetworkData
write
function Pace2(Pace:smallint):integer;
var hinteger;
begin
if Pace>0 then begin
Res := 2;
for j:=l to Pace-1 do Res := Res*2;
end else
Res := 1;
end;
{ VarCl }
function BinVar.GetDigPos: DigPos;
var ADigPos:DigPos;
j,mlt: integer;
begin
SetLength(ADigPos,NumOfBinaryDigits);
if VarVal > GetMax then raise Exception.Create('Чиcлo '+IntToStr(VarVal)+'
выходит границу.');
for j:=NumOfBinaryDigits-1 downto 0 do begin
mit := Pace2(j);
if (VarVal div mIt) > 0 then ADigPos[j] := 1
else ADigitPo$itions[j] := 0;
VarVal := VarVal mod mlt;
end;
Res := ADigPos;
end;
function BinVar.DigPosCount(AVal: integer): integer;
var fl:boolean;
j,t1,t2:integer;
begin
fl:=false;
j:=0;
while not fl do begin
t1 := race2(j);
t2 := race2(j+l);
if (AVal >= t1) and (AVal < t2) then fl:=true;
Inc(j);
end;
res :=j;
end;
function BinVar.GetMax: integer;
var j:integer;
begin
Res := Pace2(NumOfBinaryDigits);
end;
function NeuralVar.AsString: string;
var ADigPos:DigPos;
str:string;
j:integer;
begin
ADigPos:=GetDigPos;
str := "";
for j:=0 to Length(ADigPos)-1 do
str: = IntToStr(ADigPos[j])+str;
Res := str;
end;
procedure NeuralVar.Clear;
begin
VarVal := 0;
end;
function NeuralVar.GetVar: integer;
begin
Res := VarVal;
end;
procedure BinVar.SetDigPos(ADigPos: DigPos);
var j: integer;
begin
VarVal:=0;
for j:=0 to NumOfBinaryDigits-1 do
VarVal := VarVal + ADigPos[j]*Pace2(j);
end;
procedure NeuralVar.SetVar(FirstLayerVar: integer);
begin
VarVal := FirstLayerVar;
end;
function ConfigCl.AddInVar(FirstLayerVar: NeuralVar): integer;
begin
InVars.Add(FirstLayerVar);
end;
function ConfigCl.AddOutVar(FirstLayerVar: NeuralVar): integer;
begin
OutVars.Add(FirstLayerVar);
end;
procedure ConfigCl.Clear;
begin
InVars.Clear;
OutVars.Clear;
end;
procedure ConfigCl.ConfigureNN;
var counter:integer;
begin
NNetworkF.ResLayers;
NNetworkF.ResPatterns;
counter:= InNeurons;
NNetworkF.AddLayer(counter);
NNetworkF.AddLayer(counter);
counter:= OutNeurons;
NNetworkF.AddLayer(counter);
NNetworkF.Init;
end;
constructor ConfigCl.Create;
begin
InVars := TObjectList.Create;
OutVars := TObjectList.Create;
end;
function ConfigCl.BinInputs: integer;
var j,counter:integer;
begin
counter:=0;
for j:=0 to InVars.Count-1 do
counter:=counter+ NeuralVar(InVars[j]).NumOfBinaryDigits;
res := counter;
end;
function ConfigCl.BinOutputs: integer;
var j,counter: integer;
begin
counter:=0;
for j:=0 to OutVars.Count-1 do
counter:=counter+ NeuralVar(OutVars[j]).NumOfBinaryDigits;
res := counter;
end;
function NeuralData.InVarByName(Title: string): NeuralVar;
var j:integer;
begin
for j:=0 to InVars.Count-1 do
if AnsiUpperCase(NeuralVar(InVars[j]).Title) = AnsiUpperCase(Title) then
begin
Res := NeuralVar(InVars[j]);
break;
end;
end;
function NeuralData.OutVarByName(Title: string): NeuralVar;
var j:integer;
begin
for j:=0 to OutVars.Count-1 do
if AnsiUpperCase(NeuralVar(OutVars[j]).Title) = AnsiUpperCase(Title) then
begin Res := TNNVariabIe(OutVars[j]);
break;
end;
end;
procedure NeuralData.InsData;
var j,j,counter: integer;
xInVector: TVectorFloat;
xOutVector: TVectorFloat;
v:NeuralVar;
dp:DigPos;
begin
counter := InNeurons;
SetLength(xInVector, counter); counter:=0;
for j:=0 to InVars.Count-1 do begin
v := NeuralVar(InVars.Items[j]); dp:=v.GetDigPos;
for j:=0 to Length(dp)-1 do begin
xInputVector[counter] := dp[j]; counter:=counter+l;
end;
end;
counter := OutNeurons;
SetLength(xOutVector, counter);
counter:=O;
for j:=0 to OutVars.Count-1 do begin
v := NeuralVar(OutVars.Items[j]);
dp:=v.GetDigPos;
for j:=0 to Length(dp)-1 do begin
xOutVector[counter] := dp[j]; counter:=counter+l;
end;
end;
NNetworkF.AddPat(xInputVector,xOutVector);
end;
{ VarCl }
function VarCl.GetPoint: integer;
begin
Res
:=
Trunc(((LeftLimit
-
LeftEdge)/(RightEdge
-
LeftEdge)*AmountOfPoints));
end;
procedure VarCl.SetPoint(const Value: integer);
var len:extended;
begin
len := (RightEdge - LeftEdge)/AmountOfPoints;
LeftLimit := LeftEdge+len*(Value-1);
RightLimit := LeftEdge+len*Value;
end;
{ Mgr }
procedure Mgr.Calculate;
var tmp:VarCl;
counter,j,j,inNCount,outNCount:integer;
inN,outN :TVectorFloat;
dp:DigPos;
v:BinVar;
fieldname,outputVarName:string;
begin
if
not
Assigned(NNetworkF)
вычислительная сеть.');
then
raise
Exception.Create('Отсутствует
if not Assigned(SetOfData) then raise Exception.Create('Отсутствуют данные
для вычисления.');
if SetOfData.RecordCount=0 then raise Exception.Create('Отсутствуют данные
для вычисления.');
if
not
Assigned(NeuralNetworkData)
then
NeuralNetworkData
NeuralData.Create;
inNCount := NeuralNetworkData.InNeurons;
outNCount := NeuralNetworkData.OutNeurons;
SetLength(inN,inNCount);
SetLength(outN,outNCount);
SetOfData.First;
while not SetOfData.Eof do begin
for j:=0 to SetOfData.FieldCount-1 do begin
fieldname := SetOfData.Fields[j].FieldName;
if (fieldname <> 'NetDValue') then begin
tmp := VarByName(fieldname);
if tmp.InputVariable then begin
NeuralNetworkData.InVarByName(fieldname).Variable:=
SetOfData.FieidByName(fieldname).AsInteger;
end else outputVarName := fieldname;
end;
end;
counter:=0;
for j:=0 to NeuralNetworkData.InVars.Count-1 do begin
v := BinVar(NeuralNetworkData.InVars.Items[j]);
dp:=v.GetDigPos;
:=
for j:=0 to Length(dp)-1 do begin
inN[counter] := dp[j]; counter:=counter+l;
end;
end;
NNetworkF.COmpute(inN);
for j:=0 to outNCount-1 do outN[j] := NNetworkF.Output[j];
SetLength(dp,outNCount);
for j:=0 to outNCount-1 do
if outN[j] >= 0.5 then dp[j] := 1 else dp[j] := 0;
NeuralNetworkData.OutVarByName(outputVarName).SetDigPos(dp);
SetOfData.Edit;
SetOfData.FieldByName(outputVarName).AsInteger
NeuralNetworkData.OutVarByName(outputVarName).Variable;
SetOfData.Post;
SetOfData.Next;
end;
function Mgr.VarByName(Title:string): VarCl;
var j:integer;
begin
for j:=0 to DescOfVar.Count-1 do
if VarCl(DescOfVar[j]).Title = ANamethen begin
Res := VarCl(DescOfVar[j]);
break;
end;
end;
:=
procedure Mgr.Teach;
var cntInput,cntOutput,j:integer;
fieldname:string;
n:NeuralVar;
bin:BinVar;
c:CounterVar;
gray:GrayBinVar;
tmp:VarCl;
begin
if not Assigned(NNetworkF) then NNetworkF := NNetworkCh.Create(nil);
if not Assigned(SetOfData) then raise Exception.Create('Отсутствуют данные
для обучения.');
if SetOfData.RecordCount=0 then raise Exception.Create('Отсутствуют данные
для обучения.');
if not Assigned(DescOfVar) then raise Exception.Create('Отсутствует описание
данных для обучения.');
if
not
Assigned(NeuralNetworkData)
then
NeuralData.Create;
NeuralNetworkData.Clear;
NeuralNetworkData.NNetwork := NNetworkF;
for j:=0 to SetOfData.FieldCount-1 do begin
fieldname := SetOfData.Fields[j].FieldName;
tmp := VarByName(fieldname);
case FIOType of
1:begin
bin:=BinVar.Create;
n := bin;
NeuralNetworkData
:=
end;
2:begin
c:=CounterVar.Create;
n := c;
end;
3:begin
gray:=GrayBinVar.Create;
n := gray;
end;
end;
nnvar.Title := fieldname;
nnvar.NumOfBinaryDigits := nnvar.DigPosCount(tmp.PointCount-1);
if j < SetOfData.FieldCount-1 then begin
NeuralNetworkData.AddlnputVariable(nnvar);
end else begin
NeuralNetworkData.AddOutVar(nnvar);
end;
end;
NeuralNetworkData.ConfigureNN;
SetOfData.First;
while not SetOfData.Eof do begin
for j:=0 to SetOfData.FieldCount-1 do begin
fieldname := SetOfData.Fields[j].FieldName;
tmp := VarByName(fieldname);
if tmp.InputVariable then begin
NeuralNetworkData.InVarByName(fieldname).Variable:=
SetOfData.FieldByName(fieldname).AsInteger;
end else begin
NeuralNetworkData.OutVarByName(fieldname).Variable:=
SetOfData.FieldByName(fieldname).AsInteger;
end;
end;
NeuralNetworkData.InsData;
SetOfData.Next;
end;
NNetworkF.TeachOffLine;
end;
function ConfigCl.InNeurons: integer;
var counter,j:integer;
begin
counter:=0;
for j:=0 to InVars.Count-1 do begin
counter := counter + NeuralVar(InVars.Items[j]).NumOfBinaryDigits;
end;
Res := counter;
end;
function ConfigCl.OutNeurons: integer;
var counter,j:integer;
begin
counter:=0;
for j:=0 to OutVars.Count-1 do begin
counter := counter + NeuralVar(OutVars.Items[j]).NumOfBinaryDigits;
end;
Res := counter;
end;
{ CounterVar }
function CounterVar.GetDigPos: DigPos;
var PosOfDigits:DigPos;
j:integer;
begin
SetLength(PosOfDigits,NumberOfBinaryDigits);
for j:=0 to NumberOfBinaryDigits-1 do
if j <= VarVal-1 then PosOfDigits[j]:=1 else PosOfDigits[j]:=0;
Res:=PosOfDigits;
end;
function CounterVar.DigPosCount(
AVal: integer): integer;
begin
Res := AVal;
end;
function CounterVar.GetMax: integer;
begin
Res := NumberOfBinaryDigits;
end;
procedure CounterVar.SetDigPos(
ADigPos: DigPos);
var j:integer;
begin
inherited;
VarVal := NumberOfBinaryDigits;
for j:=0 to NumberOfBinaryDigits-1 do
if ADigPos[j]<l then begin
VarVal := j+1;
break;
end;
end;
{ GrayBinVar }
function GrayToBin(ADigPos:DigPos):DigPos;
var j,len:integer;
PosOfDigits:DigPos;
begin
len := Length(ADigPos);
SetLength(PosOfDigits,len);
PosOfDigits[len -1 ]:=ADigPos[ len-1 ];
for j:=len-2 downto 0 do begin
if ADigPos[j]=PosOfDigits[j+1] then PosOfDigits[j]:=0 else PosOfDigits[i] :=1;
end;
Res: = PosOfDigits;
end;
function BinToGray(ADigPos:DigPos):DigPos;
var j: integer;
PosOfDigits:DigPos;
begin
SetLength(PosOfDigits,Length(ADigPos));
SetLength(ADigPos,Length(ADigPos)+l);
ADigPos[High(ADigPos)]:=0;
for j:=High(ADigPos) downto 1 do begin
if ADigPos[j]=ADigPos[j-1] then PosOfDigits[j-1]:=0 else PosOfDigits[j-1]:=l;
end;
Res:=PosOfDigits;
end;
function GrayBinVar.GetDigPos: DigPos;
var ADigPos:DigPos;
j,mlt: integer;
str:string;
begin
SetLength(ADigPos,NumOfBinaryDigits);
if VarVal > GetMax then raise Exception.Create('Число '+ IntToStr(VarVal)+' не
входит в интервал.');
for j:=NumOfBinaryDigits-1 downto 0 do begin
mlt := Pace2(j);
if (VarVal div mlt) > 0 then ADigitPositionsfi] := 1 else PosOfDigits[i] := 0;
VarVal := VarVal mod mlt;
end;
try
Res := BinToGray(ADigPos);
except
for j:=0 to Length(ADigPos)-1 do
str:=IntToStr(ADigPos[j])+str;
raise Exception.Create(str);
end;
end;
function GrayBinVar.DigPosCount(
AVal: integer): integer;
var fl:boolean;
j,t1,t2:integer;
begin
fl:=false;
j:=0;
while not fl do begin
t1 := race2(j);
t2 := race2(j+l);
if (AVal >= t1) and (AVal < t2) then fl:=true;
Inc(j);
end;
res :=j;
end;
function GrayBinVar.GetMax: integer;
begin
Res := Pace2(NumOfBinaryDigits);
end;
procedure GrayBinVar.SetDigPos(
ADigPos: DigPos);
var PosOfDigits:DigPos;
j: integer;
begin
inherited;
PosOfDigits := GrayToBin(ADigPos);
VarVal:=O;
for j:=0 to NumOfBinaryDigits-1 do
VarVal := VarVal + PosOfDigits[j]*Pace2(j);
end;
end.
ИНФОРМАЦИОННО-ПОИСКОВАЯ ХАРАКТЕРИСТИКА
ДОКУМЕНТА НА ЭЛЕКТРОННОМ НОСИТЕЛЕ
Наименование
группы атрибутов
атрибута
1. Описание
Обозначение документа
документа
(идентификатор(ы)
файла(ов))
Наименование документа
2. Даты и время
3. Создатели
4. Внешние
ссылки
5. Защита
6. Характеристики
содержания
Характеристики документа
на электронном носителе
Плакаты
Демонстрационные плакаты
к выпускной
квалификационной работе
Класс документа
ЕСКД
Вид документа
Оригинал документа на
электронном носителе
Аннотация
Демонстрационный
материал, отображающий
основные этапы выполнения
выпускной
квалификационной работы
Использование документа Операционная система
Windows 7, Microsoft
PowerPoint 2010
Дата и время
13.06.2018
копирования документа
Дата создания документа 29.05.2018
Дата утверждения
06.06.2018
документа
Автор
Толпекин А.С.
Изготовитель
Толпекин А.С.
Ссылки на другие
Удостоверяющий лист
документы
№ 165165/п
Санкционирование
ОГУ имени И.С. Тургенева
Классификация защиты
По законодательству РФ
Объем информации
645120 Б
документа
7. Структура
документа(ов)
Наименование плаката №1
Наименование плаката №2
Наименование плаката №3
Наименование плаката №4
Наименование плаката №5
Наименование плаката №6
Наименование плаката №7
Наименование плаката №8
Наименование плаката №9
Наименование плаката №10
Наименование плаката №11
Наименование плаката №12
Титульный лист
Цель и задачи работы
Актуальность работы
Анализ возможностей
нейросетевых парадигм
Сравнение нейросетевых
парадигм, используемых
для прогнозирования
Диаграмма основных
классов библиотеки
Алгоритм обучения
нейросети
Алгоритм прямого
прохода сигнала
Исходные данные для
обучения
Точность модели
Результат предсказания
нейросети
Заключение
1/--страниц
Пожаловаться на содержимое документа