Помощь в учёбе, очень быстро...
Работаем вместе до победы

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

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

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

Содержание

  • 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. Разработка продукционной базы знаний для контроля прибора связи ЦВК «Сумматор-11 430»
    • 4. 4. Пример анализа трассы вычислительного процесса прибора связи ЦВК «Сумматор-11 430»
    • 4. 5. Выводы

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

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

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

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

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

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

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

Материалы диссертации докладывались на конференциях памяти Н. Н. Острякова (Санкт-Петербург, 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. W., Мок A. K., Fohler G. Pre-Scheduling// Real-Time Systems, 30, 2005, pp. 83−103.
Заполнить форму текущей работой

Пора сдавать?