Курс Алгоритмы оптимизации, основанные на методе проб и ошибок (1121255), страница 4
Текст из файла (страница 4)
Модельфункционирования распределенных вычислительных систем, // Вестн. Моск. Ун-та. сер 15, Вычисл. Матем.и Кибернетика. 1990, No. 3, стр. 3-21.), (Смелянский Р.Л. Об инварианте поведения программ // Вестн. МГУ,сер. 15, Вычислительная математика и Кибернетика, 1990., No. 4, С.
54-60.)]. Следуя этим работам,обозначим поведение программы Bh(PR) и определим Bh(PR) следующим образом:Bh(PR) = < S, {R (PR)}, {R (PR)}>, где S – множество всех возможных шаговпроцессов в допустимом диапазоне входных данных программы, {R (PR)} - отношения,13определяющие частичный порядок на множестве шагов каждого процесса, {R (PR)} отношения взаимодействия между процессами.Шаги процесса определяются последовательностью взаимодействий с другимипроцессами. Назовем рабочим интервалом процесса внутренние действия процесса междудвумя последовательными взаимодействиями с другими процессами.
Каждый рабочийинтервал процесса по существу является реализацией соответствующего шага процесса.Для задачи синтеза архитектур будем использовать одну из историй поведенияпрограммы H(PR)Bh(PR) (поведение программы для конкретного набора входныхданных). Для H(PR) отношение {R (PR)} является отношением полного порядка, амножество S сужается до множества шагов, которые делают процессы для конкретногонабора входных данных.H(PR) можно представить ациклическим ориентированным размеченным графом.ВершинамNNNP { pi}i 11 { pi }i 21 { pi }i K1 ,соответствуютрабочиеинтервалыпроцессов, дугам ={ ik=(pi,pk)}(i,k)(1...N) - связи, определяющие взаимодействия междурабочими интервалами из множества P (определяются объединением отношенийN{R(PR)}, {R(PR)}).
Где { pi }i 1j - множество рабочих интервалов j-го процесса, Nj число рабочих интервалов в j-ом процессе, K - число процессов в программе PR,N=N1+N2+…+NK - мощность множества P. Чередование рабочих интервалов различныхпроцессов, назначенных на один и тот же процессор, допустимо, если не нарушаетсячастичный порядок, заданный . Отношение ik представляется следующим образом:если pi ik pk , то рабочий интервал pi, необходимо выполнить до начала выполнениярабочего интервала pk. На отношение накладываются условия ацикличности итранзитивности.
Каждая вершина имеет свой уникальный номер и метки: принадлежностирабочего интервала к процессу и вычислительной сложности рабочего интервала.Вычислительная сложность рабочего интервала позволяет оценить время выполнениярабочего интервала на процессоре. Дуга определяется номерами смежных вершин и имеетметку, соответствующую объему данных обмена. Объем данных обмена для каждой связииз позволяет оценить затраты времени на выполнение внешнего взаимодействия.Таким образом, модель прикладной программы определим:1. Множеством рабочих интервалов процессов, составляющих программу PR:NNNP { pi}i 11 { pi }i 21 { pi }i K1 ,14Нумерация рабочих интервалов является сквозной и удовлетворяет условиям полнойтопологической сортировки.
Каждый рабочий интервал имеет метку принадлежности кпроцессу.2. Частичным порядком на P: ={ ik=(pi,pk)}(i,k)(1...N);3. Вычислительной сложностью рабочих интервалов:w iNi 1;4. Объемом данных обмена для каждой связи из :{vik}(i,k)(1...N);.Расписание выполнения программы определено, если заданы: 1)множествапроцессоров и рабочих интервалов, 2)привязка, 3)порядок. Привязка-всюдуопределенная на множестве рабочих интервалов функция, которая задает распределениерабочих интервалов по процессорам. Порядок задает ограничения на последовательностьвыполнениярабочихинтерваловиявляетсяотношениемчастичногопорядка,удовлетворяющим условиям ацикличности и транзитивности.
Отношение порядка намножестве, рабочих интервалов распределенных на один и тот же процессор, являетсяотношением полного порядка.Модель расписания выполнения программы определим набором простых цепей иотношением частичного порядка HP на множестве P: HP=({SPi}i=(1...M) , HP).Где {SPi}i=(1...M) -набор простых цепей (ветвей параллельной программы). Они образуютсярабочими интервалами процессов, распределенными на один и тот же процессор (M –число процессоров в ВС). Отношение частичного порядка HP на множестве P для HPопределим как объединение отношений: HP= c 1 M, i - отношение полногопорядка на SPi, которое определяется порядковыми номерами рабочих интервалов в SPi; c - набор секущих ребер, которые определяются связями рабочих интервалов,распределенных на разные процессоры.
Если рабочие интервалы pi и pj распределены наразные процессоры и в существует связь ij, то она определяет секущее ребро в HP. Наотношение HP накладываются условия ацикличности и транзитивности.Модель расписания можно рассматривать как граф HP, вершины которого имеютдополнительную метку “номер списка”, а дуги определяются отношением HP или какграф H, вершины которого доразмечены двойками: {“номер списка”, “порядковый номервершины в соответствующем списке”}. В модели HP сохраняются нумерация вершин, дуги их метки заданные в модели поведения программы H. В дальнейшем при рассмотрении15свойств расписаний в некоторых разделах будет использоваться ярусная формапредставления расписания.
Ярусной формой максимальной высоты будем называть такуюярусную форму, у которой на каждом ярусе находится не более одной вершины.Ограничения на расписание.Расписание HP является корректным (сохраняетинвариант поведения программы), если выполнены следующие ограничения:5. Каждый рабочий интервал должен быть назначен на процессор (в SPi).6. Каждый рабочий интервал должен быть назначен лишь на один процессор (водин SPi).7. Частичный порядок, заданный в H сохранен в HP: THP , THP транзитивное замыкание отношения HP .8. Расписание HP должно быть беступиковым.
Условием беступиковости являетсяотсутствие контуров в графе HP: HP ациклично .9. Все рабочие интервалы одного процесса должны быть назначены на один и тотже процессор (в один и тот же SPi).Ограничения 1-4 обеспечивают сохранение инварианта поведения программы иявляются обязательными. Ограничение 5 запрещает возобновление работы процессапосле прерывания на другом процессоре, т.е.
определяет способ организациипараллельных вычислений в ВС, и не всегда является обязательным. В дальнейшембудем говорить, что расписание корректно HP HP1* 5 , если оно удовлетворяетограничениям 1-5. Нижний индекс в HP1* 5 указывает ограничения, налагаемые нарасписание.Задачупостроениярасписанийкакзадачуусловнойоптимизацииможносформулировать следующим образом.Дано: H(PR)=(P, )- модель программы, T=f(HP,HW)- функция вычисления временивыполнения расписания HP на архитектуре HW (целевая функция), T dir - директивныйсрок выполнения программы.Требуется построить: HP– расписание выполнения программы такое, что:16min M ( HP, HW )HPT f ( HP, HW ) T dirHP HP1*5Здесь M ( HP, HW ) - число процессоров, на котором выполняется расписание.Функциявычислениявременивыполнениярасписанияможетбытьзаданаваналитическом виде или в виде имитационной модели.С материалами данного раздела можно ознакомиться в работах:1.Смелянский Р.Л. Модель функционирования распределенных вычислительных систем// Вестн.Моск.
Ун-та. сер 15, Вычисл. Матем. и Кибернетика. 1990, No. 3, С. 3-21.2.Смелянский Р.Л. Об инварианте поведения программ// Вестн. МГУ, сер. 15, Вычислительнаяматематика и Кибернетика, 1990., No. 4, С. 54-60.3.Костенко В.А. Задача построения расписания при совместном проектировании аппаратных ипрограммных средств// Программирование, 2002., №3. - С.64-80.4.Калашников А.В., Костенко В.А. Параллельный алгоритм имитации отжига для построениямногопроцессорных расписаний// Известия РАН.
Теория и системы управления, 2008., N.3, С.133142.5.Калашников А.В., Костенко В.А. Итерационные алгоритмы построения расписаний, основанные наразбиении пространства решений на области// Вестн. Моск. ун-та. Сер. 15. Вычислительнаяматематика и кибернетика. 2008., №. 3, С.56–60.1.4.2. Задача построения статико-динамических расписанийСтатико-динамическое расписание представляет собой набор окон, каждое изкоторых характеризуется временем открытия, временем закрытия и списком работ,выполняющихся внутри окна. При этом порядок выполнения работ внутри окнаопределяется динамически и заранее неизвестен.
Длина окна должна быть не меньше, чемсуммарное время выполнения работ внутри него.Системы реального времени накладывают дополнительные ограничения нарасписание. Кроме времени выполнения, каждая работа характеризуется такжедирективным интервалом, в пределах которого возможно ее выполнение. При этомвременной интервал окна должен лежать внутри каждого из директивных интерваловработ, выполняющихся в данном окне, чтобы гарантировать, что директивные интервалыработ не будут нарушены.17Примером систем реального времени, использующих статико-динамическиерасписания, являются системы, работающие по стандарту ARINC-653 [Arinc Specification 653.Airlines Electronic Engineering Committee. [PDF] (http://www.arinc.com).].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
