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

Существуютнесколько вариантов такого оператора (селекция методом рулетки, турнирныйметод, ранговый метод и др.). Все генетические операторы классического ГАоснованы на вероятностном подходе.Для сравнения решений применяются значения, полученные с помощьюфункции пригодности. Наиболее употребляемые названия для термина «функцияпригодности»: фитнесс-функция, функция приспособленности, целевая функция,функция оценки, стоимостная функция. Для различных предметных областейприходитсяпригодности,подбиратьсоответствующуюпозволяющуюоднозначнопоэффективностиустановить,чтофункциюоднорешениеэффективнее, чем другое [44].ВыводыПроведённый анализ существующих научных решений в областипостроения РСОД показывает, что в настоящее время недостаточно развитыгибкие подходы проектирования структуры программного и информационногообеспечения РСОД, построенных на базе вычислительных сетей.

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

для получения максимальногоэффектаотраспараллеливанияпрограммыособенности системной архитектуры [33].необходимоучитыватьвсе522. Применение эволюционного подхода для разработки моделей иалгоритмов составления оптимальных расписаний выполненияпрограммных модулей в вычислительной сети2.1. Постановка задачи диссертационного исследованияПоиск оптимальных расписаний выполнения программных модулейпроизводится с целью их эффективного распределения по узлам вычислительнойсети, в соответствии с её конфигурацией и спецификой алгоритма параллельнойпрограммы,длясокращениявременивыполнениякомплексаИЗЗ,представляющего большую задачу (рисунок 2.1.1).Рис. 2.1.1.

Технология решения большой задачи в РСОДПредставим комплекс ИЗЗ в виде графа H = (U, Q). В этом графе задачипредставлены в виде вершин U, а связи между ними, т.е. данные передаваемые отодной задачи к другой, в виде дуг Q. Структуру взаимодействия узлов в сети привыполнении комплекса ИЗЗ также можно представить в виде ориентированного53ациклического графа G = (P, C), где множество P представляет собой набор узлов,которые выполняют задачи, а C набор ориентированных ребер, которыепредставляют коммуникационную среду и имеют веса, установленные взависимости от оценки пропускной способности каналов связи между двумяузлами. В процессе синтеза оптимального расписания происходит поископтимальной конфигурации взаимодействия сети для решения поставленнойзадачи, т.е.

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

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

От эффективности кодирования хромосом зависитэффективность самого алгоритма.54Методы кодирования классифицируются на косвенные (indirect encoding) ипрямые (direct encoding). При прямом кодировании информация о расписании вхромосоме представлена в явном виде, например, матрицей смежности илисписком связей, также при прямом кодировании порядок выполнения задач можетбыть жёстко привязан ко времени. Косвенное кодирование требует введениядополнительной информации для описания расписания, при использовании этогометода могут быть использованы специальные грамматики [46 стр. 39].На сегодняшний день существует множество вариантов кодированияхромосом, основанных на различных критериях. В работе [39] гены содержатинформацию о задачах и узлах, в работах [47] и [48] в каждый ген включеновремя запуска соответствующего процесса, а в [48] идентификаторы узловвыносятся в отдельный вектор для упрощения вычислений операторов иуменьшения размера хромосомы.В данном описании применяется прямой метод кодирования, в которомкаждому процессу (задаче) соответствует один слот расписания, в которомсодержится идентификатор узла, выполняющего данный процесс, т.е хромосомапредставляет вектор из идентификаторов узлов, а фитнес-функция на основеэтого вектора и дополнительной информации производит расчёт общего временивыполнения.

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

Реализация алгоритмаможет быть выполнена на языке С++, с применением библиотеки MPI [49], [50].Рассмотрим задачу построения расписания в следующем вариантепостановки. Дана вычислительная сеть, на которой вычисляется комплекс ИЗЗ.Сеть представляет гетерогенную среду, т.е. все ВУ работают с разными55скоростями, а связи между узлами обладают разной пропускной способностью.

Сточки зрения начальных данных, которые известны до запуска алгоритма РСОДявляется детерминированной, т.е. нам известны производительность каждого узласети, сложность выполнения каждой задачи (каждое задание, поступающее всистему планирования, имеет файл описания в формате MPI) и порядок ихвзаимодействия,атакжепропускнаяспособностьлинийсвязи.Прираспределении задач алгоритм ориентируется на эти данные.В математической формулировке задача выглядит следующим образом.Дано множество задач U = {ui:i∈ I}, где I = {i= ̅̅̅̅̅0, n} множество идентификаторовзадач и множество узлов P = {pj: j ∈ J}, где J = {j= ̅̅̅̅0, } множествоидентификаторов узлов, тогда ŜUP={ Sz: z∈ZUP} множество расписаний для U и P,где ZUP множество всех номеров расписаний, тогда расписание представляетмножество Sz={ (pj): p∈P}, где (pj) слот расписания, представляющий процессс идентификатором i, выполняющийся на узле с номером j.

Требуется измножества расписаний Ŝ UP найти такое расписание Sz, которое будет иметьминимальное время выполнения.Первым шагом в процессе ГА является создание начальной популяции, дляэтого требуются информация о количестве процессов и узлов сети, и численностипопуляции. В нашей модели исходными данными для построения расписания икодирования хромосом являются идентификаторы узлов и задач. В таком случаегенами будут слоты (pj) расписания Sz, а хромосомой само расписание Sz .Номера узлов в слотах на этапе создания начальной популяции задаютсяслучайным образом.

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

В различных реализациях эта функция56работает с разным количеством критериев. Следует отметить, что чем большеинформации содержит хромосома, тем проще работа фитнес-функции, нобольшой размер хромосом в крупномасштабных РСОД повышает требования кобъёму оперативной памяти, а также влечёт за собой введение дополнительныхоператоров, что замедляет работу алгоритма. В представленном алгоритмехромосомы не содержат избыточной информации, в результате чего усложняетсяработафитнес-функции,ноуменьшаетсяобъемпамятизанимаемыйхромосомами, и упрощается работа кроссинговера и оператора мутации. Помимоданных, которые содержат хромосомы, фитнес-функция в приведенном алгоритмеиспользует такие критерии, как информация о длительности выполнения задач ивремя передачи данных по линиям связи, а также данные о взаимодействии задач.Рассмотрим подробнее эти критерии.Все задачи имеют разную степень сложности и поступают в системусинтеза оптимальных расписаний с уже заданными весами – оценками сложности.ПроизводительностиВУтакжеразличны,т.к.рассматриваемаяРСОДгетерогенная, таким образом, время выполнения задач на разных узлах различно ипредставляет результаты деления сложности задачи на производительность узла(более точный метод представления длительностей описан в [48 стр.15]), этиданные использует фитнес-функция при оценке расписания.Пусть M множество оценок сложности задач, тогда MU = {mi: i= ̅̅̅̅̅1, n }множество оценок сложности набора задач U, где mi оценка сложности задачи сидентификатором i.

Пусть множеством πP= { j:j= ̅̅̅̅0, } представленыпроизводительности узлов множества P, где j производительность j-го узла.Представим множеством T длительности выполнения соответствующих задач,тогда элемент множества tij =mijпредставляет длительность выполнения i-ойзадачи на j-ом узле.Следующимважныммоментомявляютсяограничения,отихбыстродействия и эффективности зависит эффективность алгоритма в целом, внашем случае ограничение заключается в соблюдение приоритетности процессов57в соответствии с графом отображающем порядок выполнения задач, это означаетчто задачи-приёмники (реципие́нты) не могут запускаться, пока задачипередатчики (доноры) не закончат выполнение и передачу данных.В работе [48] для однозначного представления порядка выполнения задачиспользуется время запуска процессов, что влечёт за собой дальнейшуюкорректировку генов с целью сохранения непротиворечивости расписания, итребует введения дополнительных операторов (гармонизации и др.), т.к.описываемый алгоритм не использует этот критерий, представим порядоквыполнения работ множеством Q = {qkr : k∈K; r∈R }, где K ⊂ I , R ⊂ I и K ∩ R,которое представляет взаимодействие программных модулей между собой, т.е.передачуданныхмеждузадачами.Этомножествоотображаетграфпредставляющий структуру комплекса ИЗЗ, и мы можем представить его в видематрицы смежности или достижимости.Следующийкритерий,скоторымработаетфитнес-функция–эффективность коммуникаций.