Диссертация (Синтез оптимальной логической структуры распределенной базы данных с помощью параллельного нейросетевого алгоритма)

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

Нижний НовгородЗащита диссертации состоится « 27 » декабря 2012 года в 13 часов в ауд.1258 на заседании диссертационного совета Д 212.165.05 при Нижегородскомгосударственном техническом университете им. Р.Е. Алексеева по адресу:603600, г. Нижний Новгород, ул. Минина, 24.С диссертацией можно ознакомиться в библиотеке Нижегородскогогосударственного технического университета им.

Р.Е. АлексееваАвтореферат разослан « 26 » ноября 2012 года.Ученый секретарьдиссертационного советаСуркова Анна Сергеевна2ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫАктуальность темы. Активная деятельность по отысканию приемлемыхспособов обобществления непрерывно растущего объема информации привела ксозданию в начале 60-х годов ХХ века специальных программных комплексов,называемыхсистемамиуправлениябазамиданных(СУБД).Быстроераспространение сетей передачи данных, резкое увеличение объема внешнейпамяти ПК при ее удешевлении в 80-е годы способствовали широкомураспределенныхвнедрениюбазданных(РБД),являющихсясейчасдоминирующими инструментами для создания приложений интенсивнойобработки данных.

Появление в последние годы новых вычислительныхмоделей и моделей ИТ-инфраструктуры, известных как среды облачныхвычислений (Microsoft SQL Azure™ Database, Amazon Relational DatabaseService), приводит к необходимости по-новому ставить задачи проектирования,реализации и эксплуатации РБД. РБД функционируют сегодня в открытыхсистемахисистемахсистем.Следствиемэтогоявляетсябольшаянестабильность режимов работы, эволюция РБД во времени, неполнотаинформации для проектирования и оптимизации, большое число стейкхолдеровс различными целями и требованиями.В общей задаче проектирования РБД существенное значение имеетсоздание логической структуры (ЛС).

Входными данными задачи синтеза ЛСРБДявляютсяизначальныерезультатытребованиякконцептуальногофункционалупроектирования,системы,атакжезафиксированныевтехническом задании. ЛС не зависит от СУБД и является основой для этапафизического проектирования РБД.В современных условиях требуется отдельная программная подсистемадля проектирования, анализа и оптимизации ЛС на различных этапахжизненногооптимальнойциклаРБД.логическойТакаяподсистемаструктуры(ОЛС)должнаРБДвыполнятьилисинтезадаптироватьсуществующую структуру к изменившимся условиям с учетом распределеннойIТ-инфраструктуры и обладать возможностью останова на субоптимальных3решениях при дефиците вычислительных ресурсов или времени.

Основой такойподсистемы являются алгоритмы для решения задачи синтеза ОЛС поопределенному критерию эффективности.Одним из критериев, часто используемых на практике, является минимумобщеговременипоследовательнойобработкимножествазапросовпользователей. Его важность определяется тем, что в системах обработкиданных время является наиболее ценным ресурсом, а последовательнаяобработка запросов актуальна в системах со сложными бизнес-процессами,отдельные этапы которых выполняются различными пользователями.Задача синтеза ОЛС по указанному выше критерию принадлежит к классузадач дискретной оптимизации и является NP-трудной нелинейной задачейцелочисленного программирования. Все практически значимые методы решенияданных задач используют эвристики и основаны на интеллектуальном поиске вобширном, но ограниченном пространстве решений задачи.Наиболееизвестные методы решения задачи синтеза ОЛС РБДпредложены в ряде работ, изданных в конце XX века.

Аналитическую модельРБД рассматривали В.В. Кульба, А.Г. Мамиконов, А.А. Ашимов, В.В.Марасанов и др., методологию интеграции РБД – Б.П. Арсеньев. В.В. Кульба,С.С. Ковалевский и др. изложили методы упорядочения и оптимизации структурРБД на этапах предпроектного анализа, технического проектирования иэксплуатации, описали методы анализа и структуризации предметных областейпользователей и синтеза ОЛС РБД. В качестве метода синтеза ОЛС РБД здесьпредложен эвристический метод сокращенного обхода дерева поиска (ЭМСО).СтруктурнаяорганизацияЭМСОнепозволяетвыделитьдостаточноеколичество процедур, допускающих параллельную реализацию, для того, чтобыона была эффективной. Из-за сложных взаимосвязей большая часть временибудет затрачена на обмен данными.

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

Цегелика посвящен рассмотрению проблем оптимальногоразмещения объектов ЛС РБД по узлам вычислительной сети (ВС). Им былипредложены математические формулировки задач оптимального размещения сразличнымикритериямиэффективности.Однако,здесьструктурнаяорганизация таблиц ЛС РБД считается уже известной и принадлежит кмножеству входных данных задачи.Быстроебольшоеразвитиевниманиевычислительных технологий заставляетразработкеэффективныхмоделейуделятьпараллельныхвычислений, что для алгоритмов, подобных ЭМСО, связано с дополнительнымивременными затратами на изменение самой модели и структурной организацииалгоритма. Вопрос эффективности алгоритма можно рассматривать в двухаспектах: как уменьшение времени получения оптимального решения задачи врезультате полного прогона алгоритма, и как уменьшение времени решениязадачи за счет возможности останова на субоптимальном допустимом решении.Последний аспект относится к тем алгоритмам, которые обладают параметрами,способными повлиять на время решения задачи.

Эффективность существующихалгоритмов решения задачи синтеза ОЛС РБД может рассматриваться в рамкахпервого аспекта, в то время как вопрос эффективности алгоритмов, основанныхна методах искусственного интеллекта, покрывает оба аспекта.На данный момент в области проектирования ОЛС РБД существуетнедостаток эффективных алгоритмов синтеза ОЛС РБД или ее адаптации кизменившимся условиям. Это является стимулом к поиску новых практическихрешений, основанных на интеграции методов параллельных вычислений сметодами, использующими искусственные нейронные сети (ИНС/НС) и другиеметодыискусственногоинтеллектатакиеэволюционные алгоритмы (ЭА).5какгенетические(ГА)иДанная работа посвящена проблеме синтеза ОЛС РБД.

Для ее решенияпредложен параллельный нейросетевой алгоритм, построенный на основенейронных сетей Хопфилда (НСХ) с параллельным табу-поиском в качествемеханизма смены состояний сети.Цель диссертационной работы заключается в разработке и апробацииметода решения задачи синтеза ОЛС РБД с использованием критерия минимумаобщеговременипоследовательнойобработкимножествазапросовпользователей.

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

Апробацияразработанного алгоритма на модельных задачах.3. Проектирование и реализация механизма табу-поиска в рамкахпостроенногонейросетевогоалгоритмасцельюповышениякачестваполучаемых решений.4. Проектирование и реализация распределенной модели разработанногонейросетевого алгоритма с целью уменьшения его временной сложности.Тестирование алгоритма на модельных задачах.5. Апробация распределенного нейросетевого алгоритма на задачеоптимизации ЛС реальной БД, используемой в международной IT-компании.6Объектомисследованиясталиобъектылогическойструктурыоднородной распределенной базы данных и методы их формального описания.Предметом исследования являются алгоритмические методы синтезалогических структур распределенной базы данных на основе интеграцииметодов параллельных вычислений с методами икусственного интеллекта.В процессе выполнения работы использовались следующие методыпроведения исследований: при изучении и анализе структур РБД вдиссертации использовались элементы теории множеств и исследованияопераций, при построении алгоритмов синтеза ОЛС РБД – математическийаппарат ИНС, схемы ГА оптимизации с элементами теории вероятностей,методы эволюционного программирования и технологии табу-поиска.Реализация программного обеспечения была выполнена с использованиемязыковпрограммированияC++иMatlab,атакжебиблиотеквысокопроизводительных параллельных вычислений Microsoft HPC Pack 2008SDK и LAM/MPI.