= РАСПРЕДЕЛЕННЫЕ ВСТРОЕННЫЕ СИСТЕМЫ РЕАЛЬНОГО ВРЕМЕНИ
•V. 'К 681.3
АЛГОРИТМЫ ПОСТРОЕНИЯ РАСПИСАНИЙ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ, ДОПУСКАЮЩИЕ ИСПОЛЬЗОВАНИЕ ИМИТАЦИОННЫХ
МОДЕЛЕЙ
© 2013 г. В.А. Костенко
Факультет вычислительной математики и кибернетики МГУ им. М.В. Ломоносова 119991 ГСП-1, Ленинские горы, МГУ, д. 1, стр. 52 E-mail: ko.st@cs.msu.su Поступила в редакцию 02.02.2013
Одним из важнейших требований к функционированию вычислительных систем реального времени (ВСРВ) является соблюдение директивных сроков выполнения прикладных программ. При нарушении директивных сроков, ВСРВ теряет свою работоспособность. В связи с этим возникает проблема обеспечения требуемой точности оценки времени выполнения прикладных программ. В работе предлагается подход к построению итерационных алгоритмов построения расписаний, в которых для оценки времени выполнения расписания прикладных программ могут использоваться имитационные модели с различной степенью детализации, что позволяет обеспечить требуемую точность оценки времени выполнения программ. Предложенный в работе подход может быть использован для построения итерационных алгоритмов следующих классов: генетические и эволюционные алгоритмы, алгоритмы имитации отжига, алгоритмы случайного поиска, локально-оптимальные алгоритмы.
1. ВВЕДЕНИЕ
Большинство современных бортовых вычислительных систем реального времени (ВСРВ) являются распределёнными. В работе [1] был предложен подход к разработке распределенных программ для ВСРВ в среде имитационного моделирования методом пошаговой детализации компонентов программы и модели аппаратных средств. Среда имитационного моделирования должна позволять описывать программы и аппаратные средства с различной степенью детализации и выполнять оценку наихудшего времени выполнения программ. Кроме этого на каждом уровне детализации должны решаться задачи проверки правильности свойств, как всей программы, так и ее отдельных компонент и построения расписания выполнения программы.
В данной работе предлагается подход к разработке итерационных алгоритмов построения расписаний, в которых для оценки времени вы-
полнения расписания программ могут использоваться имитационные модели с различной степенью детализации. Предложенный в работе подход может быть использован для построения итерационных алгоритмов следующих классов: генетические и эволюционные алгоритмы, алгоритмы имитации отжига, алгоритмы случайного поиска, локально-оптимальные алгоритмы.
В разделе 2 определены модель прикладной программы, модель расписания, условия его корректности и временная диаграмма выполнения расписания. В третьем разделе рассмотрена общая схема итерационных алгоритмов построения расписаний; сформулированы задачи, которые необходимо решить для построения конкретного алгоритма, и рассмотрены наиболее широко применяемые подходы к построению итерационных алгоритмов: схемы случайного поиска (ненаправленный случайный поиск, направленный случайный поиск без самообучения,
направленный случайный поиск с самообучением), схема имитации отжига, генетические и эволюционные алгоритмы. В разделе 4 для алгоритмов использующих лишь унарные операции преобразования расписания введены способ представления расписаний и система операций преобразования расписаний, для которой доказаны ее полнота и замкнутость в пространстве корректных расписаний; доказано, что для двух любых корректных расписаний существует линейная последовательность операций, переводящая одно расписание в другое, такая, что все промежуточные расписания корректны и введена метрика в пространстве корректных расписаний. В разделе 5 приведены стратегии применения операций преобразования расписания (какую операцию применять, к какой работе, на какую позицию в расписании перемещать работу), которые могут быть использованы для широкого класса архитектур ВСРВ. В разделе 6 рассмотрен способ представления расписаний, позволяющий использовать известные операции мутации и скрещивания для целочисленного кодирования решений; доказано, что любое корректное расписание может быть задано предложенным способом. В разделе 7 приведен краткий аналитический обзор известных методов построения параллельных итерационных алгоритмов, в разделе 8 предложен и обоснован метод распараллеливания алгоритмов построения расписаний, которые используют лишь унарные операции преобразования расписаний.
2. МОДЕЛЬ ПРИКЛАДНОЙ ПРОГРАММЫ И РАСПИСАНИЯ
Модель прикладной программы. В качестве модели прикладной программы будем использовать частный случай инварианта поведения программы предложенного в работах [2, 3]. Следуя этим работам, обозначим поведение программы БЬ(РЯ) и определим БН(РЯ) следующим образом: БН(РЯ) =< Б, (Я-(РЕ)}, (Я ^ (РЕ)} >, где Б - множество всех возможных шагов процессов в допустимом диапазоне входных данных программы, (Я ^ (РЯ)} - отношения, определяющие частичный порядок на множестве шагов каждого процесса, (Я— (РЯ)} - отношения взаимодействия между процессами.
Шаги процесса определяются последовательностью взаимодействий с другими процессами. Назовем рабочим интервалом процесса внутренние действия процесса между двумя последовательными взаимодействиями с другими процессами. Каждый рабочий интервал процесса по существу является реализацией соответствующего шага процесса.
Для задачи построения расписания будем использовать одну из историй поведения программы Н(РЯ) € БН(РЯ) (поведение программы для конкретного набора входных данных). Для Н(РЯ) отношение (Я ^ (РЯ)} является отно-
Б
ется до множества шагов, которые делают процессы для конкретного набора входных данных.
Н(РЯ) можно представить ациклическим ориентированным размеченным графом. Вершинам Р = (Ы^1! и (Рг}^=21 и ■ ■ ■ и (Рг}^ этого графа соответствуют рабочие интервалы процессов, дугам —= (<гк = (рг, рк)}(г,к)е(1...м) ~ связи, определяющие взаимодействия между рабочими ин-
Р
единением отношений (Я— (РЯ)}, (Я ^ (РЯ)}). Где (Рг}г=1 — множество рабочих интервалов го процесса, N3 - число рабочих интервалов в ^'-ом процессе, К - число процессов в программе РЯ, N = N1 + N2 + ■ ■ ■ + Nк - мощность мно-Р.
личных процессов, назначенных на один и тот же процессор, допустимо, если не нарушается частичный порядок, заданный отношением — . Отношение <гк представляется следующим образом: если рг -гк Рк, то рабочий интервал рг, необходимо выполнить до начала выполнения рабочего интервала рк .На — накладываются условия ацикличности и транзитивности. Каждая вершина имеет свой уникальный номер и метки: принадлежности рабочего интервала к процессу и вычислительной сложности рабочего интервала . Вычислительная сложность рабочего интервала позволяет оценить время выполнения рабочего интервала на процессоре. Дуга определяется номерами смежных вершин и имеет метку, соответствующую объему данных обмена (-игк}(г,к)е(1...м). Объем данных обмена для каждой связи из позволяет оценить затраты времени на выполнение внешнего взаимодействия.
Расписание выполнения программы определе-
но, если заданы: 1) множества процессоров и рабочих интервалов, 2) привязка, 3) порядок. Привязка - всюду определенная на множестве рабочих интервалов функция, которая задает распределение рабочих интервалов по процессорам. Порядок задает ограничения на последовательность выполнения рабочих интервалов и является отношением частичного порядка на множестве рабочих интервалов, удовлетворяющим условиям ацикличности и транзитивности. Отношение порядка на множестве рабочих интервалов, распределенных на один и тот же процессор, является отношением полного порядка.
Модель расписания выполнения программы определим графом НР = ({БРг}г=(Х.м), —нр). Где {БРг}г=(Х.м) ~ набор простых цепей (ветвей параллельной программы). Они образуются рабочими интервалами процессов, распределенными на один и тот же процессор (М - число процессоров в ВСРВ). Отношение частичного порядка —нр на множестве Р для НР определим как объединение отношений: —нр=—с и — х и-'-и —м, —г _ отношение полного порядка на БРг, которое определяется порядковыми номерами рабочих интервалов в БРг; —с - набор секущих ребер, которые определяются связями рабочих интервалов, распределенных на разные процессоры. Если рабочие интервалы рг и pj распределены на разные процессоры и в — существует связь , то она определяет секущее ребро в графе НР. На отношение — нр накладываются условия ацикличности и транзитивности.
Условия корректности расписания. Расписа-НР
риант поведения программы), если выполнены следующие ограничения:
1. Каждый рабочий интервал должен быть назначен на процессор (в БРг).
2. Каждый рабочий интервал должен быть назначен лишь на один процессор (в один БРг).
Н
НР
лнр
-транзитивное замы-
кание отношения —нр . НР
вым, т.е. в графе НР нет контуров: —нр _ ациклично.
5. Все рабочие интервалы одного процесса должны быть назначены на один и тот же процессор (в один и тот же БРг).
Ограничения 1-4 обеспечивают сохранение инварианта поведения программы и являются обязательными. Ограничение 5 запрещает возобновление работы процесса после прерывания на другом процессоре, т.е. определяет способ организации параллельных вычислений в ВСРВ, и не всегда является обязательным. В дальнейшем будем говорить, что расписание корректно НР £ НР^_5, если оно удовлетворяет ограничениям 1-5, здесь НР^_5 - множество всех корректных расписаний для заданной модели программы Н (РЯ). Нижний индекс в НР^_5 указывает ограничения, налагаемые на расписание.
Временная диаграмм,а выполнения, расписания, НР на архитектуре ВСРВ НШ задана, если для каждого рабочего интервала задан номер процессора, на котором он выполняется, и время начала выполнения и завершения выполнения рабочего интервала. Временная диаграмма может быть получена совместной интерпретацией моделей НШ и НР : ТЯ = Мой(НР, НШ). Получение приемлемых по точности оценок времени начала и завершения выполнения рабочих интервалов во многих случаях возможно лишь с использованием имитационных моделей ВСРВ, т.е. функция ТЯ = Мой(НР, НШ) задается имитационной моделью.
3. ИТЕРАЦИОННЫЕ АЛГОРИТМЫ
Общую схему итерационных алгори
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.