автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Совместное планирование вычислений и обменов в информационно-управляющих системах реального времени

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. Ломоносова

На правах рукописи

Шестов Пётр Евгеньевич

Совместное планирование вычислений и обменов в информационно-управляющих системах реального времени

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

15 АВГ 2013

ии&532055

Москва - 2013

005532055

Работа выполнена на кафедре автоматизации систем вычислительных комплексов факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова.

Научный руководитель:

кандидат технических наук, ведущий научный сотрудник Костенко Валерий Алексеевич доктор технических наук,

Официальные оппоненты:

профессор Топорков Виктор Васильевич

кандидат технических наук, Гончар Дмитрий Русланович

Ведущая организация:

ОАО «НИИВК им. М.А. Карцева»

Защита состоится 20 сентября 2013 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М.В. Ломоносова, расположенном по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-ой учебный корпус, факультет вычислительной математики и кибернетики, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. (495) 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М.В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте ВМК МГУ http://cs.msu.ru в разделе «Наука» — «Работа диссертационных советов» — «Д 501.001.44».

Автореферат разослан « £~ » августа 2013 г.

Ученый секретарь диссертационного совета,

к.т.н, в.н.с.

Костенко В.А.

Общая характеристика работы

Актуальность работы. Информационно-управляющие системы реального времени (ИУС РВ) используются для управления сложными техническими системами. Например, летательными аппаратами, кораблями, искусственными спутниками и т.п. Одним из важнейших требований к функционированию ИУС РВ является выполнение ограничений реального времени. Ограничения реального времени задаются в виде директивных интервалов для прикладных задач и сообщений. Прикладные задачи должны быть выполнены в рамках заданных директивных интервалов. Сообщения должны быть переданы в рамках заданных директивных интервалов. При нарушении этих ограничений ИУС РВ теряет свою работоспособность. На всех этапах разработки ИУС РВ необходимо строить расписание выполнения прикладных задач и расписание передачи сообщений для проверки возможности выполнения ограничений реального времени.

Разработка подобных ИУС РВ является сложным техническим процессом. Часто возникает задача модернизации таких систем, либо повторного использования отдельных подсистем ранее разработанных ИУС РВ. Причем изменение функционирования повторно используемых подсистем невозможно. Отсюда следует, что они обладают фиксированным интерфейсом, с помощью которого остальные устройства (в том числе другие подсистемы) в составе ИУС РВ взаимодействуют с такими подсистемами. Фиксирован формат сообщений и состав слов данных, которые получают и передают подсистемы.

К функционированию ИУС РВ предъявляется ряд требований, связанных не только с работой в реальном времени, но и обусловленных используемыми техническими стандартами, протоколами обмена данных, особенностями работы аппаратных и системных программных средств.

Настоящая диссертация посвящена алгоритмам построения совместимых

расписаний выполнения прикладных задач (работ) и передачи сообщений в ИУС РВ. Расписания выполнения работ и передачи сообщений в таких системах строятся статически. В качестве среды передачи данных в работе рассматривается канал с централизованным управлением.

Исходными данными для задачи построения расписаний являются наборы работ и сообщений, передающих данные между работами. При этом повторно используемые подсистемы рассматриваются как множества работ, выполняющихся на выделенных вычислительных модулях, на которых недопустимо выполнение других работ. На расписание передачи сообщений накладываются дополнительные ограничения, связанные с особенностями аппаратных и программных средств обеспечения работы канала с централизованным управлением. В дальнейшем такие ограничения будем называть технологическими. Задача построения совместимых расписаний состоит в нахождении расписаний выполнения работ и передачи сообщений, содержащих максимально возможное число работ и сообщений. Под совместным планированием вычислений и обменов будем понимать решение этой задачи. Актуальность разработки алгоритмов построения совместимых расписаний подтверждается особенностями рассматриваемой задачи, отличающими ее от других задач построения расписаний, а именно:

• необходимость планирования заданий двух типов: работ и сообщений;

• наличие двух типов работ: работ, подлежащих планированию, и работ в составе подсистем, которые не подлежат планированию;

• время передачи сообщения зависит от расписания выполнения работ, а именно от того, на какие вычислительные модули размещены передающая и принимающие работы;

• присутствуют технологические ограничения на корректность расписа-

ния;

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

Цель работы. Целью диссертационной работы является разработка и исследование свойств алгоритмов построения расписания выполнения задач на вычислительных модулях в составе ИУС РВ и расписания передачи сообщений между ними с соблюдением: ограничений реального времени; ограничений на их совместимость; ограничений, связанных со спецификой аппаратных и программных средств ИУС РВ.

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

Научная новизна. В диссертации сформулирована новая математическая постановка задачи построения совместимых расписаний выполнения задач и передачи сообщений между ними. Разработаны и исследованы алгоритмы решения этой задачи, относящиеся к классу жадных алгоритмов, а также алгоритм, гарантирующий максимально возможное число запланированных работ и сообщений. Теоретически полученные результаты расширяют класс задач, рассматриваемых в теории расписаний.

Теоретическая и практическая ценность. Теоретическая ценность работы состоит в постановке новой задачи построения расписаний, возникающей при модификации ИУС РВ и разработке новых ИУС РВ на базе существующих, и построении алгоритмов решения этой задачи. Свойства предложенных алгоритмов были исследованы на тестовых и реальных данных.

Практическая значимость обусловлена тем, что использование полученных результатов обеспечивает поддержку процесса модернизации ИУС РВ и разработки новых ИУС РВ на базе существующих. Практическая значимость рассмотрения ИУС РВ с каналом с централизованным управлением подтверждается существованием ряда промышленных стандартов на такие каналы (MIL STD-1553B / МКИО ГОСТ Р 52070-2003, STANAG 3910, Fibre Channel FC-AE-1553), а также широким применением этих стандартов при создании ИУС РВ.

Апробация работы. Результаты, представленные в работе, докладывались на научных семинарах лаборатории Вычислительных комплексов кафедры Автоматизации систем вычислительных комплексов факультета ВМК МГУ под руководством профессора P. J1. Смелянского, семинаре кафедры Автоматизации систем вычислительных комплексов под руководством чл.-корр. РАН JT.H. Королева а также на следующих конференциях:

• Третья европейская конференция по аэрокосмическим наукам (3rd Europea Conference for Aerospace Sciences, EUCASS'2009) (Франция, Версаль, июль 2009 г.);

• VI Московская Международная конференция по исследованию операций (ORM-2010) (Москва, октябрь 2010 г.);

• Одиннадцатая международная конференция по программируемым устройствам и встроенным системам (11th IFAC/IEEE International Conference on Programmable Devices and Embedded Systems «PDeS 2012») (Чехия, Брно, май 2012);

• VI Международная конференция «Параллельные вычисления и задачи управления» (РАСО'2012) (Москва, октябрь 2012).

Публикации. По теме диссертации имеется 6 публикаций, список которых приводится в конце автореферата; 2 из них опубликованы в журналах из списка ВАК.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения, списка литературы и четырёх приложений. Объём работы — 113 страниц, с приложениями — 134 страницы. Список литературы содержит 75 наименований.

Основное содержание работы

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

В первой главе приводится содержательная постановка задачи построения совместимых расписаний выполнения работ и передачи сообщений. Описываются особенности работы ИУС РВ и канала с централизованным управлением. Одной из главных особенностей является наличие подсистем, изменение функционирования которых невозможно. Каждая подсистема рассматривается как набор работ (прикладных задач), выполняющихся на одном вычислительном модуле, назначение выполнения других работ на этот модуль недопустимо. Работы из таких наборов будем называть работами-подсистемами. Широко применяется схема информационного обмена, при которой сообщения, передающиеся по каналу с централизованным управлением, должны передавать группами, называемыми цепочками. Сообщениями, принадлежащие одной цепочке, должны передаваться без пауз. Максимальное количество сообщений в цепочке не должно превышать заданного значения гтсс, их общая длительность не должна превышать заданного значения гтс^, меж-

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

Далее вводится математическое представление исходных данных. Исходные наборы работ и сообщений представляются в виде ориентированного ациклического графа с двумя типами вершин. Первый тип соответствует работам (в том числе работам-подсистемам), второй — сообщениям. Дугами графа задаётся частичный порядок на множествах работ и сообщений. При этом у каждого сообщения должна быть ровно одна работа-отправитель и не менее одной работы-получателя. Если две работы соединены дугой, то они обе должны быть запланированы на один и тот же вычислительный модуль, а данные между ними передаются без участия канала через внутреннюю память вычислительного модуля. Работы-подсистемы не подлежат планированию, но участвуют в передаче и приёме сообщений наряду с другими работами.

Для каждой работы г 6 \У заданы директивные сроки начала и завершения выполнения, набор допустимых вычислительных модулей. Задана функция, вычисляющая длительность выполнения работы на каждом допустимом вычислительном модуле. Для каждого сообщения ^ 6 М заданы директивные сроки начала и завершения передачи. Длительность передачи сообщения зависит от того, на каких вычислительных модулях выполняются передающая и принимающие работы, и может быть вычислена для любого варианта привязки работ.

Расписание выполнения работ Н\у представляет собой множество троек вида <работа г, номер вычислительного модуля на котором выполняется работа г, время начала выполнения работы г>: 7/ц/ = {(г, р./, а^')} . Расписание называется корректным, если выполнены следующие ограничения:

1) каждая работа включена не более чем в одну тройку (дШ1 {Н\у) < 0);

2) требование реального времени, т.е. каждая работа выполняется в рамках своего директивного интервала (ди)2 (Нцг) < 0);

3) на одном и том же вычислительном модуле в каждый момент времени может выполняться только одна работа (дтз (Нцг) < 0);

4) каждая работа должна быть запланирована только на допустимый для неё вычислительный модуль (дт4 (Н\у) < 0).

Расписание передачи сообщений Нм представляет собой множество пар вида <сообщение j, время начала передачи сообщения Нм = {(¿,5™)}-Расписание называется корректным, если выполнены следующие ограничения:

1) общие ограничения для одноприборных систем без прерывания работ:

а) каждое сообщение включено не более чем в одну пару {дті (Нм) < 0);

б) требование реального времени, т.е. каждое сообщение должно быть передано в рамках своего директивного срока (дт2 (Нм) < 0);

в) в каждый момент времени может передаваться только одно сообщение (дт3 (Нм) < 0);

2) ограничения корректности, обусловленные технологическими требованиями к обмену данными (дт4 (Нм) < 0).

Пара расписаний выполнения работ и передачи сообщений Н = (Н\у, Нм) называется совместимой, если выполнены следующие ограничения:

1) ограничения корректности для расписания выполнения работ;

2) ограничения корректности для расписания передачи сообщений;

3) в расписании передачи сообщений запланированы все сообщения, передающие данные, необходимые для выполнения запланированных работ (9l (Hw, Им) < 0);

4) в расписании выполнения работ запланированы все работы, формирующие данные, передающиеся в запланированных в расписании обменов сообщениях (f]2 (H\V) Нм) < 0);

5) в расписании выполнения работ все работы, передающие данные запланированным работам через внутреннюю память вычислительных модулей, запланированы на тот же вычислительный модуль, что и получатели данных (<73 (Н\у, Нм) < 0).

Задача построения совместимых расписаний выполнения работ и передачи сообщений состоит в построении расписаний, содержащего максимальное количество работ и сообщений, соответствующих вершинам графа исходных данных, и удовлетворяющего ограничениям корректности:

max \Н\,

{Я}

< 9w,i {Hw) <0, г = 1,2,3,4, ^

9mj{Hm)< 0, j = 1,2,3,4, . 9к{Н)< 0, fc = 1,2,3,

где \Н\ = \Hw \ + \Нм\ — суммарное количество работ и сообщений, запланированных в расписаниях.

Утверждение 1. Задача построения совместимых расписаний является NP-трудной.

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

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

1) у каждого сообщения предполагается наличие только одного получателя;

2) отсутствуют технологические ограничения;

3) другой критерий оптимальности расписания (минимизируются суммарные нарушения временных ограничений, т.е. директивные сроки могут нарушаться).

Описываются возможные подходы к решению задачи построения совместимых расписаний. Первая группа подходов основана на декомпозиции задачи на две. Сначала строится одно из двух расписаний (работ или сообщений), затем соответствующим образом изменяются исходные данные и строится оставшееся расписание. В работе показано, что вне зависимости от того, какое расписание строится первым, существуют частные задачи, допускающие построение полных и корректных совместимых расписаний, но для которых невозможно его построение в рамках этих подходов. Поэтому в диссертационной работе описываются алгоритмы, основанные на другом подходе: представление канала с централизованным управлением как специализированного вычислительного модуля и одновременное построение расписаний выполнения работ и передачи сообщений.

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

В третьей главе описываются предлагаемые алгоритмы построения

совместимых расписаний. Жадный алгоритм построения совместимых расписаний на каждой итерации основного цикла вычисляет самое раннее время, на которое возможно планирование работ и сообщений, а так же отбирает те из них, которые могут быть запланированы на это время. Время вычисляется с учетом технологических ограничений на расписание передачи сообщений. Из отобранных работ и сообщений согласно заранее заданному жадному критерию выбирается одна работа или одно сообщение, которое и размещается в расписание на ранее выбранное место. Основная сложность заключается в том, что точное время передачи сообщения не известно до привязки к вычислительным модулям работ, участвующих в передаче этого сообщения. В предлагаемом жадном алгоритме эта проблема решается следующим образом. Длительность передачи любого сообщения считается равной максимально возможной. После размещения в расписание работы просматриваются ранее запланированные сообщения для уточнения длительности передачи. Если найдено сообщение с изменившейся длительностью передачи, то осуществляется привязка принимающих его работ к вычислительным модулям, удаление из расписания всех работ и сообщений, запланированных после найденного сообщения, и его перепланирование с учетом изменившейся длительности. Доказаны завершимость и корректность этого алгоритма, найдены нижняя и верхняя оценка вычислительной сложности.

Другой из предложенных алгоритмов гарантирует нахождение совместимых расписаний, содержащих максимально возможное количество работ и сообщений. Он основан на декомпозиции задачи на три подзадачи:

1) построение привязки работ к вычислительным модулям;

2) при заданной привязке нахождение порядка выполнения работ на вычислительных модулях и передачи сообщений по каналу;

3) при заданных привязке и порядке выполнения и передачи нахождение

времён начала выполнения работ и передачи сообщений.

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

Для подзадачи построения привязки работ к вычислительным модулям вершины дерева решений представляют собой привязки работ к вычислительным модулям, а при порождении новой вершины очередная неразмещенная работа привязывается к какому-либо вычислительному модулю. Будем говорить, что в вершине дерева решений этой подзадачи рассматриваются все привязанные к вычислительным модулям работы и сообщения, которые они передают. Для подзадачи нахождения порядка выполнения работ и передачи сообщений вершины дерева решений представляют собой упорядоченные списки работ (по одному для каждого вычислительного модуля) и упорядоченный список сообщений. Будем говорить, что в вершине дерева решений этой подзадачи рассматриваются все работы и сообщения из этих списков. Эти списки задают порядок, в котором работы будут выполняться на соответствующем вычислительном модуле или в котором будут передаваться сообщения. При порождении новой вершины в конец каждого из списков добавляется одна работа или одно сообщение. Вершин порождается столько, сколько существует способов это сделать. Для оценки вершин в обоих алгоритмах используются одни и те же величины. Введём следующие обозначения: Ну — корректное расписание, построенное в вершине V, У/у и

му — подмножества работ и сообщений соответственно, рассматриваемые в вершине V. Заметим, что Ну может не содержать все рассматриваемые в вершине V работы и сообщения. Оценка снизу равна количеству работ и сообщений, которые были запланированы в расписании для данной вершины: Утгп = Доказано, что эта оценка равна гарантированному (минималь-

ному) количеству работ и сообщений, которое может быть запланировано в наиболее полных корректных расписаниях для любой вершины в поддереве с корнем в данной вершине. Оценка сверху для вершины V дерева решений равна общему числу работ и сообщений в исходных данных задачи минус число работ и сообщений, которые не удалось запланировать в корректном расписании для данной вершины: Утах = |Ж| + |М| — + \МУ\ —

Если расписание Ну не содержит все рассматриваемых в вершине работ и сообщений, то величина в скобках отлична от нуля. Доказано, что Утах равно максимально возможному количеству работ и сообщений, которое может быть запланировано в наиболее полном корректном расписании для любой вершины в поддереве с корнем в данной вершине. При наличии двух вершин V и V', для которых верно > У^ах, отсекается ветвь дерева решений с корнем в вершине У. Из доказанных свойств нижней и верхней оценок следует, что алгоритмом заведомо не будет отсечено поддерево, содержащее оптимальное решение.

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

преобразований расписания возможное начало передачи сообщения смещается на более раннее время, и сообщение может быть передано в рамках своего директивного интервала.

Последний разработанный алгоритм является жадным и допускает возможность сдвига уже построенного расписания. В случае невозможности разместить в конец расписания выбранную по жадному критерию работу или сообщение производится попытка запланировать между уже запланированными работами и сообщениями, сдвигая времена их начала выполнения и передачи. При этом минимизируется один из двух критериев: минимальное суммарное время, на которое сдвинуться времена начала выполнения ранее запланированных работ или передачи ранее запланированных сообщений; самое раннее время, на которое возможно запланировать текущую рассматриваемую работу или сообщение. Иными словами, работу или сообщение можно пытаться запланировать как можно раньше, а можно так, чтобы по минимуму сдвигать уже запланированные работы и сообщения. Доказаны заверши-мость и корректность этого алгоритма, найдены нижняя и верхняя оценка вычислительной сложности.

В четвёртой главе приведено описание методики и результаты экспериментального исследования разработанных алгоритмов. Целью экспериментального исследования разработанных алгоритмов была оценка их эффективности по следующим критериям:

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

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

Дополнительно для жадного алгоритма замерялось количество изменений расчетной длительности передачи сообщений. Для алгоритма на основе

методе ветвей и границ замерялось количество рассмотренных вершин дерева решений. Эти величины являются определяющими для вычислительной сложности алгоритмов.

Исследования проводились на пяти различных классах исходных данных, наборы данных в этих классах генерировались на основе данных с реальной ИУС РВ навигационного назначения. Для обработки результатов экспериментов применялись методы математической статистики. Это позволило исключить маловероятные значительные отклонения измеряемых характеристик, а так же сделать обобщенные выводы об их принадлежности некоторым диапазонам (не только применимыми к данной выборке). Для замеряемых характеристик работы алгоритмов находились такие диапазоны значений, что статистически достоверной (с уровнем значимости равным 0.05) является гипотеза о том, что с вероятностью 90% любое значение характеристики будет лежать в этом диапазоне.

Исследование эффективности жадного алгоритма проводилось с использованием трёх различных эвристик выбора работы или сообщения для размещения на текущем шаге:

1) минимальный директивный срок завершения;

2) минимальное раннее время завершения;

3) максимальное общее число непосредственных и транзитивных потомков.

Наилучшие результаты были достигнуты с применением первой из них. Основной вклад в вычислительную сложность алгоритма даёт количество изменений расчетной длительности передачи сообщений. При максимуме равном 2Пм « 285 (пм ~ количество сообщений, которое в среднем равнялось 85) наибольшее полученное значение равнялось 26, а при использовании эв-

ристики «минимальный директивный срок завершения» — 14. Для жадного алгоритма со сдвигом расписания наилучшие результаты показала последняя эвристика. Почти во всех случаях жадный алгоритм без сдвига расписаний показывает лучшие результаты, чем жадный алгоритм со сдвигом расписания. Исключение составляют наборы исходных данных, для которых граф исходных данных является графом произвольного вида с малым числом компонент связности. В таблице 1 для разных эвристик и классов наборов исходных данных приведены полученные диапазоны, в которых лежат доли неразмещенных в расписания работ и сообщений, относительно общего числа работ и сообщений соответственно.

Для гарантированного получения точного решения стоит пользоваться алгоритмом на основе метода ветвей и границ. Главный минус этого алгоритма — высокая вычислительная сложность. Но для большинства исходных данных в алгоритме построения привязки работ к вычислительным модулям первая построенная листовая вершина дерева решений содержит оптимальное решение. Общее число листовых вершин алгоритма нахождения порядка

/ \ Пр

выполнения работ и передачи сообщений равно Пм\ ( ^ !) яз Ю310, тогда как максимальное количество рассмотренных вершин во время экспериментального исследования составило 1286.

В пятой главе представлено инструментальное программное средство построения совместимых расписаний, разработанное на базе предложенных алгоритмов. Средство обладает следующей функциональностью и свойствами:

• построение совместимых расписаний выполнения работ и передачи сообщений по заданному набору исходных данных при помощи выбранного алгоритма построения совместимых расписаний;

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

Эвристика Набор Работы Сообщения

1 [0; 0.023] [0; 0.084]

Минимальный 2 [0; 0.049] [0; 0.183]

директивный срок 3 [0; 0] [0;0]

завершения 4 [0; 0.028] [0; 0.048]

5 [0; 0.008] [0; 0.012]

1 [0; 0.027] [0; 0.123]

Минимальное раннее время завершения 2 [0; 0.027] [0; 0.123]

3 [0; 0.014] [0; 0.067]

4 [0; 0.028] [0; 0.047]

5 [0; 0.030] [0; 0.046]

1 [0; 0.051] [0; 0.133]

Максимальное общее число потомков 2 [0; 0.028] [0; 0.119]

3 [0; 0.027] [0; 0.071]

4 [0; 0.038] [0; 0.070]

5 [0; 0.046] [0; 0.059]

Таблица 1. Данные исследования жадного алгоритма

данных, параметров работ, сообщений и вычислительных модулей;

• возможность сохранения на диск и загрузки с диска наборов исходных данных и построенных расписаний;

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

• возможность отдельного (без графического интерфейса) использования библиотеки алгоритмов в составе других средств;

• возможность расширения на другие среды передачи данных;

• кросс-платформенность, т.е. возможностью работать на вычислительных системах под управлением различных операционных систем.

В Заключении формулируются основные результаты диссертации.

В Приложении А детально описывается жадный алгоритм построения совместимых расписаний.

В Приложении Б приведён вывод верхней оценки сложности жадного алгоритма построения совместимых расписаний.

В Приложении В содержится детальное описание жадного алгоритма построения совместимых расписаний, допускающего сдвиг расписания.

В Приложение Г приведено описание процедуры получения конкретных наборов исходных данных, используемых в исследованиях.

Основные результаты, выносимые на защиту

1) Предложена математическая постановка задачи построения расписания выполнения задач и расписания передачи сообщений между ними с соблюдением: ограничений реального времени; ограничений совместимо-

сти этих расписаний; ограничений, связанных со спецификой функционирования информационно-управляющих систем реального времени. Доказана NP-трудность этой задачи.

2) Получено и исследовано решение поставленной задачи в классе жадных алгоритмов.

3) Разработан и исследован алгоритм, гарантирующий максимально возможное число запланированных задач и сообщений из исходно заданных наборов, с учётом ограничений поставленной задачи.

4) На основе предложенных алгоритмов разработана инструментальная система, позволяющая поддерживать процесс модернизации информационно-управляющих систем реального времени и разработку новых информационно-управляющих систем реального времени на базе существующих, а так же исследовать свойства предложенных алгоритмов построения расписаний.

Публикации по теме диссертации

1. Костенко В.А., Шестов П.Е. Совместное планирование вычислений и обменов в бортовых системах реального времени //VI Московская Международная конференция по исследованию операций (ORM2010), Москва, 19-23 октября 2010: Труды. 2010. С. 306-308.

2. Balashov V.V., Balakhanov V.A., Kostenko V.A., Kokarev V.A., Shestov P.E. A Technology for Scheduling of Data Exchange over Bus with Centralized Control in Onboard Avionics Systems // Journal of Aerospace Engineering, 2010, Vol. 224, no. G9, P. 993-1004.

3. Шестов П.Е., Костенко В.А. Анализ подходов к совместному планированию вычислений и обменов в системах реального времени // Программные системы и инструменты. Тематический сборник. 2011. № 12. С. 172-181.

4. Shestov P., Kostenko V., Balashov V. Scheduling Problems In Embedded Real-time Systems // Proceedings of llth IFAC/IEEE International Conférence on Programmable Devices and Embedded Systems (PDeS 2012). 2012. P. 302-306.

5. Костенко В.A., Шестов П.Е. Жадный алгоритм совместного планирования вычислений и обменов в системах реального времени // Известия РАН. Теория и системы управления. 2012. № 5. С. 35-49.

6. Шестов П.Е. Алгоритм на основе метода ветвей и границ совместного планирования вычислений и обменов в системах реального времени // «Параллельные вычисления и задачи управления» РАСО'2012. Шестая международная конференция, Москва, 24-26 окт. 2012 г. - Труды: в 3 т. 2012. Т. 3. С. 317-329.

Заказ № 59-Р/07/2013 Подписано в печать 30.07.13 Тираж 90 экз. усл. п.л. 1,0

ООО "Цифровичок", тел. (495) 797-75-76 www.cfr.ru; е-таИ:info@cfr.ru

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

имени М.В. Ломоносова

На правах рукописи

04201361042

Шестов Пётр Евгеньевич

Совместное планирование вычислений и обменов в информационно-управляющих системах реального времени

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель к.т.н., в.н.с. В. А. Костенко

Москва - 2013

Содержание

Введение ................................... 4

Глава 1. Задача построения совместимых расписаний вычислений и обменов.............................. 9

1.1. Содержательная постановка задачи................ 9

1.2. Математическая модель исходных данных............17

1.3. Математическая модель расписания и условий его корректности 19

1.4. Математическая постановка задачи................26

1.5. Классификация задачи.......................28

1.6. Практически значимые частные задачи..............31

1.7. Выводы................................33

Глава 2. Обзор возможных подходов к построению алгоритмов

решения задачи и алгоритмов решения «близких» задач . . 34

2.1. Близкие задачи и алгоритмы их решения.............34

2.2. Возможные подходы к решению поставленной задачи......38

2.3. Методы разработки алгоритмов построения статических многоприборных расписаний......................41

2.4. Выводы..............'..................48

Глава 3. Алгоритмы решения задачи построения совместимых расписаний................................49

3.1. Жадный алгоритм..........................49

3.2. Алгоритм, основанный на методе ветвей и границ........57

3.3. Жадный алгоритм со сдвигом расписания............73

Глава 4. Экспериментальное исследование разработанных ал-

горитмов..................................76

4.1. Цели исследования .........................76

4.2. Формирование исходных данных для экспериментов......77

4.3. Методика статистической обработки результатов экспериментов 81

4.4. Схема проведения экспериментов.................84

4.5. Исследование жадного алгоритма.................85

4.6. Исследование алгоритма, основанного на методе ветвей и границ 90

4.7. Исследование жадного алгоритма со сдвигом расписания .... 94

4.8. Выводы................................99

Глава 5. Описание инструментального программного средства построения совместимых расписаний...............100

5.1. Требования к инструментальному средству ...........100

5.2. Архитектура инструментального средства построения совместимых расписаний.........................101

Заключение..................................104

Литература..................................105

Приложение А. Подробное описание жадного алгоритма . . .114

Приложение Б. Сложность жадного алгоритма для случая наибольшего числа возвратов ......................125

Приложение В. Подробное описание жадного алгоритма со сдвигом расписания .............................127

Приложение Г. Построение графа работ и сообщений по шаблону .....................................131

Введение

Информационно-управляющие системы реального времени (ИУС РВ) используются для управления сложными техническими системами. Например, летательными аппаратами, кораблями, искусственными спутниками и т.п. Одним из важнейших требований к функционированию ИУС РВ является выполнение ограничений реального времени. Ограничения реального времени задаются в виде директивных интервалов для прикладных задач и сообщений. Прикладные задачи должны быть выполнены в рамках заданных директивных интервалов. Сообщения должны быть переданы в рамках заданных директивных интервалов. При нарушении этих ограничений ИУС РВ теряет свою работоспособность. На всех этапах разработки ИУС РВ необходимо строить расписание выполнения прикладных задач и расписание передачи сообщений для проверки возможности выполнения ограничений реального времени.

Разработка подобных ИУС РВ является сложным техническим процессом. Часто возникает задача модернизации таких систем, либо повторного использования отдельных подсистем ранее разработанных ИУС РВ. Причем изменение функционирования повторно используемых подсистем невозможно. Отсюда следует, что они обладают фиксированным интерфейсом, с помощью которого остальные устройства (в том числе другие подсистемы) в составе ИУС РВ взаимодействуют с такими подсистемами. Фиксирован формат сообщений и состав слов данных, которые получают и передают подсистемы.

К функционированию ИУС РВ предъявляется ряд требований, связанных не только с работой в реальном времени, но и обусловленных используемыми техническими стандартами, протоколами обмена данных, особенностями работы аппаратных и системных программных средств.

Настоящая диссертация посвящена алгоритмам построения совместимых

расписаний выполнения прикладных задач (работ) и передачи сообщений в ИУС РВ. Расписания выполнения работ и передачи сообщений в таких системах строятся статически. В качестве среды передачи данных в работе рассматривается канал с централизованным управлением. Практическая значимость рассмотрения ИУС РВ с таким каналом подтверждается существованием ряда промышленных стандартов на каналы с централизованным управлением (MIL STD-1553B / МКИО ГОСТ Р 52070-2003 [8], STANAG 3910 [46], Fibre Channel FC-AE-1553 [53]), а также широким применением этих стандартов при создании ИУС РВ.

Исходными данными для задачи построения расписаний являются наборы работ и сообщений, передающих данные между работами. При этом повторно используемые подсистемы рассматриваются как множества работ, выполняющихся на выделенных вычислительных модулях, на которых недопустимо выполнение других работ. На расписание передачи сообщений накладываются дополнительные ограничения, связанные с особенностями аппаратных и программных средств обеспечения работы канала с централизованным управлением. В дальнейшем такие ограничения будем называть технологическими. Задача построения совместимых расписаний состоит в нахождении расписаний выполнения работ и передачи сообщений, содержащих максимально возможное число работ и сообщений. Под совместным планированием будем понимать решение этой задачи. Актуальность разработки алгоритмов построения совместимых расписаний подтверждается особенностями рассматриваемой задачи, отличающими ее от других задач построения расписаний, а именно:

• необходимость планирования заданий двух типов: работ и сообщений;

• наличие двух типов работ: работ, подлежащих планированию, и работ в составе подсистем, которые не подлежат планированию;

• время передачи сообщения зависит от расписания выполнения работ, а именно от того, на какие вычислительные модули размещены передающая и принимающие работы;

• присутствуют технологические ограничения на корректность расписания;

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

Целью данной работы является разработка и исследование свойств алгоритмов построения расписания выполнения задач на вычислительных модулях в составе ИУС РВ и расписания передачи сообщений между ними по каналу с централизованным управлением с соблюдением ограничений на их совместимость.

Для достижения поставленной цели необходимо решить следующие задачи:

• Разработать математическую модель ИУС РВ и в рамках предложенной модели формализовать постановку задачи построения совместимых расписаний выполнения прикладных задач и передачи сообщений, которая позволяет учитывать технологические ограничения на корректность расписаний.

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

• На основе предложенных алгоритмов реализовать программное инструментальное средство построения совместимых расписаний, позволяю-

щее поддерживать процесс модернизации ИУС РВ и разработку новых ИУС РВ на базе существующих, а так же позволяющее проводить экспериментальные исследования алгоритмов построения совместимых расписаний.

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

Работа состоит из введения, пяти глав, заключения и четырех приложений. В первой главе описана организация работы ИУС РВ. Перечислены требования к передаче данных по каналу с централизованным управлением. Введена математическая модель ИУС РВ и исходных данных задачи построения расписаний, математическое представление требований к передаче данных, математическое представление расписаний. Сформулирована задача построения совместимых расписаний выполнения задач и передачи сообщений, дана ее формальная постановка и доказана ИР-трудность.

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

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

В четвертой главе описана методика экспериментального исследования разработанных алгоритмов построения совместимых расписаний, приведены

численные результаты исследования и их анализ. Предметом исследования являлись точность и вычислительная сложность алгоритмов на различных классах исходных данных. Исходные данные для экспериментов сформированы на основе доступных автору наборах исходных данных с реальных ВСРВ. При обработке результатов экспериментов применены методы математической статистики.

В пятой главе представлено инструментальное программное средство построения совместимых расписаний и библиотека алгоритмов, в которой реализованы предложенные алгоритмы.

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

Глава 1

Задача построения совместимых расписаний

вычислений и обменов

1.1. Содержательная постановка задачи

Информационно-управляющие системы реального времени, как правило, имеют трехуровневую архитектуру. В качестве примера рассмотрим Международную космическую станцию [15]. Архитектурные принципы построения управляющей вычислительной сети МКС (являющейся встроенной системой реального времени) жестко привязывают каждый управляющий компьютер МКС к одному из трех уровней управления (см. рис. 1.1). На первом (высшем) уровне обеспечивается управление в масштабах всей Международной космической станции. Хотя каждый космический модуль или отдельные системы МКС имеют собственные управляющие вычислительные сети, на станции выделены «главные» управляющие компьютеры первого уровня управления (для надежности их три: «основной» — работающий; резервный — дублирующий, работает в режиме «горячего» резерва; и запасной — работает в режиме «холодного» резерва, т.е. выключенный). Именно с этими «главными» компьютерами взаимодействуют компьютеры интерфейса экипажа и Центров управления полетами. Именно эти «главные» компьютеры обеспечивают управление на уровне режимов станции: на основании сбора и анализа обобщенной информации о состоянии всех подсистем МКС и команд, поступающих от интерфейсных компьютеров экипажа или с Земли, определяется один из заранее заданных режимов, в которых может находиться станция: стандартный, режим микрогравитации для выполнения научных экспериментов; режим сближения и стыковки с транспортными кораблями; режим для

Рис. 1.1. Уровни ИУС РВ МКС

выхода экипажа в открытый космос; режим выживания с отключением наименее важных экспериментов и систем; режим аварийного покидания экипажем МКС. Компьютеры следующего (второго) уровня управляют модулями МКС и отдельными подсистемами в целом, например, системами движения, электропитания, термоконтроля и т.д. И только на третьем уровне управления находятся компьютеры, непосредственно управляющие датчиками и исполнительными механизмами (клапанами, двигателями, насосами, переключателями и т.д.), относящимися к конкретной системе. Все компьютеры бортовой сети связаны с целым набором шин, проложенных как по каждому модулю (локальные шины), так и через все модули станции (общие шины), что обеспечивает обмен командами и данными как по вертикали через все уровни управления, так и по горизонтали — между компьютерами, относящимися к одной системе и расположенными в разных местах станции. Общие шины проложены по всем модулям станции и выведены на специальные разъемы в стыковочных узлах, таким образом при стыковке МКС с новым модулем или транспортным кораблем происходит объединение бортовой вычислительной

сети МКС с компьютерной сетью вновь прибывшего космического объекта. В качестве стандартной шины обмена на МКС применяется шина с централизованным управлением стандарта МТЬ-БТБ1553В (российский аналог — ГОСТ Р 52070-2003 [8]). Подобная организация вычислительной сети также характерна для многих летательных аппаратов, включая военную и гражданскую авиацию.

В данной диссертации рассматриваются алгоритмы построения расписаний для первого уровня ИУС РВ, которая рассматривается как система, состоящая из набора вычислительных модулей и готовых подсистем, подключенных к единой среде передачи данных. Рабочей нагрузкой для вычислительных модулей является заданный набор функциональных задач (работ), обеспечивающий управление всей системой. Каждая работа является минимальной единицей планирования и представляет собой один процесс, для выполнения которого требуется ровно один вычислительный модуль. Каждая подсистема может быть представлена как набор работ (в дальнейшем — работы-подсистемы), выполняющихся на отдельном вычислительном модуле, на который недопустимо назначение других работ. Работы (в том числе работы-подсистемы) взаимодействуют путем передачи сообщений по среде передачи данных. Набор работ для выполнения на вычислительных модулях и набор сообщений для передачи известны априорно, до начала функционирования системы. Для каждой работы задан директивный интервал, в рамках которого она должна быть выполнена, набор вычислительных модулей, на которые работа может быть размещена, и длительность выполнения работы на каждом из допустимых модулей. Для каждого сообщения задан директивный интервал, в рамках которого оно должно быть передано. Длительность передачи сообщения зависит от того, на каких вычислительных модулях выполняются передающая и принимающая работы. Если же передающая и все принимающие работы выполняются на одном и том же вычислительном мо-

дуле, то взаимодействие между ними происходит через внутреннюю память модуля, т.е. не используется канал передачи данных. Также априорно известны технологические требования к расписанию, обусловленные особенностями аппаратных и программных средств ИУС РВ. Технологические требования определяют дополнительные ограничения на корректность расписания. На основании перечисленных исходных данных, до начала работы ИУС РВ строятся расписания выполнения работ и передачи сообщений, в которых каждой работе и каждому сообщению сопоставлено конкретное время начала ее выполнения или передачи, каждой работе дополнительно сопоставлен конкретный вычислительный модуль, выполняющий работу. Готовые расписания загружаются на соответствующие устройства. В процессе функционирования системы все устройства отрабатывают эти расписания. Статическое расписание не может быть изменено в процессе функционирования ИУС РВ. Если ИУС РВ поддерживает различные режимы функционирования, каждому из которых соответствует отдельный набор работ и сообщений, для каждого из этих режимов строятся отдельные расписания. В рассматриваемых системах недопустимо прерывание выполнения работ и передачи сообщений. Для подсистем и соответствующего им набору работ-подсистем расписание априори существует и загружено на соответствующие устройства. Это расписание может быть неизвестно, но интервалы выполнения работ