Курс Алгоритмы оптимизации, основанные на методе проб и ошибок (1121255), страница 8

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

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

Выбрать критерий останова алгоритма.В данном разделе рассмотрим решение этих проблем при построении алгоритмаимитации отжига для решения задачи построения статических многопроцессорныхрасписаний с минимальным временем выполнения на заданном числе процессоров.3.5.1. Математическая формулировка задачиЗадачу построения расписаний будем рассматривать в следующем вариантепостановки (математические представления модели программы, расписания и условий егокорректности приведены в разделе 1.4.1.)36Дано: H(PR)=(P,  )- модель программы, T=f(HP,HW)- функция вычислениявремени выполнения расписания HP на архитектуре HW (целевая функция).Требуется построить: HP– расписание выполнения программы на заданном числепроцессоров M такое, что:min f ( HP, HW )HPHP  HP1*5Функция вычисления времени выполнения расписания может быть задана ваналитическом виде или в виде имитационной модели.3.5.2. Способы представления расписания и операций его преобразованияБинарное представление расписания.Расписание задается:матрицей привязки Y(HP)NM и матрицей смежности X(HP)NN графа HP, где элементыматриц определяются:1, если pi  SPjy ij  0, если pi  SPj1, если  ij  HPxij  0, если  ij  HP(первый индекс рабочий интервал-предшественник, второй индекс рабочий интервалприемник).

Где M – число процессоров в ВС, N – число рабочих интервалов в H.Недостаткомданногопредставленияявляетсябольшоечислобинарныхпеременных N2+NM.Целочисленное представление расписания1. Расписание задается матрицей Y(HP)NM, где элемент матрицы определяется:c, если pi  SPjy ij  ,0, если pi  SPjc – порядковый номер рабочего интервала pi в SPj.При данном способе представления расписания число целочисленных переменныхравно NM.2.

Расписание задается: вектором привязки Y(HP)K и вектором порядка X(HP)N, гдеi-й элемент вектора Y(HP)K равен номеру списка в который назначены рабочие интервалыi-го процесса, а i-й элемент вектора X(HP)N равен порядковому номеру рабочего интервала37в соответствующем списке. При данном способе представления расписания числоцелочисленных переменных равно K+N.Операции преобразования расписанияМожно выделить следующие варианты отличия расписаний HP и HP друг отдруга:расписания HP и HP отличаются лишь порядком рабочих интервалов какминимум в одном SPj;расписания HP и HP отличаются привязкой рабочих интервалов.Введем соответствующие операции преобразования расписаний, позволяющиеустранить указанные варианты отличия: O={O1,O2} [Костенко В.А. Задача построениярасписания при совместном проектировании аппаратных и программных средств// Программирование,2002., №3. - С.64-80.].

Операции O1,O2 определим для целочисленного непосредственногопредставления расписания. Операции будем определять при предположениях: каждыйпроцесс имеет не более одного рабочего интервала или при условии, что на расписание ненакладывается ограничение 5. После доказательства теоремы о замкнутости и полнотесистемы операций O={O1,O2} и получении условий их применимости покажемвозможность снятия указанных предположений.Операция изменения порядка рабочих интервалов в одном списке изменяетпорядковый номер рабочего интервала pi в списке SPm (порядковый номер рабочегоинтервала становится равным c) и корректирует порядковые номера соответствующихрабочих интервалов в данном списке (NSm – число рабочих интервалов в списке SPm):c1  y im , y im  c  (1,, c1  1); j y jm  0  c  y jm  c1 : y jm  y jm  1 уменьшение порядкового номераO1( pi , SPm , c)  c1  y im , y im  c  (c1  1,, NS m ); j y jm  0  c1  y jm  c : y jm  y jm  1 увеличение порядкового номераОперация изменения привязки рабочих интервалов переносит рабочий интервал piиз списка SPm в список SPk (порядковый номер рабочего интервала становится равным c)и корректирует порядковые номера соответствующих рабочих интервалов в списках SPm иSPk:O 2( pi , SPm  SPk , c)  { y ik  c  (1 NS k  1); j y jk  0  c  y jk : y jk  y jk  1, NS k  NS k  1;j y jm  0  y im  y jm : y jm  y jm  1, NS m  NS m  1, y im  0}38Указанные интервалы параметра операций c могут привести к нарушениюограничений 3,4.

Покажем замкнутость и полноту системы операций O={O1,O2} иполучим условия их применимости (выбор значения параметра c) не нарушающиеограничений 3,4.Теорема( HP, HP' HP1* 4 ),1.ЕслитоHPисуществуетHP-конечнаяпроизвольныецепочкакорректныекомандрасписания{Oi }iK1 , Oi  {O1, O 2} ,переводящая расписание HP в HP, такая, что все K промежуточных расписаний являютсякорректными и K  2N.Доказательство. Введем понятие канонического расписания HP0: все рабочиеинтервалы находятся в SP1 и порядковые номера рабочих интервалов в SP1 равны номерамрабочих интервалов в графе H.

HP0 является допустимым, поскольку нумерация рабочихинтервалов в графе H удовлетворяет условиям полной топологической сортировки.Полноту системы операций {O1,O2} докажем, показав, что существует стратегия(последовательность выбора рабочих интервалов, операция для каждого интервала изпоследовательности и значение параметра c) с числом шагов K  N позволяющаяперевести произвольное расписание HP в расписание HP0, такая, что все промежуточныерасписания HPi (полученные после выполнения отдельной операции Oi) являютсядопустимыми и любая операция из цепочки {Oi }iK1 , Oi  {O1, O 2} является обратимой.Применение операций O1,O2 не может привести к нарушению ограничений 1,2 поопределению операций при любой стратегии.Расписания HP, HP0 и HPi будем представлять в ярусной форме максимальнойвысоты.

Покажем, что следующая стратегия позволяет перевести HP в HP0, не нарушаяограничений 3-4 для промежуточных расписаний HPi:1) выбор рабочих интервалов осуществляется в соответствии с их номерами в H;2) если очередной рабочий интервал pis  SP1 , то применяем O1; если pis  SP1 , топрименяем O2 (нижний индекс – номер рабочего интервала в H, верхний –номер яруса на котором расположен рабочий интервал);3) для рабочего интервала pis параметр c=i.Рассмотрим применение данной стратегии к рабочему интервалу с номером i=1.Если рабочий интервал находится в SP1 на первом ярусе, то его перенос не требуется.Если рабочий интервал находится в SP1 на ярусе отличном от первого, то увеличиваем на1 номера ярусов с первого яруса по ярус, предшествующий ярусу на котором находилсяпервый рабочий интервал, и применяем к нему операцию O1.

Полученное при этомрасписание HP1 удовлетворяет ограничению 3 в силу того, что нумерация рабочих39интервалов в H удовлетворяет условиям полной топологической сортировки, и являетсяярусным, следовательно, удовлетворяет ограничению 4. Если рабочий интервал ненаходится в SP1, то применяем к нему операцию O2, осуществляющим его перенос в SP1на первый ярус. Если рабочий интервал находился на ярусе отличном от первого, тоаналогично, как и при применении операции O1, корректируем номера ярусов.Полученное при этом расписание HP1 удовлетворяет ограничению 3 в силу того, чтонумерация рабочих интервалов в H удовлетворяет условиям полной топологическойсортировки, и является ярусным, следовательно, удовлетворяет ограничению 4.Поскольку, HP допустимое расписание, то операции O1/O2 являются обратимыми(параметр c в обратной операции принимает старый номер рабочего интервала).Пусть расписание HPi-1 является корректным.

На предыдущих шагах всепредшественники i-го рабочего интервала перенесены на ярусы лежащие выше i-го ярусав SP1. Переносим i-й рабочий интервал в SP1 на i-й ярус, используя операцию O1/O2. Еслиi-й рабочий интервал находился не на i-м ярусе, то перед применением операцииувеличиваем на 1 номера ярусов с i-го яруса по ярус, предшествующий ярусу на которомнаходилсяi-йрабочийинтервал.ПолученноерасписаниеHPi,удовлетворяетограничениям 3 и 4, так как все предшественники i-го рабочего интервала находятся наярусах выше i-го яруса, последователи на ярусах ниже i-го яруса, и граф HPi представленв ярусной форме максимальной высоты.

Поскольку, HPi-1 и HPi корректные расписания,то операции O1/O2 являются обратимыми (параметр c в обратной операции принимаетстарый номер рабочего интервала).После обхода всех вершин в соответствии с используемой стратегией получимрасписание HP0. Если операции O1/O2 применялись для всех рабочих интервалов то K=N.Поскольку, каждая операция из цепочки {Oi }iK1 , Oi  {O1, O 2} обратима, то существуетстратегия перехода от HP0 к произвольному HP, такая, что все K промежуточныхрасписаний являются корректными и KN. Следовательно, существует стратегия переходаот произвольного корректного варианта расписания HP к произвольному корректномуварианту расписания HP, такая, что все промежуточные расписания корректны и K2N.Следствие 1. Существует стратегия перехода от произвольного корректногорасписаниякоптимальномурасписанию,такая,чтодлинацепочкикоманд{Oi }iK1 , Oi  {O1, O 2} , переводящей произвольное корректное расписание в оптимальное,не превосходит значения 2N (K2N) и все K промежуточных расписаний являютсякорректными.40Условия применимости операций не нарушающие ограничений на HPПолучим интервал значений параметра c при применении операции O1/O2 крабочему интервалумаксимальнойpis .

Расписания HP будем представлять в ярусной формевысоты.ОбозначимчерезIN i  { p kl : ki  0}-множествонепосредственных предшественников рабочего интервала pis (всегда выполняется k<i иl<s), OUTi  { p kl : ik  0} - множество непосредственных последователей рабочегоинтервалаpis (всегда выполняется k>i и l>s). Операция lin  max(l ) - получаетIN iмаксимальный номер яруса, на котором расположен один из непосредственныхпредшественников рабочего интервалаpis , для рабочих интервалов, не имеющихпредшественников lin=0 (нулевой ярус всегда пуст). Операция lout  min(l ) - получаетOUTiминимальный номер яруса, на котором расположен один из непосредственныхпоследователей рабочего интервалаpis , для рабочих интервалов, не имеющихпоследователей lout=N (N – число ярусов в HP, для ярусной формы максимальной высотычисло ярусов всегда равно числу рабочих интервалов).

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

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