Лекция 9 (1121237)

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

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

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

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...K) , _HP).

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

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

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

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

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

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

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

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

Дано:

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

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

• - директивный срок выполнения программы.

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

- число процессоров, на котором выполняется расписание.

1. Сгенерировать случайным образом популяцию размера P.

2. Выполнить операцию скрещивания.

3. Выполнить операцию мутации.

4. Вычислить функцию выживаемости для каждой строки популяции.

5. Выполнить операцию селекции.

6. Если критерий останова не достигнут, перейти к шагу 2, иначе завершить работу.

Параметрическое представление расписаний с использованием приоритетов

Расписание задается вектором Y_N+K :

K - число процессов в H,

N_i – число рабочих интервалов в i-ом процессе,

- операция построения вектора из параметров и .

содержит номер процессора, на котором выполняются рабочие интервалы i-го процесса.

используются алгоритмом восстановления расписания (определение отношения полного порядка в каждом SP_i) в качестве приоритетов рабочих интервалов.

Алгоритм восстановления полного порядка рабочих интервалов в SP (A1)

Mножество рабочих интервалов разобьем на три подмножества: :

• P1 - множество рабочих интервалов распределенных в SP алгоритмом восстановления на предыдущих шагах;

• P2 - множество рабочих интервалов, у которых все предшественники принадлежат P1;

• P3 - множество рабочих интервалов, у которых хотя бы один из предшественников не принадлежит P1.

1. Начальное разбиение множества P:

• P1=;

• - множество рабочих интервалов в H без предшественников;

• - множество рабочих интервалов в H, у которых имеются предшественники.

2. Находим в P2 рабочий интервал с наименьшим значением параметра (если таких интервалов более одного, то выбираем интервал с наименьшим номером):

• размещаем его в конец соответствующего списка SP (номер списка определяется значением параметра );

• переносим его из P2 в P1.

3. Проверяем P3 с целью возможности переноса рабочих интервалов в P2:

• если есть рабочие интервалы, у которых все предшественники принадлежат P1, то переносим их в P2.

4. Если P2, то к п.2, иначе завершить работу.

Утверждение. Алгоритм A1 восстановления расписания по его параметрическому представлению Y_N+K получает расписание , и расписание восстанавливается однозначно.

Теорема. Любое допустимое расписание может быть задано параметрическим представлением с использованием приоритетов (Y_N+K) и однозначно восстановлено алгоритмом A1, если допустимая верхняя граница L значений параметров больше или равна числу рабочих интервалов (LN).

Кодирование решений

– закодированное решение,

– привязка,

– приоритеты,

– оператор конкатенации строк.

Преобразование решения

1. Параметры могут принимать целочисленные значения в диапазоне [1,…,K],

2. Параметры могут принимать целочисленные значения в диапазоне [1,…,N],

3. количество изменяемых параметров может быть от 1 до N+K.

Операции преобразования решений, удовлетворяющие условиям 1-3 при использовании алгоритма восстановления A1, будут получать решения удовлетворяющие ограничениям на корректность расписаний 1-5, что следует непосредственно из утверждения 1.

Из теоремы 2 следует, что операции преобразования решения, удовлетворяющие условиям 1-3, и алгоритм восстановления A1 позволяют получить любой допустимый вариант решения.

Операции мутации и скрещивания

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

Операция селекции

Для выполнения селекции используется комбинация схемы пропорциональной селекции и схемы рулетки:

• если или это первая итерация алгоритма, то запоминаем как лучшую строку и переносим ее в новую популяцию,

• для вычисления целого числа потомков используется схема пропорциональной селекции,

• для распределения остатка – схема рулетки.

Функция выживаемости

F(k_t, k_e)=C₁k_t+C₂k_e,

С₁+С₂=1, C_i≤0 (i=1,2)

Критерий останова

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

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

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

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

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

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

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