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

Толмачева Марина Владимировна

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

ООЗиэои^—

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

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

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

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

003058020

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

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

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

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

доктор технических наук, профессор Фетисов Владимир Андреевич

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

кандидат технических наук, старшии

научный сотрудник

Павлов Владимир Анатольевич

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

Защита состоится ¿9мА ) 2007 г в /-^"час на заседании диссертационного совета Д 212 233 02 при ГОУ ВПО «Санкт-Петербургский государственный университет аэрокосмического приборостроения» по адресу 190000, Санкт-Петербург, ул Большая Морская, 67

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

Автореферат разослан 2-0 2007 г

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

Осипов Л А

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

Проблеме планирования вычислительного процесса при распределенных вычислениях всегда уделялось и продолжает уделяться достаточно большое внимание Широкое освещение этих результатов дается в работах Коффмана Э Г , Левина В И , Топоркова В В Целый ряд решений этих вопросов был предложен в рамках теории расписаний в работах Конвея Р В , Максвелла В Л , Миллера Л В , Танаева В С , Перовской Е И и многих других Известные алгоритмы поиска оптимальных расписаний для распределенных вычислительных систем характеризуются высокой алгоритмической сложностью, в связи с чем на практике обычно используют приближенные локально-оптимальные алгоритмы или алгоритмы, основанные на эвристиках Однако и эти алгоритмы достаточно сложны и не учитывают особенностей организации вычислительного процесса в навигационном комплексе (НК), которые, вообще говоря, характерны для многих систем реального времени В настоящей диссертации исследуются вопросы планирования вычислительного процесса, в рамках которых предлагается простой субоптимальный алгоритм, учитывающий особенности НК

Контроль корректности реализуемого вычислительного процесса является неотъемлемой составляющей системы контроля и диагностики НК

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

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

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

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

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

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

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

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

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

максимальное отклонение от заданных директивных сроков и не требуют перебора вариантов

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

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

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

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

Разработанные программные средства планирования и контроля нашли практическое применение при разработке в ЦНИИ «Электроприбор» вычислительных систем морских навигационных комплексов, среди которых Струна - 3 1, Струна - 3 2, Сумматор - 11430 Положения, выносимые на защиту

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

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

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

Принципы построения информационной системы планирования и контроля вычислительного процесса в навигационном комплексе

Апробация работы. Материалы диссертации докладывались на конференциях памяти Н Н Острякова (Санкт-Петербург, 2002, 2004 г.г), на 6-й международной конференции по морским интеллектуальным технологиям (Санкт-Петербург, 2005 г), на 6-й международной конференции «Интеллектуальные и многопроцессорные системы» (Геленджик, 2005 г), на 2-й Всероссийской научной конференции «Методы и средства обработки информации» (Москва, 2005г), на 1-й Всероссийской мультиконференции по управлению (Санкт-Петербург, 2006 г),

Публикации По теме диссертации опубликованы 17 печатных работ, из них 5 статей (1 статья - в журнале «Известия РАН Теория и системы управления», рекомендованном ВАК Минобразования и науки РФ), 3 доклада и 9 рефератов докладов на международных и Всероссийских конференциях

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и приложения и содержит 154 страницы, 55 рисунков, 14 таблиц

Краткое содержание работы

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

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

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

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

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

Пусть рассматриваемая система С = (¿,7) характеризуется иерархией Ь = {¿,,¿2» из т ЭВМ и множеством J = ,./„) из п решаемых

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

Определение ЭВМ доминирует над ЭВМ 1Г (ЬЧ>ЬГ), если

лип т . > тах г .

1 4 } 1

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

Класс 1. Множество ЭВМ представляет собой последовательность Ь, > ¿2 > > 1т

Класс 2 Множество ЭВМ представляет собой последовательность < ¿2 < < Ьт, возрастающую по отношению доминирования Класс 3. Множество ЭВМ представляет собой пару соединенных последовательностей Ь^<Ь2< < Ьь > > > Ьт, 1 <И<т, первая из которых возрастает, а вторая убывает по отношению доминирования

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

Алгоритм 1

1 Выделим задачу Js, которая удовлетворяет условию

т* т*

£ С =пип{£г;,}

1=2 ' ыг

1 Сформируем расписание л{=[кJ¡'\, где л - произвольное расписание для (п-1) задач, не содержащее задачи Js

Здесь и далее звездочкой (*) отмечены характеристики критического пути Отметим два существенных обстоятельства Во-первых, в данном алгоритме отсутствует перебор вариантов расписаний Во-вторых, для оптимальности расписания достаточно лишь правильного выбора последней исполняемой задачи, которая должна быть наиболее быстро решаемой на всех ЭВМ критического пути системы, кроме возможно первого Упорядоченность же остальных задач не влияет на время исполнения расписания

Рассмотрим правила формирования расписания для систем из второго класса

Алгоритм 2

1 Выделим задачу Jl, которая удовлетворяет условию

5Х, =тт {£>;,}

2 Сформируем расписание где я - произвольное расписание для (п-1) задач, не содержащее задачи J¡

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

возможно, последней Упорядоченность же остальных задач не влияет на время выполнения расписания

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

Алгоритм 3

1 Выделим задачу Js, которая удовлетворяет условию

Л*-1 Л"-1

Хг/\ =т;п {!>'/}

1=1 ' 1=1

2 Выделим задачу 3р, которая удовлетворяет условию

3 Сформируем расписание = где тс - произвольное расписание для (п-2) задач, не содержащее задач Js и Jр

4 Сформируем расписание я"4 = ??•/,.]> повторив пп 1-3, но, выполнив п п 1 и 2 в другой последовательности

5 Выберем среди расписаний лъ и я\, наилучшее расписание

Отметим, что в данном алгоритме перебор расписаний также

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

Рассмотрим теперь вторую постановку задачи Предположим, что для каждой задачи из исходного списка | у = 1 ,п] определен директивный

срок = ее завершения Рассмотрим некоторое расписание

л- = (У,,У2, выполнения этих задач Каждая задача при этом будет

характеризоваться временем завершения |у = 1,и}, для которого может быть определено смещение \б^] = \,п\ относительно заданного

директивного срока 81 = ^ - с1] Проблема состоит в поиске алгоритма составления расписаний, минимизирующего максимальное отклонение

<5тах=шаХ(5 В работе показано, что для систем из второго класса

)

упорядочение должно осуществляться в порядке возрастания исходных

директивных сроков | ) = 1, л), а для систем из первого и третьего

классов - в соответствии с некоторыми виртуальными директивными сроками, определяемыми следующими выражениями

т'

■ класс 1 <1]=<1]- _

1=2

■ классЗ <1™ =с1]-'^1т1]

|=А+|

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

1 Найти в системе С = (¿,У)вычислительный путь рк, который назовем критическим и который характеризуется наибольшим значением

суммы 1{рк) = У\т, верхних границ г, = тахг, времен решения задач

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

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

3 Определить с использованием соответствующих алгоритмов (алгоритмы 1, 2, 3) одну из крайних (первую или последнюю) задач будущего расписания (классы 1 и 2), либо обе крайние задачи (класс 3) Если множество У непусто, то перейти к п 2, иначе конец

Классификация в п 2 алгоритма осуществляется путем выделения у рассматриваемой системы определяющего признака - наличия убывающей последовательности (класс 1), либо наличия возрастающей последовательности (класс 2), либо наличия состыкованных возрастающей и убывающей последовательностей (класс 3) Для этого анализируется интервальная зависимость для ЭВМ критического пути времени выполнения

100 90 80 70 60 50 40 30 20 10 О

5 6 7 8

-Проигрыш < 10% -—Проигрыш <20%

Число злда I

9 10

Проигрыш < 30%

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

всех задач от номера ЭВМ Анализ включает аппроксимацию верхних

границ этой зависимости параболой При этом если вершина параболы

оказывается слева от интервала номеров ЭВМ, то система относится к

классу 1, если справа, то - к классу 2, если внутри интервала, то - к классу 3

Оценка эффективности предложенного алгоритма осуществлялась на

основе компьютерного моделирования и производилась по отношению к

классу иерархических систем, структура которых описывается бинарным сбалансированным графом (все вычислительные пути в таких системах имеют одинаковую длину) В основу использованного подхода было положено случайное генерирование примеров При этом фиксировалось число ЭВМ (ш=15 или т=31), образующих иерархию, а число задач п варьировалось в интервале от 5 до 10 Для каждого значения п из этого интервала генерировалось 100 примеров Причем времена решения задач на каждой из ЭВМ формировались как случайные величины, равномерно распределенные на заданном интервале Для каждого получаемого примера строилось расписание на основе предложенного алгоритма и путем полного перебора (оптимальное расписание) Эти расписания сравнивались между собой по относительной разности времен выполнения Результаты моделирования приведены на рис 2 и 3 Результаты показывают, что, например, при п=5 и т=15 (рис 2) предлагаемый алгоритм в 53% случаев строил расписания, которые уступали по длительности оптимальному расписанию не более 10%, а в 80% случаев были построены расписания, уступающие оптимальному не более 30 % При использовании алгоритма в отношении системы из 31 ЭВМ не менее чем в 75% случаев строится расписание, уступающее по длительности выполнения оптимальному расписанию не более 30% (рис 3)

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

100 90 80 70 60 50 40 30 20 10 О

5 6 7 8 9 10 -*—Проигрыш < 10% -—Проигрыш < 20% Л Проигрыш < ЗС/о

Рис 3 Эффектившстъ субоптималыюго алгоритма для иерарчических систем, состоящих из 31 ЭВМ

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

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

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

Среди примененных принципов доминирующими и определяющими новизну данной разработки являются два - применение экспертного подхода для анализа диагностической информации и использование технологии баз данных (БД) для реализации этого подхода Для упрощения процесса проектирования экспертная оболочка и сама экспертная система разрабатывались в среде С++ Builder, которая поддерживает механизм реляционных БД В результате правила в базе знаний были представлены как записи БД, а проверка срабатывания правил осуществлена как формирование SQL-запроса Предложенные программные средства нашли применение при разработке в ЦНИИ «Электроприбор» вычислительных систем морских навигационных комплексов, среди которых Струна -3 1, Струна - 3 2, Сумматор - 11430

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

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ

1 Толмачева М В , Матросов Ю М Принципы диспетчеризации вычислительного процесса навигационной системы // Гироскопия и навигация, 2002, № 4 Рефераты докладов XXIII Научно-технической конференции памяти Н Н Острякова, СПб С 74

2 Толмачева М В , Матросов Ю М, Цал 3 И Универсальная программа диспетчеризации вычислительного процесса навигационной системы// Гироскопия и навигация, 2004, № 4 Рефераты докладов XXIV Научно-технической конференции памяти Н Н Острякова, СПб С 99

3 Толмачева М В , Колесов Н В Составление расписаний решения задач в конвейерных вычислительных системах // Информационно-управляющие системы, 2005 г ,№ 5 С 16-21

4 Толмачева М В , Колесов Н В Оптимизация расписаний работ с неопределенными временами выполнения // Рефераты докладов 6-ой международной конференции по морским интеллектуальным технологиям, СПб, 2005 С 73-74

5 Толмачева М В, Колесов Н В Оптимизация расписаний работ с неопределенными временами выполнения // Материалы докладов 6-ой международной конференции по морским интеллектуальным технологиям, СПб, 2005 С 160-164

6 Толмачева М В , Колесов Н В Построение расписаний решения задач в многопроцессорных системах при заданных директивных сроках // Материалы 6-ой международной конференции «Интеллектуальные и многопроцессорные системы», Геленджик, 2005 С 122-124

7 Толмачева М В , Колесов Н В Приближенный рекурсивный алгоритм построения расписаний для конвейерных вычислительных систем // Труды 2-ой Всероссийской научной конференции «Методы и средства обработки информации», Москва, 2005 С 559-563

8 Толмачева М В, Соколов А А Экспертная система постанализа вычислительных процессов приборов навигационного комплекса // Гироскопия и навигация, 2006, № 2 С 109

9 Толмачева М В , Колесов Н В Субоптимальный алгоритм построения расписаний для иерархических вычислительных систем // Информационно-управляющие системы, 2006 г ,№ 2 С 14-20

10 Толмачева М В , Колесов Н В Построение расписаний решения задач в микропроцессорных системах при заданных директивных сроках // Вестник компьютерных и информационных технологий, № 7, 2006 г С 48-54

11 Толмачева М В , Колесов Н В Планирование вычислительного процесса в морских навигационных комплексах // Гироскопия и навигация, 2006, № 4 Рефераты докладов 1-й Всероссийской мультиконференции по управлению, СПб С 109

12 Толмачева МВ Информационная система планирования, мониторинга и анализа вычислительного процесса в навигационном комплексе // Гироскопия и навигация, 2006, № 4 Рефераты докладов 1-й Всероссийской мультиконференции по управлению), СПб С 109

13 Толмачева М В , Безмен Г В Специализированная экспертная оболочка для диагностирования навигационных систем // Гироскопия и навигация, 2007, №2 С 97

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

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

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

17 Толмачева М В , Колесов Н В Планирование и контроль вычислений в навигационном комплексе // Гироскопия и навигация, 2007, № 2 С 37-48

Подписано в печать 18 04 07 Заказ №82 Тираж 100 экз Объем 1 п л Государственный научный центр РФ - ЦНИИ «Электроприбор» 197046 С -Петербург, ул Малая Посадская, 30

Введение

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

Введение.

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

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

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

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

Введение.

2.1.Базовые классы иерархических систем.

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

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

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

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

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

2.5.Вывод ы.

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

Введение.

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

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

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

ЗАПрограммные средства для поддержки планирования вычислительного процесса и для исследования алгоритмов планирования.

3.5.Выводы.

4. Контроль вычислительного процесса в морском навигационном комплексе.

Введение.

4.1 .Принципы построения информационной системы контроля и отладки вычислительного процесса.

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

4.3.Разработка продукционной базы знаний для контроля прибора связи ЦВК «Сумматор-11430».

4.4.Пример анализа трассы вычислительного процесса прибора связи ЦВК «Сумматор-11430».

4.5.Вывод ы.

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

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

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

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

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

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

Материалы диссертации докладывались на конференциях памяти Н.Н. Острякова (Санкт-Петербург, 2002, 2004 г.г.), на 6-ой международной конференции по морским интеллектуальным технологиям (Санкт-Петербург, 2005 г.), на 6-ой международной конференции «Интеллектуальные и многопроцессорные системы» (Геленджик, 2005 г.), на 2-ой Всероссийской научной конференции «Методы и средства обработки информации» (Москва, 2005г.), на 1-ой Всероссийской мультиконференции по управлению (Санкт-Петербург, 2006 г.).

На защиту выносятся следующие положения:

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

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

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

Принципы построения информационной системы планирования и контроля вычислительного процесса в навигационном комплексе.

4.4. Выводы

Настоящая глава посвящена вопросам мониторинга и контроля вычислений в морском НК. При этом получены следующие результаты.

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

2. Разработана инфологическая модель для информационной системы контроля и отладки вычислительного процесса в морском НК, включающая входные информационные объекты («Временная диаграмма», «Приборы» и «Правила»), выходные («Результаты») и справочные («События» и «Проекты»).

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

Заключение

В настоящей работе рассмотрены теоретические и практические аспекты планирования и контроля вычислений в навигационных комплексах.

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

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

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

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

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

2. Архангельский А.Я. Программирование в С++ Builder 6. М.: БИНОМ, 2005.- 1162 с.

3. Барский А.Б. Параллельные процессы в вычислительных системах. -М.: Радио и связь, 1990. 256 с.

4. Бетелин В.Б., Галатенко В.А."ЭСКОРТ инструментальная среда программирования.", Юбилейный сборник трудов институтов Отделения информатики РАН. Том 2. Москва, 1993. С. 47 - 52.

5. Ведешенков В.А. Подход к самодиагностированию неоднородных цифровых систем // АиТ. 2006. № 1. С. 162 177.

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

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

8. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. СПб.: Питер, 2000. - 382 с.

9. Галатенко В.А. Программирование в стандарте POSIX (часть 1). М.: Интернет-Университет Информационных Технологий, 2004. - 554 с.

10. Ю.Галатенко В.А. Программирование в стандарте POSIX (часть 2). М.: Интернет-Университет Информационных Технологий, 2005. - 380 с.

11. Галатенко В.А., Костюхин К.А. Отладка и мониторинг распределенных разнородных систем. //Программирование, 2002, №1. С. 37 40.

12. Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. -СПб.: Питер, 2003. 734 с.

13. З.Гордеев А.В., Штепен В.А. Управление процессами в операционныхсистемах реального времени. Л.: ЛИАП, 1988. - 76 с.

14. Н.Дмитриев С.П., Колесов Н.В., Осипов А.В. Информационная надежность, контроль и диагностика навигационных систем. СПб.: ЦНИИ «Электроприбор», 2003. - 206 с.

15. Дмитриев С.П., Колесов Н.В., Осипов А.В. Система интеллектуальной поддержки судоводителя при расхождении судов // Теория и системы управления, № 2, 2003. С. 75 80.

16. П.Калмыков С.А., Шокин Ю.А., Юлдашев З.Х. Методы интервального анализа. Н.: Наука, 1986. - 294 с.

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

18. Каляев А.В., Левин И.И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. М.: Янус-К, 2003.-325 с.

19. Каравай М.Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах // АиТ. 2004. № 12. С.125 142.

20. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979. -262 с.

21. Колесов Н.В. Многоуровневое проектирование средств тестового и функционального диагностирования специализированных вычислительных комплексов. Л.: ЦНИИ «Румб», 1992. - 70 с.

22. Колесов Н.В., Осипов А.В. Экспертная система управлениянавигационным комплексом корабля // Материалы 3-й научной школы «Автоматизация создания математического обеспечения», Саратов, 1992. С.43-46.

23. Конвей Р.В., Максвелл B.JL, Миллер JI.B. Теория расписаний. М.: Наука, 1975.320 с.

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

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

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

27. Лукомский Ю.А., Пешехонов В.Г., Скороходов Д.А. Навигация и управление движением судов. СПб.: Элмор, 2002. - 360 с.

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

29. ЗО.Основы технической диагностики. Под ред. Пархоменко П.П. М.: Энергия, 1976. - 464 с.

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

31. Пархоменко П.П. Определение технического состояния многопроцессорных вычислительных систем путем анализа графа синдромов // АиТ. 1999.№ 5. С. 175- 182.

32. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики. -М.: Энергия, 1981.-320 с.

33. Попов Э.В. (ред) Динамические интеллектуальные системы вуправлении и моделировании. М.: МИФИ, 1996. - 380 с.

34. Поспелов Д. А. Моделирование рассуждений. Опыт анализа мыслительных актов. М.: Радио и связь, 1989. 276 с.

35. Сластен J1.M. Алгоритм многокадровой трассировки многопроцессорной вычислительной системы // Труды Второй Всероссийской научной конференции «Методы и средства обработки информации», М., 2005. С. 490 495.

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

37. Смелянский P.JL, Костенко В.А. Задача построения расписания при совместном проектировании аппаратных и программных средств// Программирование. 2002, № 3. С. 77 82.

38. Сорокин С. Системы реального времени. // Современные технологии автоматизации, 1997, № 2. С. 22 29.

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

40. Стрельников Ю.Н., Борисов Н.А. Разработка экспертных систем средствами инструментальной оболочки в среде MS Windows. Тверь: ТГТУ, 1997.- 52 с.

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

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

43. Тихонов А.В., Попиков П.Н. Алгоритм нечетко поиска по трассам работы распределенных вычислительных систем // Труды Второй Всероссийской научной конференции «Методы и средства обработки информации», М., 2005. С. 496 500.

44. Толмачева М.В., Матросов Ю.М. Принципы диспетчеризации вычислительного процесса навигационной системы// Гироскопия и навигация, 2002, № 4. Рефераты докладов XXIII Научно-технической конференции памяти Н.Н. Острякова, СПб. С. 74.

45. Толмачева М.В., Матросов Ю.М., Цал З.И. Универсальная программа диспетчеризации вычислительного процесса навигационной системы// Гироскопия и навигация, 2004, № 4. Рефераты докладов XXIV Научно-технической конференции памяти Н.Н. Острякова, СПб. С.99.

46. Толмачева М.В., Колесов Н.В. Составление расписаний решения задач в конвейерных вычислительных системах// Информационно-управляющие системы, 2005 г., № 5. С. 16-21.

47. Толмачева М.В., Колесов Н.В. Оптимизация расписаний работ с неопределенными временами выполнения// Рефераты докладов 6-ой международной конференции по морским интеллектуальным технологиям, СПб, 2005. С. 73 74.

48. Толмачева М.В., Колесов Н.В. Оптимизация расписаний работ с неопределенными временами выполнения// Материалы докладов 6-ой международной конференции по морским интеллектуальным технологиям, СПб, 2005. С. 160-164.

49. Толмачева М.В., Колесов Н.В. Построение расписаний решения задач в многопроцессорных системах при заданных директивных сроках// Материалы 6-ой международной конференции «Интеллектуальные и многопроцессорные системы», Геленджик, 2005. С. 122-124.

50. Толмачева М.В., Колесов Н.В. Приближенный рекурсивный алгоритм построения расписаний для конвейерных вычислительных систем // Труды 2-ой Всероссийской научной конференции «Методы и средства обработки информации», Москва, 2005. С. 559 563.

51. Толмачева М.В., Соколов А.А. Экспертная система постанализавычислительных процессов приборов навигационного комплекса// Гироскопия и навигация, 2006, № 2. С. 109.

52. Толмачева М.В., Колесов Н.В. Субоптимальный алгоритм построения расписаний для иерархических вычислительных систем// Информационно-управляющие системы, 2006 г., № 2. С. 14 20.

53. Толмачева М.В., Колесов Н.В. Построение расписаний решения задач в микропроцессорных системах при заданных директивных сроках// Вестник компьютерных и информационных технологий, № 7, 2006 г. С. 48 54.

54. Толмачева М.В., Колесов Н.В. Планирование вычислительного процесса в морских навигационных комплексах// Гироскопия и навигация,2006, № 4. Рефераты докладов 1-й Всероссийской мультиконференции по управлению, СПб. С. 109.

55. Толмачева М.В. Информационная система планирования, мониторинга и анализа вычислительного процесса в навигационном комплексе// Гироскопия и навигация, 2006, № 4. Рефераты докладов 1-й Всероссийской мультиконференции по управлению), СПб. С. 109.

56. Толмачева М.В., Безмен Г.В. Специализированная экспертная оболочка для диагностирования навигационных систем // Гироскопия и навигация,2007, №2. С. 97.

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

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

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

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

61. Топорков В.В. Совместное планирование и назначение процессов как метод оптимизации архитектурных решений вычислительных систем // АиТ. -2001,№ 12. С.112- 117.

62. Топорков В.В. Разрешение коллизий параллельных процессов в масштабируемых вычислительных системах // АиТ. 2003, № 5. С. 99 - 102.

63. Управление вычислительными процессами / Бриттов Г.С., Игнатьев М.Б., Мироновский Л.А., Смирнов Ю.М. Изд. ЛГУ, 1973. 220 с.

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

65. Хорошевский В.Г. Кластеры. Эвристические алгоритмы распределения задач//Автометрия, 2004, № 1, 4.

66. Частиков А.П., Гаврилова Т.А., Белов Д.Л. Разработка экспертных систем. Среда CLIPS. СПб.: БХВ-Петербург, 2003. - 606 с.

67. Anderson J.H., Holman P. Group-Based Pfair Scheduling // Real-Time Systems, 2006, № 32, pp. 125 168.

68. Baker T.P. An Analysis of Fixed-Priority Schedulability on a Multiprocessor // Real-Time Systems, 2006, № 32, pp. 49 71.

69. Balbastre P., Ripoll I., Crespo A. Analysis of window-constrained execution time systems // Real-Time Systems, 2007, № 35, pp. 109 134.

70. Baruah S. The Non-preemptive Scheduling of Periodic Tasks upon Multiprocessors // Real-Time Systems, 2006, № 32, pp. 9 -20.

71. Bini E., Buttazzo G. Measuring the Performance of Schedulability Tests// RealTime Systems, 30, 2005, pp. 129 154.

72. Dmitriev S. P., Kolesov N.V., Osipov A.V. Intelligent mariner's work station // International Workshop, Irkutsk, 2003. pp. 129 154.

73. Dmitriev S. P., Kolesov N.V., Osipov A.V., Romanicheva G. N. System of Intelligent Support for the Ships Collision Avoidance //Navigation Technology for the 21-st Century, 55-th Annual Meeting, Cambridge, USA, 1999. pp. 229 250.

74. Dmitriev S. P., Kolesov N.V., Osipov A.V. Safety Measures for a Ships Passing Track in the Multiagent Framework // 5th IFAC Conference on Maneuvering and Control of Marine Craft, Aalborg, Denmark, 2000. pp. 159 -164.

75. Graham A.S. String searching algorithm. UK: World Scientific Publishing Company, 1994. pp. 123 134.

76. Kleinrock L., Nilson А/ On optimal scheduling algoritms for time-shared systems // Journal of the АСМ/ -1981. V. 28, № 3. pp. 99 - 104.

77. Krone M., Stieglitz K. Heuristic programming solution of a flowshop scheduling problem // Operations Research. 1974. V. 22. № 3. pp. 239 244.

78. Lundberg L., Lennerstad H. Guaranteeing response times for aperiodic tasks in global multiprocessor scheduling // Real-Time Systems, 2007, № 35, pp.136 -151.

79. Marchand A., Sily-Chetto M. Dynamic Real-time Scheduling of Firm Periodic Tasks with Hard and Soft Aperiodic Tasks // Real-Time Systems, 2006,32, pp. 21 47.

80. 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.

81. Mastrolilli M.L., Gambardella M. Effective neighborhood functions for the flexible job shop problem// J. Scheduling. 2000. V/ 3. Issue 1. pp. 109 124.

82. Sethuraman J., Teo C.-P. Effective Routing and Scheduling in Adversarial Queueing Networks.// Algorithmica, 43, 2005. pp. 29 54.

83. Wang W., Мок A. K., Fohler G. Pre-Scheduling// Real-Time Systems, 30, 2005, pp. 83-103.