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

3.1.1.1. Главное окно программы «Анализатор генетических алгоритмов»Исходные данные конфигурации вычислительной сети, графа комплексаИЗЗ и начальной популяции расписаний записываются в файл ConfigGA.ini. Нижепредставлен список секций и параметров файла.[NumTasks] – число задач[NumNodes] – число узлов{CharacteristicsTasks} – секция «характеристики задач» содержит секции{Task…}{Task… } – секция с параметрами для задачи с номером …[InteractionTasks] – зависимости задач[WeightTask] – вес задачи91[VolDate] – объем передаваемых данных[ProductivityNodes] – производительность узлов{WeightCommunications} – секция с параметрами линий связей узлов[Node…] – связи узла с идентификатором[SizePopulation] – размер популяции[PointCrossingover] – точка скрещивания[NumPointMutation] – число точек мутации[ChromosomeSchedule] – начальная популяция расписанийДля исключения ошибок, возникающих при вводе данных, и удобстваввода в программе, предусмотрен специальный интерфейс, который вызываетсяиз меню «Конфигурация»->«INI-файл» (рисунок 3.1.1.2).

При этом открываетсяокно «Инициализация», в котором производится ввод параметров.Рис. 3.1.1.2. Окно ввода параметровПосле ввода параметров активируется кнопка «Запуск ГА»(рисунок3.1.1.3), при нажатии на которую, программа производит поиск оптимальногорасписания, используя два алгоритма с классической фитнес-функцией имодифицированной. Соответствующие окна показывают времена выполнения92фитнес-функций и лучшие расписания на каждой итерации, а также графикиобщего времени выполнения каждой фитнес-функциии ,график, отображающийизменения значения лучшего расписания в процессе поиска.Рис.

3.1.1.3. Главное окно программы «Анализатор ГА» перед запуском3.1.2. Подготовка исходных данных и проведение экспериментаЦельэкспериментазаключаетсявполучениерезультатов,подтверждающих ускорение вычислений модифицированной фитнес-функции посравнению с классической при различном числе итераций.Результат эксперимента считается положительным при неснижающихсярезультатах поиска эффективных расписаний.Предполагается, что время работы фитнес-функции в процессе поискаоптимальной структуры будет экспоненциально сокращаться.93В качестве исходных данных при проведении эксперимента были введеныпараметры полносвязной гетерогенной сети и комплекса ИЗЗ со следующимиконфигурациями.Сеть состоит из трёх узлов (рисунок 3.1.2.1), которые имеют разныеоценки производительности, и межузловых связей, обладающих различнойпропускной способностью.ВыбранныйКаноническаякомплексформаориентированногоИЗЗИЗЗсостоитпредставленаациклическогографаизна[4],шестнадцатирисункев3.1.2.2процедур.ввидеконфигурационныйфайлпрограммы граф вводится в виде матрицы достижимости.

Ниже представлены всеисходные параметры вычислительной сети и комплекса ИЗЗ.Рис. 3.1.2.1. Структурная схема вычислительной сети94Рис. 3.1.2.2. Граф комплекса ИЗЗ и его матрица достижимости95Параметры вычислительной сети и комплекса ИЗЗ представлены втаблицах 3.1.2.1, 3.1.2.2, 3.1.2.3, 3.1.2.4. Таблица 3.1.2.5 содержит начальнуюпопуляцию расписаний из 20 особей.Таблица 3.1.2.1. Оценки производительности узловузел №1Оценкапроизводительности2узел №24узел №36№ узлаТаблица 3.1.2.2. Матрица весов межузловых коммуникаций№ узла123102622043640Таблица 3.1.2.3.

Веса процедур комплекса ИЗЗ№ процедуры 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16Вес процедуры 3 2 4 2 1 3 2 9 2 4 5 5 5 5 5 2Таблица 3.1.2.4. Веса передаваемых данныхСвязи процедур 1->5 1->6 2->5 2->7 3->7 4->8 5->9 5->13 6->10 6->13 7->11 8->12Вес передачи223344334452Связи процедур 9->13 10->13 10->14 11->14 11->15 12->15 13->16 14->16 15->16Вес передачи22233567696Таблица 3.1.2.5. Начальная популяция расписаний№особиСлоты расписания12 2 3 2 2 2 1 3 3 1 2 3 3 1 2 223 3 1 2 3 3 1 3 1 2 3 3 1 2 3 132 2 1 1 2 2 1 3 2 2 2 1 3 3 1 241 2 3 2 2 2 3 1 2 2 1 2 2 2 2 353 3 3 3 3 3 3 1 1 3 2 3 2 1 2 261 1 3 2 3 2 1 2 2 1 3 2 2 2 1 372 2 1 3 1 1 2 1 2 3 2 3 2 2 3 383 3 3 3 3 3 3 1 2 1 2 3 1 3 3 391 1 2 1 2 3 1 3 3 3 3 3 3 3 1 2102 3 2 3 2 3 2 2 3 2 1 2 2 1 3 2113 3 3 3 3 3 3 3 2 1 2 2 1 3 2 1121 3 1 2 1 2 1 3 3 3 3 3 3 2 1 2131 2 3 2 3 2 2 3 2 2 3 2 1 2 2 1143 2 2 3 3 3 2 3 3 3 3 3 3 2 1 2151 1 2 3 2 1 1 3 3 3 3 3 1 1 3 2162 3 1 2 1 2 2 3 2 3 2 2 3 2 2 3171 2 3 3 1 2 3 2 3 3 3 3 3 3 2 1181 1 2 3 1 3 1 2 1 2 1 3 3 3 3 3191 2 3 2 3 2 1 1 3 1 2 1 2 1 3 2203 3 2 3 2 3 3 2 3 2 1 1 3 1 2 1Далее представлены результаты эксперимента в таблицах и на графиках.9786848280Мx%7876747270010002000300040005000600070008000900010000Число итерацийРис.

3.1.2.3. График роста скорости модифицированной фитнес-функции поотношению к классическойТаблица 3.1.2.6. Результаты экспериментаКолвоитерацийСреднее времяработыфитнес-функцииклассическогоГА, мс101001000100000,352,441423СредняяСредняя оценкаСреднее времяоценкалучшей особиработылучшей особиГА сфитнес-функцииГА смодифицированмодифицированногоклассическойной фитнесГА, мсфитнесфункцией,*функцией, *0,0997880,688857,25848460,58484*оценки измеряются в условных квантах времени98Рис. 3.1.2.4.

График сходимости алгоритмов при 10 итерацияхРис. 3.1.2.5. График сходимости алгоритмов при 100 итерацияхРис. 3.1.2.6. График сходимости алгоритмов при 1000 итерациях99ВыводыПроведенный эксперимент доказывает, что при назначении расписаниямнеточных оценок, время работы алгоритма значительно сокращается, что невлияет на результаты поиска эффективных расписаний.Из таблицы 3.1.2.6 видно, что модифицированная фитнес-функциявыполняет вычисления значительно быстрее, чем классическая, а при небольшомчисле итераций ГА, применяющий описанный алгоритм с назначением неточныхоценок неэффективным расписаниям, находит решение наиболее близкое коптимальному.Недостаток разработанных алгоритмов заключается в большей склонностиГА, использующего модифицированную фитнес-функцию к ранней конвергенции(рисунки 3.1.2.4, 3.1.2.5, 3.1.2.6), что следует из графиков, отображающихсходимости алгоритмов.

Данный недостаток может устраняться попеременнымвключением алгоритмов. Также значительный прирост в скорости даётвозможность усиливать мутацию и кроссинговер.Предложенные алгоритмы могут применяться в РСОД, в которыхнахождениеэффективногорасписания,максимальноприближенногокоптимальному, требуется выполнить за минимально короткое время.3.2. Оценка эффективности разработанных алгоритмовМатричные вычисления фигурируют в процессах решения различныхнаучных вычислительных задач в таких областях как вычислительная математика,физика, экономика и др. [60].

Операции над матрицами широко используются вматематическом моделировании разнообразных процессов, явлений и систем.Т.к. матричные вычисления являются вычислительно-трудоемкими, онипредставляютсобойклассическуюобластьпримененияпараллельныхвычислений. С одной стороны, использование РСОД позволяет существенноповысить сложность решаемых задач. С другой стороны, в силу своей100достаточной наглядности и простоты формулировки операции над матрицамипредоставляют идеальную основу для демонстрации и анализа приемов, иметодов параллельного программирования [61].Специальные подходы к исследованию ряда задач, в частности, например,задач электродинамики на основе решения интегральных уравнений, опираютсяна работу с большими матрицами, генерация которых является основнымвычислительно емким местом.

В таких случаях очень часто помогает то, чтовычисление отдельных элементов матриц можно производить параллельно [1].В качестве наглядного примера задачи,длярешения которойприменяются операции над матрицами, можно привести обычную в физике или вмашиностроении задачу затухания, описанную Э. Таненбаумом в работе [24].Исходныезначенияпредставляютматрицу.Этизначенияпредставляюттемпературу в разных точках листа металла. Задача заключается в определениискорости распространения разогрева от пламени, воздействующего на один из егоуглов.Производитсяпреобразованиезаконам термодинамики, и полученияисходнойматрицысоответствующееисходной матрицы для ее следующейверсии, чтобы посмотреть все температурные показания через время ΔT.

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