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

применении вданной части, таких алгоритмов, которые ограничивают пространство поисказначениями, которые вероятно являются оптимальными решениями;2) кодирование хромосом (существуют различные методы кодирования,которые обсуждаются в работе [25]).3) входных параметров генетического алгоритма таких как: количествопредков и потомков, частота мутаций и т.д. Данные параметры не должныпрепятствовать быстрому прохождению процедуры ранжирования особей поприспособленности и приводить к преждевременному схождению к неверномурезультату [55].Проблема выбора фитнес-функции и кодирование хромосом тесно связанымежду собой, т.к.

чем меньше информации содержится в хромосоме, тем сложнеевычисления фитнес-функции и наоборот. Другой аспект проблемы - повышениетребования к объёму оперативной памяти при использовании сложной кодировкихромосом.При решении задачи построения логической структуры комплекса ИЗЗ вкачестве «хромосомы» выступает расписание выполнения задач на узлахвычислительной сети.

В данной работе выбрана максимально простая кодировка –каждый слот расписания соответствует одной задаче из канонической формыграфа комплекса ИЗЗ и содержит идентификатор узла, на котором данная задачавыполняется, таким образом, меняя идентификаторы узлов, задачи объединяютсяв различные ОМ и распределяются по вычислительной сети [4]. В частиоператоров ГА выбор был сделан в пользу классики, т.е применялись операторотбора – "колесо рулетки" [56], одноточечный кроссинговер и простой оператормутации, меняющий случайно выбранные гены местами.Прииспользованиипростойкодировкивозрастаютвычисленияпроизводимые фитнес-функцией.

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

Далее представлен алгоритм, оптимизирующийработу фитнес-функции.Определим множество расписаний в популяции размером n, как̅̅̅̅̅S={si: i∈I}, I={i:0,n},̅̅̅̅̅а каждое i-е расписание, как si = { : j∈ J }, J={j:0,m}, где m – количествозадач в комплексе ИЗЗ, а xj – ген-слот, кодирующий задачу с идентификатором j .Обозначим фитнес-функцию как F(si), данная функция вычисляет времявыполнения расписания si , а f( ) процедура функции F(si), обрабатывающая слот .Пусть Ti время выполнения расписания si , – время выполнения задачи сидентификатором j расписания si , а Tmin минимальное время выполнения для ужеобработанных расписаний, тогда = f( ).(2.3.1.1)Тогда функцию F(si) можно записать какF( , +1… −1, ) ->F(f( ) f(+1)… f(−1) f()) ,(2.3.1.2)а время выполнения расписания siTi= F(f( ) f(+1)… f(−1) f()) .(2.3.1.3)82Блок-схема на рисунке 2.3.1.1 представляет алгоритм выполнениямодифицированной фитнес-функции.Рис.

2.3.1.1. Алгоритм выполнения модифицированной фитнес-функции83Несмотрянадополнительныеоперациисравнения,происходитуменьшение времени работы фитнес-функции за счёт сокращения вычисленийвремени выполнения задач. В процессе реализации алгоритм предполагаетсяразделять на потоки с помещением переменной Тmin в общую память.Величина назначаемой неточной оценки вопрос, требующий отдельногорассмотрения.

Т.к. назначение нулевых оценок не позволяет попадать менееэффективным расписаниям в следующие популяции, что может приводить кпреждевременнойсходимости[57],[58].Впроведённомисследованиинеэффективным расписаниям назначается минимальная ненулевая оценка, чтоувеличивает вероятность отбора данных расписаний и сохраняет стохастичностьГА, также при назначении неточных оценок могут быть введены дополнительныеоперации с использованием процентной шкалы и смещением точки стартаалгоритма.2.3.2.

Разработка модифицированного генетического алгоритма длядлинных расписанийАлгоритм, предложенный в предыдущем разделе, предназначен дляобработки сравнительно коротких расписаний. В связи с чем был разработаналгоритм, предназначенный для обработки расписаний большой размерности.При использовании данного алгоритма расписание разбивается нанесколько участков, число участков зависит от конкретной длины расписания изадаётся в параметрах алгоритма.Каждый участок обрабатывается в своём цикле, и операция сравненияпроизводится на последней итерации, за счёт чего происходит сокращениеопераций сравнения. Блок-схема алгоритма для отдельного участка расписанияпоказана на рисунке 2.3.2.1.84Рис 2.3.2.1. Блок-схема алгоритма фитнес-функции для обработки расписаний большойразмерности85Далее представлен материал, который имеет отношение к практическойреализации алгоритма. Он носит информативный характер и основан на личныхотметках и наблюдениях автора, сделанных при реализации модифицированногоалгоритмаввидемногопоточногоприложения,выполняющегосянамногоядерных вычислительных устройствах под управлением операционнойсистемы реального времени QNX.Существует несколько способов распараллеливания фитнес-функции.

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

связей которые содержат в себе больше двух узлов.При наличии данных связей может возникнуть ситуация, которую можнопредставить, глядя на рисунок 2.3.2.2, когда передача между задачами 1->4использует связь, которая является транзитной для передачи 12->15. Далеепредставим,чтоиз-заспецификирасписания,трудоёмкостизадачигетерогенности сети в определённый момент времени возникает ситуация, когдазадача 12 готова к передаче данных для задачи 15, а задача 1 в данное время всёещё выполняется. В таком случае при параллельном расчёте общего временивыполнения по ярусам на первом этапе параллельно будут вычисляться задачи 1,2, 3, далее 4, 5, 6, далее 7, 8, 9 и 10, 11, 12 при расчёте времени передачи от задачи12 к задаче 15 окажется, что время начала передачи меньше, чем времявыполнения задачи 1.

Вышеописанная ситуация приведёт к пересчёту всейпоследовательности, начиная с 4 задачи, и для её исключения, придется вводитьдополнительные циклы и стеки, что нецелесообразно.Отсюда следует вывод, что данный участок кода лучше проходитьпоследовательно.86Рис. 2.3.2.2. Пример вычислений фитнес-функцииВ том случае, если число узлов больше чем расписаний в популяции дляисключения простоев целесообразно будет увеличить популяцию в соответствиис законом симметричности распараллеливания, который представлен ниже.Представим задачу, состоящую из нескольких одинаковых потоков, назовёмих родительскими, каждый из этих потоков порождает некоторое количествоодинаковых т.н. дочерних потоков, если число родительских и дочерних потоковравно, а количество ядер (узлов) равно или меньше, то распараллеливание, либопо родительским потокам, либо по дочерним даст одинаковый прирост (рисунок2.3.2.3).87Рис.

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

При проведениивычислений,модифицированнаяфитнес-функцияназначаетрасписаниямнеточные оценки, за счёт чего происходит уменьшение времени её выполнения.Для расписаний различной длины предлагается применять два различных типа88алгоритмов. Приведенные в конце главы предложения по распараллеливаниювычислительного процесса фитнес-функции, могут учитываться при применениипредложенных алгоритмов на практике.Алгоритмы могут применяться, как при распараллеливании программ,предназначенныхдлявыполнениявРСОД,планировщиков, работающих в облачных сервисах.такиприразработках893. Оценка работоспособности и эффективности разработанных моделей иалгоритмов составления оптимальных расписаний выполненияпрограммных модулей в вычислительной сети3.1. Оценка работоспособности разработанных алгоритмов3.1.1.Разработкастендадляпроведенияэкспериментапоработоспособности алгоритмовДля исследования эффективности модифицированного алгоритма посравнению с классическим был разработан стенд, который состоит изперсонального компьютера (ПК) под управлением 32-разрядной Windows7 ипрограммы«Анализаторгенетическихалгоритмов».ХарактеристикиПКпредставлены в таблице 3.1.1.1 .Таблица 3.1.1.1.

Характеристики ПКПроцессорОЗУAMD Athlon(tm)NeoProcessor MV-40 1,60 GHz2,00 ГбПрограмма реализована на языке С++/CLI, являющемся расширениемязыка С++, в среде VisualStudio 2008 выбор языка и среды обусловленвозможностью в пределах одного программного кода разделить данные науправляемые и неуправляемые, и сделать свою программу более эффективной,поскольку неуправляемые системой данные быстрее обрабатываются, и ихсуществование определяется только программистом, а не сборщиком мусора [59].Стенд позволяет задавать различные конфигурации вычислительной сети икомплекса ИЗЗ, и на основе этих данных получать времена выполненияклассической и модифицированной фитнес-функций, оценки лучших особей накаждой итерации, а также отображает на графиках общее время работы фитнесфункций, и изменение значения лучшего расписания в процессе поиска.90Выходные данные операторов ГА и всех созданных популяций каждогоалгоритма,сохраняютсявфайлеGen_Al.txt,чтодаётвозможностьпроанализировать результаты работы каждого оператора.Главное окно программы представлено на рисунке 3.1.1.1.Рис.