Московский государственный университет

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

Факультет вычислительной математики и кибернетики

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

Бычков Иван Алексеевич

ПЛАНИРОВАНИЕ ОБМЕНОВ В СЕТЯХ С ТОПОЛОГИЕЙ

КОЛЬЦА С АРБИТРАЖЕМ ДЛЯ СИСТЕМ

РЕАЛЬНОГО ВРЕМЕНИ

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

АВТОРЕФЕРАТ

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

Москва 2013

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

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

Официальные оппоненты: доктор технических наук, профессор Колесов Николай Викторович;

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

Ведущая организация: ОАО «НИИВК им. М. А. Карцева».

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

+7 (495) 939-30-10 (для оформления заявки на пропуск).

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

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

Учёный секретарь диссертационного совета Д 501.001. к. т. н., в. н. с. Костенко В. А.

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

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

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

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

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

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

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

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

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

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

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

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

Разработать алгоритм построения расписаний обменов в кольце с арбит­ Разработать алгоритм выбора порядка абонентов в кольце с арбитражем.

Провести исследование разработанных алгоритмов на реальных и мо­ дельных данных.

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

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

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

1. Предложена математическая модель информационных обменов в кольце с арбитражем, которая позволяет описывать различные способы постро­ ения кольца с арбитражем. В рамках разработанной модели предложена постановка задач построения расписания обменов и выбора порядка або­ нентов в кольце с арбитражем. Доказана NP-трудность поставленных 2. Разработан алгоритм построения расписаний обменов в кольце с арбит­ ражем на основе метода ветвей и границ. Получены достаточные усло­ вия, при которых алгоритм является точным. Получена верхняя оценка вычислительной сложности алгоритма.

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

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

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

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

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

Практическая ценность. Разработано программное средство, в кото­ ром реализованы предложенные алгоритмы построения расписаний обменов и выбора порядка абонентов в кольце с арбитражем. Данной программное средство может быть использовано при проектировании сложных вычисли­ тельных систем, в которых информационные обмены выполняются по ста­ тическому расписанию, а в качестве среды передачи данных используется кольцо с арбитражем стандарта Fibre Channel.

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

III Всероссийская научная конференция «Методы и средства обработки информации» (MCO-2009), Москва, 6-8 октября 2009;

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

VI Международная конференция «Параллельные вычисления и задачи управления» (PACO’2012), Москва, 24-26 октября 2012.

Публикации. По теме диссертации опубликовано 7 печатных работ, в том числе работа в журнале «Математическое моделирование», который вхо­ дит в перечень рецензируемых научных журналов ВАК РФ. Список работ приведён в конце автореферата.

Структура и объём диссертации. Диссертация состоит из введения, шести глав, заключения, списка литературы и девяти приложений. Объём ра­ боты — 170 страница (включая приложения), объём приложений составляет 65 страниц. Список литературы содержит 81 наименование.

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

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

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

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

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

Для каждого информационного обмена из множества известны зна­ чения следующих его атрибутов:

() – количество слов данных в информационном обмене;

() – адрес порта-передатчика информационного обмена;

() – множество адресов портов-приёмников информационного об­ () – директивное время начала выполнения информационного обмена – момент времени, ранее которого не должно начинаться выполнение информационного обмена;

() – директивное время окончания выполнения информационного об­ мена – момент времени, позднее которого не должно заканчиваться вы­ полнение информационного обмена.

Совокупность этих величин позволяет однозначно вычислить:

для каждого информационного обмена величину () – длительность информационного обмена;

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

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

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

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

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

В разделе 1.4 описаны формальная модель информационных обменов и формальная постановка задачи TSCH выбора порядка абонентов в кольце с арбитражем.

Определение 1. Множеством исходных информационных обме­ нов называется непустое конечное множество, на котором определены следующие четыре функции:

() : R+ – директивное время начала выполнения информацион­ () : R+ – директивное время окончания выполнения информа­ () : R+ – длительность выполнения информационного обмена ;

(, ) : R+ – функция минимально допустимых задер­ Определение 2. Расписанием обменов (соответствующим мно­ жеству исходных информационных обменов ) называется множе­ ство, на котором определена функция * () : R+ – время нача­ ла выполнения информационного обмена. Причём для множества и для функции * () должны выполняться следующие два условия:

1. () * () * () () – интервал выполнения каж­ дого информационного обмена должен лежать внутри его директивного интервала;

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

Здесь использованы следующие обозначения:

* () = * () + () – время окончания выполнения информационного () – множество информационных обменов, непосредственно следу­ ющих за информационным обменом. Множество () может содер­ жать несколько информационных обменов, если время начала выполне­ ния * () для них одинаково.

Формальная постановка задачи TSCH построения расписания обменов в кольце с арбитражем. Задано множество исходных информа­ ционных обменов с определёнными на нём функциями (), (), () и функция (, ), определённая на множестве. Требуется найти расписание, такое что || max.

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

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

В разделе 2.2 приведено описание задачи выбора порядка абонентов в кольце с арбитражем. Данная задача рассматривается для различных топо­ логий и различных способов организации информационных обменов в кольце с арбитражем. Для каждой из топологий определён свой набор параметров топологии, а для каждого способа организации информационных обменов – свой набор параметров способа организации информационных обменов. Ито­ говая совокупность параметров кольца с арбитражем образуется объединени­ ем этих параметров и зависит от того, какая используется топология и какой способ организации информационных обменов.

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

Задача выбора порядка абонентов в кольце с арбитражем рассматрива­ ется в данной работе в следующей постановке. Заданы:

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

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

В разделе 2.3 приведена формальная постановка задачи выбора порядка абонентов в кольце с арбитражем. Задачу выбора порядка абонентов в коль­ це с арбитражем сокращённо будем обозначать символом TORD. Исходные данные в задаче TORD выбора порядка абонентов в кольце с арбитражем:

– фиксированный набор значений неизменяемых параметров;

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

– непустое конечное множество исходных информационных обменов.

На множестве определены функции:

– () : R+ – директивное время начала выполнения информа­ – () : R+ – директивное время окончания выполнения инфор­ допустимых задержек.

Определение 6. Индивидуальной задачей TORD (), получающейся при фиксированном порядке абонентов, будем называть задачу TSCH, для ко­ торой:

=. На множестве определены функции:

Здесь все величины «с волной» относятся к задаче TORD (), а «без волны» – к задаче TORD. Элемент множества соответствует элементу множества. Значение величины задано из условий задачи TORD.

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

Здесь запись TORD () означает, что расписание информационных обме­ нов является оптимальным решением задачи TORD ().

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

метод полного перебора, жадные алгоритмы, метод ветвей и границ, гене­ тические и эволюционные алгоритмы, муравьиные алгоритмы, метод дина­ мического программирования, алгоритмы на основе нейросетей Хопфилда, ненаправленный случайный поиск, направленный случайный поиск.

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

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

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

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

Раздел 4.1 посвящён алгоритму решения задачи построения расписания обменов. В подразделе 4.1.1 описаны входные данные и результат работы алгоритма. Входными данными алгоритма ASCH являются:

непустое множество исходных информационных обменов с определён­ ными на нём функциями (), (), (), (, );

0, (| | 1) – максимальная глубина перебора в дереве поис­ Кроме того, должно быть задано отношение порядка, определяю­ щее порядок выбора информационных обменов при размещении их в распи­ сание, и отношение порядка, определяющее информационный обмен, подлежащий удалению в случае, если алгоритм просмотрел все допустимые варианты.

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

В подразделе 4.1.2 описан принцип работы предлагаемого алгоритма ASCH решения задачи построения расписаний обменов. Данный алгоритм основан на методе ветвей и границ со стратегией поиска в глубину. Процесс работы алгоритма ASCH можно представить как обход дерева поиска – ори­ ентированного графа (, ). Каждой вершине данного графа соответствует некоторое расписание () – набор размещённых в расписании работ (под работой понимается информационный обмен) – и набор () ещё не размещённых работ. Корнем дерева является вершина 0, соответствующая пустому расписанию: (0 ) =, (0 ) =. Вершина называет­ ся тупиковой, если хотя бы одна работа из множества () не может быть добавлена в конец расписания (), поскольку такое добавление по­ влечёт за собой нарушение директивного интервала данной работы или на­ рушение ограничения функции минимально допустимых задержек. Из тупиковых вершин в дереве поиска рёбра не исходят. Вершина, для которой |()| = 0, называется концевой.

Если вершина не является тупиковой, то из неё исходит |()| ориентированных рёбер, каждое из которых соединяет вершину с верши­ ной такой, что () = (), () = (), (). Таким образом, каждому ребру в графе поиска соответ­ ствует некоторая работа, а переходу по ребру = (, ) соответству­ ет перемещение работы из множества неразмещённых работ () в расписание (). При этом работе назначается время начала выполне­ ния * ( ), причём значение величины * ( ) не должно нарушать коррект­ ности расписания (). Существование такого момента времени гаранти­ рованно тем, что вершина не является тупиковой, а значит любая работа из множества () может быть добавлена к расписанию () без нарушения условий его корректности.

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

Для возможности контроля вычислительной сложности алгоритма вве­ дён параметр – максимальная глубина перебора. Если алгоритм на какой-то итерации достиг вершины с глубиной, то возврат по дереву поиска разрешается лишь до вершины с глубиной ( ). При = возвраты по дереву поиска запрещены, при = (| | 1) алгоритм имеет возможность просмотреть всё дерево поиска.

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

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

Алгоритм останавливается, когда найдена концевая вершина.

В подразделе 4.1.3 описаны функции и переменные, используемые в алго­ ритме. В подразделах 4.1.4 и 4.1.5 приведено пошаговое описание алгоритма и используемых в нём функций. В подразделах 4.1.6 и 4.1.7 доказаны кор­ ректность и завершимость алгоритма. В подразделе 4.1.8 доказаны условия, при которых алгоритм является точным.

Утверждение 4. Если = (| |1) и существует полное распи­ сание, то алгоритм построит расписание, которое будет полным.

Утверждение 5. Если для некоторого множества исходных работ и значения параметра алгоритм ASCH выдаёт полное расписание, то при увеличении значения параметра расписание, выдаваемое алгоритмом, также будет полным.

В подразделе 4.1.9 получена следующая верхняя оценка вычислительной сложности алгоритма: (| | +2 ).

Раздел 4.2 посвящён алгоритму AORD решения задачи выбора порядка абонентов в кольце с арбитражем. В подразделе 4.2.1 описаны входные дан­ ные и результат работы алгоритма. Входные данные для алгоритма AORD совпадают с исходными данные для задачи TORD выбора порядка абонентов в кольце с арбитражем.

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

Каждая особь представляет собой порядок абонентов в кольце с арбитражем и кодируется перестановкой длины, где – число абонентов в кольце с ар­ битражем. Целевая функция определяется как максимальное число работ, ко­ торое можно разместить в расписание для порядка абонентов, соответствую­ щего заданной особи. Значения целевой функции в алгоритме AORD прибли­ жённо вычисляются алгоритмом ASCH. На вход алгоритма ASCH подаётся заданное множество исходных информационных обменов, получающееся при фиксировании порядка абонентов, для которого вычисляется целевая функция. В подразделе 4.2.2 описаны также параметры алгоритма, крите­ рии останова, операция создания случайной особи, алгоритмы выполнения селекции, скрещивания и мутации особей и формирования новой популяции.

В подразделе 4.2.3 доказаны корректность и завершимость алгоритма.

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

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

В подразделе 5.2 описаны исходные данные, используемые в эксперимен­ тах. Исследования проводились на реальных и модельных исходных данных.

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

Использовались три вида реальных данных: неизменённые реальные дан­ ные, реальные данные с увеличенным объёмом передаваемой информации и шаблонные реальные данные.

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

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

Шаблонными реальными данными (или просто шаблонными данными) называются исходные данные, полученные по неизменённым реальным дан­ ным с применением метода шаблонов. Этот метод позволяет получать ис­ ходные данных, имеющие частотно-фазовые характеристики, близкие к ча­ стотно-фазовым характеристикам исходных неизменённых реальных данных.

Использовалось два вида модельных данных: заведомо совместимые мо­ дельные данные и заведомо несовместимые модельные данные. Для заведомо совместимых модельных данных существуют полные расписания, тогда как для заведомо несовместимых модельные данных полных расписаний не суще­ ствует.

В подразделе 5.3 описаны результаты исследований. Подраздел 5.3.1 по­ свящён результатам исследования алгоритма построения расписаний ASCH.

Для данного алгоритма были выбраны параметры и операции, которые ис­ пользовались в исследованиях. Сначала было выбрано отношение порядка, определяющее очередную работу, подлежащую добавлению в расписа­ ние. Исследование показало, что лучшим отношением порядка является отно­ шение порядка с функцией () = ()+* ()+(). Затем было выбрано отношение порядка, определяющее работу, подлежащую удалению из расписания. Было получено, что наилучшими являются отношения порядка и () = () соответственно. Затем была выбрана максимальная глубина перебора, при которой время работы алгоритма не превосходит мин. на одном ядре суперкомпьютера «Ломоносов», установленном в МГУ имени М. В. Ломоносова (процессор Intel Xeon 5570 Nehalem). Исследование проводилось на модельных данных с числом исходных информационных об­ менов, равным 25, 100, 500 и 2500, для которых были получены следующие значения максимальной глубины перебора: 5, 3, 1, 0 соответственно.

Была выполнена оценка точности алгоритма построения расписаний на выбранных значениях параметров. Исследование на трёх множествах реаль­ ных исходных данных показало, что для каждого из этих множеств можно увеличить объём передаваемых данных в 320, 830 и 2140 раз соответственно, и при этом алгоритм построит полное расписание. Исследование на заведомо совместимых модельных данных с числом исходных работ равным 100 пока­ зало, что даже на самом сложном классе исходных данных с вероятностью не менее 0,95 алгоритм в худшем случае не размещает только одну работу.

Была выполнена оценка числа выполненных возвратов по дереву поис­ ка для различных типов исходных данных. Наибольшее значение возвратов составило 68 588 311 на заведомо совместимых модельных данных с числом исходных информационных обменов, равным 25, и максимальной глубиной перебора, равной 10.

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

Подраздел 5.3.2 посвящён результатам исследования алгоритма AORD выбора порядка абонентов. В подразделе 5.3.2.1 выбраны исходные данные, на которых проводились исследования. Выбор осуществлялся на основании значения вероятности построения полного расписания для случайно выбран­ ного порядка абонентов. Всего было выбрано семь различных наборов исход­ ных данных. В подразделе 5.3.2.2 выбраны параметры, используемые в даль­ нейших исследованиях. В подразделе 5.3.2.3 выполнено исследование точно­ сти алгоритма. При стократном запуске алгоритма AORD на всех семи на­ борах исходных данных разработанный алгоритм нашёл порядок абонентов, для которого было построено полное расписание. В подразделе 5.3.2.4 выпол­ нено исследование вычислительных затрат на выполнение алгоритма. Разра­ ботанный алгоритм сравнивался с алгоритмом случайного поиска. Исследова­ ние показало, что в большинстве исследованных случаев преимущество алго­ ритма AORD составляет 10–35%. В подразделе 5.3.2.5 показана стабильность алгоритма. В подразделе 5.3.2.6 исследовался вклад составляющих алгорит­ ма в его точность. В качестве составляющих алгоритма рассматривались его параметры. Исследование показало, что наибольшее влияние на точность ал­ горитма оказывает параметр «доля элитных особей от размера популяции при формировании новой популяции». Остальные параметры оказывают су­ щественно меньшее влияние на результат работы алгоритма.

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

редактировать параметры кольца с арбитражем;

редактировать множества информационных обменов в кольце с арбитра­ жем (в т. ч. импортировать данные из файлов для шины МКИО ГОСТ Р 52070-2003);

выполнять построение расписаний информационных обменов;

выполнять выбор порядка абонентов в кольце с арбитражем.

Кроме того, инструментальная система должна:

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

обеспечивать возможность работы как в консольном режиме, так и с использованием графического интерфейса пользователя;

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

В подразделе 6.2 приведена структура инструментальной системы. Ин­ струментальная система состоит из трёх компонентов. Все компоненты систе­ мы написаны на языке C++. Суммарный объём кода составляет 10012 строк, 338 Кбайт.

Главным компонентом разработанной инструментальной системы явля­ ется библиотека «система автоматизированного построения расписаний в кольце с арбитражем», реализующая предложенные в данной работе алго­ ритмы. Данная библиотека состоит из шести классов и одного пространства имён.

Второй компонент системы – два консольных приложения: asch и aord, которые позволяют из командной строки запускать соответственно алгорит­ мы ASCH и AORD. Кроме того, эти программы используются в приложении с графическим интерфейсом пользователя.

Третий компонент системы – приложение с графическим интерфейсом пользователя, написанное с использованием кросс-платформенного средства разработки программного обеспечения версии 4.7.

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

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

1. Бычков И. А., Костенко В. А. Возможность использования арбитражного кольца Fibre Channel в вычислительных системах реального времени // Программные системы и инструменты. Тематический сборник №8, М.:

Изд-во факультета ВМиК МГУ, 2007. – С. 157-172.

2. Бычков И. А. Алгоритмы построения расписания обменов и выбора по­ рядка устройств в кольце с арбитражем для систем реального времени // Сборник тезисов лучших дипломных работ 2008 года / Сост. Шевцова И. Г., Ильин А. В. – М.: Издательский отдел Факультета ВМиК МГУ им.

М. В. Ломоносова; МАКС Пресс, 2008. – С. 81-82.

3. Бычков И. А., Костенко В. А. Задачи построения расписания обменов и выбора структуры сети для кольца с арбитражем // Методы и сред­ ства обработки информации: Третья Всероссийская научная конферен­ ция, Москва, 6-8 октября 2009 г.: Труды конференции / Под ред. Л. Н.

Королёва. – М.: Издательский отдел ф-та ВМиК МГУ; МАКС Пресс, 2009. – С. 204-214.

4. Бычков И. А., Костенко В. А. Особенности задачи построения расписа­ ния обменов в кольце с арбитражем для систем реального времени // VI Московская международная конференция по исследованию операций (ORM2010): Москва, 19-23 октября 2010 г.: Труды / Отв. ред. П.С. Крас­ нощёков, А. А. Васин. – М.: МАКС Пресс, 2010. – С. 285-287.

5. Бычков И. А. Представление математических моделей сред передачи дан­ ных жёсткого реального времени для задач статического планирования // Математическое моделирование. – 2011. – Т. 23. – №12. – С. 117-131.

6. Бычков И. А. Алгоритм выбора порядка абонентов в сети с топологией кольца с арбитражем // Параллельные вычисления и задачи управления (PACO’2012). Шестая международная конференция, Москва, 24–26 окт.

2012 г. – Труды: в 3 т. – М.: ИПУ РАН, 2012. – Т. 1. – С. 238-249.

7. Бычков И. А. Алгоритм решения задачи построения расписаний для про­ извольно заданной функции минимально допустимых задержек // Мир компьютерной автоматизации: встраиваемые компьютерные системы, №2, 2013. – С. 52-64.