WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 |

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

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

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

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

Автореферат

диссертации на соискание ученой степени

кандидата технических наук

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

2007 г.

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

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

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

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

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

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

Защита состоится 2007 г. в час. на заседании диссертационного совета Д 212.233.02 при ГОУ ВПО «Санкт-Петербургский государственный университет аэрокосмического приборостроения» по адресу: 190000, Санкт-Петербург, ул. Большая Морская, 67.

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

Автореферат разослан __________________ 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, и рассматривается построение оптимальных алгоритмов планирования вычислительного процесса для трех классов иерархических систем, называемых далее базовыми. Учитывая, что все решаемые в НК задачи являются периодическими, предполагается, что рассмотрение каждый раз ведется в рамках одного периода, а отношение предшествования, существующее между задачами, выполняемыми на разных ЭВМ (системах и приборах) учитывается в иерархической структуре задач.

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

Определение. ЭВМ доминирует над ЭВМ (), если.

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

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

Класс 2. Множество ЭВМ представляет собой последовательность, возрастающую по отношению доминирования.

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

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

Алгоритм 1.

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

.

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

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

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

Алгоритм 2.

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

.

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

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

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

Алгоритм 3.

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

.

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

.

  1. Сформируем расписание, где - произвольное расписание для (n-2) задач, не содержащее задач и.
  2. Сформируем расписание, повторив п.п. 1-3, но, выполнив п.п. 1 и 2 в другой последовательности.
  3. Выберем среди расписаний и наилучшее расписание.

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

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

Pages:     || 2 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»