Планирование и контроль вычислительного процесса в морских навигационных комплексах тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Толмачева, Марина Владимировна

• Толмачева, Марина Владимировна
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Толмачева, Марина Владимировна

Введение

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. Разработана продукционная база знаний для информационной системы контроля и отладки вычислительного процесса в приборе связи морского НК и проиллюстрировано ее практическое использование.

Заключение

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Толмачева, Марина Владимировна, 2007 год

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.