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

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

<—

с;

Юхта Павел Валерьевич

ПЛАНИРОВАНИЕ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА В НАВИГАЦИОННЫХ КОМПЛЕКСАХ

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

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

3 О СЕН 2010

Санкт-Петербург 2010

004609486

Работа выполнена в ОАО «Концерн «ЦНИИ «Электроприбор» -Государственный научный центр Российской Федерации

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

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

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

доктор технических наук, профессор Колесов Николай Викторович

доктор технических наук, профессор Тропченко Александр Ювенальевич

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

ОАО «Российский институт радионавигации и времени»

Защита состоится 20 октября 2010 г. в 15 час. 30 мин. на заседании диссертационного совета Д212.227.06 при Санкт-Петербургском государственном университете информационных технологий, механики и оптики по адресу: 197101 Санкт-Петербург, Кронверкский просп., 49.

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

Автореферат разослан 13 сентября 2010 г. Ученый секретарь диссертационного совета,

доктор технических наук, профессор Г Лисицына Л.С.

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

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

Проблеме планирования вычислительного процесса всегда уделялось и продолжает уделяться достаточно большое внимание. Широкое освещение известных результатов можно найти в работах Коффмана Э.Г., Левина В.И., Топоркова В.В., Костенко В.А., Stankovic J.A, Cottet F., Liu J.W.S. Целый ряд решений вопросов планирования был предложен в рамках теории расписаний в работах Конвея Р.В., Танаева B.C., Brucker Р. и многих других. Тем не менее, в настоящее время многие проблемы из этой области и, в особенности для систем реального времени не решены с достаточной полнотой. Так, известные алгоритмы поиска оптимальных планов характеризуются высокой алгоритмической сложностью, поэтому на практике обычно используют приближенные локально-оптимальные алгоритмы или алгоритмы, основанные на эвристиках. Однако и эти алгоритмы достаточно сложны и не учитывают особенностей организации вычислительного процесса в навигационном комплексе, которые характерны для многих систем реального времени. Кроме того, следует констатировать, что в литературе практически отсутствуют

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

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

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

- анализ современных методов планирования вычислительного процесса в системах реального времени;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Разработанное программное обеспечение, в котором реализован метод многопоточного планирования, позволяет существенно сократить временные затраты на составление планов вычислительного процесса в навигационных комплексах. Программное обеспечение применено в опытно-конструкторских разработках цифрового вычислительного комплекса типа «Струна», входящего в состав морского навигационного комплекса типа «Симфония».

2. Разработанный метод планирования с минимизацией средней неточности временной привязки задач применен в гидроакустическом лаге изделия «Амазонка».

Основные положения, выносимые на защиту:

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

- результаты анализа эффективности субоптимального метода однопоточного планирования вычислительного процесса для распределенных систем реального времени с иерархическим отношением предшествования для решаемых задач;

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

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

Апробация работы. Материалы диссертации докладывались на международных научно-технических конференциях «Кибернетика и высокие технологии XXI века» (Воронеж, 2007; 2009), на 3-й Всероссийской научно-технической конференции «Методы и средства обработки информации» МСО-2009 (Москва, 2009), на XXVI конференции памяти выдающегося конструктора гироскопических приборов H.H. Острякова (Санкт-Петербург,

2008), на IX, X, XI, и XII конференциях молодых ученых «Навигация и управление движением» (Санкт-Петербург, 2007-2010).

Публикации. По материалам диссертации имеется 13 опубликованных работ, из них 2 статьи в научно-технических журналах («Вестник компьютерных и информационных технологий» и «Гироскопия и навигация»), рекомендуемых ВАК Минобразования и науки РФ, 9 докладов и 1 реферат доклада на международных и всероссийских конференциях, 1 свидетельство о государственной регистрации ПО для ЭВМ.

Структура и объем диссертации. Диссертация состоит из введения, четырех разделов, заключения и списка использованных источников, содержащего 80 наименований. Объем работы составляет 149 страниц, включая 59 рисунков и 24 таблицы.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении приводится общая характеристика работы - ее актуальность, научная новизна, практическая ценность и апробация. Формулируются основные положения, выносимые на защиту.

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

вычислительной системы С = {Ь,т}, которая характеризуется иерархией

решаемых задач. Каждая задача разбивается на п фрагментов (по числу процессоров). В результате отношение предшествования для фрагментов любой задачи имеет иерархический характер. При этом /-ый фрагмент у-ой задачи решается на / -ом процессоре за время еч / = 1, п, _/ = 1, т и еи = - /,"у, где и /*у - времена начала и конца решения фрагмента У-ой задачи на /'ом процессоре.

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

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

Причины неточной временной привязки моментов начала решения задач могут быть различны. Среди них зависимость длительности решения задач от значений текущих исходных данных, прерывания, апериодические задачи, изменения в составе решаемых задач. Будем говорить, что у'-ая задача привязана к моменту времени Г с точностью 8 ■, если время начала решения

этой задачи лежит в интервале [Г - <5 , Г +<3]. При этом время решения ] -ой задачи может быть охарактеризовано временным интервалом

из п процессоров и множеством т = {тj\j = l,m) из т

} = 1,'и. Неопределенность времени выполнения задачи определяется величиной Д; "€/)•

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

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

1. Построить план тс*. ={гу |/= \,т}, оптимальный по критерию минимума максимального отклонения от заданных директивных сроков.

2. Осуществить переупорядочивание (сортировку) задач лдс в рамках

ограничений по директивным срокам по возрастанию степени Д (у = \,т)

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

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

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

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

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

1. Для каждой 7 -й задачи в каждой /-й компоненте связности вычисляется средняя по множеству связанных с ней задач неопределенность

IX

длительности Д. = ——.

' )

2. Для каждой /-й компоненты связности вычисляется Д' = тт А'.. Для

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

3. Множество размещенных задач исключается из состава /'-й компоненты. Если множество планируемых задач исчерпано, то конец, иначе перейти к п. 1.

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

Подытоживают этот фрагмент диссертации материалы по применению на практике полученных результатов при планировании вычислительного процесса в одной из систем НК - гидроакустическом лаге «Амазонка».

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

Рис. 1. Пример иерархической системы (пунктирной линией обозначено отношение доминирования)

Для каждой задачи из исходного списка т = {т]\] = \,т) определен директивный срок (с/у | ] = 1,т} ее завершения. При этом в результирующем плане задачу будем характеризовать отклонением от заданного для нее директивного срока {¿Г | ] = \,т], которое вычисляется как 5] = I" - для всех

} = 1, т, /* -время завершения ) -ой задачи. Проблема состоит в поиске алгоритма планирования, минимизирующего максимальное отклонение

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

Определение. Процессор L4 доминирует над процессором Lr (Lq> Lr) на

заданном множестве задач, если mine > maxer .

у 4.1 j ■1

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

Класс I. Множество процессоров системы представляет собой последовательность Lt > ¿2 >...> Ln, убывающую по отношению доминирования.

Класс 2. Множество процессоров системы представляет собой последовательность Lt < L2 <... < Ln, возрастающую по отношению доминирования.

Класс 3. Множество процессоров системы представляет собой пару соединенных последовательностей Ц < Ь2 <... < Lh >... > Lni > Ln, 1 <h<n первая из которых возрастает, а вторая убывает по отношению доминирования.

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

1. Класс 1: в порядке возрастания виртуальных директивных сроков, определяемых выражением:

d)=drteu. i=2

2. Класс 2: в порядке возрастания исходных директивных сроков dj.

3. Класс 3: в порядке возрастания виртуальных директивных сроков, определяемых выражением: d" = d.- £ е],

где К - процессор на стыке возрастающей и убывающей последовательностей процессоров критического пути.

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

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

Предлагаемый метод представляет собой итерационный метод построения плана, на каждом шаге которого в формируемом плане размещается одна задача из числа принадлежащих исходному множеству г = {гу |у = 1,1я) и не

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

I 1 (

шаге система Cj={L,rt}, где тк - множество неразмещенных задач

(гт с...сг4 с с.-.сг, =г), к = \,т - номер итерации. В более формальном описании алгоритм имеет вид:

1. Найти в системе С[=(1,тк) (на первом шаге к = 1, С'к = С) вычислительный путь рп который назовем критическим и который

характеризуется наибольшим значением суммы е(р,) = ¿е, верхних границ

(.1

el=ma.\ei J времен решения задач. Заметим, что критический путь в общем

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

2. На основе эвристического классификационного правила определить, к какому разрешимому классу наиболее близка рассматриваемая система С[ =(Ь,т'к) на к-м шаге.

3. Определить с использованием соответствующего метода задачу 5, которая размешается к-й в итоговом плане. Если к^т, то исключить задачу 5 из множества х'к, которое будет обозначаться как и перейти к п.1 алгоритма. Если к~т, конец.

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

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

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

процессоров (рис.2), так и для системы из 31 процессора не менее чем в 80%

случаев были построены планы, уступающие оптимальному плану

14

(полученному методом полного перебора вариантов) не более чем на 10%, а в 99% случаев - планы, уступающие оптимальному не более чем на 30%.

0,9 --------------г -----------------------

0 3------- ....----------------_ _------ .. ------------ ------

0,7--------------------------------- -...... - -------

06---------------------------------„ . ----—.....—-----

—•— ОТХЛ 10%

05--------------------------------------------- - откл 20%

0 4_________ ___________________________________-*-- откл 30%

0,3 . ---------------------------------- ---------

0.2-------------------- ------------ -------

0,1-------- ------------------- - - - - - - -------- - - - --

5(75) в (90) 7(105) 8(120) 9(135) 10(150)

число задач (фрагментов)

Рис. 2. Эффективность субоптнмалыюго метода для иерархических систем, состоящих

из 15 процессоров

Упрощенное описание предложенного метода многопоточного планирования включает четыре этапа:

1. Определение на основе анализа алгоритмического обеспечения НК множества планируемых задач, их характеристик и состава потоков.

2. Внутрипоточное планирование задач предложенным субоптимальным методом и совмещение планов потоков по известному ЯМБ-алгоритму.

3. Формирование задания для планирования обменов в магистральном канале обмена (МКО) с централизованным управлением (при наличии такового).

4. Планирование по известным алгоритмам обменов МКО с централизованным управлением (при наличии такового).

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

Метод многопоточного планирования реализован в программном обеспечении поддержки планирования вычислительного процесса в навигационных комплексах «Система автоматизации разработки плана вычислительного процесса» [13].

В четвертом разделе диссертации представлены результаты апробации предлагаемого метода многопоточного планирования при планировании вычислительного процесса в морском НК типа «Симфония», который включает 16 процессоров и предназначен для высокоточной выработки параметров навигации и ориентации морского объекта и выдачи этой информации потребителям. При этом потребовался предварительный анализ задач, решаемых комплексом, для выделения среди них планируемых задач по принципу «одна задача - один вырабатываемый в НК параметр». В результате сформировано 3 потока (10Гц, 1 Гц, 0.01 Гц), 9 задач высокочастотного потока, 19 задач низкочастотного потока, 1 задача фонового потока. Общее число фрагментов функциональных задач составило 109.

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

навигационного комплекса «Симфония»

В четвертом разделе приведены также результаты симуляции построенного плана с помощью стенда моделирования ДИАНА, разработанного сотрудниками факультета ВМиК МГУ имени М.В. Ломоносова. Проанализирована зависимость временного запаса потоков от неопределенности их длительности. Проведенная апробация продемонстрировала эффективность предложенного метода и соответствующего программного обеспечения.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

1. Юхта, П. В. Планирование вычислительного процесса в многопроцессорных системах при заданных для решаемых задач директивных сроках / П. В. Юхта, Н. В. Колесов, М. В. Толмачева // Вестник компьютерных и информационных технологий. - 2009. - № 6. -С. 31-37.

2. Юхта, П. В. Опыт применения программной среды ДИАНА для моделирования и интеграции бортовых вычислительных систем / П. В. Юхта и [и др.] // Гироскопия и навигация. - 2009. - № 2. - С. 48-55.

3. Юхта, П. В. Оптимальные алгоритмы планирования вычислений в распределенных иерархических системах при заданных директивных сроках. Кибернетика и высокие технологии / П. В. Юхта, Н. В.Колесов, М. В. Толмачева // Кибернетика и высокие технологии XXI века: тр. X межд. науч,-техн. конф., Воронеж, 15-17 мая 2007 / НПФ "Саквоее" ООО, 2007. - Т. 1. - С. 680-688

. 4. Юхта, П. В. Программные средства для разработки и исследования вычислительного процесса в навигационном комплексе / П. В. Юхта, М. В. Толмачева // Навигация и управление движением: материалы докл. IX конф. молодых ученых, СПб, 13-15 2007 г. / ГНЦ РФ ЦНИИ "Электроприбор" - СПб, 2008. -С. 282-288.

5. Юхта, П.В. Построение расписаний решения задач с заданными директивными сроками//Гироскопия и навигация. - 2008. -№2. -С. 88.

6. Юхта, П. В. Исследование эффективности алгоритма планирования вычислительного процесса в иерархической системе / П. В. Юхта, М. В. Толмачева // Навигация и управление движением: материалы докл. IX конф. молодых ученых, СПб, 13-15 марта 2007 г. / ГНЦ РФ ЦНИИ "Электроприбор" -СПб,2008. -С.277-282.

7. Юхта, П.В. Планирование вычислений в управляющих системах реального времени / П. В. Юхта, Н. В. Колесов, М. В. Толмачева // Управление и информационные технологии: сб. 5-й науч. конф., 2008. - Т. 2. - С. 43-48

8. Юхта, П. В. Опыт применения программной среды ДИАНА для моделирования и интеграции бортовых вычислительных систем. П. В. Юхта и [и др.] // Рефераты докладов XXVI конференции памяти выдающегося конструктора гироскопических приборов H.H. Острякова. - СПб: ЦНИИ «Электроприбор», 2008 - С. 60-61.

9. Юхта, П. В. Построение расписаний решения задач с заданными директивными сроками // Навигация и управление движением: материалы докл. X конф. молодых ученых, СПб, 11-14 2008 г. / ГНЦ РФ ЦНИИ "Электроприбор" - СПб, 2009 г. - С. 174-179.

10. Юхта, П. В. Исследование чувствительности вычислительного процесса в системах реального времени к его параметрам // Навигация и управление движением: материалы докл. XI конф. молодых ученых, СПб., 1012 2009 г. / ГНЦ РФ ЦНИИ "Электроприбор"- СПб, 2009 г. - С. 160-164.

11. Юхта, П.В. Планирование вычислительного процесса с минимизацией средней неточности временной привязки задач / П. В. Юхта, Н. В. Колесов, М. В. Толмачева // Кибернетика и высокие технологии XXI века: тр. X межд. науч.-техн. конф., Воронеж, 13-15 мая 2009 / НПФ "Саквоее" ООО, 2009-Т. 1.-С. 172-176.

12. Юхта, П. В. Субоптимальное планирование вычислительного процесса в распределенных системах реального времени / П. В. Юхта, Н. В. Колесов, М. В. Толмачева // Методы и средства обработки информации: тр. всеросс. науч.-техн. конф., Москва, 6-8 октября 2009/ М: Издательский отдел факультета ВМиК МГУ имени М.В. Ломоносова; МАКС Пресс, 2009. - 484 с.

13. Юхта П.В. Свидетельство о государственной регистрации программы для ЭВМ №2010613554. Система автоматизации разработки плана вычислительного процесса, 2010.

Введение.

1. Анализ современных подходов при планировании вычислительного процесса в системах реального времени.

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

1.1.1. Классификация методов планирования.

1.1.2. Планирование в однопроцессорных системах реального времени.

1.1.3. Планирование вычислительного процесса в многопроцессорных системах.

1.1.4. Планирование в распределенных системах.

1.2. Особенности организации вычислительного процесса в навигационных комплексах.

1.3. Постановка проблемы планирования в навигационных комплексах.

1.4. Выводы.

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

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

2.1.1. Планирование независимых задач.

2.1.2. Планирование независимых задач при заданных директивных сроках.

2.1.3. Планирование зависимых задач.

2.1.4. Планирование в вычислительной подсистеме гидроакустического лага.

2.2. Разрешимые случаи иерархических систем.

2.3. Построение для распределенных иерархических систем из разрешимых классов оптимальных планов при заданных директивных сроках.

2.4. Выводы.

3. Методы построения планов выполнения задач в навигационных комплексах.

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

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

3.3. Метод многопоточного планирования вычислительного процесса в навигационных комплексах.

3.4. Выводы.

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

4.1. Анализ функционального программного обеспечения НК.

4.2. Построение плана вычислительного процесса НК.

4.3 Анализ корректности плана вычислительного процесса НК с использованием имитационного моделирования.

4.4. Выводы.

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

Проблеме планирования вычислительного процесса всегда уделялось и продолжает уделяться достаточно большое внимание. Широкое освещение этих вопросов дается в работах Коффмана Э.Г., Левина В.И., Топоркова В.В. Stankovic J.A, Cottet F., Liu J.W.S. Целый ряд решений был предложен в рамках теории расписаний в работах Конвея Р.В., Танаева B.C., Brucker Р. и многих других. Известные алгоритмы поиска оптимальных планов особенно для распределенных вычислительных систем характеризуются высокой алгоритмической сложностью, поэтому на практике обычно используют приближенные локально-оптимальные алгоритмы или алгоритмы, основанные на эвристиках. Однако и эти алгоритмы достаточно сложны и, кроме того, не учитывают особенностей организации вычислительного процесса в навигационных комплексах (НК), которые, вообще говоря, характерны для многих систем реального времени. В связи с этим представляется актуальным совершенствование методов планирования вычислительного процесса в НК по пути их формализации, снижения вычислительной сложности и расширения возможностей за счет учета особенностей НК, а также снижения трудоемкости в результате автоматизации процедур планирования. Всё сказанное и определило цель и задачи настоящей диссертационной работы.

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

Полученные результаты имеют существенную практическую значимость. Так предложенный метод многопоточного планирования был положен в основу разработанного программного обеспечения «Система автоматизации разработки плана вычислительного процесса», которое нашло практическое применение при проектировании морского навигационного комплекса типа «Симфония» в ОАО «Концерн «ЦНИИ «Электроприбор», что позволило существенно сократить временные затраты на разработку плана вычислительного процесса. Кроме того, разработанный алгоритм планирования для однопроцессорных систем был применен при построении плана вычислительного процесса гидроакустического лага, входящего в изделие «Амазонка».

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

Материалы диссертации докладывались на международных научно-технических конференциях «Кибернетика и высокие технологии XXI века» (Воронеж, 2007, 2009 г.г.), на 3-й Всероссийской научно-технической конференции «Методы и средства обработки информации» МСО-2009 (Москва, 2009), на XXVI конференции памяти выдающегося конструктора гироскопических приборов H.H. Острякова (Санкт-Петербург, 2008 г.), на IX, X, XI и XII конференциях молодых ученых «Навигация и управление движением» (Санкт-Петербург, 2007, 2008, 2009 и 2010 гг.).

По материалам диссертации опубликовано 15 работ, из них 2 статьи в научно-технических журналах, рекомендуемых ВАК, 5 докладов в материалах проводимой в Санкт-Петербурге конференции молодых ученых «Навигация и управление движением», 2 доклада в сборниках трудов международной научно-технической конференции в г. Воронеж, 1 доклад в сборнике Всероссийской научно-технической конференции «Методы и средства обработки информации» МСО-2009, г. Москва.

На защиту выносятся следующие научные результаты:

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

- результаты анализа эффективности субоптимального метода однопоточного планирования вычислительного процесса для распределенных систем реального времени с иерархическим отношением предшествования для решаемых задач;

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

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

4.4. Выводы

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

1. Произведен анализ функционального программного обеспечения НК «Симфония» и осуществлено его преобразование к виду, удобному для планирования.

2. Сформирован план вычислительного процесса с использованием «Системы автоматизации разработки плана вычислительного процесса».

3. Произведен анализ полученного плана с помощью стенда моделирования «ДИАНА» с целью определения временных запасов для потоков при различной неопределенности длительности выполнения задач.

Заключение

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

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

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

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

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

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

1. Анучин О.Н., Емельянцев Г.И. Интегрированные системы ориентации и навигации для морских подвижных объектов. — СПб.: ЦНИИ «Электроприбор», 2003. 388 с.

2. Вентцель, Е. С. Исследование операций. — М.: Советское радио. -1972.- 552 с.

3. Воеводин, В. В. Параллельные вычисления/ В. В. Воеводин, Вл. В. Воеводин. СПб.: БХВ-Петербург, 2002. - 608 с.

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

5. Дмитриев, С.П. Оценка сдвига частоты в доплеровском измерителе скорости путем идентификации модели принятого сигнала / С. П. Дмитриев, А. И. Соколов // Гироскопия и навигация. — 2006. — №1. — С. 2128.

6. Дубовик, Е. 08ЕК операционная система для автомобильной электроники. // Современная Электроника. - 2010. - №2. - С. 10-11.

7. Зыков А. А. Основы теории графов М.: Наука, 1987. — 383с.

8. Каляев, А. В. Многопроцессорные системы с программируемой архитектурой. М.: Радио и связь. - 1984. - 240 с.

9. Колесов, Н. В. Планирование вычислительного процесса в иерархических системах / Н. В. Колесов, М. В. Толмачева // Теория и системы управления. 2007. - № 2. - С. 5-12.

10. Конвей, Р.В. Теория расписаний. / Р. В. Конвей, В. Л. Максвелл, Л. В. Миллер М.: Наука. - 1975. - 320 с.

11. Костенко В. А. Задача построения расписания при совместном проектировании аппаратных и программных средств // Программирование. — 2002.-№3.-С. 64-80.

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

13. Левин, В. И. Структурно-логические методы исследования сложных систем с применением ЭВМ. М.: Наука. - 1987. — 304 с.

14. Левин, В. И. Оптимизация расписаний в М-стадийной системе с неопределенными временами обработки. // Автоматика и телемеханика. — 2002.- №2.-С. 125- 136.

15. Мирецкий, И. Ю. Синтез субоптимальных расписаний для систем последовательного типа //Изв. РАН. Т и СУ. 2002. - № 1. - С. 137 - 144.

16. Операционная система реального времени QNX Neutrino 6.3. Системная архитектура: Пер. с англ. СПб.: БХВ-Петербург, 2006. — 336 с.

17. Павлов, А. М. Организация перспективных систем информационного обмена: характеристики и ограничения // Изв. РАН. ТиСУ.- 2002. № 6. - С. 123-130.

18. Смелянский, Р. Л. Модель функционирования распределенных вычислительных систем. // Вестн. Московского университета, Сер. 15, Вычислительная математика и кибернетика. 1990. - № 3. - С. 3- 21.

19. Столингс, В. Операционные системы. М.: Изд. Дом «Вильяме», 2002. - 844 с.

20. Танаев, В. С. Теория расписаний. Многостадийные системы. / В. С. Танаев, Ю. Н. Сотсков, В. А. Струсевич М.: Наука. - 1989. - 328 с.

21. Теория расписаний и вычислительные машины / Под ред. Э. Г. Коффмана. М.: Наука. - 1984. - 334 с.

22. Таненбаум, Э. Современные операционные системы. 2-е изд. -СПБ.: Питер, 2002. - 1040 с.

23. Таненбаум, Э. Архитектура компьютера. 5-е издание. — СПб.: Питер, 2007. - 844 с.

24. Топорков, В. В. Модели распределенных вычислений. М.: Физматлит, 2004. - 316 с.

25. Хорошевский, В. Г. Архитектура вычислительных систем. — М.: МГТУ им. Н.Э. Баумана, 2005. 512 с.

26. Юхта, П.В. Программные средства для разработки и исследования вычислительного процесса в навигационном комплексе / П. В. Юхта, М. В. Толмачева // Гироскопия и навигация. 2007. - №2. - С. 105.

27. Юхта, П. В. Исследование эффективности алгоритма планирования вычислительного процесса в иерархической системе / П. В. Юхта, М. В. Толмачева // Гироскопия и навигация. 2007. - №2. — С. 104105.

28. Юхта, П.В. Построение расписаний решения задач с заданными директивными сроками // Гироскопия и навигация. 2008. — №2. - С. 88.

29. Юхта, П.В. Планирование вычислений в управляющих системах реального времени / П. В. Юхта, Н. В. Колесов, М. В. Толмачева // Управление и информационные технологии: сб. 5-й науч. конф., 2008. Т. 2. -С. 43-48

30. Юхта, П. В. Построение расписаний решения задач с заданными директивными сроками // Навигация и управление движением: материалы докл. X конф. молодых ученых, СПб, 11-14 2008 г. / ГНЦ РФ ЦНИИ "Электроприбор" СПб, 2009 г. - С. 174-179.

31. Юхта, П. В. Планирование вычислительного процесса в многопроцессорных системах при заданных для решаемых задач директивных сроках / П. В. Юхта, Н. В. Колесов, М. В. Толмачева // Вестник компьютерных и информационных технологий. 2009. - № 6. - С. 31-37.

32. Юхта, П. В. Опыт применения программной среды ДИАНА для моделирования и интеграции бортовых вычислительных систем / П. В. Юхта и и др. // Гироскопия и навигация. 2009. - № 2. - С. 48-55.

33. Юхта, П. В. Исследование чувствительности вычислительного процесса в системах реального времени к его параметрам// Гироскопия и навигация. 2009. - № 2. - С. 88.

34. Юхта П.В. Свидетельство о государственной регистрации программы для ЭВМ №2010613554. Система автоматизации разработки плана вычислительного процесса, 2010.

35. Andersson В., Baruah S. and Jonsson J., Static-priority scheduling on multiprocessors. // Proceedings of the 22nd IEEE Real-Time Systems Symposium, London, pp. 193-202, December 2001.

36. Baruah S., Buttazzo G., Gorinsky S., Lipari G. Scheduling periodic task systems to minimize output jitter. // Proceedings of the Sixth International Conference on Real-Time Computing Systems and Application, pp. 62-69 1999.

37. Berstis V. Fundamentals of Grid Computing. // Redbooks paper. IBM. 2002. 28 p.

38. Blazewicz J., Scheduling dependent tasks with different arrival times to meet deadline. // Modeling and Performance Evaluation of Computer Systems, North Holland, Amsterdam, pp. 57-65, 1977.

39. Blazewicz J., Ecker K. Multiprocessor Task Scheduling with Resource Requirements // Real-Time Systems, vol. 6. pp 37—53, 1994.

40. Brucker P., Jurisch В., and Sievers B. A branch and bound algorithm for the job-shop scheduling problem.// Discrete Applied Mathematics, vol. 49(1-3), pp. 107-127, 1994.

41. Brucker P. Scheduling Algorithms. // Springer. 2007 371 p.

42. J. Carlier and E. Pinson. An algorithm for solving the job-shop problem. //Management Science, vol. 35(2), pp. 164-176, 1989.

43. Cheng A.M.K. Real-Time Systems. Scheduling, Analysis, and Verification. // John Wiley & Sons, Inc., Hoboken, New Jersey. 2002. 266 p.

44. Cottet F., Kaiser J., Mammeri Z. Scheduling in Real-Time Systems. // John Wiley & Sons Ltd. 2002. 266p.

45. Dertouzos M.L. and Mok A.K.L., Multiprocessor on-line scheduling of hard real-time tasks. // IEEE Transactions on Software Engineering, vol. 15(12), pp. 1497-1506, 1989.

46. Dhall S.K., Scheduling periodic-time critical jobs on single processor and multiprocessor computing systems, PhD thesis, University of Illinois, ApriL 1977.

47. Gendy Ayman K., Pont Michael J. Automatically Configuring Time-Triggered Schedulers for Use With Resource-Constrained, Single-Processor Embedded Systems // IEEE Transactions on industrial informatics, vol. 4, № 1, pp. 37-46, 2008.

48. Jayachandran P., Tarek F. Abdelzaher. Delay composition in preemptive and non-preemptive real-time pipelines. // Real-Time Systems vol. 40(3), pp. 290-320, 2008.

49. Johnson S.M. Optimal two-and-three-stage production schedules with set-up times included. // Naval Research Logistic Quaterly, vol; 1, pp. 61-68, 1954.

50. Kats V., Levner E. Cyclic scheduling of operations for a part type in an FMS handled by a single robot: a parametric critical-path approach.// The International Journal of FMS, vol. 10 (2), pp. 129-138, 1998.

51. Kleinrock, L., and R. R. Muntz: Processor Sharing Queueing Models of Mixed Scheduling Disciplines for Time Shared System. // Journal of the ACM (JACM), vol. 19 (3), 1972.

52. Kopetz K. Real-Time Systems. Design Principles for Distributed Embedded Applications. // Kluwer Academic, Dordrecht, 1997. 356p.

53. Levner E. Multiprocessor Scheduling. Theory and Applications. // I-Tech Education and Pablishing, Vienna, Austria, 2007. — 436 p.

54. Liu J.W.S. Real-Time Systems.// Prentice Hall, Englewood Cliffs, NJ, 2000. 600p.

55. Liu C.L. and Layland J.Wi Scheduling algorithms for multiprogramming in a hard real-time environment. // J. ACM, vol. 20, № 1, pp. 40-61, 1973.

56. Mark J., Tazartes D., Curey R. Partitioned executive structure for realtime embedded software applications // 8-th Saint-Peterburg international conference on integrated navigation systems, 28-30 may, 2001, Russia, St.Peterburg. pp. 176 184.

57. McNaughtan R., Scheduling with deadlines and loss functions. // Management Science, vol. 6, pp. 1-12, 1959.

58. Mok 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.

59. Muth, J. F., Thompson, G. L. Industrial Scheduling. // Englewood Cliffs, N. J.: Prentice-Hall, 1963

60. Marco Di Natale, J.A. Stankovic. Scheduling Distributed Real-Time Tasks with Minimum Jitter.// IEEE Transactions on computers, vol. 49, № 4, pp. 303-316, 2000.

61. Michael L. Pinedo. Scheduling. Theory, Algorithms, and Systems. // Springer. 2008 671 p.

62. Sahni S.K., Preemptive scheduling with due dates. // Operational Research, vol. 27(5), pp. 925-934, 1979.

63. Stankovic J.A. Distributed real-time computing: the next generation. // Technical Report TR92-01, University of Massachusetts, 1992.

64. Stankovic John A., M. Spuri, K. Ramemritham, G.C. Buttazzo. Deadline Scheduling for Real-Time Systems. // Kluwer Academic Publishers, London, 1998.-273 p.

65. Tindell K., Burns A., and Wellings A. Allocating Real-Time Tasks (an NP-Hard Problem Made Easy). // Real-Time Systems, vol. 4(2), pp. 145-165, 1992.

66. Wang Ji-Bo, Zun-Quan Xia. Scheduling jobs under decreasing linear deterioration. // Information Processing Letters, vol. 94(2), pp. 63-69, 2005.

67. Wang Ji-Bo. Flow shop scheduling problems with decreasing linear deterioration under dominant machines. // Computers and Operations Research, vol. 37(7), pp. 2043-2058, 2007.

68. Xiliang Zhong and Cheng-Zhong Xu. Energy-Aware Modeling and Scheduling for Dynamic Voltage Scaling with Statistical Real-Time Guarant // IEEE Transactions on Computers, vol. 56(3), pp. 358-372, 2005.