Автореферат (1091134), страница 2

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

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

Содержит137 с. текста (из них 117 с. основного текста, 13 с. литературы и 7 с. приложений),включает 35 рисунков и 17 таблиц.6Основное содержание работыВовведенииобосновываетсяактуальностьнаучнойзадачи,формулируются цель и задачи исследования, отмечаются научная новизна ипрактическая значимость результатов, перечисляются основные положения,выносимые на защиту.Первая глава содержит анализ существующих РСОД, методов ихклассификации и обзор коммуникационных топологий, а также описаниеразличных методов поиска оптимальных расписаний, применяющихся в РСОД.Глава содержит подробное описание классического генетического алгоритма.Во второй главе выполнена постановка задачи диссертационногоисследования. Глава содержит описание разработки и обоснование моделей иэволюционных алгоритмов составления оптимальных расписаний выполненияпрограммных модулей в вычислительной сети.При решении больших задач в РСОД, целесообразным является ихпредставление в виде комплекса информационно-зависимых задач (ИЗЗ).

В своюочередь в вычислительной сети, на базе которой организована РСОД, данныйкомплекс ИЗЗ представляет совокупность программных модулей, над которымивыполняется процедура распределения для обеспечения их параллельноговыполнения и сокращения времени решения большой задачи. Таким образом,происходит отображение логической структуры комплекса ИЗЗ в физическую.Разработка моделей составления оптимальных расписаний выполненияпрограммных модулей в вычислительной сети на основе эволюционного подходазаключается в реализации представления комплекса ИЗЗ с помощью матричных играфовых моделей, и предполагает использование совокупности процедурпоследовательного преобразования канонической структуры комплекса ИЗЗ влогическую,учитывающуюархитектуруконкретнойилигипотетическойвычислительной сети, для чего граф канонической формы, преобразуется вагрегированный граф, вершины которого называются операционными модулями(ОМ).7Постановка задачи выглядит следующим образом.Aixi  aiiПусть–матрицаобъемовпередачинформации,гдеLaii    wilв  wiвхl  vl – объем передачи информации между задачами i и i’.

Даннаяl 1матрица является также матрицей смежности для канонической формы комплексаИЗЗ.Пусть B jxj  b jj  – матрица характеристик каналов связи вычислительнойсети.Дано:– множество оценок трудоёмкости задач P = {pi: i=,} , гдеpi – оценка трудоёмкости задачи с идентификатором i, pi>0 ,I – максимальное значение идентификатора i ;– множество оценок производительности узлов вычислительной сети}, гдеN = {nj:nj – оценка производительности узла с идентификатором j, nj> 0,J – максимальное значение идентификатора j;H – число ярусов в канонической структуре комплекса ИЗЗ.ПустьPN= { Sz: z} множество расписаний для P и N, гдеSz – расписание с номером z,m – мощность множества |PN|, m = .Расписание для P и N представляет множество, где={,} – ген-слот расписания c номером z, представляющийзадачу с идентификатором i, выполняющуюся на узле с идентификатором j.Пусть– оценка расписания Sz,множество оценок множества расписанийRPN , где RPN = {PN: z.Данные множества конечные и биективное отображениеPN–>RPNфункция F, областью определения которой являются элементы множестваобластью значений элементы множества RPN , тогда:8} –, естьPN,аPN –>RPNF:=> F(Sz) =(1 ).Множество RPN ограничено, и его верхняя грань будет являться оценкойоптимальных расписаний, т.е.Y = supRPN– оптимальная оценка расписаний.Тогда задача построения оптимальной логической структуры комплексаИЗЗ сводится к синтезу расписания c оценкой= Y, т.е.

нахождениюмаксимумов функции:Sz €ŜPNД  ŜPNгде(2 )maxF (Sz) ,ŜPNДмножестводопустимыхрасписаний,учитывающихограничения:– на однозначное распределение задач по модулямHIh 1i 0 Eijh  1, i, i  0, I ,(3)– на неравномерность загрузки узлов вычислительной сетиJH1/ J  Thj  j 0h 1J Thj  1 / J j 0HTh 1hj ,(4 )где  - допустимое отклонение от среднего времени выполнения ОМ ввычислительной сети;– на сложность межоперационного интерфейсаJH 1JHL    j 0гдеj ' 0h 1S’опh ' h 1 l 1–Blhj BX lh ' j '  S 'оп ,максимальноеколичество(5 )передаваемыхпоканаламинформационных элементов;– на сложность межоперационного интерфейса между отдельными узламивычислительной сетиN 1NL n 1n '  n 1 l 1гдеS jj B–lhj BX lh ' j '  S ' jj  ,максимальное(6 )количествопередаваемыхинформационных элементов между узлами j и j’;– на общее число задач в составе каждого ОМ на ярусе9поканаламIE М hj , h, j, h  1, H , j  1, J ,hiji o(7 )где M h i – максимальное число задач в hj-ом ОМ;– на число информационных элементов, обрабатываемых процедурамизадач каждого ОМL Lhj ,hjl(8)l 1Lhjгде–максимальноечислоинформационныхэлементов,обрабатываемых процедурами задач каждого ОМ;– ограничение на объем доступной памяти в узлах вычислительной сетиHIL   E v  h 1i 0гдеVjh iijl 1–lnmvl   V j , j  0, J ,с( з)(9 )максимальныйобъем доступнойпамятивj-омузлевычислительной сети;– на однозначное распределение задач по узлам вычислительной сетиJEj 0*ij 1, i, i  0, I ;(10)– на неравномерность загрузки узлов вычислительной сетиJjj 0j 0(1 / J ) T j    T j  (1 / J ) T j  ,(11)гдеILT j   Eij*  ij  t ij   с ( з )l j i 0l 1с( з) ljt– время реализации задач j-ого узлавычислительной сети, а  - допустимое отклонение от среднего временивыполнения работы узлов в вычислительной сети.Таблица 1.

Используемые обозначенияОбозначение*ijEСодержание1, если i-ая задача обрабатывается на j-ом узле сети;0 – в противном случае101, если i-ая задача обрабатывается на h-ом этапе в j-ом узле сети;0 – в противном случаеEijhПродолжение таблицы 1.Обозначениес( з)hjlСодержание1, еслиIR Eihj  wilс( з )  1 ; 0, еслиEi 0 lhjвх ( в )1, еслиIEhiji 0 nnmm1, еслиLl 1l1, если*ijс( з)ilE 1 ; 0, еслиhiji i 1 ; 0, еслиLE w*ij wilвх ( в )  0 lnm  в lnm  0вхl 1Ii 0 wilс ( з )  0I lnm  в lnm  1 ; 0, еслиE wi 0r 1вхIjwвх ( в )ilnmrс( з)il0viчисло узлов вычислительной сетичисло процедурчисло информационных элементовсреднее время считывания r-ой процедуры из внешней памяти воперативную в m-ом узле вычислительной сетисреднее время обработки i-ой процедуры в j-ом узлевычислительной сетисреднее время считывания (записи) l-ого информационногоэлемента в из внешней памяти в оперативную в m-ом узлевычислительной сетисреднее время передачи l-ого информационного элемента помагистрали вычислительной сетисреднее время работы программ операционной системы дляустановления связи между узлами вычислительной сетисреднее время работы программ операционной системы дляобслуживания ОМ в узле вычислительной сетиобъем i-ой задачиvlобъем l-ого информационного элементаwilвх (в )1, если l-ый информационный элемент является входным(выходным) для i-ой процедуры; 0 – в противном случае1, если l-ый информационный элемент считывается (записывается)i-ой процедурой; 0 – в противном случаеJILt ij ijс( з) ljttlсt проt прwilс ( з )Основнойидеейэволюционногоподходаявляетсямоделированиеестественного отбора, основанного на назначении оценок, соответствующихуровнюприспособленностиоператоромотбора,экземпляровиспользующимпопуляций,функцию11котораяреализуетсяприспособленности,тогдаэволюционная модель синтеза оптимального расписания в математическойформулировке будет иметь следующий вид.Представим популяцию расписаний в виде мультимножествана множествеk=PNс мощностью G = | |, где Y* :PN→=(PN, Y*), а k– номер итерации,, где K – число итераций синтеза расписания,Тогда расписание, есть подмультимножество мультимножестваg – идентификатор расписания в k-ой популяции, g =, где, где G размерпопуляции.Тогда мультимножество R* = (RPN,y*) на множестве RPN, где y*: RPN →а,– элемент мультимножества R*, который представляет оценку временивыполнения g-го расписания, принадлежащего k-ой популяции.Эволюционная модель представляет совокупность трёх операторов:отбора, скрещивания и мутации.Оператор отбора в эволюционной модели составления оптимальныхрасписаний целесообразно представить в виде параметрической функции:D(Xrand) =,(12)где Xrand случайное число, Xrandравному закону, ас функцией распределения подиапазон сектора для g-го расписанияс оценкой,который расчитывается по формуле:gQg   rg  .kg 0Расчёт оценки(13)в эволюционной модели выполняет фитнес-функция.В общем виде фитнес-функция вычисляет время каждой задачи приограничениях на порядок выполнения (задачи-приёмники не могут запускаться довыполнения соответствующих им задач-передатчиков) и освобождение узлов и12коммуникаций, т.к.

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

Расчёт данного параметрапроизводится на основе информации, которую содержат матрицы Aixi и B jxj последующей формуле:= max [++)…++)],где tоп  tпр  tпр ,сос,– идентификаторы задач-отправителей для i-ой задачи,,– идентификаторы передающих узлов,13(15)и– характеристики соответствующих объёмов передач иканалов связей.Причем, если> 0, то f()<0,(16)Тогда время выполнения комплекса ИЗЗ, соответствующее расписанию, рассчитывается по следующей формуле:(17),где xi , xi+1 … хI[0, J].После оператора отбора происходит запуск оператора скрещивания,который представляет деление расписанияна два подмножествамощность каждого из которых равна=={: i=,, j==}, а={=Ø.,:i=и,, j=}Популяция k-ой итерации представляет мультимножество, элементыкоторого представляют следующее объединение:(18)Оператор мутации представляет функцию:→M*где,(19)– новое расписание, получившееся в результате примененияоператора мутации к расписанию= {: i=,., j=m=}, где слоты, у которых m = 1,[0, J] , при условии, что j ≠ jrand .меняют значение j на случайное числоСледующая популяция представляет мультимножество:={},где k– номер итерации, k =популяции, g =, а g – идентификатор расписания в k-ой.14Идея частных эволюционных моделей заключается в сокращениивычислений фитнес-функции за счёт частичной обработки расписаний иназначении неточных оценок неэффективным экземплярам.Пустьпеременнаяхарактеризуетвремятекущеголучшегорасписания, тогда:(20)где H* = h , если=, причём, еслипри H* ≠ H, то Norm(=где rmin – минимальная оценка времени выполнения rmin≠ 0, rmin= rmin,[ω, ὠ], где [ω, ὠ] – диапазондопустимых значений rmin.При работе с расписаниями большой размерности операции сравнениявыполняются после обработки нескольких слотов, т.е.

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

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