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

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

В каждой работе последовательностьопераций строго фиксирована. Объединение работ называется партией.Машина – обозначает устройство, на котором производится выполнениеопераций, представляющих работы. Множество машин, которое требуется длявыполненияоперацийработисходнойпартии,называетсясистемойобслуживания.Следующеепонятиетеориирасписанийназываетсяпроцессобслуживания.

Данное понятие представляет выполнение операций из партииработмашинами,принадлежащимисистемеобслуживания.Процессобслуживания описывается следующими параметрами: количество машин, принадлежащих системе обслуживания; число операций, входящих в каждую работу; последовательность машин, которую проходит каждая работа.Для того, чтобы описать процесс обслуживания требуется синтезрасписания, которое будет определять время реализации операций на каждоймашине либо последовательность работ, составляющих партию. Критерийоптимальности расписания может представлять общее время выполненияпроцесса обслуживания или среднее время продвижения работ в системе.Данные составляющие являются формальными, и какие конкретнофизические объекты они подразумевают для теории расписаний, не имеетзначения.В математической формулировке задача синтеза оптимального расписаниявыполнения программных модулей в РСОД выглядит следующим образом.64Разработка моделей основана на представлении исходной большой задачи в видекомплекса ИЗЗ.

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

мелкозернистый параллелизм неэффективен в распределённыхсистемах, каноническая форма графа ИЗЗ, преобразуется в агрегированный граф(рисунок 2.2.1.1), вершины которого называются операционными модулями (ОМ)[4].Рисунок 2.2.1.1. Логическая структура программного и информационногообеспечения ИЗЗ65Оптимизационные модели логической структуры комплекса ИЗЗ ввычислительной сети разрабатываются с учетом показателя целесообразностираспараллеливания ИЗЗ в вычислительной сети (ВС) – γ. При γ > 1 актуальнойявляется задача синтеза оптимальной логической структуры комплекса ИЗЗ покритерию минимального времени решения (задача F1 рисунок 2.2.1.2).При γ ≤ 1 с точки зрения сокращения времени решения комплекса ИЗЗэффект от распараллеливания в вычислительной сети (ВС) отрицательный.Поэтому в качестве критерия целесообразно использовать минимум суммарногомежоперационного интерфейса (задача F2).Таким образом, общую последовательность проектирования оптимальнойлогической структуры комплекса ИЗЗ можно представить в виде алгоритма,изображенного на рисунке 2.2.1.2.В качестве начальной информации используются характеристики ВС, иканонической структуры комплекса ИЗЗ в ярусно-параллельной форме.

ЗадачаF1* главным образом отличается от задачи F1 тем, что учитывает временныезатраты на протоколы.Содержательная постановка задачи F1(F1*) формулируется следующимобразом. По известным характеристикам узлов вычислительной сети, каналовпередачи данных, топологии вычислительной сети, канонической структурыкомплекса ИЗЗ необходимо определить логическую структуру комплекса ИЗЗ ввиде множеств операционных модулей (ОМ) и отношений между ними, а такжеразмещение ОМ в вычислительной сети, которые обеспечивали бы минимальноевремя решения комплекса ИЗЗ и выполнение сетевых, системных и структурныхограничений.66Рисунок 2.2.1.2. Общая последовательность проектирования оптимальнойлогической структуры ПО комплекса ИЗЗ.При выборе стратегии распараллеливания комплекса ИЗЗ (задача F1*) ипринятии решения об использовании метода последовательного улучшения,происходит запуск алгоритма поиска оптимального расписания выполненияпрограммных модулей в вычислительной сети.Задача синтеза оптимального расписания является NP-полной и для еёрешения применяются приближённые методы и эвристические алгоритмы на67основеэволюционногомножествоподхода.примененийприЭволюционноерешениимоделированиеразличныхклассовнаходитзадач[36].Заимствование законов развития природы даёт возможность решать эти задачи вболее широком, универсальном смысле без ограничений, ранее разработанныхматематических моделей [51 стр.

3]. Различные эволюционные моделирассмотрены в [52], [53], [54].Основываясь на вышеизложенном декомпозиционно-композиционномподходепостроениялогическойструктурыкомплексаИЗЗ,разработанаматематическая постановка этой задачи на основе эволюционного подхода.Для постановки задачи необходимо определить ряд величин.ПустьAixi  aii–матрицаобъемовпередачинформации,гдеLaii    wilв  wiвхl  vl – объем передачи информации между задачами i и i’.

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

нахождениюмаксимумов функции:max F (Sz) ,Sz €ŜPNДгде(2.2.1.2)ŜPNДŜPN множество допустимых расписаний, учитывающихограничения:– на однозначное распределение задач по модулямHIh 1i 0LJ 1Jl 1j 0j  j 1 Eijh  1, i, i  0, I ,  Ll 1BXlhj lhj'  0, h, h  1, H ,lhj B lh ' j  0, h, h' , j, j  0, J ,h'  h ;(2.2.1.3)69– на неравномерность загрузки узлов вычислительной сетиJHJHj 0h 1j 0h 11/ J  Thj    Thj  1/ J  Thj   ,(2.2.1.4)где  - допустимое отклонение от среднего времени выполнения ОМ ввычислительной сети;– на сложность межоперационного интерфейсаJH 1JHL    j 0j ' 0h 1S’опгдеh ' h 1 l 1–Blhj BX lh ' j '  S 'оп ,максимальноеколичество(2.2.1.5)передаваемыхпоканаламинформационных элементов;– на сложность межоперационного интерфейса между отдельными узламивычислительной сетиN 1NL n 1n '  n 1 l 1S jj где–Blhj BX lh ' j '  S ' jj  ,максимальноеколичество(2.2.1.6)передаваемыхпоканаламинформационных элементов между узлами j и j’;– на общее число задач в составе каждого ОМIEi ohij М hj , h, j, h  1, H , j  1, J ,(2.2.1.7)где M h i - максимальное число задач в hj-ом ОМ;– на число информационных элементов, обрабатываемых процедурамизадач каждого ОМLl 1hjl Lhj ,(2.2.1.8)70Lhjгде–максимальноечислоинформационныхэлементов,обрабатываемых процедурами задач каждого ОМ;– ограничение на объем доступной памяти в узлах вычислительной сетиL I h i  Eij v   с ( з )lnmvl   V j , j  0, J ,h 1  i  0l 1HгдеVj–максимальныйобъем доступной(2.2.1.9)памятивj-омузлевычислительной сети;– на однозначное распределение задач по узлам вычислительной сетиJEj 0 1, i, i  0, I ;*ij(2.2.1.10)– на неравномерность загрузки узлов вычислительной сетиJjj 0j 0(1 / J ) T j    T j  (1 / J ) T j  ,IгдеLT j   Eij*  ij  t ij   с ( з )l j i 0l 1(2.2.1.11)с( з) ljt – время реализации задач j-ого узлавычислительной сети, а  - допустимое отклонение от среднего временивыполнения работы узлов в вычислительной сети.Таблица 2.2.1.1.

Используемые обозначенияОбозначениеСодержаниеEij*1, если i-ая задача обрабатывается на j-ом узле сети;0 – в противном случаеEijh1, если i-ая задача обрабатывается на h-ом этапе в j-ом узлесети;0 – в противном случае71Продолжение таблицы 2.2.1.1.Обозначениес( з)hjlСодержание1, еслиIEhjii 00, еслиREnmrr 1 lhjвх ( в )1, если wilс ( з )  1 ;IEhiji 0 wilвх ( в )  1 ;IE0, если nnmm1, еслиL lnm  в lnm  1 ;вхl 10, еслиLl 1 wilвх ( в )  0hiji i lnm  в lnm  0вхIlj1, еслиE wi 0с( з)il*ijI0, если wilс ( з )  0E wi 0*ijс( з)il10viчисло этапов канонической структуры ИЗЗчисло узлов вычислительной сетичисло процедурчисло информационных элементовсреднее время считывания r-ой процедуры из внешнейпамяти в оперативную в m-ом узле вычислительной сетисреднее время обработки i-ой процедуры в j-ом узлевычислительной сетисреднее время считывания (записи) l-ого информационногоэлемента в из внешней памяти в оперативную в m-ом узлевычислительной сетисреднее время передачи l-ого информационного элементапо магистрали вычислительной сетисреднее время работы программ операционной системыдля установления связи между узлами вычислительнойсетисреднее время работы программ операционной системыдля обслуживания ОМ в узле вычислительной сетиобъем i-ой задачиvlобъем l-ого информационного элементаHJILt ij ijс( з) ljttlсt проt пр72Продолжение таблицы 2.2.1.1.ОбозначениеСодержание1, если l-ый информационный элемент является входным(выходным) для i-ой процедуры;0 – в противном случае1, если l-ый информационный элемент считывается(записывается) i-ой процедурой;0 – в противном случаеwilвх (в )wilс ( з )Ограничение (2.2.1.3) является необходимым и достаточным условиемраспараллеливания последовательности задач и размещения их по ОМ.