научная статья по теме АЛГОРИТМЫ ПОСТРОЕНИЯ РАСПИСАНИЙ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ, ДОПУСКАЮЩИЕ ИСПОЛЬЗОВАНИЕ ИМИТАЦИОННЫХ МОДЕЛЕЙ Математика

Текст научной статьи на тему «АЛГОРИТМЫ ПОСТРОЕНИЯ РАСПИСАНИЙ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ, ДОПУСКАЮЩИЕ ИСПОЛЬЗОВАНИЕ ИМИТАЦИОННЫХ МОДЕЛЕЙ»

= РАСПРЕДЕЛЕННЫЕ ВСТРОЕННЫЕ СИСТЕМЫ РЕАЛЬНОГО ВРЕМЕНИ

•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 рублей.

Показать целиком

Пoхожие научные работыпо теме «Математика»