На правах рукописи

КУДУХОВ АЛАН НОДАРОВИЧ

РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ ИНТЕЛЛЕКТУАЛЬНОГО

КЭШИРОВАНИЯ ИНФОРМАЦИОННЫХ ОБЪЕКТОВ В СИСТЕМАХ

УПРАВЛЕНИЯ ПРОМЫШЛЕННЫМИ ПРЕДПРИЯТИЯМИ

Специальность: 05.13.01 – Системный анализ, управление

и обработка информации (промышленность)

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата технических наук

Владикавказ – 2014

Работа выполнена в ФГБОУ ВПО «Северо-Кавказский горно-металлургический институт (государственный технологический университет)»

Научный руководитель: доктор технических наук, профессор Кумаритов Алан Мелитонович

Официальные оппоненты: Ошхунов Муаед Музофарович, доктор технических наук, профессор ФГБОУ ВПО «Кабардино-балкарский государственный университет им. Х.М. Бербекова» (г.

Нальчик), профессор кафедры «Вычислительная математика»

Сапронов Павел Викторович, кандидат технических наук, Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В.А. Трапезникова Российской академии наук (г. Москва), научный сотрудник

Ведущая организация: ФГБОУ ВПО «Южно-Российский государственный политехнический университет (НПИ) имени М.И. Платова» (г. Новочеркасск)

Защита диссертации состоится «19» сентября 2014 г. в 1500 часов на заседании диссертационного совета Д212.246.01 при ФГБОУ ВПО «Северо-Кавказский горно-металлургический институт (государственный технологический университет)» по адресу: 362021, г. Владикавказ, ул. Николаева, 44, СКГМИ (ГТУ). Факс: (8672) 407-203. E-mail: [email protected].

С диссертацией можно ознакомиться в библиотеке и на сайте www.skgmigtu.ru ФБГОУ ВПО «СКГМИ (ГТУ)».

Автореферат разослан «10»июля 2014 г.

Ученый секретарь диссертационного совета Д 212.246.01 к.т.н., доцент А. Ю. Аликов.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. В настоящее время всё большую роль играют технологии обеспечивающие хранение, анализ и обработку данных. Это связано с наблюдаемым с конца прошлого века лавинообразным ростом информации, в том числе и в различных отраслях промышленности. Информационные системы промышленных предприятий представляют собой сложный комплекс взаимосвязанных компонентов, которые накапливают, обрабатывают и анализируют огромное количество разнородной технологической информации, создаваемой системами управления. Данные из этих систем являются критически важными для непосредственного управления производственными процессами и составляют необходимую базу для проведения анализа эффективности, расчета ключевых показателей производительности, определения узких производственных мест и решения других задач, требующих использования всего доступного объема производственной информации. Таким образом, промышленные предприятия это область больших данных (Big Data), где накапливаются и обрабатываются большие массивы данных.

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

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

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

­ уменьшение среднего значения времени ожидания пользователем запрошенных данных;

­ уменьшение нагрузки на локальные и глобальные сети за счет применения кэширования на локальных уровнях.

Данные обстоятельства делают актуальным теоретическое и практическое исследование способов и методов применения интеллектуальных алгоритмов замещения объектов в кэш-памяти для повышения эффективности функционирования информационных систем управления крупными промышленными предприятиями.

В настоящее время к разработке новых алгоритмов кэширования выражается очень большой интерес. Увеличению эффективности систем кэширования посвящены работы таких исследователей, как: Aho A.V., Denning P.J., Ullman J.D., Chen Y.C., Shedler G.S., Nilson R.A., Sharieh A., Belady L.A.,Coffinan E.G., Dasarathan D., Megiddo N., Modha D., Castro M., Adya A., Liskov В., Sabeghi M., Yaghmaee M.H., Subramanian R., Smaragdakis. Y.,Соколинский Л.Б., Кузнецов С.Д., Сущенко С.П. и других.

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

Поставленная цель потребовала решения следующих задач:

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

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

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

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

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

6. Разработка основных компонентов подсистемы кэширования для повышения эффективности функционирования информационных систем управления промышленными предприятиями.

Объект исследований – системы сбора, анализа и обработки данных информационных системы управления промышленными предприятиями.

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

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

Научная новизна диссертационной работы:

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

2. Предложен способ хранения объектов в кэш-памяти, позволяющий уменьшить время выполнения операций добавления, удаления и поиска информационных объектов в подсистеме кэширования;

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

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

Практическая значимость диссертационной работы:

1. На основе проведенного анализа существующих систем управления промышленными предприятиями и подсистем кэширования обозначены следующие приоритетные задачи: увеличение производительности функционирования интегрированных информационных систем за счет применения высокоуровневого интеллектуального кэширования информационных объектов; увеличение производительности основных алгоритмов подсистемы кэширования.

2. Спроектирована и разработана подсистема интеллектуального кэширования, позволяющая:

­ повысить эффективность функционирования информационных систем управления промышленными предприятиями;

­ снизить нагрузку на базу данных, за счет выполнения части запросов подсистемой кэширования;

­ увеличить пропускную способность каналов передачи данных по стандартным протоколам TCP/IP;

­ уменьшить время ожидания ответа на запросы, поступающие в информационную систему.

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

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

Обоснованность и достоверность научных положений, выводов и результатов исследований подтверждаются соответствием результатов теоретических исследований экспериментальным данным и внедрением разработанных методов и алгоритмов интеллектуального кэширования информационных объектов в системах управления Северо-Осетинского филиала ОАО «МРСК Северного Кавказа».

Апробация диссертационной работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на ежегодных НТК СКГМИ (ГТУ), научных семинарах кафедры информационных систем в экономике СКГМИ (ГТУ) (2011 – 2014 гг.),а также на еженедельном научно-исследовательском семинаре по математической физике и вычислительной математике ФГБОУ ВПО «Кабардино-балкарский государственный университет им. Х.М. Бербекова». Основные результаты диссертационной работы получили апробацию на следующих международных конференциях: Международная научно-техническая конференция «Наука, техника, инновации 2014», г.

Брянск 2014г., X студенческая международная заочная научно-практическая конференция «Молодежный научный форум: технические и математические науки», г. Москва 2014г.; Международная научно-практическая конференция «Приоритетные направления развития науки», г. Уфа 2014г.; XVIII Международная научно-практическая конференция «Перспективы развития информационных технологий», г. Новосибирск 2014г.; I Международная научно-практическая конференция «Проблемы и перспективы современной науки», г.

Ставрополь 2014г.; V Международная научно-практическая конференция «Молодые ученые в решении актуальных проблем науки», г. Владикавказ 2014г.; XI Международный симпозиум «Интеллектуальные системы», г.

Москва 2014г.

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

Публикации. По теме диссертации опубликовано 12 печатных работ, в т. ч. 2 работ в ведущих рецензируемых научных журналах и изданиях, определенных ВАК РФ для публикации основных научных результатов.

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Освободить память для Рисунок 1 – Стандартный алгоритм кэширования Функционирование стандартного алгоритма кэширования происходит по следующей схеме (рисунок 1): информационная система получает запрос на предоставление объекта, после чего перенаправляет данный запрос подсистеме кэширования. Подсистема кэширования определяет наличие соответствующего запросу объекта в кэш-памяти и, если он найден, возвращает его информационной системе, которая, в свою очередь, предоставляет его пользователю.

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

Проведенный анализ основных алгоритмов кэширования (LRU, SLRU LRU-K, LFU, NRO, FIFO, MRU, Size, PC) выявил следующие недостатки:

1. Вычисление кэш-рейтинга объекта на основе временной локальности или количества обращений, не учитывая другие важные характеристики 2. Кэширование объектов, размер которых не превосходит некоторый установленный параметр ;

3. Удаление актуальных объектов из кэш-памяти;

4. Сложность реализации некоторых алгоритмов кэширования.

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

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

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

Интеллектуальность алгоритма определяется количеством кэш-попаданий, т.е.

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

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

где Q – коэффициент, определяющий количество запросов обрабатываемых кэш-системой; S – количество запросов за определенное время; K – количество кэш-попаданий.

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

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

1. Временная локальность, которая описывается выражением:

где – время пассивности объекта, – текущее время, – определяет последнее время доступа к i-ому объекту.

2. Количество обращений к объекту, за определенный промежуток времени, которое описывается выражением:

где – суммарное количество обращений к i-ому объекту за определенный промежуток времени; –обращение к объекту.

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

где – время загрузки объекта из базы данных в кэш-память; – время окончания загрузки объекта; – время начала загрузки объекта.

Пусть – размер кэш-памяти, – общее число объектов в кэш-памяти ( ), – вероятность того, что полученный запрос относиться к кэш-памяти, – кэш-рейтинг объекта.

Тогда вероятность обращения к i-ому объекту можно определить следующим образом:

Таким образом, вероятности зависит также от кэш-рейтинга объекта. В идеале параметр должен стремиться к, [1 … ], где значение, зависящее от постановки задачи; – должен стремиться к, [1 … ], где – также зависит от постановки задачи; параметр – должен стремиться, [1 … ], где – максимально время загрузки объекта из базы данных в кэш-память, так как чем больше времени занимает загрузка, тем лучший рейтинг объекта.

Представим рейтинг объекта в виде суммы:

где 1, 2, 3 – нелинейные функции, причем должно выполнятся:

Тогда, идеальный кэш-рейтинг объекта можно представить в следующем виде:

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

где – выбранный параметр [,, ]; – минимальное значение;

– максимальное значение.

Тогда функцию вычисления кэш-рейтинга можно представить следующим образом:

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

Таким образом, не все параметры должны вкладывать одинаковый коэффициент значимости в выходное значение. Каждый параметр должен определить свой коэффициент значимости.

Тогда функцию (10), представим в следующем виде:

где,, – коэффициент значимости каждого параметра.

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

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

Структура разработанной нейронной сети представлена на рисунке 2.

Рисунок 2 – Нейронная сеть для вычисления коэффициентов значимости Входной слой нейронной сети, состоит из трех нейронов, так как кэш-рейтинг объекта характеризуется тремя параметрами [,, ], выходной слой также содержит три нейрона, которые отражающий результат произведенных вычислений. Процесс обучения проходит по способу «обучение без учителя», так как целевая функция неизвестна.

Алгоритмически процесс обучения представлен на рисунке3.