Лекция 6 (1121246)

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

Текст из файла

Поведение программы Bh(PR):

Bh(PR) = < S, {R  (PR)}, {R  (PR)}>,

S – множество всех возможных шагов процессов (рабочих интервалов) в допустимом диапазоне входных данных программы,

{R  (PR)} - отношения, определяющие частичный порядок на множестве шагов каждого процесса,

{R  (PR)} - отношения взаимодействия между процессами.

Рабочий интервал процесса - внутренние действия процесса между двумя последовательными взаимодействиями с другими процессами.

Для задачи построения расписания будем использовать одну из историй поведения программы H(PR)Bh(PR).

Для H(PR) отношение {R  (PR)} является отношением полного порядка, а множество S сужается до множества шагов, которые делают процессы для конкретного набора входных данных.

H(PR) можно представить ациклическим ориентированным размеченным графом.

Вершинам соответствуют рабочие интервалы процессов,

дугам ={ _ik=(p_i,p_k)}_{(i,k)Î(1...N)} - связи, определяющие взаимодействия между рабочими интервалами из множества P (определяются объединением отношений {R(PR)}, {R(PR)}).

Модель прикладной программы определим:

1. Множеством рабочих интервалов процессов, составляющих программу PR:

Нумерация рабочих интервалов является сквозной и удовлетворяет условиям полной топологической сортировки. Каждый рабочий интервал имеет метку принадлежности к процессу.

1. Частичным порядком на P:

={ _ik=(p_i,p_k)}_{(i,k)(1...N)};

1. Вычислительной сложностью рабочих интервалов:

;

1. Объемом данных обмена для каждой связи из :

{v_ik}_{(i,k)(1...N)};.

Расписание выполнения программы определено, если заданы:

• привязка,

• порядок.

Модель расписания выполнения программы определим набором простых цепей и отношением частичного порядка _HP на множестве P:

HP=({SP_i}_i=(1...M) , _HP).

{SP_i}_i=(1...M) -набор простых цепей (ветвей параллельной программы).

Отношение частичного порядка _HP на множестве P для HP определим как объединение отношений: _HP= _c ₁ _M, _i - отношение полного порядка на SP_i, которое определяется порядковыми номерами рабочих интервалов в SP_i; _c - набор секущих ребер, которые определяются связями рабочих интервалов, распределенных на разные процессоры.

Если рабочие интервалы p_i и p_j распределены на разные процессоры и в существует связь _ij, то она определяет секущее ребро в HP.

На отношение _HP накладываются условия ацикличности и транзитивности.

Расписание HP является корректным, если выполнены следующие ограничения:

1. Каждый рабочий интервал должен быть назначен на процессор (в SP_i).

2. Каждый рабочий интервал должен быть назначен лишь на один процессор (в один SP_i).

3. Частичный порядок, заданный в H сохранен в HP:

4. Расписание HP должно быть беступиковым. Условием беступиковости является отсутствие контуров в графе HP: .

5. Все рабочие интервалы одного процесса должны быть назначены на один и тот же процессор (в один и тот же SP_i).

В дальнейшем будем говорить, что расписание корректно , если оно удовлетворяет ограничениям 1-5.

Дано:

• H(PR)=(P, )- модель программы,

• T=f(HP,HW)- функция вычисления времени выполнения расписания HP на архитектуре HW.

Требуется построить: HP– расписание выполнения программы на заданном числе процессоров M такое, что:

1. Разработать способ представления решения X и операций преобразования текущего решения на шаге 3.

2. Разработать стратегию применения операций преобразования текущего решения на шаге 3: какую операцию применять, к какому элементу X, как его изменять.

3. Выбрать закон понижения температуры на шаге 7.

4. Определить функционал , используемый для оценки качества текущего решения на шаге 4.

5. Выбрать критерий останова алгоритма, используемый на шаге 6.

Бинарное представление расписания.

Расписание задается:

• матрицей привязки Y(HP)_NM

• матрицей смежности X(HP)_NN графа HP.

Элементы матриц определяются:

M – число процессоров в ВС,

N – число рабочих интервалов в H.

Недостатком данного представления является большое число бинарных переменных N²+NM.

Целочисленное представление расписания

1. Расписание задается матрицей Y(HP)_NM, где элемент матрицы определяется: ,

c – порядковый номер рабочего интервала p_i в SP_j.

При данном способе представления расписания число целочисленных переменных равно NM.

2. Расписание задается:

• вектором привязки Y(HP)_K (i-й элемент вектора Y(HP)_K равен номеру списка в который назначены рабочие интервалы i-го процесса),

• вектором порядка X(HP)_N, (i-й элемент вектора X(HP)_N равен порядковому номеру рабочего интервала в соответствующем списке).

При данном способе представления расписания число целочисленных переменных равно K+N.

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

Можно выделить следующие варианты отличия расписаний HP и HP^ друг от друга:

• расписания HP и HP^ отличаются лишь порядком рабочих интервалов как минимум в одном SP_j;

• расписания HP и HP^ отличаются привязкой рабочих интервалов.

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

• изменяет порядковый номер рабочего интервала 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. Если выбранный ярус занят, то осуществляется коррекция ярусной формы путем соответствующего сдвига ярусов.

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

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