ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2008, № 3, с. 133-142
СИСТЕМНЫЙ АНАЛИЗ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
УДК 681.3
ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ИМИТАЦИИ ОТЖИГА SIMULATED ANNEALING ДЛЯ ПОСТРОЕНИЯ МНОГОПРОЦЕССОРНЫХ
РАСПИСАНИЙ
© 2008 г. А. В. Калашников, В. А. Костенко
Москва, МГУ Поступила в редакцию 09.11.07 г.
Рассмотрены алгоритмы имитации отжига для решения задач построения многопроцессорных расписаний, предложен подход к их распараллеливанию и приведены результаты сравнительного исследования классического последовательного, последовательного и параллельного алгоритмов имитации отжига, использующих разбиение исходного пространства решений на области.
Введение. Алгоритмы имитации отжига в процессе поиска оптимального решения с некоторой вероятностью допускают переход в состояние с более высоким значением целевой функции. Это свойство позволяет им выходить из локальных оп-тимумов. Принципы, положенные в основу работы алгоритмов, можно объяснить на следующей физической аналогии [1]. На рис. 1 изображен шарик в коробке, внутренняя поверхность которой соответствует ландшафту целевой функции. При сильном встряхивании коробки в горизонтальном направлении шарик может переместиться из произвольной точки в любую другую. При постепенном уменьшении силы встряхивания будет достигнуто условие, когда эта сила обеспечивает перемещение шарика из точки А в точку В, но недостаточна для того, чтобы шарик мог переместиться из В в А. При дальнейшем уменьшении силы встряхивания до нуля шарик остановится в точке В - точке глобального минимума. В алгоритмах имитации отжига аналогом силы встряхивания является вероятность перехода в состояние с более высоким значением целевой функции. В начале работы алгоритма эта вероятность должна быть достаточно велика, чтобы была возможность перехода от выбранного начального приближения к любому другому решению. В процессе работы алгоритма вероятность перехода уменьшается в соответствии с выбранным законом.
Для многих ЛР-трудных задач наилучшие решения были получены алгоритмами имитации отжига. Однако их недостатком является высокая вычислительная сложность. Это обусловлено тем, что для получения хорошего решения требуется очень медленное понижение вероятности перехода в состояние с более высоким значением целевой функции, которое приводит к большому числу итераций алгоритма. При проектировании вычислительных систем реального времени на каждом этапе проектирования от аванпроекта до создания опытного
образца необходимо решение задачи построения статических многопроцессорных расписаний. Для оценки времени выполнения расписания используются имитационные модели. По мере детализации аппаратных и программных средств вычислительной системы сложность и соответственно время выполнения имитационных моделей увеличиваются. Кроме того, на начальных этапах часто поддерживается несколько версий разрабатываемой системы. В [2] показано, что алгоритмы имитации отжига могут применяться для построения расписаний выполнения прикладных программ на всех стадиях проектирования вычислительных систем реального времени. Однако для их практического внедрения актуальной остается задача уменьшения вычислительной сложности алгоритмов.
Одним из подходов, направленных на достижение этой цели, является разбиение пространства решений на области и поиск решения в каждой из них отдельно. Данный подход также позволяет строить параллельные алгоритмы с низким трафиком обмена между параллельными процессами. Построение алгоритма имитации отжига, основанного на этом подходе, требует решения следующих проблем:
Целевая функция
Рис. 1. Иллюстрация принципов работы алгоритмов имитации отжига
1) разбиение исходного пространства корректных решений на несколько непересекающихся областей, дающих в объединении все пространство;
2) выбор начального корректного решения в каждой из областей;
3) введение операций преобразования решения таким образом, чтобы они были замкнуты в каждой из областей;
4) выбор способа распределения областей по узлам вычислительной системы и схемы отсечения "неперспективных" областей в ходе работы алгоритма.
Для задач комбинаторной оптимизации решение этих проблем существенно зависит от конкретной задачи, так как структура пространства решений в каждом случае различна. В работе рассмотрены задачи построения многопроцессорных расписаний и приведены результаты сравнительного исследования классического последовательного, последовательного и параллельного алгоритмов имитации отжига, использующих разбиение исходного пространства решений на области.
1. Задача построения многопроцессорных расписаний. Общая задача построения статических многопроцессорных расписаний заключается в распределении и упорядочивании множества фиксированных работ (процессов) на заданное число ресурсов (процессоров) таким образом, чтобы оптимизировать желаемую меру эффективности расписания и выполнить заданные ограничения, которые обеспечивают корректность полученного решения. Прежде чем конкретизировать постановку задачи построения расписаний, определим модели исходных данных и самого расписания. При этом предполагаем, что выделение работ, подлежащих планированию, и параллелизм, допускаемый при выполнении программы, заданы (выявлены) предварительно.
Модель прикладной программы. В качестве модели прикладной программы будем использовать частный случай инварианта поведения программы, предложенного в [3], котрый является одной историей поведения программы для конкретного набора входных данных. Программа задается набором взаимодействующих процессов. Точками взаимодействия каждый процесс разбивается на упорядоченный набор рабочих интервалов. Модель программы может быть представлена размеченным ацикличным ориентированным графом Н(РЯ) = {Р, <}, где Р - множество вершин, соответствующих рабочим интервалам, < - множество дуг графа, отражающее взаимодействие рабочих интервалов. Отношение < представляется следующим образом: если р, < рк, то рабочий интервал р, необходимо выполнить до начала рабочего интервала рк. На < накладываются условия ацикличности и транзитивности. Каждая вершина имеет свой уникальный номер и метки: принадлежности рабочего интервала к процессу и вычислительной сложности рабочего интервала.
Вычислительная сложность рабочего интервала позволяет оценить время его выполнения на процессоре. Дуга определяется номерами смежных вершин и имеет метку, соответствующую объему данных обмена, который для каждой связи из < позволяет оценить затраты времени на выполнение внешнего взаимодействия.
Расписание выполнения программы. Расписание НР сформировано, если для каждого рабочего интервала введены привязка и порядок <НР. Привязка - всюду определенная на множестве рабочих интервалов функция, которая задает их распределение по процессорам. Порядок устанавливает ограничения на последовательность выполнения рабочих интервалов и является отношением частичного порядка, удовлетворяющим условиям ацикличности и транзитивности. Отношение порядка на множестве рабочих интервалов, распределенных на один и тот же процессор, представляет отношение полного порядка. Различные варианты расписаний могут быть получены изменением привязки и порядка в установленных ограничениями пределах, которые задаются требованием не нарушения отношения частичного порядка в модели поведения прикладной программы и определениями привязки и порядка.
Расписание НР корректно, если выполнены следующие ограничения:
1) каждый рабочий интервал должен быть назначен на процессор;
2) любой рабочий интервал обслуживает лишь один процессор;
3) частичный порядок, заданный в Н, сохранен
т т
в НР: <С <НР, <НР - транзитивное замыкание отношения <НР;
4) расписание НР должно быть беступиковым. Условием беступиковости при неограниченном размере буферов обмена является отсутствие контуров в графе НР: <НР - ациклично;
5) все рабочие интервалы одного процесса должны быть назначены на один и тот же процессор.
Ограничения 1)-4) обеспечивают сохранение инварианта поведения программы и являются обязательными. Ограничение 5) запрещает возобновление работы процесса после прерывания на другом процессоре, т.е. определяет способ организации параллельных вычислений в вычислительной системе (ВС). В дальнейшем будем говорить, что расписание
допустимо НР £ НР*-5, если оно удовлетворяет
ограничениям 1)-5). Нижний индекс в НР*-5 указывает ограничения, налагаемые на расписание.
Временная диаграмма выполнения программы. Она задана, если для каждого рабочего интервала установлены процессор, которому он соответсвует, и времена его начала и завершения. Временная диаграмма строится для заданных расписания и архи-
тектуры ВС или в ходе работы алгоритма. Согласно терминологии, используемой в теории расписаний, временная диаграмма также является одним из способов представления расписания. Однако в дальнейшем будем применять термин "временная диаграмма". Для ее построения приемлемы модели ВС различной степени детализации, получающие соответственно различную точность времен начала и завершения выполнения рабочих интервалов.
Задачу построения расписаний будем рассматривать в следующем варианте постановки.
Дано: H(PR) = (P,<) - модель программы, f(HP, HW) - функция вычисления времени выполнения расписания HP на архитектуре HW (целевая функция).
Требуется определить: HP- расписание выполнения программы.
Должны выполняться условия: T = f(HP, HW) —» min - минимум времени выполнения, HP £
£ HP*_5 - ограничения 1-5.
Функция вычисления времени выполнения расписания может быть задана в аналитическом виде или в виде имитационной модели.
2. Особенности задачи и анализ подходов к ее решению. Основными особенностями рассмотренной задачи построения расписания выступают:
1) задача является NP-трудной;
2) для большинства архитектур ВС целевая функция, с помощью которой оценивается качество полученного решения - вычислимая функция, т.е. задается в виде имитационной модели;
3) задача построения расписаний относится к классу задач комбинаторной оптимизации.
Выделим три укрупненных класса алгоритмов, различающихся по использу
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.