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

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

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

Тогда, рабочий интервал pis можетбыть размещен в любой из списков SPj на любой из ярусов из интервала lin<s<lout. Есливыбранныйярусзанят,тоосуществляетсякоррекцияяруснойформыпутемсоответствующего сдвига ярусов.Пусть рабочий интервал pis переносится в SPj или изменяется его порядковыйномервэтомсписке.РазобьеммножествоSPjнатриподмножества:PIN j  { p kl : l  lin, p kl  SPj } - множество рабочих интервалов из списка SPj, находящихсяна ярусах, расположенных выше яруса (lin-1); PI j  { p kl : lin  l  lout , p kl  SPj } множество рабочих интервалов из списка SPj, находящихся на ярусахlin, lout  ;POUT j  { p kl : l  lout , p kl  SPj } - множество рабочих интервалов из списка SPj,находящихся на ярусах, расположенных ниже яруса (lout+1).

Параметр c при размещениирабочего интервала pis в SPj может принимать следующие значения, не нарушающиеограничения на HP (индекс j для PIN, PI, POUT будем опускать):PINPIPOUTC1PIN=PI=POUT=c=12PIN=PI=POUTc=1413PIN=PIPOUT=1  c  max ( y jk )  1PI4PIN=PIPOUT1  c  max ( y jk )  1PI5PINPI=POUTc  min ( y jk )  1PIN6PINPI=POUT=c  min ( y jk )  1PIN7PINPIPOUT=min ( y jk )  c  max ( y jk )  1PI8PINPIPOUTPImin ( y jk )  c  max ( y jk )  1PIPIУказанные выше интервалы значений параметра c не нарушающие ограничения наHP могут быть расширены, если ярусная форма максимальной высоты будет приведена ктакому виду, что все рабочие интервалы SPj, которые не находятся в отношениитранзитивного порядка с непосредственным предшественником рабочего интервала pis(находящимся на ярусе lin) и расположены на ярусах с меньшими номерами чем lin, будутперенесены на ярусы с номерами большими чем lin.

Аналогичное преобразование яруснойформы может быть осуществлено и для непосредственного последователя рабочегоинтервала pis , находящимся на ярусе lout.Пусть непосредственным предшественником рабочего интервала pis являетсярабочий интервал p mlin , находящийся на ярусе lin, и рабочий интервал pis переносится вSPj или изменяется его порядковый номер в этом списке.

Пусть lin* ярус, на которомнаходится транзитивный предшественник рабочего интервала p mlin , принадлежащий SPj ис наибольшим порядковым номером в SPj. Рабочие интервалы SPj, находящихся междуярусами lin* и lin могут быть перераспределены по ярусам, таким образом, что они будутнаходиться на ярусах с большими номерами, чем lin (при этом осуществляетсясоответствующее перераспределение по ярусам рабочих интервалов и других списков).Аналогичное преобразование ярусной формы осуществляется и для последователей.Возможность снятия условий: каждый процесс имеет не более одного рабочегоинтервала или на расписание не накладывается ограничение 5Поскольку, при доказательстве теоремы 1 и получении условий применимостиопераций O1/O2 использована ярусная форма максимальной высоты (на каждом ярусенаходится лишь один рабочий интервал), то полученные результаты легко могут бытьобобщены на случаи когда: каждый процесс может иметь более одного рабочего42интервала или на расписание накладывается ограничение 5.

При перемещении рабочегоинтервала из одного списка в другой, перемещаются также и все рабочие интервалыпроцесса, которому принадлежит перемещаемый рабочий интервал, но при этом остаютсяна прежних ярусах. В результате получаем ярусную форму нового расписания, и,следовательно, полученное расписание удовлетворяет ограничениям 3-5.3.5.3.

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

Приприменении операций O1,O2 делается попытка уменьшить задержки рабочих интервалов.Стратегия заполнения простоев. Эта стратегия основана на эмпирическойгипотезе: чем меньше времени в сумме простаивают процессоры, тем лучше расписание.При применении операций O1,O2 делается попытка уменьшить суммарный простойпроцессоров.Смешанная стратегия.

Смешанная стратегия объединяет две предыдущих. Вовременнойдиаграммевыполнениярасписаниявыделяютсяинтервалыпростояпроцессоров и вычисляются задержки рабочих интервалов. При применении операцийO1,O2 делается попытка уменьшить задержку рабочих интервалов путем перемещения ихв интервалы простоя процессоров.Возможны следующие схемы реализации стратегий:случайный выбор операций и их параметров из допустимого диапазона;детерминированное применение операций на основе эвристических критериев;комбинированные схемы, сочетающие первые две.Более подробно со стратегиями применения операций и схемами их реализацииможно ознакомиться в следующих работах:1.Калашников А.В., Костенко В.А. Параллельный алгоритм имитации отжига для построениямногопроцессорных расписаний// Известия РАН.

Теория и системы управления, 2008., N.3,С.133-142.432.Калашников А.В., Костенко В.А. Итерационные алгоритмы построения расписаний,основанные на разбиении пространства решений на области// Вестн. Моск. ун-та. Сер. 15.Вычислительная математика и кибернетика. 2008., №. 3, С.56–60.3.Д.А.Зорин, В.А.Костенко. Алгоритм синтеза архитектуры вычислительной системы реальноговремени с учетом требований к надежности// Известия РАН.

Теория и системы управления,2012., № 2, С.124–131.3.5.4. Стандартные операцииВ качестве закона понижения температуры используется закон описанный вразделе 3.3.В качестве функционала F ( f ( X ), g i ( X )) используется функция T=f(HP,HW).В качестве критерия останова используется исходно заданное количество итерацийбез улучшения значения функции T=f(HP,HW).3.6. Параллельный алгоритм имитации отжига для построениястатических многопроцессорных расписанийВ данном разделе рассмотрим построение параллельного алгоритма имитацииотжига, основанного на декомпозиции пространства расписаний на области. Для этогомножество всех возможных решений HP1* 5 задачи построения расписаний представляетсясовокупностью областейHP1 , HP2 , , HPk .

Такое разбиение должно удовлетворятьследующим условиям:1) HP1  HP2  ...  HPk  HP1*5 ;2) HPi  HPj  , i, j : i  j ;3) введённые в HP1* 5 операции преобразования должны быть замкнутыми наобластях HP1 , HP2 , , HPk и сохранять на них свойство полноты.Определенное таким образом разбиение пространства всех решений на областипозволяет искать решение в каждой из них независимо от других. Используя априорныенижние оценки времени выполнения расписания в каждой области, можно отсекать те,которые заведомо не содержат оптимального решения. Поиск решения в любой областиможно осуществлять на разных узлах вычислительной системы.

При этом в связи свозможным отсечением областей, в том числе в процессе поиска решений, распределениеобластей по узлам вычислительной системы должно обеспечивать однородную загрузкувсех узлов в ходе всего времени работы алгоритма.44Таким образом, построение параллельного алгоритма требует решения следующихподзадач:1) разбиение исходного пространства корректных расписаний на нескольконепересекающихся областей, дающих в объединении все пространство;2) выбор начального корректного расписания в каждой из областей;3) модификация операций преобразования расписаний таким образом, чтобымодифицированные операции были замкнуты в каждой из областей и сохраняли всесвойства базовых операций;4) выбор способа распределения областей по узлам вычислительной системы исхемы отсечения областей.3.6.1.

Метрика в пространстве расписанийДля разбиения пространства расписаний на непересекающиеся области необходимоввести метрику на этом пространстве. Метрика в пространстве HP* корректныхрасписаний будет строиться как количество элементарных операций O={O1, O2}преобразования расписания.Пусть S = {s1,…,sK} - произвольная цепочка операций O1 и O2.Цепочка Sдопустима для расписания HP  HP*, если операции из этой цепочки могут бытьприменены к HP в заданном порядке, причем так, что все получаемые промежуточныерасписания являются корректными.

Обозначим:  (HP) - множество всех допустимыхцепочек операций преобразования для расписания HP; HP1=S(HP) – расписание,полученное последовательным применением операций из цепочки S к расписанию HP.Длиной L(S) цепочки S будем называть количество операций в этой цепочке.Метрика в пространстве HP* вводится следующим образом. Пусть HP1, HP2  HP* два произвольных корректных расписания. Расстоянием  (HP1,HP2) между расписаниямиHP1 и HP2 будем называть число, равное длине минимальной допустимой цепочкиопераций O1 и O2, которая переводит расписание HP1 в расписание HP2:  (HP1,HP2)=minS  ( HP1 ), S ( HP1 )  HP2L(S).Покажем корректность введенной метрики.

Для этого надо доказать, что:1) функция  определена всюду на HP*;2) для  выполнены аксиомы метрики.45Выполнение первого требования, очевидно, следует из теоремы 1 о полноте изамкнутости системы операций O={O1, O2} (см. раздел 3.6.2.). Покажем, что для функции выполняются все свойства метрики:Свойство 1.  HP1, HP2  HP* :  (HP1,HP2)  0 и  (HP1,HP2) = 0  HP1=HP2.Доказательство. Первая часть утверждения вытекает из того, что длина цепочкиопераций не может быть отрицательной. В совпадающих расписаниях каждый процессимеет одинаковые значения привязки и порядка, поэтому применение любой операцииделает эти расписания несовпадающими, откуда следует вторая часть утверждения.Свойство 2.

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

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