Содержание к диссертации
Введение
1. Анализ распределённых систем обработки данных 12
1.1. Анализ классификаций распределённых систем обработки данных 24
1.2. Анализ топологий распределённых систем обработки данных 38
1.3. Анализ основных подходов составления оптимальных расписаний выполнения программных модулей в распределённых системах обработки данных 43
Выводы 50
2. Применение эволюционного подхода для разработки моделей и алгоритмов составления оптимальных расписаний выполнения программных модулей в вычислительной сети 52
2.1. Постановка задачи диссертационного исследования 52
2.2. Разработка эволюционных моделей поиска оптимальных расписаний выполнения программных модулей в вычислительной сети
2.2.1. Разработка общей модели поиска оптимальных расписаний выполнения программных модулей в вычислительной сети 61
2.2.2. Разработка частных моделей поиска оптимальных расписаний выполнения программных модулей в вычислительной сети 73
2.3. Разработка модифицированных алгоритмов составления оптимальных расписаний выполнения программных модулей в вычислительной сети 76
2.3.1. Разработка модифицированного генетического алгоритма для коротких расписаний 76
2.3.2. Разработка модифицированного генетического алгоритма для длинных расписаний 80 Выводы 84
3. Оценка работоспособности и эффективности разработанных моделей и алгоритмов составления оптимальных расписаний выполнения программных модулей в вычислительной сети 86
3.1. Оценка работоспособности разработанных алгоритмов 86
3.1.1. Разработка стенда для проведения эксперимента по работоспособности алгоритмов 86
3.1.2. Подготовка исходных данных и проведение эксперимента 89
Выводы 96
3.2. Оценка эффективности разработанных алгоритмов 96
3.2.1. Обоснование критериев эффективности 98
3.2.2. Подготовка исходных данных и проведение эксперимента 102
3.2.3. Применение разработанного алгоритма при разработке стенда для отработки
программного обеспечения системы аварийной защиты двигателя 103
Выводы 109
Заключение 110
Список сокращений 113
Литература 114
- Анализ топологий распределённых систем обработки данных
- Анализ основных подходов составления оптимальных расписаний выполнения программных модулей в распределённых системах обработки данных
- Разработка частных моделей поиска оптимальных расписаний выполнения программных модулей в вычислительной сети
- Обоснование критериев эффективности
Введение к работе
Актуальность темы исследования. Уровень развития современных
технологий вызывает необходимость решения задач, требующих
высокопроизводительных вычислений, т.н. больших задач. В качестве некоторых примеров таких задач можно привести: имитационное моделирование в реальном времени, моделирование физико-химических и ядерных реакций, глобальных атмосферных процессов, процессов аэродинамики и др.
Существующие методы и технологии, применяемые для решения подобных задач, требуют соответствующих по эффективности вычислительных ресурсов и невыполнимы на рядовых персональных машинах.
Рост производительности современных ЭВМ, развитие сетевых
технологий и методов распределённой обработки информации, позволяют
проектировать на основе вычислительных сетей (локальных и глобальных)
распределённые системы обработки данных (РСОД), одним из аспектов области
применения которых является параллельное выполнение программ, реализующих
алгоритмы решения больших задач. Технология проведения таких вычислений в
РСОД заключается в декомпозиции прикладной программы и последующем
распределение её сегментов, представляющих программные модули различной
вычислительной сложности по максимально соответствующим узлам
вычислительной сети.
РСОД, в общем виде, представляет вычислительную сеть, ресурсы которой
посредством специализированного программного обеспечения (ПО)
предоставляются пользователю, как единый виртуальный ресурс с большой вычислительной мощностью. Класс РСОД включает в себя различные кластеры, распределенные среды, а также облачные сервисы, предоставляющие пулы виртуальных машин, работающих на разных серверах.
При решении больших задач в РСОД, целесообразным является их представление в виде комплекса информационно-зависимых задач (ИЗЗ). В свою очередь в вычислительной сети, на базе которой организована РСОД данный
комплекс ИЗЗ представляет совокупность программных модулей, над которыми выполняется процедура распределения для обеспечения их параллельного выполнения и сокращения времени решения большой задачи. Таким образом, происходит отображение логической структуры комплекса ИЗЗ в физическую.
Актуальность темы исследования связана с тем, что даже применение РСОД, не позволяет решать большие задачи в полном объеме. В связи с чем для эффективного использования вычислительных ресурсов РСОД необходимо обеспечить равномерную загрузку всех узлов, для чего при заданных свойствах комплекса ИЗЗ и вычислительной сети, а также наложенных на них ограничениях, требуется найти эффективный алгоритм упорядочения задач, т.е. поиск оптимальных расписаний выполнения программных модулей. Поэтому в последние годы отмечается все возрастающий интерес к теории расписаний. Рациональные расписания позволяют не только завершать выполнение параллельных частей задачи как можно раньше, но и обеспечивают максимальное использование реcурсов РСОД. Оценка расписания зависит от общего времени выполнения всех задач и общего времени незанятости узлов. Расписание с минимальной оценкой минимизирует время простоя, что в свою очередь приводит к эффективному использованию вычислительных ресурсов.
В связи с этим создание корректных и эффективных алгоритмов составления расписаний на сегодняшний день является актуальной задачей.
Данная область является объектом активных исследований, т.к. сложность структуры современных РСОД постоянно повышается, что приводит к многократно возрастающей сложности управления. Поэтому сегодня крайне важен поиск новых методов, алгоритмов и способов организации управления вычислительными ресурсами. Перед разработчиками стоит задача обеспечения максимально эффективного режима выполнения реальных приложений, задействующих все выделенные им ресурсы вычислительной сети.
С другой стороны, согласно проведенным исследованиям среди ученых, использующих в своей деятельности высокопроизводительные вычисления, все больше возрастает интерес к облачным сервисам, в которых для эффективного
применения виртуальных машин требуется разработка планировщиков, учитывающих топологию коммуникационной среды.
Стремление добиться большей производительности и
энергоэффективности РСОД, не меняя существующие модели программирования, требуют применения эффективных систем распараллеливания и планирования. В этой связи актуальной задачей на сегодняшний день остаётся синтез оптимального расписания выполнения программных модулей в вычислительной сети.
Цели и задачи. Целью диссертационной работы является разработка и исследование эволюционных моделей и алгоритмов составления расписаний выполнения программных модулей в вычислительной сети и повышения их эффективности для получения прироста производительности РСОД.
В соответствии с целью были поставлены следующие задачи:
- исследование существующих моделей и алгоритмов составления
оптимальных расписаний выполнения программных модулей в вычислительной
сети;
- разработка моделей и алгоритмов на основе эволюционного подхода,
позволяющих составлять оптимальное расписание выполнения программных
модулей в вычислительной сети, при котором суммарная продолжительность
обработки комплекса ИЗЗ будет минимальна.
Научная новизна результатов заключается в разработке теоретического
аппарата, включающего модели и алгоритмы составления расписаний
выполнения программных модулей в вычислительной сети на основе
эволюционного подхода, позволяющего находить более эффективные по
критерию минимального времени расписания выполнения заданий в
вычислительной сети по сравнению с существующими алгоритмами за счет повышения скорости вычислений и оптимизации построения структуры программного и информационного обеспечения для комплекса решаемых задач, учитывающей архитектуру РСОД.
Практическая значимость. Применение разработанного теоретического
аппарата в разработке моделирующего стенда в ОКР «Разработка
платформонезависимого программного обеспечения системы аварийной защиты двигателя 11Д58МФ» в виде методик синтеза оптимальной структуры программного обеспечения и моделирования доказало его эффективность в части, касающейся повышения производительности РСОД при решении больших задач. В связи с этим результаты диссертационной работы могут быть использованы как для разработки системного программного обеспечения РСОД реального времени специального назначения, так и для совершенствования структуры программного и информационного обеспечения существующих РСОД и технологий облачных вычислений.
Объектом исследования является распределенная система обработки данных, спроектированная на базе вычислительной сети.
Предметом исследования является программное и информационное обеспечение распределенной системы обработки данных.
Методы исследования. В качестве методов исследования использованы: методы системного подхода, методы исследования операций, методы теории расписаний, методы эволюционного поиска, методы теории планирования эксперимента, а также методы системного и прикладного программирования, методы объектно-ориентированного программирования для организации и проведения эксперимента.
Положения, выносимые на защиту.
1. Математические модели составления расписаний выполнения
программных модулей в вычислительной сети:
- общая математическая модель составления расписания выполнения
программных модулей в вычислительной сети;
- частные математические модели составления оптимальных расписаний
выполнения программных модулей в вычислительной сети по критерию
минимального времени для длинных и коротких расписаний.
-
Модифицированные генетические алгоритмы составления оптимальных расписаний выполнения программных модулей в вычислительной сети, учитывающие характеристики аппаратного обеспечения и параметры комплекса ИЗЗ.
-
Методика применения разработанного теоретического аппарата при проектировании структуры специального программного обеспечения моделирующего стенда в ОКР «Разработка платформонезависимого программного обеспечения системы аварийной защиты двигателя 11Д58МФ».
4. Программный комплекс «Анализатор генетических алгоритмов».
Достоверность научных результатов и выводов обусловлена
обоснованностью применения используемого математического аппарата, оценкой
адекватности разработанного теоретического аппарата результатам проведенного
эксперимента, а также успешным практическим использованием разработанных
математических, алгоритмических и программных средств при разработке
моделирующего стенда в ОКР «Разработка платформонезависимого
программного обеспечения системы аварийной защиты двигателя 11Д58МФ».
Внедрение результатов работы. Результаты, полученные в ходе
диссертационной работы, были использованы в разработках АО «ГосНИИП» при
выполнении ОКР «Разработка платформонезависимого программного
обеспечения системы аварийной защиты двигателя 11Д58МФ» в виде методик синтеза оптимальной структуры программного обеспечения моделирующего стенда, а также в учебном процессе РГСУ при проведении лекционных и лабораторных занятий по дисциплинам «Моделирование систем», «Системы искусственного интеллекта».
Апробация работы. Изложенные в диссертации результаты обсуждались на 7 международных и российских научных конференциях, в том числе на конференции молодых специалистов и аспирантов АО «ГосНИИП».
Публикации. По теме диссертации опубликовано 9 печатных работ (из них 4 – в изданиях из перечня ведущих рецензируемых научных журналов и изданий ВАК РФ).
Личный вклад автора заключается в разработке моделей и алгоритмов составления оптимальных расписаний выполнения программных модулей в вычислительной сети на основе эволюционного подхода, обосновании принципов работы этих алгоритмов, проектировании и реализации инструментальных средств для проведения вычислительного эксперимента, а также его планирование, проведение и интерпретация полученных результатов.
Структура и объем работы. Диссертация состоит из введения, трёх глав, заключения, списка литературы (109 наименований) и 3 приложений. Содержит 130 с. текста (из них 113 с. основного текста, 13 с. литературы и 4 с. приложений), включает 35 рисунков и 15 таблиц.
Анализ топологий распределённых систем обработки данных
Потребность проведения крупномасштабных вычислений в области тяжёлого моделирования и других областях науки и техники, а также развитие облачных технологий приводят к интенсивному развитию распределенных моделей предоставления вычислительных ресурсов [9], [10], [11]. Научно-технические достижения в области распределённой обработки данных и вычислительных сетей, позволяют проектировать РСОД, которые предоставляют платформу для решения прикладных задач очень высокого уровня сложности.
На сегодняшний день в научно-технической области, включающей разработку программно-аппаратных средств, для решения больших задач, широкое распространение получили кластеры. Кластер – представляет совокупность вычислительных узлов (ВУ) объединённых в локальную вычислительную сеть, для решения одной общей задачи. Узлы кластера не распределены территориально и каждый ВУ может включать один или несколько процессоров. По сравнению с другими типами РСОД, например распределёнными средами, кластер характеризуется повышенной надёжностью и детерминированностью конфигурации.
В качестве примеров применения кластеров для решения больших задач можно привести проведение расчетов полей течения вокруг компоновки перспективного пассажирского самолета на крейсерском режиме с моделированием работы двухконтурного турбореактивного двигателя, на кластере ТТИ ЮФУ описанного в работе [12]. Тенденция развития кластеров очевидна и подтверждается выводами, сделанными на основе анализа списка TOP-500, более половины представителей, которого составляют кластеры.
ТОП-500 – современный сервис, позволяющий отслеживать развитие кластеров и их производительность. Первая версия списка вышла в свет в 1993 году, его предназначение заключалось в иерархиризации области разработок высокопроизводительных систем с параллельной архитектурой. Причиной появления идеи создания списка стало возникновение потребности получения сравнительных характеристик таких систем. После построения первых экземпляров было решено продолжить ежегодное сравнение на основе разработанной методики.
Современная версия списка обновляется два раза в год в июне и ноябре. Построение списка выполняется на основе выполнения специальной тестовой программы, разработанной в Аргонской национальной лаборатории, которая называется LINPACK.
Тесты основаны на решении систем линейных алгебраических уравнений с помощью матричных методов. В 1986 году размерность матрицы увеличена до 1000 элементов в каждом измерении, а в 1991-1993 годах были выпущены версии позволяющие задавать произвольные размеры матриц (HPL - High-performance Linpack).
При выполнении данной программы ТОП-500 накладывает дополнительные ограничения, которые касаются размерности матриц (допускаются только большие размерности) и представления матричных элементов, элементы представляются только в 64-разрядном формате.
Благодаря списку ТОП-500 стало значительно легче владеть актуальной информацией о максимальной пиковой производительности, самых мощных на сегодняшний день кластеров. Россия в июньском списке 2016 года занимает 41, 109, 159, 348, 351, 489, 498 позиции.
Не смотря на то, что таблица отображает максимальную и пиковую производительность, стоит отметить, что при решении реальных задач достижение такой производительности является серьёзной проблемой.
В соответствии с данными приведёнными в Top 500 на сегодняшний день самый производительный кластер находится в Китае и называется Sunway Taihu Light (рисунок 1.1).
Sunway Taihu Light в тесте Linpack показывает производительность 93.014,6 TFLOPs, но теоретически его производительность может достигать 125.435,9 TFLOPs. Такая вычислительная мощность достигается благодаря специализированным процессорам, которые являются внутренней разработкой китайского центра National Research Center of Parallel Computer Engineering & Technology (NRCPC). В Sunway TaihuLight установлены процессоры ShenWei.
Процессор SW26010 содержит 260 ядер, один чип обеспечивает вычислительную производительность 3 TFLOPS. Кластер Sunway TaihuLight содержит 40960 узлов, каждый из узлов оснащен SW26010. 260 ядер на узел в сумме предоставляют 10649600 ядер. С вычислительной производительностью на чип 3 TFLOPS процессор SW26010 находится на одном уровне с вычислительными ускорителями Xeon Phi поколения Knights Landing [13].
Емкость оперативной памяти составляет 32 Гбайт на узел, то есть кластер оснащен, в общей сложности, 1,3 Петабайтами. Используется память DDR3. Частота ядер процессоров составляет 1,45 ГГц, каждое ядро может работать только с одним потоком. Пропускная способность каналов между узлами в Sunway Taihu Ligh составляет 16 Гбайт/с. При организации коммуникаций на основе MPI пропускная способность снижается до 12 Гбайт/с. Энергопотребление кластера Sunway TaihuLight составляет 15,3 МВт при нагрузке тестом Linpack.
Анализ основных подходов составления оптимальных расписаний выполнения программных модулей в распределённых системах обработки данных
Представим комплекс ИЗЗ в виде графа H = (U, Q). В этом графе задачи представлены в виде вершин U, а связи между ними, т.е. данные передаваемые от одной задачи к другой, в виде дуг Q. Структуру взаимодействия узлов в сети при выполнении комплекса ИЗЗ также можно представить в виде ориентированного ациклического графа G = (P, C), где множество P представляет собой набор узлов, которые выполняют задачи, а C набор ориентированных ребер, которые представляют коммуникационную среду и имеют веса, установленные в зависимости от оценки пропускной способности линии связи между двумя узлами. В процессе синтеза оптимального расписания происходит поиск оптимальной конфигурации взаимодействия сети для решения поставленной задачи, т.е. наложение графа представляющего комплекс ИЗЗ на графы, представляющие различные варианты взаимодействия узлов сети, таким образом, происходит отображение канонической структуры ИЗЗ в логическую [45]. Вариантов распределения ИЗЗ по узлам РСОД может быть очень много в зависимости от количества задач и узлов сети, поэтому задача приобретает NP-полноту и для её решения перспективной считается разработка приближённых методов и эвристических алгоритмов.
В РСОД ГА (в общем виде) представлен следующими операторами: оператор скрещивания (кроссинговер), оператор мутации, оператор отбора, а также функция пригодности (фитнес-функция). Алгоритм представляет собой цикл, проходящий стадии: создание начальной популяции, оценка функции пригодности, отбор наиболее приспособленных, скрещивание, мутация и селекция наиболее приспособленных особей (формирования новой популяции). Процесс повторяется в течение заданного отрезка времени. В результате чего эволюционируют расписания выполнения комплекса ИЗЗ.
В природе каждую особь однозначно идентифицируют хромосомы – наборы генов. Механизмы эволюции работают именно с генами, в эволюционной модели планирования хромосома представляет расписание выполнения задач, в таком случае гены представляют критерии, позволяющие установить порядок выполнения процессов на узлах, и с помощью которых возможно было бы дать объективную оценку расписания ориентированную на общее время завершения или простоя всех узлов. От эффективности кодирования хромосом зависит эффективность самого алгоритма. Методы кодирования классифицируются на косвенные (indirect encoding) и прямые (direct encoding). При прямом кодировании информация о расписании в хромосоме представлена в явном виде, например, матрицей смежности или списком связей, также при прямом кодировании порядок выполнения задач может быть жёстко привязан ко времени. Косвенное кодирование требует введения дополнительной информации для описания расписания, при использовании этого метода могут быть использованы специальные грамматики [46 стр. 39].
На сегодняшний день существует множество вариантов кодирования хромосом, основанных на различных критериях. В работе [39] гены содержат информацию о задачах и узлах, в работах [47] и [48] в каждый ген включено время запуска соответствующего процесса, а в [48] идентификаторы узлов выносятся в отдельный вектор для упрощения вычислений операторов и уменьшения размера хромосомы.
В данном описании применяется прямой метод кодирования, в котором каждому процессу (задаче) соответствует один слот расписания, в котором содержится идентификатор узла, выполняющего данный процесс, т.е хромосома представляет вектор из идентификаторов узлов, а фитнес-функция на основе этого вектора и дополнительной информации производит расчёт общего времени выполнения. Алгоритм не рассматривает такой критерий, как время запуска каждого процесса, а для однозначного представления порядка выполнения задач использует матрицу смежности. При таком способе кодирования размер хромосомы сокращается, что упрощает манипуляцию данными и повышает скорость алгоритма.
Спецификой ГА при распараллеливании (либо планировании) в РСОД является учёт временных затрат на передачу данных по линиям связи между узлами сети, поэтому алгоритм использует этот критерий. Реализация алгоритма может быть выполнена на языке С++, с применением библиотеки MPI [49],[50].
Рассмотрим задачу построения расписания в следующем варианте постановки. Дана вычислительная сеть, на которой вычисляется комплекс ИЗЗ. Сеть представляет гетерогенную среду, т.е. все ВУ работают с разными скоростями, а связи между узлами обладают разной пропускной способностью. С точки зрения начальных данных, которые известны до запуска алгоритма РСОД является детерминированной, т.е. нам известны производительность каждого узла сети, сложность выполнения каждой задачи (каждое задание, поступающее в систему планирования, имеет файл описания в формате MPI) и порядок их взаимодействия, а также пропускная способность линий связи. При распределении задач алгоритм ориентируется на эти данные.
В математической формулировке задача выглядит следующим образом. Дано множество задач U = {ui:i I}, где I = {i= } множество идентификаторов задач и множество узлов P = {pj: j J}, где J = {j= } множество идентификаторов узлов, тогда UP={ Sz: z ZUP} множество расписаний для U и P, где ZUP множество всех номеров расписаний, тогда расписание представляет множество Sz={ (pj): p P}, где (pj) слот расписания, представляющий процесс с идентификатором i, выполняющийся на узле с номером j. Требуется из множества расписаний UP найти такое расписание Sz, которое будет иметь минимальное время выполнения.
Первым шагом в процессе ГА является создание начальной популяции, для этого требуются информация о количестве процессов и узлов сети, и численности популяции. В нашей модели исходными данными для построения расписания и кодирования хромосом являются идентификаторы узлов и задач. В таком случае генами будут слоты (pj) расписания Sz, а хромосомой само расписание Sz . Номера узлов в слотах на этапе создания начальной популяции задаются случайным образом. Каждая особь содержит ровно одну копию каждой задачи, т. е. число слотов в хромосоме эквивалентно количеству ИЗЗ. Размер популяции задаётся параметром алгоритма и остаётся постоянным в процессе всей эволюции.
Разработка частных моделей поиска оптимальных расписаний выполнения программных модулей в вычислительной сети
При выборе стратегии распараллеливания ИЗЗ и принятии решения об использовании метода последовательного улучшения, происходит запуск алгоритма поиска оптимальной логической структуры комплекса ИЗЗ.
Т.к. данная задача обладает NP-полнотой, и её решение невозможно произвести при помощи полного перебора, целесообразным считается применение приближённых методов и эвристических алгоритмов, в том числе и на основе эволюционной модели.
ГА – это стохастические эвристические оптимизационные методы эволюционного моделирования, основанные на принципах естественного отбора. ГА используется в разных областях, где невозможно найти лучшее решение и требуется найти решение максимально приближенное к оптимальному [25]. Математическое описание и применение классического ГА в распределении программных модулей в вычислительной сети подробно рассмотрено в работах [39], [40]. В общем виде ГА представляет последовательность следующих шагов: 1)формирование популяции; 2)расчёт оценок для каждой особи (фитнес-функция); 3) стохастический отбор наиболее приспособленных особей; 4) скрещивание (кроссинговер); 5) мутация. Основные проблемы, которые возникают при применении и разработке программного обеспечения, использующего аппарат генетических алгоритмов, заключается в выборе: 1) функции приспособленности (фитнес-функции), т.е. применении в данной части, таких алгоритмов, которые ограничивают пространство поиска значениями, которые вероятно являются оптимальными решениями; 2) кодирование хромосом (существуют различные методы кодирования, которые обсуждаются в работе [25]). 3) входных параметров генетического алгоритма таких как: количество предков и потомков, частота мутаций и т.д. Данные параметры не должны препятствовать быстрому прохождению процедуры ранжирования особей по приспособленности и приводить к преждевременному схождению к неверному результату [55].
Проблема выбора фитнес-функции и кодирование хромосом тесно связаны между собой, т.к. чем меньше информации содержится в хромосоме, тем сложнее вычисления фитнес-функции и наоборот. Другой аспект проблемы - повышение требования к объёму оперативной памяти при использовании сложной кодировки хромосом.
При решении задачи построения логической структуры комплекса ИЗЗ в качестве «хромосомы» выступает расписание выполнения задач на узлах вычислительной сети. В данной работе выбрана максимально простая кодировка – каждый слот расписания соответствует одной задаче из канонической формы графа комплекса ИЗЗ и содержит идентификатор узла, на котором данная задача выполняется, таким образом, меняя идентификаторы узлов, задачи объединяются в различные ОМ и распределяются по вычислительной сети [4]. В части операторов ГА выбор был сделан в пользу классики, т.е применялись оператор отбора – "колесо рулетки" [56], одноточечный кроссинговер и простой оператор мутации, меняющий случайно выбранные гены местами.
При использовании простой кодировки возрастают вычисления производимые фитнес-функцией. Временные затраты связаны с поиском и обработкой матриц, описывающих каноническую форму графа ИЗЗ и структуру вычислительной сети, а также данных, содержащих информацию о весах задач и объёмах пересылаемых данных, производительности узлов и пропускной способности коммуникаций. В связи с тем, что распараллеливание программ в масштабе реального времени накладывает значительные временные ограничения, возникает необходимость в применении алгоритмов, поиска эффективных расписаний с повышенным быстродействием. Вследствие чего необходима их модификация.
Алгоритмы, предложенные ниже, направлены на ускорение вычислений производимых фитнес-функцией. Далее представлен алгоритм, оптимизирующий работу фитнес-функции.
Математическая формулировка классической фитнес-функции подробно описана в работе [31]. В общем виде фитнес-функция вычисляет время каждой задачи при ограничениях на порядок выполнения (задачи-приёмники не могут запускаться до выполнения соответствующих им задач-передатчиков) и освобождение узлов и коммуникаций, т.к. если узел или линия связи заняты процедура не может начать выполнение или передачу данных.
Определим множество расписаний в популяции размером n, как S={si: i I}, I={i: }, а каждое i-е расписание как si = { : j }, J={j: }, где m – количество задач в комплексе ИЗЗ, а xj – ген-слот, кодирующий задачу с идентификатором j . Обозначим фитнес-функцию как F(si), данная функция вычисляет время выполнения расписания si , а f( ) процедура функции F(si), обрабатывающая слот . Пусть Ti время выполнения расписания si , – время выполнения задачи с идентификатором j расписания si , а Tmin лучшая оценка для уже обработанных расписаний, тогда
Обоснование критериев эффективности
Платформонезависимое программное обеспечение системы аварийной защиты (ППОСАЗ) представляет собой набор математических функций, на основе которых разрабатывается рабочая программа системы аварийной защиты двигателя. Применение набора функций данного инструментального средства сокращает сложность и время разработки ПО для систем аварийной защиты (САЗ) двигателей. САЗ состоит из модулей микро-ПК к которым через аналого-цифровые преобразователи (АЦП) поступают сигналы от датчиков различного типа. Микро-ПК производит обработку полученных данных и в соответствии с алгоритмом управления выдаёт сигналы на исполняющие механизмы (ИМ).
В качестве микро-ПК могут применяться процессорные модули типа CPC307 производства компании Fastwel. CPC307 разработан для приложений, требующих использования х86 архитектуры центральных процессоров и подсистемы ввода вывода на базе CAN и COM портов. СРС307 соответствует спецификации PC/104-Plus, и совместим с большим количеством периферийных модулей и источников питания, выполненных в данном стандарте и поставляемых различными производителями.
Базируясь на однокристальном центральном процессоре х86 архитектуры Vortex 86SDX с частотой 600 МГц, адресацией к запаянной динамической памяти DDR2 256 Мбайт и широком наборе интерфейсов ввода-вывода, СРС307 предлагает разработчикам легкость программирования и использование операционных систем DOS, Linux и QNX.
Для загрузки операционной системы, CPC307 предлагает использование либо запаянного набортного флэш-диска с объемом 1Гбайт, либо использование сменных карт формата Micro Secure Digital (microSD), либо внешнего диска с интерфейсом IDE.
Устройство содержит два изолированных порта СAN 2.0 и широкий набор промышленных интерфейсов, таких как RS-232, RS-485, RS-422, USB и Fast Ethernet. СРС307 предлагает интегрированный функционал, получаемый при использовании нескольких продуктов различных производителей.
CPC307 потребляет на более 3,5 Ватт, не требует принудительного охлаждения, выпускается для эксплуатации в индустриальном -40...+85 С0 температурном диапазоне. Модификация СPC 307-05 - для эксплуатации в диапазоне -50...+90 С [64].
Количество датчиков и микро-ПК, а также их технические характеристики могут изменяться в зависимости от версии САЗ и от типа двигателя.
В процессе разработки платформонезависимого программного обеспечения САЗ необходимо его тестирование на стенде, моделирующем работу систем комплекса бортового оборудования (КБО) в реальном времени. Стенд представляет РСОД, организованную на базе локальной вычислительной сети предприятия. Все узлы в РСОД работают под управлением ОСРВ QNX 6.5.0. ОСРВ применяется в целях обеспечения необходимого времени реакции. QNX 6.5.0, основанная на микроядерной архитектуре [65], [66], [67], [68] характеризуется повышенным быстродействием. Особенности данной архитектуры обеспечивают реакцию системы в течение строго определённого периода времени [69], [70].
Коммуникационная среда РСОД организована на основе родного протокола QNX – QNET. Сеть QNET работает над протоколом IP и обеспечивает распределённую обработку данных. Сеть QNET представляет объединение сильносвязных машин, и обеспечивает запуск любого процесса на любом вычислительном узле сети [71], [72]. Структурная схема САЗ и моделирующего стенда представлена на рисунке 3.2.3.1. При работе в режиме моделирования входные параметры поступают в систему от центральных ПК, для чего ПО моделирующего стенда постоянно производит вычисления (в том числе матричные). Для своевременной выдачи управляющих сигналов возникла необходимость повышения эффективности вычислительного процесса на 10 %. Для получения прироста производительности необходимо распределённое выполнение данного процесса. В связи, с чем в систему включается планировщик, работающий на основе эвристических алгоритмов, который равномерно распределяет нагрузку между ВУ.
Т.к. данный планировщик работает в условиях сильно ограниченных временных ресурсов большинство известных эвристических алгоритмов не могут применяться для решения поставленной задачи. В связи с чем был разработан планировщик на основе модифицированного ГА.
Применение разработанного модифицированного ГА сократило время реакции системы и увеличило производительность на 13%, что обеспечило необходимую скорость вычислительного процесса.