Введение к работе
Актуальность. Для систем реального времени, к которым, безусловно, относятся и навигационные комплексы, вопросы планирования вычислительного процесса и контроля его корректности при реализации вычислений имеют первостепенное значение Особенно остро эти вопросы встают в случае распределенных вычислений В настоящей работе вычислительный процесс рассматривается как последовательность некоторых характерных событий, примерами которых могут служить запуск или окончание системной или функциональной задачи, запуск или окончание потока, обработка прерывания и т п Под планированием вычислительного процесса будем понимать определение момента запуска для каждого из рассматриваемых событий
Проблеме планирования вычислительного процесса при распределенных вычислениях всегда уделялось и продолжает уделяться достаточно большое внимание Широкое освещение этих результатов дается в работах Коффмана Э Г , Левина В И , Топоркова В В Целый ряд решений этих вопросов был предложен в рамках теории расписаний в работах Конвея Р В , Максвелла В Л , Миллера Л В , Танаева В С , Перовской Е И и многих других Известные алгоритмы поиска оптимальных расписаний для распределенных вычислительных систем характеризуются высокой алгоритмической сложностью, в связи с чем на практике обычно используют приближенные локально-оптимальные алгоритмы или алгоритмы, основанные на эвристиках Однако и эти алгоритмы достаточно сложны и не учитывают особенностей организации вычислительного процесса в навигационном комплексе (НК), которые, вообще говоря, характерны для многих систем реального времени В настоящей диссертации исследуются вопросы планирования вычислительного процесса, в рамках которых предлагается простой субоптимальный алгоритм, учитывающий особенности НК
Контроль корректности реализуемого вычислительного процесса является неотъемлемой составляющей системы контроля и диагностики НК
Важное место среди этих средств занимает так называемая трассировка, когда информация о событиях вычислительного процесса записывается в реальном времени в специально отведенную область памяти для последующего анализа (постанализа) Визуальный анализ этой информации, представленной в виде временных диаграмм, возможен, но в большинстве случаев весьма затруднителен и не эффективен В связи с этим представляется актуальной разработка на основе экспертного подхода программных средств для автоматического постанализа такой информации
Цель работы и задачи исследования. Цель работы состоит в дальнейшем повышении эффективности процессов проектирования и эксплуатации морских навигационных комплексов, направленном на решение следующих задач
разработка алгоритмов планирования вычислительного процесса, учитывающих особенности морских навигационных комплексов,
разработка алгоритмов контроля вычислительного процесса в режиме постанализа,
разработка программных средств планирования и контроля вычислительного процесса в морских навигационных комплексах
Методы исследования Для решения поставленных задач использовались методы дискретной математики, теории расписаний, интервального анализа Научная новизна
Разработаны оптимальные алгоритмы планирования вычислительного процесса для трех базовых классов иерархических систем Алгоритмы минимизируют общее время выполнения заданного списка задач и не требуют перебора вариантов
Разработаны оптимальные алгоритмы планирования вычислительного процесса при заданных директивных сроках для трех базовых классов иерархических систем Алгоритмы минимизируют
максимальное отклонение от заданных директивных сроков и не требуют перебора вариантов
Предложен субоптимальный алгоритм планирования вычислительного процесса для иерархических систем общего вида, не требующий перебора вариантов Алгоритм учитывает особенности морских навигационных комплексов и несущественно проигрывает оптимальному алгоритму, минимизирующему время выполнения заданного списка задач
Предложены принципы построения информационной системы планирования и контроля вычислительного процесса в морских навигационных комплексах Практическая ценность
Разработанный субоптимальный алгоритм позволяет существенно сократить временные затраты на планирование вычислительного процесса в навигационных комплексах
Разработанная информационная система планирования и контроля вычислительного процесса позволяет осуществлять эффективную поддержку процессов проектирования и контроля навигационных комплексов
Разработанные программные средства планирования и контроля нашли практическое применение при разработке в ЦНИИ «Электроприбор» вычислительных систем морских навигационных комплексов, среди которых Струна- 3 1, Струна- 3 2, Сумматор - 11430 Положения, выносимые на защиту
Оптимальные по критерию минимума времени выполнения заданного списка задач алгоритмы планирования вычислительного процесса для трех базовых классов иерархических детерминированных и недетерминированных систем
Оптимальные алгоритмы планирования вычислительного процесса при заданных директивных сроках для трех базовых классов иерархических систем
Субоптимальный алгоритм планирования вычислительного процесса для иерархических систем общего вида
Принципы построения информационной системы планирования и контроля вычислительного процесса в навигационном комплексе
Апробация работы. Материалы диссертации докладывались на конференциях памяти Н Н Острякова (Санкт-Петербург, 2002, 2004 г.г), на 6-й международной конференции по морским интеллектуальным технологиям (Санкт-Петербург, 2005 г), на 6-й международной конференции «Интеллектуальные и многопроцессорные системы» (Геленджик, 2005 г), на 2-й Всероссийской научной конференции «Методы и средства обработки информации» (Москва, 2005г), на 1-й Всероссийской мультиконференции по управлению (Санкт-Петербург, 2006 г),
Публикации По теме диссертации опубликованы 17 печатных работ, из них 5 статей (1 статья - в журнале «Известия РАН Теория и системы управления», рекомендованном ВАК Минобразования и науки РФ), 3 доклада и 9 рефератов докладов на международных и Всероссийских конференциях
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и приложения и содержит 154 страницы, 55 рисунков, 14 таблиц
