Диссертация (1091135), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

Равенство(2.2.1.5) необходимо для получения однонаправленности вычислительногопроцесса в рамках логики последовательно-параллельных форм.Целесообразность включения в задачу ограничений (2.2.1.5), (2.2.1.11)обусловленавозможностьюдостиженияминимальногозначенияцелевойфункции за счёт уменьшения коэффициента использования технических средств,что ведёт к низкой производительности и невысокой эффективности работывычислительной сети.Основнойидеейэволюционногоподходаявляетсямоделированиеестественного отбора, основанного на назначении оценок, соответствующихуровнюприспособленностиэкземпляровпопуляций, котораяреализуетсяоператором отбора, использующим функцию приспособленности, тогда задачаэволюционная модель синтеза оптимального расписания в математическойформулировке будет иметь следующий вид.Представим популяцию расписаний в виде мультимножества Š∗ = (ŜPN , Y*)на множестве ŜPN с мощностью G = |∗ |, гдеY* : ŜPN → ℕ ,̅̅̅̅̅k – номер итерации, k = 0, , где K число итераций синтеза расписания,∗Тогда расписание , есть подмультимножество мультимножества Š∗ ,где̅̅̅̅̅g – идентификатор расписания в k-ой популяции, g = 0, , где G размерпопуляции.73Тогда мультимножество R* = (RPN, y*) на множестве RPN , гдеy*: RPN → ℕ , – элемент мультимножества R*, который представляет оценку временивыполнения g-го расписания принадлежащего k-ой популяции.Эволюционная модель представляет совокупность трёх операторов:отбора, скрещевания и мутации.Оператор отбора в эволюционной модели составления оптимальныхрасписаний целесообразно представить в виде параметрической функции:0,1,D(Xrand) =0 ≤ ≥ < ≥ +12, +1< ≥ +2… − 1, −2 < ≥ −1, −1< ≥ {,(2.2.1.12)где Xrand случайное число, Xrand ∈ [0, ] с функцией распределения по∗равному закону, а диапазон сектора для g-го расписания с оценкой ,который расчитывается по формуле:gQg   rg  .k(2.2.1.13)g 0Расчёт оценки в эволюционной модели выполняет фитнес-функция.Математическая формулировка классической фитнес-функции подробноописана в работе [31].

В общем виде фитнес-функция вычисляет время каждойзадачи при ограничениях на порядок выполнения (задачи-приёмники не могутзапускатьсядовыполнениясоответствующихимзадач-передатчиков) иосвобождение узлов и коммуникаций, т.к. если узел или линия связи занятыпроцедура не может начать выполнение или передачу данных.74Определим время выполения комплекса ИЗЗ в соответствии с расписанием∗, как Т .∗Назначение оценки расписанию производится на основе значениявремени выполнения Т , данное назначение представляет нормирующуюфункцию Norm, которая выполняет отображение Norm : Т → .∗Расчёт оценки расписания производится по следующей формуле:g 1r  Tkgg kg 0GTg   g 1g k.(2.2.1.14)∗Пусть f( , n , c ) – процедура функции F() , обрабатывающая генслот , гдеn∗– оценка трудоёмкости задачи с идентификатором i расписания ,–оценкапроизводительностиузлавычислительнойсетиcидентификатором j ,c– число дуг, соответствующих незавершённым передачам, входящихв вершину графа комплекса ИЗЗ, соответствующую задаче с идентификатором i.Пусть ℎ–время выполнения комплекса ИЗЗ в соответствии с∗расписанием на h-ом ярусе.

– время передачи данных для i-ой задачи, соответствующеевходящей дуге с самым высоким весом (в данное время входит также времявыполнения задачи отправителя). Расчёт данного параметра производится наоснове информации, которую содержат матрицы Aixi и B jxj . для i-ой задачи выполняющейся на j-том узле рассчитывается последующей формуле: = max [ (+ оп+ ′ ∗ ′ ) … (+ оп+ ′′ ∗ ′′ )], (2.2.1.15)′′′где ′ , ′′ – идентификаторы задач-отправителей для i-ой задачи,75 ′ , ′′ – идентификаторы передающих узлов, ′ , ′′ и ′ , ′′ – характеристики соответствующих объёмов передач иканалов связей.Причем, если c> 0, то f( , n , c ) < 0 , f( , n , c )=(n+ ) ∗ (−c + 1).(2.2.1.16)Тогдаmax[f( , n , c ) , f(+1 , n+1 , c+1 ) … f( , n , c ) ] − ℎ−1(2.2.1.17)время выполнения яруса с номером h.Тогда время выполнения рассчитывается по следующей формуле:(2.2.1.18) = ∑ (max[f( , n1 , c ) , f(+1 , n2 , c+1 ) … f( , n , c ) ]) − ℎ−1ℎ=1где xi , xi+1 … хI ∈ [0, J].Выполнив подстановку формулы 2.2.1.18 в формулу 2.2.1.14 получимобщую эволюционную модель составления расписания выполнения программныхмодулей в вычислительной сети.После оператора отбора, происходит запуск оператора скрещевания,∗∗∗который представляет деление расписания на два подмножества и ∗∗мощность каждого из которых равна || = ||=∗||2∗∗, ∩ =Ø.∗ |∗ |̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅||∗∗∗̅̅̅̅ }, а = { : i= 0,, i ∈ ℕ0 , j=0,= { : i =, || , i ∈ ℕ0 ,22̅̅̅̅ }j=0,Популяция k-ой итерации представляет мультимножество элементыкоторого представляют следующее объединение:∗∗∗= −1 ⋃ .(2.2.1.19)76Оператор мутации представляет функцию∗∗МM*: → ,∗Мгде (2.2.1.20)– новое расписание, получившееся в результате применения∗оператора мутации к расписанию .∗М̅̅̅̅ }, где слоты у которых m=1,={ m: i= ̅̅̅̅0, I , i ∈ ℕ0 , j= ̅̅̅̅0, , m= 0,1меняют значение j на случайное число ∈ [0, J] , при условии, что j ≠ jrand .Следующая популяция представляет мультимножество∗М̅̅̅̅̅̅̅̅̅̅Š∗+1 = {: k = 0, , g = 0,},где̅̅̅̅̅k – номер итерации, k = 0,,̅̅̅̅̅g – идентификатор расписания в k-ой популяции, g = 0,.2.2.2.

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

Тогда расчёт для коротких расписаний принимает следующийвид:77(2.2.2.1)∗ = ∑ [min ((max [f ( , n , c ) , … f ( , n , c )]) , )] − ℎ−1 ,ℎ=1minminгде H* = h , если min = Tcur, причём, если T gk = Tcur, при H* ≠ H, то Norm(T gk )= rmin,где rmin – минимальная оценка времени выполнения rmin≠ 0, rmin ∈ [ω, ὠ], где [ω, ὠ] – диапазондопустимых значений rmin .Т.к. при работе с расписаниями большой размерности операции сравненияпосле вычисления значения каждого слота могут снижать эффективностьпредложенногоподхода,целесообразнымспособомрешенияявляетсявыполнение сравнения с лучшим текущим после обработки не одного, анескольких слотов, т.е.

некоторого участка расписания.Пусть переменная D* характеризует размер участка обрабатываемогорасписания, который измеряется в ярусах, а переменная С*= ⌈ ∗ ⌉ показываетчисло участков в расписании, причем, если∗∉ ℕ, то размер последнего участкаравен п∗ = H – (C* – 1)*D*, тогда время выполнения для расписаний большойразмерности рассчитывается по следующей формуле:(2.2.2.2)=∑С∗ ∗ =1∗min ((∑∗ =1 [f( , n , c ), … f( , n , c )] − −1 ), ) − ∗ (−1) ,где С* = с* , еслиmin = , причём, если = , при С* ≠ ⌈ ∗ ⌉, тоNorm( )= rmin, где rmin – минимальная оценка времени выполнения rmin≠ 0, rmin ∈ [ω, ὠ], где[ω, ὠ] – диапазон допустимых значений rmin .Таким образом выполнив подстановку вышепредставленных формул2.2.2.1, 2.2.2.2. в формулу 2.2.1.14 получим частные эволюционные модели длядлинных и коротких расписаний.Данные модели имеют следующую особенность.

Если представить графканонической формы комплекса ИЗЗ (рисунок 2.2.2.1 а) и предположить, чтозадачи 1 и 2 в соответствии с расписанием будут выполняться на одном узле,78предложенные модели не будут учитывать последовательность их выполнения наузле.Рис. 2.2.1.3. Графы канонической формы ИЗЗДля корректных расчётов в граф канонической формы ИЗЗ, должнывводиться дополнительные дуги, располагающиеся на одном ярусе с нулевымивесами, отображающие порядок выполнения задач на узле (рисунок 2.2.2.1 б).Цепочка из дуг должна вести на следующий ярус (рисунок 2.2.2.1 в).Вышеописанная особенность связана с необходимостью определенияпорядка выполнения задач одного яруса на одном узле. Порядок можетизменяться, что порождает различные варианты расписаний, даже приоднозначном совпадении значений слотов.Привыполнениисинтезарациональногорасписаниявыполненияпрограммных модулей в РСОД, данное свойство может учитываться за счётдополнительной информации, определяющей порядок выполнения задач, либо неучитываться в случае стохастического выполнения.792.3.Разработкаоптимальныхмодифицированныхрасписанийвыполненияалгоритмовпрограммныхсоставлениямодулейввычислительной сети2.3.1.

Разработка модифицированного генетического алгоритма длякоротких расписанийПри выборе стратегии распараллеливания ИЗЗ и принятии решения обиспользованииметодапоследовательногоулучшения,происходитзапускалгоритма поиска оптимальной логической структуры комплекса ИЗЗ.Т.к. данная задача обладает NP-полнотой, и её решение невозможнопроизвести при помощи полного перебора за приемлемое время, целесообразнымсчитается применение приближённых методов и эвристических алгоритмов, в томчисле и на основе эволюционной модели.ГА – это стохастические эвристические оптимизационные методыэволюционного моделирования, основанные на принципах естественного отбора.ГА используется в разных областях, где невозможно найти лучшее решение итребуется найти решение максимально приближенное к оптимальному [25].Математическое описание и применение классического ГА в распределениипрограммных модулей в вычислительной сети подробно рассмотрено в работах[39], [40]. В общем виде ГА представляет последовательность следующих шагов:1)формирование популяции;2)расчёт оценок для каждой особи (фитнес-функция);3) стохастический отбор наиболее приспособленных особей;4) скрещивание (кроссинговер);5) мутация.Основные проблемы, которые возникают при применении и разработкепрограммного обеспечения, использующего аппарат генетических алгоритмов,заключается в выборе:801) функции приспособленности (фитнес-функции), т.е.

Характеристики

Список файлов диссертации