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

0034Э4627

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. Ломоносова Факультет вычислительной математики и кибернетики

ОБЕСПЕЧЕНИЕ СОВМЕСТИМОСТИ ТРЕБОВАНИЙ К РАСПИСАНИЮ ОБМЕНА ПО КАНАЛУ С ЦЕНТРАЛИЗОВАННЫМ УПРАВЛЕНИЕМ

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

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

БАЛАШОВ Василий Викторович

МОСКВА-2010

2 5 МАР 2010

003494627

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

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

доктор физико-математических наук, профессор Смелянский Руслан Леонидович.

доктор технических наук, профессор Топорков Виктор Васильевич; кандидат физико-математических наук, доцент Фуругян Меран Габибуллаевич.

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

ЗАО НТЦ «Модуль»

Защита диссертации состоится 2 апреля 2010 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М.В.Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет вычислительной математики и кибернетики, аудитория 685.

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

Автореферат разослан «Z 6 » февраля 2010 г.

Ученый секретарь

диссертационного совета Д 501.001.44 профессор

Н.П. Трифонов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

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

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

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

Цель работы

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

При этом предъявляются следующие требования к решению:

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

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

Основные результаты работы

Основные результаты диссертационной работы заключаются в следующем:

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

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

1 Stewart D. B., Arora G. A Tool for Analyzing and Fine Tuning the Real-Time Properties of an Embedded System // IEEE Trans. Software Engineering. - 2003. -Vol. 29, No. 4.-P. 311-326.

2 Park J., Ryu M., Hong S., Bello L. L. Rapid Performance Re-engineering of Distributed Embedded Systems via Latency and k-level diagonal search // Journal of Parallel and Distributed Computing. - 2006. - Vol. 66, Issue 1. - P. 19-31.

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

Научная новизна

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

Сформулированные в работе достаточные условия несовместимости требований к расписанию обмена по каналу с централизованным управлением учитывают ряд требований к расписанию, не принимаемых во внимание другими известными достаточными условиями невозможности построения полных и корректных расписаний функционирования ВСРВ3,4'5. Утверждение о достаточности сформулированных условий доказано в работе.

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

Практическая ценность

Предложенный в работе алгоритм обеспечения совместимости требований к расписанию информационного обмена по каналу с централизованным управлением реализован в составе инструментальной системы «САПР

3 Liu C. L., Layland J. W. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment // Journal of the ACM. -1973. - Vol. 20, No. 1. - P. 46-61.

4 Tindell K. W., Burns A., Wellings A. J. An Extendible Approach for Analyzing Fixed-Priority Hard Real-Time Tasks // Journal of Real-Time Systems. - 1994. - Vol. 6,No. 2.-P. 133-152.

5 Pollex V., Kollmann S., Albers K.., Slomka F. Improved Worst-Case Response-Time Calculations by Upper-Bound Conditions // Proc. Conference on Design Automation and Test in Europe (DATE'09). - 2009. - P. 105-110.

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

Методы исследования

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

Апробация работы

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

1. Международная научная конференция «Интеллектуализация обработки информации» (Алушта, 2002).

2. Научная конференция молодых ученых факультета ВМК МГУ (Дубна, 2002).

3. Всероссийская научная конференция «Методы и средства обработки информации» (Москва, 2003,2005 и 2009 гг.).

4. Научная конференция «Ломоносовские чтения» (Москва, 2003 и 2007 гг.).

5. 7th International Symposium on Computer Networks (Istanbul, Turkey, 2006).

6. Международная научно-техническая конференция «Интеллектуальные САПР» (пос. Дивноморское, 2006).

7. Международная конференция «Параллельные вычисления и задачи управления» (Москва, 2006 и 2008 гг.).

8. V Московская международная конференция по исследованию операций (Москва, 2007).

9. EUCASS European Conference for Aerospace Sciences (Brussels, Belgium, 2007; Versailles, France, 2009).

Работа выполнена при частичной поддержке РФФИ (гранты № 04-01-00556, № 07-01-00237).

Публикации

По теме диссертации опубликовано 14 печатных работ, в том числе работа в

журнале «Известия РАН. Теория и системы управления», входящем в перечень

4

ведущих рецензируемых научных журналов ВАК РФ. Список работ приведён в конце автореферата.

Структура и объём диссертации

Диссертация состоит из введения, восьми глав, заключения, списка литературы и пяти приложений. Объём работы - 124 страницы, с приложениями - 171 страница. Список литературы содержит 69 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассмотрена проблема несовместимости требований к расписанию информационного обмена по каналу с централизованным управлением. В разделе 1.1 описана общая организация информационного обмена по каналу из этого класса и введена циклическая схема обмена, применяемая в ряде современных ВСРВ. В рамках этой схемы, рабочей нагрузкой для канала является набор (множество) заданий; для каждого задания известна длительность и требуемая частота выполнения. Набору заданий соответствует набор работ, каждая из которых характеризуется длительностью и директивным интервалом. Набор работ строится с учётом заданной длительности интервала планирования (обычно равной НОК периодов заданий). Для каждой работы, входящей в расписание обмена, зафиксировано время начала выполнения этой работы. Интервал планирования разбивается на подцикпы - интервалы равной длины, в каждом из которых выполняется непрерывная последовательность (цепочка) работ. Циклическая схема обмена может быть применена как на каналах с централизованным управлением, так и на каналах с распределённым управлением (Ethernet, Fibre Channel FC-AE-ASM, VME, FASTBUS, CAN, FlexRay, MOST).

Далее в разделе 1.1 введены конкретные технологические требования к расписанию обмена, применяемые в рамках циклической схемы, а именно: минимально допустимый отступ цепочки работ от начала подцикла (йтсо); минимально допустимый резерв времени в конце подцикла (Дг/); максимальное число работ в цепочке (йтсс); минимально допустимый резерв времени для сдвига расписания (RrfS)\ максимально допустимое отклонение расстояния между последовательными работами одного задания от периода этого задания (Rmpe), левый и правый фазовые сдвиги задания (определяются для конкретного

5

задания т: К<р 1(771), Кф2(7п)). Каждое из этих требований характеризуется числовым значением, т.е. является количественным требованием. Все перечисленные требования применяются в реальных ВСРВ. Технологические требования к расписанию обмена (далее - требования к расписанию), наряду с директивными сроками, определяют набор ограничений на корректность расписания. Практическое применение в ВСРВ имеют расписания, являющиеся полными (включающими все работы из исходно заданного набора работ) и корректными (удовлетворяющими всем ограничениям).

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

В разделе 1.3 показано, что проблема несовместимости требований к расписанию обмена возникает неоднократно в течение жизненного цикла ВСРВ, в том числе в процессе «текущей» разработки программного обеспечения ВСРВ. Это подтверждает актуальность задачи обеспечения совместимости требований. Далее рассмотрен ряд работ по методам корректировки параметров ВСРВ в случае невозможности построения полного и корректного расписания. Эти методы не учитывают рассмотренные в разделе 1.1 требования к расписаниям, существенные для каналов с централизованным управлением. Кроме того, в рамках этих методов предлагается проводить выборочное сокращение длительности заданий, что применительно к информационному обмену требует сокращения объёма передаваемой информации и, как следствие, потере части функциональности ВСРВ. По результатам анализа рассмотренных работ сделан вывод о том, что не существует готовых методов решения задачи обеспечения совместимости требований к расписанию обмена по каналу с централизованным управлением, и актуальна разработка алгоритмов и инструментальных средств решения этой задачи.

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

В разделе 2.1 даны определения набора периодических заданий; набора работ; расписания для одноприборной системы без прерывания работ (с точки зрения теории расписаний, каналы с централизованным управлением могут рассматриваться как такие системы). Введено понятие вектора требований - это вектор вида х = (Хц-.-.х^), каждому элементу которого соответствует требование Д(- к расписанию, и значением этого требования является х1. За X1 обозначено множество всевозможных значений элемента за Xм - множество всевозможных векторов требований: Xм = X1 х,,.хх"х, Далее в работе рассматриваются требования к расписанию, представимые в виде ограничений на расписание, имеющих вид:

д,(Н,х) < О, I = 1..Ыв, д(-.{ЩхХЛ1 -> М, (2.1) где Я - расписание, {Я} - множество всевозможных расписаний в соответствии с данным ранее определением расписания. В приложении А для требований к расписаниям, встречающихся на практике в современных ВСРВ и описанных в разделе 1.1, введены в виде (2.1) соответствующие им ограничения на расписание.

Далее введено понятие корректного расписания - это расписание, которое

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

корректности, но и ограничениям, соответствующим требованиям к расписанию.

Корректное расписание может быть неполным (не включать некоторые из работ

из соответствующего набора работ).

В разделе 2.2 дана формальная постановка задачи Ррасп построения

расписания для одноприборной системы без прерывания работ, в виде:

шах ]Н| яеуад

0,(Н,2)< О, ¡ = 1..Л^ (2.2)

х е Ха11, х — фиксирован где Ну - множество расписаний, соответствующих набору работ V. В задаче Рра[п максимизируемый критерий - число работ в корректном расписании. Далее в работе рассматриваются только такие детерминированные алгоритмы построения расписания, которые решают задачу построения расписания в этой постановке.

Раздел 2.3 содержит формальную постановку задачи обеспечения совместимости требований Рост. Пусть Л5сЬ£,(1 - алгоритм построения расписания, решающий задачу Ррасп.

Определение 2.2. Значения требований из вектора х'пс £ Ха11 в (2.2) будем называть несовместимыми относительно алгоритма если этот алгоритм «роит неполное расписание при х = х1пс.

Определение 2.3. Значения требований из вектора х1пс е Х"и в (2.2) будем называть принципиально несовместимыми, если для х = х1пс не существует решения задачи Ррасп, которое является полным расписанием.

Наравне с формулировкой «совместимые (несовместимые) значения требований из вектора х» в работе применяется краткая формулировка «совместимый (несовместимый) вектор х».

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

Задача обеспечения совместимости требований к расписанию (далее -задача Яосг) ставится в следующем виде.

Пусть заданы: ограничения ,д.{Н,х) <0, 1 = \..Ид на' расписание, соответствующие требованиям к расписанию; набор работ V; детерминированный алгоритм /45Сьеа построения расписания, решающий задачу построения расписания Ррасп; интервалы Х' = [х?™;х™1*], 1 = 1..^, в рамках которых допустимо изменять значения требований к расписанию (причём [х™1";*™3*] ¿ = 1..ЛГХ); начальный вектор требований х* = {х\,...,х"Нх) (причём х* = 1..ЛУ; функция стоимости изменения значений требований относительно заданных в х': созЬ(х) = с( * |х(* — где сг > О, [ = 1..-коэффициенты стоимости изменения значений требований.

Введём обозначения: Х = Х Х...Х - множество, в рамках которого допустимо изменять вектор требований к расписанию; Я(Л5Сьеа,И,ж) -корректное расписание, построенное алгоритмом ЛсЬеа по набору работ V, с учётом требований, значения которых заданы вектором х; |Н(Л5с[1е(1,1',х)| -

6 Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. -М.: Мир, 1982.-416 с.

число работ в расписании Н(А$сьеЛ, Введём функцию совместимости значений требований, определённую на множестве Xм:

СОтр(х)-к\Н(Л,Лед,У,х)\<Ыу

где Щ - число работ в наборе V.

Формальная постановка задачи Рост обеспечения совместимости требований к расписанию имеет вид7:

!шт cost(x) сотр(х) = 1

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

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

В третьей главе введён специальный класс требований к расписанию обмена - требования, допускающие ослабление. В разделе 3.1 предполагается, что зафиксирован конкретный состав требований к расписанию, а также соответствующие им множество Ха" и набор функций [ = 1.. задающих ограничения вида (2.1) на расписание.

Пусть аеХ1 - константа. Обозначим: х{(а) = (у £ Х>- у > а}; х!_(а) = {уех'-. у < а).

Определение 3.1. Ослаблением элемента X; будем называете увеличение (уменьшение) его значения, если для любого расписания Я 6 {Я} и для любого вектора хЕХа11, таких что выполнены условия д1(Н,х)<01 1 = 1..Ыд, эти условия также выполнены для вектора х^еак, полученного из х заменой в ]-а позиции значения X) на произвольное значение у еХ{(х^ (для уменьшения -соответственно, у 6 Х1(х/У).

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

Изменение x¡, противоположное ослаблению, будем называть усилением. Под «ослаблением требования й» будем понимать ослабление соответствующего ему элемента вектора х. Далее в работе вместо формулировок вместо формулировок «для требования R определено понятие ослабления», «для Xj определено понятие ослабления» используются более краткие: «R допускает ослабление», «Xj допускает ослабление».

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

Доказано утверждение о том, что введённые в разделе 1.1 (и формализованные в приложении А) количественные требования к расписанию допускают ослабление при том условии, что от их значений не зависит выполненность прочих требований к расписанию. Дано обоснование того, что это условие выполнено для описанной в разделе 1.1 циклической схемы обмена.

В разделе 3.2 приведена частная постановка задачи Рост для требований к расписанию, допускающих ослабление. Её отличие от общей постановки в том, что допустимо изменение значений только тех требований, которые допускают ослабление, причём только ослабление относительно значений из начального вектора х' (в связи с чем функция cost(x) становится линейной, а не кусочно-линейной). Далее в работе задача Рост рассматривается именно в этой частной постановке, в применении к циклической схеме обмена. В качестве конкретных практически важных требований, допускающих ослабление, в рамках этой задачи рассматриваются введённые в разделе 1.1 количественные требования к расписанию.

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

на условия, накладываемые на директивные сроки работ; технологические требования к расписанию принимаются во внимание в очень ограниченном объёме - например, в одной из статей учитывается частота вызова планировщика вычислительных задач. Анализ известных автору источников позволяет сделать вывод о том, что необходимые условия совместимости требований (принципиальной или относительно заданного алгоритма построения расписания) для требований к расписанию обмена, введённых в разделе 1.1, ранее не были сформулированы.

Следующее утверждение позволяет по известному принципиально несовместимому решению х задачи Яост получить множество принципиально несовместимых решений этой задачи путём усиления требований в составе х.

Утверждение 4.1. Пусть в задаче Р0„, Я = Я1 х...хЯ"х - множество, в рамках которого допустимо изменять вектор требований к расписанию, и х 6 Я - принципиально несовместимый вектор требований. Тогда принципиально несовместимы также все вектора из множества:

Хрг1пс{х,Х) = {у е Х:-1и>еакег(у1,х1), I = 1..Л/*}, где юеакегСу^ х{) означает (у( < х(), если ослаблением элемента х1 является уменьшение его значения, и (уг > х1)< если ослаблением элемента Х[ является увеличение его значения.

В разделе 4.1 сформулированы и доказаны достаточные условия принципиальной несовместимости для векторов требований, в состав которых входят значения таких требований, как йтсс, Ктса, К,-/, Приведены

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

Утверждение 4.2. Пусть зафиксированы: набор работ V, длительность интервала планирования ¡¡пе, длительность подцикла 11С, значения всех требований (кроме Ятсс). В таком случае принципиальная совместимость (несовместимость) вектора требований инвариантна относительно изменения входящего в него значения требования Дтсс на множестве [Ятаг;0ья' +00)-

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

В разделе 4.3 предложено рассматривать вектора требований х е Ха11 как координаты точек в метрическом пространстве К"*. Пусть Ясотр - множество

совместимых решений из Я: Ясотр = {х е Я\сотр(х) = 1}. Множества Я и Ясотр можно рассматривать как области в К"*. В целях унификации обозначений, в таком случае будем говорить об «области Я», «области Ясотр». Под структурой облает Я будем понимать взаимное расположение входящих в неё областей совместимых и несовместимых решений. Автором было выполнено экспериментальное исследование, в рамках которого был построен ряд двумерных сечений области Я, для различных наборов работ, основанных на данных с реальных ВСРВ, и различных интервалов изменения значений требований. Для построения расписания использовался жадный алгоритм. В разделе 4.3 перечислены выявленные в результате проведённого экспериментального исследования виды структур, встречающиеся у областей в составе области Я. Применяемые в разработанном алгоритме решения задачи Рост эвристики учитывают эти виды структур. Проведённое исследование также показало, что априорно предсказать конкретную структуру области Я по характеристикам набора заданий и интервалам изменения значений требований - весьма нетривиальная задача. Её решение заслуживает отдельного изучения и выходит за рамки данной работы.

В завершающем разделе главы 4, по результатам проведённого в главе исследования, сформулированы требования к построению алгоритма решения задачи Рост. Алгоритм должен: включать процедуры, каждая из которых эффективно применима на одном или нескольких выявленных видах структуры областей в составе Я; выполнять отсечение множеств принципиально несовместимых векторов требований в соответствии с утверждением 4.1; сокращать рассматриваемый интервал значений требования Лтсс в соответствии с утверждением 4.2.

В пятой главе проведён обзор методов решения задач математического программирования и выполнен сравнительный анализ их применимости к задаче Рост. В разделе 5.1 дана характеристика Рост как задачи математического программирования. В связи с неизвестностью аналитического выражения для функции сотр(х), из дальнейшего рассмотрения исключены методы математического программирования, опирающиеся на аналитические свойства ограничений задачи (в частности, симплекс-метод и двойственные методы). В последующих разделах рассмотрены такие методы, как: исчерпывающий поиск; детерминированный направленный поиск; ненаправленный и направленный случайный поиск; метод ветвей и границ; динамическое программирование;

12

алгоритмы имитации отжига; генетические и эволюционные алгоритмы; жадные алгоритмы. Показано, что рассмотренные методы разбиваются на следующие группы: (1) в принципе не применимые к задаче Рост; (2) представляющие собой схемы, требующие существенной настройки на специфику задачи Рост (разработка операций, выбор значений параметров и т.п.) - оценка применимости таких методов к Рост может быть выполнена только для конкретного наполнения схемы; (3) в принципе применимые к задаче Рост, но есть проблемы при самостоятельном применении каждого из этих методов. К группе 3 относятся: детерминированный направленный поиск; направленный и ненаправленный случайный поиск; метод ветвей и границ. Для методов из этой группы, в соответствующих разделах обзора сформулированы предположения о том, на каких видах структуры областей в составе области Я эти методы могут быть эффективно применимы.

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

В шестой главе описан алгоритм А0„, предложенный автором работы для решения задачи обеспечения совместимости требований Рост. Алгоритм Аа„ выполняет поиск решения задачи Рост на конечной сетке, введённой на множестве Я решений этой задачи. Сетка введена в разделе 6.1; в работе дана оценка максимального отклонения значения целевой функции на лучшем совместимом решении, принадлежащем множеству узлов сетки, от оптимального решения задачи Рост.

Раздел 6.2 содержит общее описание алгоритма Лост, в т.ч. его блок-схему. В основе алгоритма лежат методы решения задач математического программирования из группы 3, выделенной в пятой главе; эти методы расширены и объединены в единую схему с учётом требований к построению

алгоритма решения задачи Рост, сформулированных в выводах из четвёртой главы.

До выполнения каких-либо действий по поиску решений, Аа„ выполняет покоординатное сокращение области поиска решения посредством: (1) сужения интервалов изменения значений тех требований, для которых в разделе 4.1 получены достаточные условия принципиальной несовместимости; (2) сужения интервала изменения значения требования Ятсс на основании утверждения 4.2.

Первый этап алгоритма Лост состоит в выполнении ненаправленного случайного поиска с сужением множества поиска по мере нахождения совместимых или принципиально несовместимых решений. При нахождении совместимого решения хк £ Ясотр, из множества поиска исключается множество решений, на которых целевая функция со$4(2) принимает значения, большие или равные свя^х*). При нахождении принципиально несовместимого решения х1, из множества поиска исключаются решения (вектора требований), элементы которых либо равны соответствующим элементам х1, либо являются более «сильными» в соответствии с определением 3.1. Эти решения являются принципиально несовместимыми в соответствии с утверждением 4.1. Исключению множества несовместимых решений предшествует его расширение, при котором выполняется покоординатное ослабление х' до тех пор, пока сохраняется принципиальная несовместимость результирующего решения.

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

На втором этапе алгоритма А0СТ выполняется локальное уточнение найденных на первом этапе совместимых решений алгоритмом направленного поиска, основанном на градиентном спуске. При достижении несовместимого решения в результате сдвига вдоль направления (—у^""1) наискорейшего убывания целевой функции со5£(х), алгоритм АЕГгЛ выполняет поиск новых приближений, от которых возможно продолжение сдвига по направлению (—увгаЛ). Эти приближения ищутся среди решений, имеющих то же значение

14

что и последнее полученное при сдвиге вдоль ('—у9гаЛ) совместимое решение. От каждого из них выполняется сдвиг вдоль (—уйга1!), аналогично первоначальному сдвигу. Выбирается одно совместимое решение, являющееся лучшим по значению соб^х) из результатов этого сдвига; далее процесс продолжается итеративно, пока на очередной итерации улучшение значения не станет слишком малым.

Начальным приближением для третьего (последнего) этапа алгоритма А0С1 является лучшее по значению целевой функции решение, найденное на втором этапе. На третьем этапе выполняется направленный поиск совместимых решений с последовательным изменением значений некоторых требований по-отдельности в направлении усиления. Такой поиск позволяет обнаружить изолированные области в составе Ясатр, которым принадлежат такие решения х, что для некоторого г, х1 равно х™п или х,тах. Существование таких областей выявлено экспериментальным путём (раздел 4.3). При поиске выполняется перебор различных последовательностей изменения требований с сочетанием детерминированного и случайного выбора элементов последовательности (т.е. номеров требований); каждое корректируемое требование входит в конкретную последовательность не более одного раза. Лучшее из найденных алгоритмом Л[))Г5,Г совместимых решений является результатом алгоритма Аогг.

Если допустима корректировка требования Ятсс, в начале выполнения алгоритма А0СТ, после покоординатного сужения области поиска, выполняется поиск решения — 1) - мерной задачи Рост с фиксированным требованием Дтсс, значение которого выбирается на основании утверждения 4.2. Этот поиск включает описанные выше три этапа. Если совместимое решение (_ЫХ — 1) -мерной задачи найдено, от совпадающего с ним совместимого решения исходной Ых - мерной задачи осуществляется поиск совместимых решений с меньшими (более «сильными») значениями требования йтсс. Применение описанного подхода позволяет дополнительно сузить множество поиска решений исходной задачи за счёт использования специфики требования Ктсс.

В разделах 6.3-6.6 описаны алгоритмы, выполняемые на различных этапах алгоритма Лост. Дня каждого алгоритма обоснована завершимостъ и приведена оценка сложности. В разделе 6.7 приведена схема выполнения алгоритма лост и дана итоговая оценка сложности этого алгоритма. Сложность алгоритма Лост является полиномиальной относительно числа корректируемых требований и числа работ в наборе работ. Детальное описание алгоритма Логг( включая

15

пошаговые схемы выполнения всех алгоритмов в его составе и вывод оценок сложности, приведено в приложении Б.

Алгоритм Лост допускает настройку на состав технологических требований к расписанию обмена, специфический для конкретной ВСРВ или для класса ВСРВ, посредством: (1) включения в состав алгоритма Лост процедур проверки достаточных условий принципиальной несовместимости требований, и применения результатов проверки для сокращения множества поиска решений; (2) включения в состав алгоритма Лост алгоритмов, учитывающих специфику конкретных требований. Для применения алгоритма Аост совместно с тем или иным детерминированным алгоритмом построения расписания Asc hed, необходимо использовать алгоритм ¿4sche(i для вычисления функции сотр(х).

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

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

На основании проведённого исследования сделаны следующие выводы: (1) применение в алгоритме Лост подходов, предложенных в настоящей работе, вносит существенный вклад в точность и стабильность этого алгоритма; (2) на рассмотренных примерах задачи Рост с числом корректируемых требований 3 и 4, алгоритм Лост стабильно находит оптимальное решение, либо решение, несущественно (не более чем на 3% по значению целевой функции) уступающее

оптимальному8; (3) при испытаниях на данных по реальным ВСРВ, алгоритм Лост демонстрирует точность, стабильность и вычислительную сложность, необходимые для его практического применения; кроме того, изменение таких характеристик набора заданий, как загрузка канала, количество и длительности заданий, фазовые сдвиги, не приводит к ухудшению характеристик алгоритма <40СТ. Максимальные, по всем рассмотренным в исследовании примерам задачи Рост, затраты процессорного времени на выполнение алгоритма Лост не превысили 15 минут (процессор Core 2 Duo, тактовая частота 3 ГТц). Разброс значений целевой функции на решении при многократных выполнениях алгоритма Лост на фиксированных примерах задачи Рост не превысил 10% (при числе корректируемых требований не более 4 - не превысил 3%). Исследование показало, что каждый из выполняемых в составе Лост алгоритмов вносит существенный вклад в точность и стабильность решения.

В восьмой главе описана созданная рабочей группой под руководством автора инструментальная система (ИС) «САПР циклограмм», в рамках которой автором реализован предложенный в работе алгоритм Лост. ИС «САПР циклограмм» автоматизирует планирование информационного обмена по каналу с централизованным управлением. Кроме собственно построения расписания, данная ИС поддерживает внедрение этого расписания в целевую ВСРВ (через генерацию кода) и разработку документации по построенным расписаниям (через формирование отчётов). Также ИС «САПР циклограмм» поддерживает этап разработки требований к расписанию обмена, позволяя корректировать эти требования в случае если не удалось построить полное и корректное расписание. ИС «САПР циклограмм» прошла апробацию на практических задачах построения расписаний обмена по каналам МКИО.

В разделе 8.1 перечислены основные функции ИС «САПР циклограмм», указаны виды обеспечения этой ИС по ГОСТ 23501.101-87 «Системы автоматизированного проектирования. Основные положения», показана схема поддерживаемого ИС «САПР циклограмм» процесса планирования информационного обмена. Разработанная ИС имеет модульную структуру, что позволяет путём локальных модификаций обеспечивать поддержку различных

8 Точность алгоритма А0С1 на примерах задачи Рост размерности более 4 не оценивалась в связи с очень высокой вычислительной сложностью точного

переборного алгоритма, применяемого для поиска оптимального решения задачи р

'ост-

технологических требований к расписанию обмена, а также настройку алгоритмов на специфику исходных данных по конкретному классу ВСРВ. Раздел 8.2 содержит описание созданной автором настоящей работы подсистемы обеспечения совместимости требований к расписанию информационного обмена, входящей в состав ИС «САПР циклограмм». Схематически показана архитектура подсистемы, включая основные функциональные блоки и потоки данных между ними. Лежащая в основе подсистемы библиотека реализует предложенные в данной работе алгоритмы; программный интерфейс библиотеки обеспечивает возможность применения: процедур проверки различных достаточных условий принципиальной несовместимости требований к расписанию обмена; специализированных алгоритмов обеспечения совместимости требований, учитывающих специфику конкретных видов требований; различных алгоритмов построения расписания (для оценки совместимости требований). Тем самым обеспечивается настройка средств обеспечения совместимости требований в ИС «САПР циклограмм» на частную задачу обеспечения совместимости требований, определяемую спецификой разрабатываемой ВСРВ.

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Полученные автором результаты изложены в следующих работах:

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

18

ограничений на ее функционирование // Искусственный интеллект (Донецк).

- 2002. - № 2. - С. 397—405.

2. Балашов В, В. О внесении изменений во встроенную систему при нарушении директивных сроков задач // Сборник статей студентов и аспирантов. Факультет ВМК МГУ им. М.В. Ломоносова. Вып. I. - М.: Издательский отдел факультета ВМК МГУ им. М. В. Ломоносова, 2002. - С. 5-21.

3. Балашов В. В. О поддержке анализа поведения встроенных вычислительных систем // Методы и средства обработки информации. Труды первой Всероссийской научной конференции. - М.: Издательский отдел факультета ВМК МГУ им. М. В. Ломоносова, 2003. - С. 274-281.

4. Балашов В. В. Поддержка принятия решений при построении циклограммы обменов по мультиплексному каналу // Методы и средства обработки информации. Труды второй Всероссийской научной конференции.

- М.: Издательский отдел факультета ВМК МГУ им. М. В. Ломоносова, 2005. -С. 508-515.

5. Балашов В. В., Вавинов С. В., Гурьянов Е. С., Костенко В. А., Смелянский Р. Л. Система автоматического построения циклограммы обменов по шине с централизованным управлением // Методы и средства обработки информации. Труды второй Всероссийской научной конференции. - М.: Издательский отдел факультета ВМК МГУ им. М. В. Ломоносова, 2005. -С. 516-521.

6. Balashov V. V., Kostenko V. A., Smeliansky R. L., Vavinov S. V. A Tool System for Automatic Scheduling of Data Exchange in Real-Time Distributed Embedded Systems // Proc. 7th IEEE International Symposium on Computer Networks (ISCN'06). -2006. - P. 179-184.

7. Балашов В. В. Исследование алгоритмов формирования рекомендаций по изменению требований к информационному обмену в составе САПР комплексирования бортовых устройств // Труды международных научно-технических конференций «Интеллектуальные системы», «Интеллектуальные САПР». - М.: ФИЗМАТЛИТ, 2006. - С. 359-366.

8. Балашов В. В., Вавинов С. В., Костенко В. А., Смелянский Р. Л. САПР для поддержки комплексирования бортовых устройств в единую информационно-управляющую систему // Труды международных научно-технических конференций «Интеллектуальные системы», «Интеллектуальные САПР». - М.: ФИЗМАТЛИТ, 2006. - С. 82-88.

9. Балашов В. В. Формирование рекомендаций по изменению требований к информационному обмену при невозможности построения циклограммы обменов по мультиплексному каналу // Труды Третьей международной конференции «Параллельные вычисления и задачи управления» (РАСО'2006). -М.: Институт проблем управления им. В.А.Трапезникова РАН, 2006. -С. 422-437.

10. Балашов В.В. Алгоритмы формирования рекомендаций при планировании информационного обмена по каналу с централизованным управлением // Известия РАН. Теория и системы управления. - 2007. - № б. -С. 76-84.

11. Balashov V. V., Kostenko V.A., Smeliansky R.L. A Tool System for Automatic Scheduling of Data Exchange in Real-Time Distributed Avionics Systems // Proc. 2nd European Conference for Aerospace Sciences (EUCASS'2007). - 2007. - Электрон, опт. диск (CD-ROM).

12. Балашов В. В., Шестов П. Е. Формирование рекомендаций по обеспечению совместимости требований к обмену по общей шине во встроенных системах реального времени // Труды Четвертой международной конференции «Параллельные вычисления и задачи управления» (РАСО'2008). -М.: Институт проблем управления им. В.А.Трапезникова РАН, 2008. -С. 1385-1404.

13. Balashov V. V., Balakhanov V, A., Kostenko V. A., Smeliansky R. L., ShestovP. E. A Technology for Scheduling of Data Exchange over Bus with Centralized Control in Onboard Avionics Systems // Proc. 3rd European Conference for Aerospace Sciences (EUCASS'2009). - 2009. - Электрон, опт. диск (CD-ROM).

14. Балашов В. В., Костенко В. А. Задачи планирования вычислений для одноприборных систем, входящих в состав вычислительных систем реального времени // Методы и средства обработки информации. Труды третьей Всероссийской научной конференции. -М.: Издательский отдел факультета ВМК МГУ им. М. В. Ломоносова, 2009. - С. 193-203.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 18.02.2010 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 063. Тел. 939-3890. Тел./факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Введение.

1 Описание проблемы.

1.1 Организация информационного обмена по каналу с централизованным управлением.

1.2 Задача обеспечения совместимости требований к расписанию обмена.

1.3 Анализ проблемы несовместимости требований к расписанию обмена.

2 Модель предметной области и формальная постановка задачи.

2.1 Расписание для одноприборной системы без прерывания работ.

2.2 Формальная постановка задачи построения расписания.

2.3 Формальная постановка задачи обеспечения совместимости требований к расписанию (Рост).

3 Свойства требований к расписанию информационного обмена, допускающих ослабление.

3.1 Формальная модель и свойства требований, допускающих ослабление.

3.2 Задача обеспечения совместимости требований к расписанию, допускающих ослабление.

4 Совместимость требований к расписанию информационного обмена.

4.1 Достаточные условия принципиальной несовместимости требований.

4.2 Инвариантность принципиальной совместимости требований относительно максимального числа работ в цепочке.

4.3 Структура области решений задачи Рост.

4.4 Выводы.

5 Существующие методы решения задачи -Рост.

5.1 Характеристика задачи обеспечения совместимости требований.

5.2 Исчерпывающий поиск.

5.3 Детерминированный направленный поиск.

5.4 Случайный поиск.

5.5 Метод ветвей и границ.

5.6 Динамическое программирование.

5.7 Алгоритмы имитации отжига и генетические алгоритмы.

5.8 Жадные алгоритмы.

5.9 Выводы.

6 Решение задачи обеспечения совместимости требований к расписанию информационного обмена.

6.1 Конечная сетка на множестве решений.

6.2 Общее описание алгоритма решения задачи Рост.

6.3 Случайный поиск решений с сужением множества поиска.

6.4 Поиск по направлению наискорейшего убывания целевой функции.

6.5 Последовательное усиление требований.

6.6 Эвристическое сужение области поиска на основе свойств требования Rmcc

6.7 Алгоритм обеспечения совместимости требований.

7 Экспериментальное исследование разработанного алгоритма.

7.1 Структура методики исследования.

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

7.3 Выбор алгоритмов решения задачи Рост для сравнительного исследования.

7.4 Выбор алгоритмов построения расписания.

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

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

7.7 Схемы проведения и результаты экспериментов.

7.8 Выводы.

8 Инструментальные средства обеспечения совместимости требований к расписанию информационного обмена.

8.1 Инструментальная система планирования обмена по каналу с централизованным управлением.

8.2 Подсистема обеспечения совместимости требований к расписанию обмена

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

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

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

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

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

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

При этом предъявляются следующие требования к решению:

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

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

На настоящую работу оказали влияние предложенные в [33, 34] подходы к модификации параметров ВСРВ в случае невозможности построения корректных расписаний функционирования ВСРВ. Необходимо отметить, что ни эти подходы, ни предложенные в [35, 36, 37], не учитывают ряд требований к расписаниям, существенных для каналов с централизованным управлением.

Основные результаты диссертационной работы заключаются в следующем:

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

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

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

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

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

Во второй главе представлена формальная модель предметной области, включающая такие понятия, как набор периодических заданий, набор работ, расписание. В рамках этой модели дана формальная постановка задачи Рост обеспечения совместимости требований к расписанию. Эта задача поставлена в виде задачи математического программирования.

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

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

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

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

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

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

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

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

1 ОПИСАНИЕ ПРОБЛЕМЫ

Основные результаты диссертационной работы заключаются в следующем:

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

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

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

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

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

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

• использование целевой функции, отличной от линейной; в частности:

- кусочно-линейной функции с различными значениями коэффициентов с, на различных участках интервала [xflin; х™ах];

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

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

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

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

• каналы с распределённым управлением [38-44];

• однопроцессорные вычислительные узлы27 [5, 14];

• одноприборные системы, в которых выполнение заданий конвейеризовано например, кольцо с арбитражем FC-AL [68]), в связи с чем длительность выполнения последовательности заданий отлична от суммы длительностей этих

28 заданий и зависит от порядка следования заданий ;

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

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

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

ЗАКЛЮЧЕНИЕ

1.Г0СТ Р 52070-2003. Интерфейс магистральный последовательный системы электронных модулей. - Введ. 01.01.2004 - М. : Изд-во стандартов, 2001. — 23 с.

2. Бахрушин Н. И., Догадкин В. А., Колодцева М. В. и др. Универсальная корабельная система управления // Патент РФ на полезную модель №47540, 27.08.2005.

3. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. -М.: Мир, 1982.-416 с.

4. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990.-486 с.

5. Костенко В. А., Гурьянов Е. С. Алгоритм построения расписаний обменов по шине с централизованным управлением и исследование его эффективности // Программирование. 2005. - № 6. С. 340-346.

6. Гуз Д. С. Разработка точных и приближенных алгоритмов составления расписаний и синтеза систем жесткого реального времени : дис. . канд. физ.-мат. наук : 05.13.18/МФТИ.-М„ 2005. 132 с.

7. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. М.: ФИЗМАТЛИТ, 2005. - 368 с.

8. Растригин Л. А. Статистические методы поиска. -М.: Наука, 1968. 376 с.

9. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы. М.: ФИЗМАТЛИТ, 2006. - 320 с.

10. Беллман Р. Динамическое программирование. — М.: Изд-во иностранной литературы, 1960. -400 с.

11. Коган Д. И. Задачи и методы конечномерной оптимизации. Часть 3. Динамическое программирование и дискретная многокритериальная оптимизация.- Нижний Новгород: Изд-во Нижегородского университета, 2004. 157 с.

12. Уоссермен Ф. Нейрокомпьютерная техника: Теория и практика. — М.: Мир, 1992. -240 с.

13. Трекин А. Г. Структурный синтез вычислительной системы с помощью генетических алгоритмов : дис. . канд. физ.-мат. наук : 05.13.11 / МГУ им. М. В. Ломоносова. М., 2002. - 111 с.

14. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. -2-е изд. М.: Издательский дом Вильяме, 2005. — 1290 с.

15. Ильин В. А., Ким Г. Д. Линейная алгебра и аналитическая геометрия. М.: Изд-во Московского университета, 2002. — 320 с.

16. ГмурманВ. Е. Теория вероятностей и математическая статистика. М.: Высшая школа, 2003.-479 с.

17. Калинина В. Н., Панкин В. Ф. Математическая статистика. М.: Высшая школа, 1998.-336 с.

18. ГОСТ 23501.101-87. Системы автоматизированного проектирования. Основные положения. Введ. 01.07.1988 - М. : Изд-во стандартов, 2001.- 11 с.

19. Кремер Н. Ш. Теория вероятностей и математическая статистика. — М.: Юнити, 2004. 573 с.

20. Чистяков В. П. Курс теории вероятностей. М.: Наука, 1978. - 224 с.

21. Guide to Digital Interface Standards for Military Avionic Applications : Technical report ASSC/110/6/2-ISSUE 3 // Avionics Systems Standardization Committee (ASSC).- UK, 2006. 249 p.

22. Information technology Fibre Channel - Part 312: Avionics environment upper layer protocol MIL-STD-1553B Notice 2 (FC-AE-1553) : Technical Report TR 14165-312:2009 // International Organization for Standardization (ISO). - 2009. - 84 p.

23. Stewart D. В., Arora G. A Tool for Analyzing and Fine Tuning the Real-Time Properties of an Embedded System // IEEE Trans. Software Engineering. 2003. - Vol. 29, No. 4.-P. 311-326.

24. Park J., Ryu M., Hong S., Bello L. L. Rapid Performance Re-engineering of Distributed Embedded Systems via Latency and k-level diagonal search // Journal of Parallel and Distributed Computing. 2006. - Vol. 66, Issue 1. - P. 19-31.

25. Chien S., Gratch J. Producing Satisfying Solutions to Scheduling Problems: An Iterative Constraint Relaxation Approach // Proc. 2nd International Conference on Artificial Intelligence Planning Systems (AIPS'94). -2006. P. 78-87.

26. BambhaN. K., Bhattacharyya S. S., Teich J., Zitzler E. Hybrid Global/Local Search for Dynamic Voltage Scaling in Embedded Multiprocessors // Proc. 9th International Symposium on Hardware/Software Codesign. 2001. - P. 243-248.

27. IEEE 802.3-2008. IEEE Standard for Information technology Specific requirements - Part 3: Carrier Sense Multiple Access with Collision Detection (CMSA/CD) Access Method and Physical Layer Specifications // IEEE Standards Association. - 2008.

28. Information Technology Fibre Channel - Avionics Environment - Anonymous Subscriber Messaging (FC-AE-ASM): Technical Report INCITS/TR-41:2006 // International Committee for Information Technology Standards (INCITS). - 2006. - 32 p.

29. ISO/IEC 15776:2001. VME64bus Specification // International Organization for Standardization (ISO). - 2001. - 262 p.

30. IEEE Std 960-1993. FASTBUS Module High-Speed Data Acquisition and Control System // Institute of Electrical & Electronics Engineering (IEEE). 1994. - 352 p.

31. ISO 11898-4:2004. Road vehicles Controller area network (CAN) - Part 4: Time-triggered communication // International Organization for Standardization (ISO). - 2004. -32 p.

32. FlexRay Communications System Protocol Specification. Version 2.1 //FlexRay Consortium. 2005. - 245 p.

33. Media Oriented System Transport (MOST) Specification. Rev. 3.0 //MOST Cooperation. 2008. - 233 p.

34. Balashov V. V., Kostenko V. A., Smeliansky R. L. et al. A Tool System for Automatic Scheduling of Data Exchange in Real-Time Distributed Embedded Systems // Proc. 7th IEEE International Symposium on Computer Networks (ISCN'06). 2006. -P. 179-184.

35. Blazewicz J., Ecker K., Pesch E., Schmidt G., Weglarz J. Handbook on Scheduling: From Theory to Applications. Springer, 2007. - 647 p.

36. Liu C. L., Layland J. W. Scheduling Algorithms for Multiprogramming in a Hard-RealTime Environment//Journal of the ACM. -1973. Vol. 20, No. 1. - P. 46-61.

37. Audsley N. С., Burns A., Richardson M. F., Wellings A. J. Hard Real-Time Scheduling: The Deadline Monotonic Approach // Proc. 8th IEEE Workshop on Real-Time Operating Systems and Software. 1991. - P. 135-138.

38. Jeffay K., Donald F., Stanat D. F., Martel C. U. On Non-Preemptive Scheduling of Periodic and Sporadic Tasks // Proc. 12th IEEE Real-Time Systems Symposium. 1991. -P. 129-139.

39. Tindell K. W., Burns A., Wellings A. J. An Extendible Approach for Analyzing Fixed-Priority Hard Real-Time Tasks // Journal of Real-Time Systems. 1994. - Vol. 6, No. 2. -P. 133-152.

40. Bate I.J. Scheduling and Timing Analysis for Safety Critical Real-Time Systems : Ph.D. thesis / University of York. York, UK, 1998. - 245 p.

41. Katcher D. I., Arakawa H., Strosnider J. K. Engineering and Analysis of Fixed Priority Schedulers // IEEE Trans, on Software Engineering. 1993. - Vol. 19, No. 9. - P. 920-934.

42. Arora G. Automated Analysis And Prediction of Timing Parameters in Embedded Real-Time Systems Using Measured Data : M.Sc. thesis (advisor: Stewart D. B.) / University of Maryland. Maryland, USA, 1997. - 78 p.

43. Sjodin M., Hansson H. Improved Response Time Analysis Calculations // Proc. 19th IEEE Real-Time Symposium. 1998. - P. 399^108.

44. Pollex V., KoIImann S., Albers K., Slomka F. Improved Worst-Case Response-Time Calculations by Upper-Bound Conditions // Proc. Conference on Design Automation and Test in Europe (DATE'09). 2009. - P. 105-110.

45. Sun J. Fixed-Priority End-To-End Scheduling in Distributed Real-Time Systems : Ph.D. thesis // University of Illinois at Urbana-Champaign. -Champaign, IL, USA, 1997. 183 P.

46. Peng Z. Synthesis of Fault-Tolerant Schedules with Transparency/Performance Tradeoffs For Distributed Embedded Systems // Proc. Conference on Design Automation and Test in Europe (DATE'06). 2006. - P. 706-711.

47. Pop Т., Pop P., Eles P., Peng Z. Analysis and Optimisation of Hierarchically Scheduled Multiprocessor Embedded Systems // International Journal of Parallel Programming. 2008. -Vol. 36, No. 1.-P. 37-67.

48. Standard Template Library: Containers. HTML] (http://www.cplusplus.com/reference/stl/).

49. Glover F., Laguna F. Tabu search. Norwell, MA, USA: Kluwer Academic Publishers, 1997.-408 p.

50. Kirkpatrick S., Gelatt C. D., Vecchi, M. P. Optimization by Simulated Annealing //Science. 1983.-No. 4598.-P. 671-680.

51. Wah B. W., Chen Y. Hybrid Constrained Simulated Annealing and Genetic Algorithms for Nonlinear Constrained Optimization // Proc. IEEE Congress on Evolutionary Computation. -2001.-P. 925-932.

52. Barr R., Golden B. L., Kelly J. P., Resende M. G. C., Stewart W. R. Designing and Reporting on Computational Experiments with Heuristic Methods // Journal of Heuristics.- 1995. Vol. 1, No. 1.-P. 9-32.

53. Mason R. L., Gunst R. F., Hess J. L. Statistical Design and Analysis of Experiments, with Applications to Engineering and Science. 2nd edition. - Wiley, 2003. - 760 p.

54. Мок A. K. Fundamental design problems of distributed systems for the hard-real-time environment : Ph.D. thesis / Massachusetts Institute of Technology. Cambridge, MA, USA, 1983.- 186 p.

55. Balashov V. V., Kostenko V. A., Smeliansky R. L. A Tool System for Automatic Scheduling of Data Exchange in Real-Time Distributed Avionics Systems // Proc. 2nd European Conference for Aerospace Sciences. 2007. - Электрон, опт. диск (CD-ROM).

56. WxWidgets Cross-Platform GUI Library. HTML] (http://wxwidgets.org/).

57. ISO/IEC 14165-122:2005. Information technology Fibre Channel - Part 122: Arbitrated Loop-2 (FC-AL-2) // International Organization for Standardization (ISO). - 2005.- 144 p.

58. Unified Modeling Language Specification. Version 1.4.2. PDF] (http://www.omg.org/docs/formal/05-04-01 .pdf).