Лекции All in One (1121240), страница 5

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

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

Операция изменения порядка рабочих интервалов в одном списке:

• изменяет порядковый номер рабочего интервала p_i в списке SP_m (порядковый номер рабочего интервала становится равным c),

• корректирует порядковые номера соответствующих рабочих интервалов в данном списке (NS_m – число рабочих интервалов в списке SP_m).

Операция изменения привязки рабочих интервалов

• переносит рабочий интервал p_i из списка SP_m в список SP_k (порядковый номер рабочего интервала становится равным c),

• корректирует порядковые номера соответствующих рабочих интервалов в списках SP_m и SP_k:

Теорема. Если HP и HP^ - произвольные корректные расписания ( ), то существует конечная цепочка команд , переводящая расписание HP в HP^, такая, что все K промежуточных расписаний являются корректными и K  2N.

Условия применимости операций не нарушающие ограничений на HP

Получим интервал значений параметра c при применении операции O1/O2 к рабочему интервалу . Расписания HP будем представлять в ярусной форме максимальной высоты.

- множество непосредственных предшественников рабочего интервала (всегда выполняется k<i и l<s),

- множество непосредственных последователей рабочего интервала (всегда выполняется k>i и l>s).

Операция - получает максимальный номер яруса, на котором расположен один из непосредственных предшественников рабочего интервала , для рабочих интервалов, не имеющих предшественников lin=0 (нулевой ярус всегда пуст).

Операция - получает минимальный номер яруса, на котором расположен один из непосредственных последователей рабочего интервала , для рабочих интервалов, не имеющих последователей lout=N

Тогда, рабочий интервал может быть размещен в любой из списков SP_j на любой из ярусов из интервала lin<s<lout. Если выбранный ярус занят, то осуществляется коррекция ярусной формы путем соответствующего сдвига ярусов.

Возможность снятия условий: каждый процесс имеет не более одного рабочего интервала или на расписание не накладывается ограничение 5

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

Стратегии применения операций преобразования текущего решения

Стратегия уменьшения задержек.

Если время начала выполнения каждого рабочего интервала равно длине критического пути в графе H от истоков до рабочего интервала, то расписание будет оптимальным.

Стратегия заполнения простоев.

Эта стратегия основана на эмпирической гипотезе: чем меньше времени в сумме простаивают процессоры, тем лучше расписание.

Смешанная стратегия.

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

Схемы реализации стратегий

• случайный выбор операций и их параметров из допустимого диапазона;

• детерминированное применение операций на основе эвристических критериев;

• комбинированные схемы, сочетающие первые две.

Закон понижения температуры - закон с искусственным выходом из локальных оптимумов.

В качестве функционала используется функция T=f(HP,HW).

В качестве критерия останова используется исходно заданное количество итераций без улучшения значения функции T=f(HP,HW).

Параллельный алгоритм имитации отжига для построения статических многопроцессорных расписаний

Множество всех возможных решений задачи построения расписаний представляется совокупностью областей :

1. ;

2. ;

3. введённые в операции преобразования должны быть замкнутыми на областях и сохранять на них свойство полноты.

Построение параллельного алгоритма требует решения следующих подзадач:

1. разбиение исходного пространства корректных расписаний на несколько непересекающихся областей, дающих в объединении все пространство;

2. выбор начального корректного расписания в каждой из областей;

3. модификация операций преобразования расписаний таким образом, чтобы модифицированные операции были замкнуты в каждой из областей и сохраняли все свойства базовых операций;

4. выбор способа распределения областей по узлам вычислительной системы и схемы отсечения областей.

Метрика в пространстве HP^*

Пусть HP₁, HP₂ HP^* - два произвольных корректных расписания. Расстоянием (HP₁,HP₂) между расписаниями HP₁ и HP₂ будем называть число, равное длине минимальной допустимой цепочки операций O₁ и O₂, которая переводит расписание HP₁ в расписание HP₂:

(HP₁,HP₂)= L(S).

L(S)- длина цепочки S (количество операций в этой цепочке).

(HP) - множество всех допустимых цепочек

Функция (HP₁,HP₂) является метрикой:

1. функция определена всюду на HP^*;

2. для выполнены аксиомы метрики.

Свойство 1. HP₁, HP₂ HP^* : (HP₁,HP₂) 0 и (HP₁,HP₂) = 0 HP₁=HP₂.

Свойство 2. HP₁,HP₂ HP^* : (HP₁,HP₂) = (HP₂,HP₁)

Свойство3(неравенство треугольника). HP₁,HP₂,HP₃ HP^*: (HP₁,HP₃) (HP₁,HP₂)+ (HP₂,HP₃).

Разбиение исходного пространства решений на области

Каждой из областей , можно поставить в соответствие граф .

P - множество вершин, соответствующих рабочим интервалам.

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

Отношения J и K соответствуют ограничениям на привязку рабочих интервалов:

• два рабочих интервала и связаны отношением J, , если они должны выполняться на одном процессоре;

• два рабочих интервала и связаны отношением K, , когда они распределены на разные процессоры.

Дополнительно к ограничениям 1-5 на корректность расписания вводятся еще два ограничения:

• отношение J должно быть сохранено в HP: любые два рабочих интервала, связанные отношением J, должны быть назначены на один и тот же процессор;

• отношение K сохраняется в HP: любые два рабочих интервала, связанные отношением K, должны быть назначены на разные процессоры.

Алгоритм разбиения исходного пространства решений на области

Алгоритм позволяет так осуществлять разбиение на области, что критические пути в графах областей разбиения будут существенно отличаться между собой.

Это позволяет отбросить большое количество областей (без запуска в них алгоритма имитации отжига), в которых критический путь больше времени выполнения расписаний, полученных при запуске алгоритма имитации отжига в других областях.

Операции преобразования расписания

– множество рабочих интервалов, которые должны выполняться на одном процессоре с рабочим интервалом p;

- множество рабочих интервалов, для которых запрещено выполнение на одном процессоре с рабочим интервалом p;

SP – множество всех процессоров;

- процессор, на который распределён рабочий интервал p в расписании HP.

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

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