Лекция 9. Алгоритмы планирования вычислений в ИУС РВ (Лекции 2014-2015)

Алгоритмы планированиявычислений в ИУС РВКафедра АСВК,Лаборатория Вычислительных КомплексовКостенко В.А.Способы представления расписания1. Временная диаграмма – для каждой работызадано время начала выполнения s’(tj) ипроцессор на котором она выполняется.2. Привязка работ к процессорам и порядковыйномер выполнения работы на процессоре.3. Привязка работ к процессорам и приоритетработы.4. Статико-динамические расписания.124356PU1:23PU2:146577PU12PU2163574времяМеры оценки эффективности расписания1.

Время выполнения расписания.2. Число используемых процессоров длявыполнения множества работ за время непревышающее заданные директивный срок.3. Максимальное число совместимых работ.4. Критерии, основанные на использованиифункций штрафа за нарушение директивныхсроков работ.Конструктивные алгоритмы построениярасписаний3221456231t721463574t• Жадные алгоритмы• Метод ветвей и границ• Алгоритмы сочетающие жадные стратегии истратегии ограниченного перебораtИтерационные алгоритмы построениярасписанийf(HP)HP1••••HP2HP3HPАлгоритмы случайного поискаИмитация отжигаАлгоритмы локальной оптимизацииГенетические и эволюционные алгоритмыАлгоритмы имитации отжига(принцип работы)Алгоритмы имитации отжига(общая схема одной итерации)1.

HP=2. f(HP)=PU1:23PU2:14PU12PU2165635774время3. Проверка критерия останова4. HP =PU1:23PU2:145675. Выбор текущего приближения HPАлгоритмы имитации отжига(общая схема)5. Алгоритмы имитации отжига с некоторойвероятностью допускают переход в состояние сболее высоким значением целевой функции:1,P( HP k  HP k 1 )   f ),exp(TПоиск продолжается до тех пор,пока алгоритм не попадает вминимум, из которого он уже неможет выйти за счет тепловыхфлуктуацийf  0f  0Алгоритмы имитации отжига (системаопераций преобразования расписаний)O2PU1:PU2:23651721434Теорема. Для любых двух корректных O1расписаний HP1 и HP2 существуетцепочка операций {O1, O2},переводящая расписание HP1 в HP2так, что каждое промежуточноерасписание корректно и длинацепочки <=2N.657Алгоритмы имитации отжига(асимптотическая скорость сходимости)Чтобы достичь наперед заданной точности,нужно совершить число итераций,пропорциональное квадрату от размерапространства поиска.Алгоритмы имитации отжига(направленные стратегии примененияопераций)Стратегия уменьшения задержек.Утверждение.

Если время начала выполнениякаждой работы равно длине критического пути вграфе потока данных, то расписание будет иметьминимальное время выполнения.Стратегия заполнения простоев.Утверждение. Если простоев процессоров нет, торасписание будет иметь минимальное времявыполнения.Генетический алгоритм Холланда(SGA)• Holland J.N. Adaptation in Natural andArtificial Systems. Ann Arbor, Michigan:Univ. of Michigan Press, 1975.Генетический алгоритм Холланда(SGA)• Основан на использованиимеханизмов естественной эволюции:1.

Изменчивость→ операция мутации2. Наследственность→ операцияскрещивания3. Естесственный отбор → операция селекцииОсновные понятия• Популяция - это множество битовых строк.• Каждая строка - одно из возможныхрешений задачи.• По строке может быть вычислена функциявыживаемости, которая характеризуеткачество решения.• Основные операции алгоритма: селекция,скрещивание и мутация выполняются надэлементами популяции.Схема ГА1. Сгенерировать случайным образом популяциюразмера P.2.

Вычислить функцию выживаемости для каждойстроки популяции.3. Выполнить операцию селекции.4. Выполнить операцию скрещивания:– 4.1. Выбрать пары для скрещивания.– 4.2. Для каждой выбранной пары выполнитьскрещивание, получить двух потомков и произвести впопуляции замену родителей на их потомков.5. Выполнить операцию мутации.6.

Если критерий останова не достигнут, перейти кп.2, иначе завершить работу.Требования к кодированию решений1. Однозначность: каждая закодированнаястрока должна соответствоватьединственному решению исходной задачи.2. Возможность кодирования любогодопустимого решения.3. Получение в результате генетическихопераций корректных вариантов решений.4. Возможность перехода от любого корректногорешения к любому другому корректномурешению.Требования к кодированию решений•Для задач непрерывного и целочисленногомат.

программирования, оптимизируемыепараметры задаются:– двоичным кодом числа,– кодами Грея.Создание начальной популяции• Случайным образом генерируетсяначальная популяция в пределахдопустимых значений (в областипоиска):Функция выживаемости• Выбирается согласно предметной области• Определяет качество решения• Применяется ко всем элементам популяцииОперация селекции• Схема пропорциональной селекции:• Схема рулетки:…Операция скрещиванияОперация мутацииКритерий останова• Процесс продолжается итерационно• Варианты критерия останова:– Выполнение заданного числа итераций– Выполнение заданного числа итераций без улучшения– Достижение заданного значения функциивыживаемостиCхемыCхемыпримеры схемCхемы• Порядок схемы (K)- количествофиксированных позиций в схеме:Cхемы• Определяющая длина схемы (L)– расстояниемежду самыми дальними фиксированнымипозициями:CхемыCхемы• Для любой схемы, представляющейхорошее решение, нужно, чтобыколичество ее примеровувеличивалось с увеличениемколичества итераций• На преобразование схем влияютоперации ГА: мутация, скрещивание иселекцияТеорема схемТеорема схемТеорема схемТеорема схемТеорема схемТеорема схем• Проблема выбора параметров ГА являетсядля многих приложений сложной задачей• Теоретические результаты для решенияданной проблемы на данный моментотсутствуют• На практике данная проблема решаетсяэкспериментальным путемГипотеза строительных блоков• Строительные блоки - схемы с низкимпорядком, малыми определяющими длинамии большими значениями средних целевыхфункций.• Гипотеза строительных блоков:комбинирование хороших строительныхблоков дает хорошую строку.Муравьиные алгоритмы(биологическая модель)1.

Изначальновероятности выборамаршрутов равны2. Муравьи, выбравшиекратчайший маршрут,возвращаютсябыстрее, количествоферомона на короткихмаршрутах больше3. Вероятность выборакратчайшего маршрутаповышаетсяМуравьиные алгоритмы(МА для решения задачи коммивояжера)Общая схема итерации:• «Создание» муравьев• Построение маршрутовмуравьями• Обновлениеферомонного следа нанайденных маршрутахМуравьиные алгоритмы(построение маршрута и обновление феромонов)ji   ij t     ij t  , j  Lk   t    t Pij , k t   ilil lJ k0, j  Lkm ij t  1  1  p  ij t     ij, k t k 1 F Tk t , i, j   Tk t  ij, k t   0, i, j   Tk t Муравьиные алгоритмы(использование для построения расписаний)Построение маршрутовПостроение расписанийпо маршрутамВычисление целевыхфункциидаостанов?нетОбновлениеферомонного следаАлгоритмы случайного поиска•Основой методов случайного поиска служититерационный процесс:X X  , k  0,1,,k 1kk k – величина шага,  (1,,n) – некоторая реализация n-мерногослучайного вектора .•Л.А.

Растригин. Статистические методыпоиска.- М.: Наука, 1968.Алгоритмы случайного поискаf(X)=C1X*f(X)=C2f(X)=C3Алгоритмы случайного поиска•алгоритм с парной пробой,•алгоритм с возвратом при неудачном шаге,•алгоритм наилучшей пробы,•алгоритм с линейной экстраполяцией,•алгоритм статистического градиента,•алгоритмы с самообучением.Алгоритмы случайного поиска(параметры алгоритма)начальный шаг α > 0,коэффициент уменьшения шага γ > 1,предельное число неудачных попыток K,параметр точности ε > 0,начальное приближениеX 0.Записать схему алгоритма, показать завершимость идостижение параметра точности.Конструктивные алгоритмы построениярасписаний3221456231t721463574t• Жадные алгоритмы• Метод ветвей и границ• Алгоритмы сочетающие жадные стратегии истратегии ограниченного перебораtЖадные алгоритмы(общая схема)Разложимые функции:min f ( x, y)  min f1 ( x, min f 2 ( y))( x, y )( x)( y)1.

Выбрать очередную работу ≡ переменную xили у.2. Выбрать в соответствии с локальной функцией(f1,f2) место размещения работы ≡ присвоитьзначение переменной.Жадные алгоритмы(построение расписания выполнения работв одноприборном устройстве)• Для частной задачи:max HH H *' j: t j  f j  s j• известен оптимальный жадный алгоритмсложности O(n∙log n).Жадные алгоритмы(GrA - алгоритм построения расписания дляодноприборного устройства)1. Упорядочиваем работы по возрастанию fj.Заявки с одинаковым значением fjрасполагаем в произвольном порядке.Сложность - O(n∙log n).2. Размещаем в расписание работу j=1.3.

Ищем первую работу для которой si≤ fj ,размещаем ее в расписание и j=i.4. Шаги 2, 3 повторяем пока список неисчерпан. Количество повторов - O(n).Жадные алгоритмы(оптимальность алгоритма GrA)Теорема. Алгоритм GrA включает в расписаниенаибольшее возможное количество совместимыхработ.Доказательство.Если в каком-то оптимальном расписании работа 1отсутствует, то можно в нем заменить заявку с самымменьшим f на работу 1.Не нарушится совместимость работ и не изменится ихколичество в расписании.Жадные алгоритмы(оптимальность алгоритма GrA)Т.е. можно искать оптимальное расписание содержащееработу 1 → существует оптимальное расписание,начинающееся с жадного выбора.Из исходного набора можно удалить все работынесовместимые с 1.Задача сводится, к выбору набора работ из множестваоставшихся работ, т.е.

мы свели задачу к аналогичнойзадаче с меньшим числом работ.Рассуждая по индукции, получаем, что делая на каждомшаге жадный выбор, мы придем к оптимальномурасписанию.Жадные алгоритмы (как доказать, что алгоритмполучает оптимальное решение)1. Доказываем что жадный выбор на первомшаге не исключает возможности полученияоптимального решения.2. Показываем, что подзадача, возникающаяпосле жадного выбора на первом шаге,аналогична исходной.3. Рассуждение завершается по индукции.Алгоритмы сочетающие жадные стратегии истратегии ограниченного перебораВыбор очередной работы(k1)Построение мн.

допустимых мест (А)для размещения работы в расписаниенетА=0даВыбор местаразмещения (k2)Разместить работув расписаниеВызов процедурыограниченного перебораПример процедуры ограниченного перебора0.4M1M2M30.20.40.20.10.50.50.40.30.30.40.1Материалы курса• http://lvk.cs.msu.su/courses/– Презентации лекций– Вопросы к экзамену (скоро)– Оттиски статей.