Главная » Просмотр файлов » Автореферат

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

Файл №1091134 Автореферат (Разработка моделей и алгоритмов составления оптимальных расписаний выполнения программных модулей в вычислительной сети на основе эволюционного подхода) 2 страницаАвтореферат (1091134) страница 22018-01-18СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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.При работе с расписаниями большой размерности операции сравнениявыполняются после обработки нескольких слотов, т.е.

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

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

Разработка моделей и алгоритмов составления оптимальных расписаний выполнения программных модулей в вычислительной сети на основе эволюционного подхода
Документы
Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6374
Авторов
на СтудИзбе
309
Средний доход
с одного платного файла
Обучение Подробнее