Лекция 6 (1121246), страница 2

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

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

Возможность снятия условий: каждый процесс имеет не более одного рабочего интервала или на расписание не накладывается ограничение 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.

Алгоритм выполнения операции O2:

Шаг 1. Случайным образом выбирается рабочий интервал p.

Шаг 2. Строится множество процессоров , на которые возможно перенести рабочий интервал p: .

Шаг 3. Случайным образом выбирается процессор из и на него переносятся все рабочие интервалы из множества .

Алгоритм выполнения операции O1 :

Шаг 1. Случайным образом выбирается рабочий интервал p.

Шаг 2. Определяется допустимый диапазон ярусов . Этот диапазон выбирается таким образом, что рабочий интервал p может быть перенесён на любой ярус из найденного диапазона.

Шаг 3. Ярус из допустимого диапазона выбирается случайным образом и на него переносится рабочий интервал p.

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

Пусть n – количество областей разбиения,

m – количество узлов вычислительной системы, осуществляющих поиск решений в областях (n > m).

Области упорядочиваются по критическому пути в графах.

В i-й узел (1 i m) будут распределены области с номерами

j : j mod m = i (1 j n).

Р

ис. Сравнение времени работы алгоритмов.

Рис. Улучшение качества решений при использовании разбиения на области и параллельного алгоритма по сравнению с решениями, полученными классическим алгоритмом.

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

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