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

Федеральное государственное бюджетное образовательноеучреждение высшего образования«РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ СОЦИАЛЬНЫЙ УНИВЕРСИТЕТ»Факультет информационных технологий и техносферной безопасностиНа правах рукописиУральский Николай БорисовичРазработка моделей и алгоритмов составления оптимальных расписанийвыполнения программных модулей в вычислительной сетина основе эволюционного подходаспециальность 05.13.11 Математическое программное обеспечениевычислительных машин, комплексов и компьютерных сетейДиссертацияна соискание учёной степеникандидата технических наукНаучный руководитель:профессор, д.т.н.

В.А. СизовМОСКВА 20172ОглавлениеВведение ...................................................................................................................................................41. Анализ распределённых систем обработки данных ......................................................................121.1. Анализ классификаций распределённых систем обработки данных ...................................

241.2. Анализ топологий распределённых систем обработки данных ............................................ 381.3. Анализ основных подходов составления оптимальных расписаний выполненияпрограммных модулей в распределённых системах обработки данных .................................... 43Выводы ..............................................................................................................................................

502. Применение эволюционного подхода для разработки моделей и алгоритмов составленияоптимальных расписаний выполнения программных модулей в вычислительной сети ...............522.1. Постановка задачи диссертационного исследования ............................................................ 522.2. Разработка эволюционных моделей поиска оптимальных расписаний выполненияпрограммных модулей в вычислительной сети ............................................................................. 612.2.1.

Разработка общей модели поиска оптимальных расписаний выполнения программныхмодулей в вычислительной сети ......................................................................................................... 612.2.2. Разработка частных моделей поиска оптимальных расписаний выполнения программныхмодулей в вычислительной сети ......................................................................................................... 762.3. Разработка модифицированных алгоритмов составления оптимальных расписанийвыполнения программных модулей в вычислительной сети .......................................................

792.3.1. Разработка модифицированного генетического алгоритма для коротких расписаний ...... 792.3.2. Разработка модифицированного генетического алгоритма для длинных расписаний ....... 83Выводы .............................................................................................................................................. 873. Оценка работоспособности и эффективности разработанных моделей и алгоритмовсоставления оптимальных расписаний выполнения программных модулей в вычислительнойсети .........................................................................................................................................................893.1.

Оценка работоспособности разработанных алгоритмов ....................................................... 893.1.1. Разработка стенда для проведения эксперимента по работоспособности алгоритмов ....... 893.1.2. Подготовка исходных данных и проведение эксперимента .................................................. 92Выводы .................................................................................................................................................. 993.2. Оценка эффективности разработанных алгоритмов .............................................................. 993.2.1.

Обоснование критериев эффективности ................................................................................ 1013.2.2. Подготовка исходных данных и проведение эксперимента ................................................ 10533.2.3. Применение разработанного алгоритма при разработке стенда для отработкипрограммного обеспечения системы аварийной защиты двигателя ............................................. 107Выводы ................................................................................................................................................

113Заключение ..........................................................................................................................................114Список сокращений ............................................................................................................................117Литература ...........................................................................................................................................118Приложение А (обязательное). ..........................................................................................................131Свидетельство о регистрации программы ........................................................................................131«Анализатор генетических алгоритмов» ..........................................................................................131Приложение Б (обязательное).

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

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

Для проведенияодного численного эксперимента с моделью атмосферы необходимо выполнитьпорядка 1016 – 1017 арифметических операций с плавающей запятой. Такимобразом, даже при выполнении 1012 операций в секунду вычисления будутпроизводиться несколько часов.

Использование полной климатической моделиувеличивает это время на порядок. Еще на порядок увеличивается время за счетнеэффективного программирования и накладных расходов при компиляциипрограмм и т. д. На практике подобных больших задач очень много. К этомуклассуможноотнестимногиезадачи,возникающиевкриптографии,комбинаторные задачи или задачи проектирования новых лекарственныхпрепаратов [1] и исследования обтекания летательных аппаратов [2].РостпроизводительностисовременныхЭВМ,развитиесетевыхтехнологий и методов распределённой обработки информации, позволяют5проектировать на основе вычислительных сетей (локальных и глобальных)распределённые системы обработки данных (РСОД). Одним из аспектов областиприменения РСОД является параллельное выполнение программ, реализующихалгоритмы решения больших задач.

Технология проведения таких вычислений вРСОД заключается в декомпозиции прикладной программы и последующемраспределение её сегментов, представляющих программные модули различнойвычислительнойсложностипомаксимальносоответствующимузламвычислительной сети.РСОД, в общем виде, представляет вычислительную сеть, ресурсы которойпосредствомспециализированногопрограммногообеспечения(ПО)предоставляются пользователю, как единый виртуальный ресурс с большойвычислительной мощностью [3].При решении больших задач в РСОД, целесообразным является ихпредставление в виде комплекса информационно-зависимых задач (ИЗЗ) [4]. Всвою очередь в вычислительной сети, на базе которой организована РСОД,данный комплекс ИЗЗ представляет совокупность программных модулей, надкоторымивыполняетсяпроцедурараспределениядляобеспеченияихпараллельного выполнения и сокращения времени решения большой задачи.Таким образом, происходит отображение логической структуры комплекса ИЗЗ вфизическую [4].Следует отметить, что термины распределённая и параллельная обработка(распределениеираспараллеливание)неявляютсяравнозначными,т.к.распределение означает размещение программных сегментов ПО в соответствиисо спецификой аппаратно-программного обеспечения узлов вычислительной сетидля эффективного использования её ресурсов.

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

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