Совместное планирование вычислений и обменов в информационно-управляющих системах реального времени тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Шестов, Пётр Евгеньевич

• Шестов, Пётр Евгеньевич
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Шестов, Пётр Евгеньевич

Введение

Глава 1. Задача построения совместимых расписаний вычислений и обменов.

1.1. Содержательная постановка задачи.

1.2. Математическая модель исходных данных.

1.3. Математическая модель расписания и условий его корректности

1.4. Математическая постановка задачи.

1.5. Классификация задачи.

1.6. Практически значимые частные задачи.

1.7. Выводы.

Глава 2. Обзор возможных подходов к построению алгоритмов решения задачи и алгоритмов решения «близких» задач

2.1. Близкие задачи и алгоритмы их решения.

2.2. Возможные подходы к решению поставленной задачи.

2.3. Методы разработки алгоритмов построения статических многоприборных расписаний.

2.4. Выводы.'.

Глава 3. Алгоритмы решения задачи построения совместимых расписаний.

3.1. Жадный алгоритм.

3.2. Алгоритм, основанный на методе ветвей и границ.

3.3. Жадный алгоритм со сдвигом расписания.

Глава 4. Экспериментальное исследование разработанных алгоритмов.

4.1. Цели исследования

4.2. Формирование исходных данных для экспериментов.

4.3. Методика статистической обработки результатов экспериментов

4.4. Схема проведения экспериментов.

4.5. Исследование жадного алгоритма.

4.6. Исследование алгоритма, основанного на методе ветвей и границ

4.7. Исследование жадного алгоритма со сдвигом расписания

4.8. Выводы.

Глава 5. Описание инструментального программного средства построения совместимых расписаний.

5.1. Требования к инструментальному средству

5.2. Архитектура инструментального средства построения совместимых расписаний.

Введение диссертации (часть автореферата) на тему «Совместное планирование вычислений и обменов в информационно-управляющих системах реального времени»

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

Разработка подобных ИУС РВ является сложным техническим процессом. Часто возникает задача модернизации таких систем, либо повторного использования отдельных подсистем ранее разработанных ИУС РВ. Причем изменение функционирования повторно используемых подсистем невозможно. Отсюда следует, что они обладают фиксированным интерфейсом, с помощью которого остальные устройства (в том числе другие подсистемы) в составе ИУС РВ взаимодействуют с такими подсистемами. Фиксирован формат сообщений и состав слов данных, которые получают и передают подсистемы.

К функционированию ИУС РВ предъявляется ряд требований, связанных не только с работой в реальном времени, но и обусловленных используемыми техническими стандартами, протоколами обмена данных, особенностями работы аппаратных и системных программных средств.

Настоящая диссертация посвящена алгоритмам построения совместимых расписаний выполнения прикладных задач (работ) и передачи сообщений в ИУС РВ. Расписания выполнения работ и передачи сообщений в таких системах строятся статически. В качестве среды передачи данных в работе рассматривается канал с централизованным управлением. Практическая значимость рассмотрения ИУС РВ с таким каналом подтверждается существованием ряда промышленных стандартов на каналы с централизованным управлением (MIL STD-1553B / МКИО ГОСТ Р 52070-2003 [8], STANAG 3910 [46], Fibre Channel FC-AE-1553 [53]), а также широким применением этих стандартов при создании ИУС РВ.

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

• необходимость планирования заданий двух типов: работ и сообщений;

• наличие двух типов работ: работ, подлежащих планированию, и работ в составе подсистем, которые не подлежат планированию;

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

• присутствуют технологические ограничения на корректность расписания;

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

Целью данной работы является разработка и исследование свойств алгоритмов построения расписания выполнения задач на вычислительных модулях в составе ИУС РВ и расписания передачи сообщений между ними по каналу с централизованным управлением с соблюдением ограничений на их совместимость.

Для достижения поставленной цели необходимо решить следующие задачи:

• Разработать математическую модель ИУС РВ и в рамках предложенной модели формализовать постановку задачи построения совместимых расписаний выполнения прикладных задач и передачи сообщений, которая позволяет учитывать технологические ограничения на корректность расписаний.

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

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

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

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

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

В четвертой главе описана методика экспериментального исследования разработанных алгоритмов построения совместимых расписаний, приведены численные результаты исследования и их анализ. Предметом исследования являлись точность и вычислительная сложность алгоритмов на различных классах исходных данных. Исходные данные для экспериментов сформированы на основе доступных автору наборах исходных данных с реальных ВСРВ. При обработке результатов экспериментов применены методы математической статистики.

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

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Шестов, Пётр Евгеньевич

4.8. Выводы

Результаты экспериментального исследования показали, что почти во всех случаях жадный алгоритм без сдвига расписаний показывает лучшие результаты, чем жадный алгоритм со сдвигом расписания. Исключение составляют наборы исходных данных вида R, для которых граф исходных данных является графом произвольного вида с малым числом компонент связности. Полученные данные позволяют сделать вывод о практической применимости жадного алгоритма без сдвига расписания при использовании эвристики «минимальный директивный срок завершения» на наборах вида Q, Qmodule, С и R. А жадного алгоритма со сдвигом расписания на наборах вида R при использовании эвристики «максимальное общее число непосредственных и транзитивных потомков».

Для гарантированное получения точного решения стоит пользоваться алгоритмом на основе метода ветвей и границ. Главный минус этого алгоритма — высокая вычислительная сложность. При решении практических задач большого размера следует использовать вместе все разработанные алгоритмы. Для быстрой оценки возможности построения полного расписания использовать жадный алгоритм. Если же результаты его работы не устраивают по точности, а также имеется возможность «дождаться» результатов алгоритма на основе метода ветвей и границ, то использовать последний. При этом разница во времени работы между жадным алгоритмом без сдвига расписания и алгоритмом на основе метода ветвей и границ может достигать нескольких сотен раз.

Описание инструментального программного средства построения совместимых расписаний

5.1. Требования к инструментальному средству

К инструментальному программному средству построения совместимых расписаний предъявляются следующие требования:

• по заданному набору исходных данных при помощи выбранного алгоритма построения совместимых расписаний строить совместимые расписания работ и сообщений;

• задавать параметры алгоритмов построения расписаний;

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

• обеспечивать возможность сохранения на диск и загрузки с диска наборов исходных данных и построенных расписаний;

• обеспечивать возможность визуализации построенных и загруженных с диска расписаний;

• предоставлять возможность отдельного (без графического интерфейса) использования библиотеки алгоритмов в составе других средств;

• предоставлять возможность расширения на другие среды передачи данных;

• обладать кросс-платформенностью, т.е. обладать возможностью работать на вычислительных системах под управлением различных операционных систем.

5.2. Архитектура инструментального средства построения совместимых расписаний

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

В состав библиотеки построения совместимых расписаний входят классы, представляющие отдельные работы и сообщения, вычислительные модули, канал с централизованным управлением, класс, хранящий в себе зависимости между работами и сообщениями, классы разработанных алгоритмов построения совместимых расписаний. Все классы алгоритмов наследуют от единого базового класса, который позволяет добавлять в библиотеку новые алгоритмы построения совместимых расписаний. Так же реализован общий класс среды передачи данных, использование которого позволяет расширить функционал библиотеки на новые среды передачи данных помимо канала с централизованным управлением. В общей сложности в состав библиотеки входит 19 классов, общий объем кода — 5663 строки, 165Кб. Для большинства современных операционных систем и платформ существуют компиляторы языка С++, так же как и реализации библиотеки STL. Этим обеспечивается кросс-платформенность библиотеки построения совместимых расписаний.

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

Открыть Ciap иань Опфмть распмсаммс Построить расписание Соараимть расписание ВмИщ

Работы в*, работы о*, аюбшв*« Hot работы Исх сссбцм Имць . ♦ 5 0 левыйв/с: 18в1

Прм ид/с 19794

Джтсяыисты 6» Е - в В В В в в Ш и

Сообымы вчтвботы иск. работы зав

ПрвыйдЛ: 6362

О - ♦

Е 3 "ti □

Тип: Настояции МКИО

М: 500 ш ® ®

IF3

Рис. 5.1. Главное окно графического средства построения совместимых расписаний

Основные функции интерфейса следующие:

• визуализация графа исходных данных;

• добавление и удаление из графа вершин и дуг;

• редактирование характеристик конкретных работ и сообщений;

• сохранение на диск и загрузка с диска наборов исходных данных;

• построение расписания реализованными алгоритмами;

• визуализация построенных расписаний;

• сохранение на диск и загрузка с диска расписаний.

Перечисленные функции соответствуют предъявленным ранее требованиям к инструментальному средству. Реализация графического интерфейса содержит 7 классов, общий объем кода — 1878 строк, 57Кб. Он был реализован на языке С++ при помощи кросс-платформенной библиотеки С^ [70], что обеспечивает его кросс-платформенность.

Помимо этого с использованием библиотеки построения совместимых расписаний был реализован набор процедур для создания тестовых наборов исходных данных. Общий объем этого кода — 594 строки, 16Кб. Суммарный объем кода, написанный автором, составил 8135 строк, 238Кб.

8. ГОСТ Р 52070-2003. Интерфейс магистральный последовательный системы электронный модулей. - Введ. 01.01.2004. М.: Изд-во стандартов, 2001. 23 с.

9. Гэри М., Джонсон Д. Вычислительный машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

10. Калинина В. Н., Панкин В. Ф. Математическая статистика. М.: Высшая школа, 1998. 336 с.

11. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. 2-е изд. М.: Издательский дом Вильяме, 2005. 1290 с.

12. Костенко В. А. Алгоритмы оптимизации, опирающиеся на метод проб и ошибок, в совместном проектировании аппаратных и программных средств ВС // Труды Всероссийской научной конференции «Высокопроизводительные вычисления и их приложения». 2000. С. 123-127.

13. Костенко В. А. Алгоритмы построения расписаний для одноприборных систем, входящих в состав систем реального времени // Методы и средства обработки информации. Труды третьей Всероссийской научной конференции. 2009. Р. 245-258.

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

15. Куминов В., Наумов Б. Космические компьютеры: открытые стандарты и технологии выходят в открытый космос // Мир компьютерной автоматизации. 2002. № 3.

26. Baker K. R. et al. Preemptive Scheduling of a Single Machine to Minimize Maximum Cost Subject to Release Dates and Precedence Constraints // Operations Research. 1983. Vol. 31, no. 2. P. 381-386.

27. Baker T. Multiprocessor EDF and deadline monotonic schedulability analysis //In Proc. of the 24th IEEE Real-Time Systems Symposium. 2003. P. 120-129.

28. Balashov V. V., Balakhanov V. A., Kostenko V. A. et al. A technology for scheduling of data exchange over bus with centralized control in onboard avionics systems // Journal of Aerospace Engineering. 2010. Vol. 224, no. 9. P. 993-1004.

29. Baruah S. The non-preemptive scheduling of periodic tasks upon multiprocessors // Real-Time Systems. 2006. Vol. 32, no. 1-2. P. 9-20.

30. Baruah S., Cohen N., Plaxton C., Varvel D. Proportionate progress: a notion of fairness in resource allocation //In Proc. of the ACM Symposium on the Theory of Computing. 1993. P. 345-354.

31. Blazewicz J., Ecker K., Pesch E. et al. Handbook on Scheduling. Berlin, Germany: Springer, 2007. 647 pp.

32. Blazewicz J., Lenstra J. K., Kan A. H. G. R. Scheduling subject to resource constraints: classification and complexity // Discrete Appl. Math. 1983. P. 11-24.

33. Brucker P. Scheduling algorithms. 5th edition. Springer, 2007. 372 pp.

34. Burns A., Nicholson M., Tindell K., Zhang M. Allocating and Scheduling Hard Real-Time Tasks on a Point-to-Point Distributed System //In Proceedings

52. Information Technology - Fibre Channel - Avionics Environment -Anonymous Subscriber Messaging (FC-AE-ASM) : Technical Report IN-CITS/TR-41:2006 // International Committee for Information Technology Standards (INCITS). 2006. 32 pp.

53. Information technology - Fibre Channel - Part 312: Avionics environment upper layer protocol MIL-STD-1553B Notice 2 (FC-AE-1553) : Technical Report TR 14165- 312:2009 // International Organization for Standardization (ISO). 2009. 84 pp.

54. ISO 11898-4:2004. Road vehicles - Controller area network (CAN) - Part 4: Timetriggered communication // International Organization for Standardization (ISO). 2004. 32 pp.

55. ISO/IEC 15776:2001. VME64bus - Specification // International Organization for Standardization (ISO). 2001. 262 pp.

56. Jaffar J., Mäher M. J. Constraint logic programming: A survey // The Journal of Logic Programming. 1994. Vol. 19/20. P. 503-582.

57. Jonsson J., Shin K. G. A parametrized branch-and-bound strategy for scheduling precedence-constrained tasks on a multiprocessor system //In Proc. of International Conference on Parallel Processing. 1997. P. 158-165.

58. Kasahara H., Narita S. Practical multiprocessor scheduling algorithms for efficient parallel processing // IEEE Transactions on Computers. 1984. Vol. C-33, no. 11. P. 1023-1029.

59. Kelley J. E. Critical-path planning and scheduling: mathematical basis // Operations Research. 1961. Vol. 9. P. 296-320.

60. Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by Simulated Annealing // Science. 1983. no. 220. P. 671-680.

61. Kwok Y.-K., Ahmad I. Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors // IEEE Transactions on Parallel and Distributed Systems. 1996. Vol. 7, no. 5. P. 506-521.

62. Land A. H., Doig A. G. An automatic method of solving discrete programming problems // Econometrica. 1960. Vol. 28, no. 3. P. 497-520.

63. Liao C.-J., Tseng C.-T., Luarn P. A discrete version of particle swarm optimization for flowshop scheduling problems // Computers & Operations Research. 2007. Vol. 34. P. 3099-3111.

64. Liu C. L., Layland J. W. Scheduling algorithms for multiprogramming in a hard real-time enviroment // Journal of ACM. 1973. Vol. 20, no. 1. P. 46-61.

65. Media Oriented System Transport (MOST) Specification. Rev. 3.0 // MOST Cooperation. 2008. 233 pp.

66. Mitra H., Ramanathan P. A genetic approach for scheduling non-preemptive tasks with precedence and deadline constraints //In Proceedings of the 26th Hawaii International Conference on System Sciences. 1993.

67. Nossal R. An evolutionary approach to multiprocessor scheduling of dependent tasks // Future Generation Computer Systems. 1998. Vol. 14, no. 5-6. 383-392 pp.

68. Oh J., Wu. C. Genetic-algorithm-based real-time task scheduling with multiple goals // Journal of Systems and Software. 2004. Vol. 71, no. 3. 245-258 pp.

69. Peng D.-T., Shin K. G., Abdelzaher T. F. Assignment and scheduling of communicating periodic tasks in distributed real-time systems // IEEE Transac-. tions on Software Engineering. 1997. Vol. 23, no. 12. P. 745-758.

70. Qt. URL: http://qt.digia.com/ (дата обращения: 24.03.2013).

71. Tindell К., Burns A., Wellings A. Allocating Hard Real-Time Tasks: An NP-Hard Problem Made Easy // Journal of Real-Time Systems. 1992. Vol. 4, no. 2. P. 145-166.

72. Topcuoglu H., Hariri S., Wu M. Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing // IEEE Transactions on Parallel and Distributed Systems. 2002. Vol. 13, no. 3. P. 260-274.

73. Wu A. S., Yu H., Jin S. et al. An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling // IEEE Transactions on Parallel and Distributed Systems. 2004. Vol. 15, no. 9. P. 824-834.

74. Wiirtz J. Constraint-Based Scheduling in Oz // Operations Research Proceedings. Springer-Verlag, 1997. P. 218-223.

75. Xu J. Multiprocessor Scheduling of Processes with Release Times, Deadlines, Precedence, and Exclusion Relations // IEEE Transactions on Software Engineering. 1993. Vol. 19, no. 2. P. 139-154.