Обеспечение совместимости требований к расписанию обмена по каналу с централизованным управлением тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Балашов, Василий Викторович

• Балашов, Василий Викторович
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Балашов, Василий Викторович

Введение.

1 Описание проблемы.

1.1 Организация информационного обмена по каналу с централизованным управлением.

1.2 Задача обеспечения совместимости требований к расписанию обмена.

1.3 Анализ проблемы несовместимости требований к расписанию обмена.

2 Модель предметной области и формальная постановка задачи.

2.1 Расписание для одноприборной системы без прерывания работ.

2.2 Формальная постановка задачи построения расписания.

2.3 Формальная постановка задачи обеспечения совместимости требований к расписанию (Рост).

3 Свойства требований к расписанию информационного обмена, допускающих ослабление.

3.1 Формальная модель и свойства требований, допускающих ослабление.

3.2 Задача обеспечения совместимости требований к расписанию, допускающих ослабление.

4 Совместимость требований к расписанию информационного обмена.

4.1 Достаточные условия принципиальной несовместимости требований.

4.2 Инвариантность принципиальной совместимости требований относительно максимального числа работ в цепочке.

4.3 Структура области решений задачи Рост.

4.4 Выводы.

5 Существующие методы решения задачи -Рост.

5.1 Характеристика задачи обеспечения совместимости требований.

5.2 Исчерпывающий поиск.

5.3 Детерминированный направленный поиск.

5.4 Случайный поиск.

5.5 Метод ветвей и границ.

5.6 Динамическое программирование.

5.7 Алгоритмы имитации отжига и генетические алгоритмы.

5.8 Жадные алгоритмы.

5.9 Выводы.

6 Решение задачи обеспечения совместимости требований к расписанию информационного обмена.

6.1 Конечная сетка на множестве решений.

6.2 Общее описание алгоритма решения задачи Рост.

6.3 Случайный поиск решений с сужением множества поиска.

6.4 Поиск по направлению наискорейшего убывания целевой функции.

6.5 Последовательное усиление требований.

6.6 Эвристическое сужение области поиска на основе свойств требования Rmcc

6.7 Алгоритм обеспечения совместимости требований.

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

7.1 Структура методики исследования.

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

7.3 Выбор алгоритмов решения задачи Рост для сравнительного исследования.

7.4 Выбор алгоритмов построения расписания.

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

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

7.7 Схемы проведения и результаты экспериментов.

7.8 Выводы.

8 Инструментальные средства обеспечения совместимости требований к расписанию информационного обмена.

8.1 Инструментальная система планирования обмена по каналу с централизованным управлением.

8.2 Подсистема обеспечения совместимости требований к расписанию обмена

Введение диссертации (часть автореферата) на тему «Обеспечение совместимости требований к расписанию обмена по каналу с централизованным управлением»

Встроенные системы представляют собой наиболее многочисленный класс вычислительных систем. Встроенные системы реального времени (ВСРВ) функционируют в непосредственном взаимодействии с внешней средой и должны за строго ограниченный сверху интервал времени формировать результат в виде управляющих воздействий или сообщений пользователю. Важным подклассом ВСРВ являются распределённые системы управления сложными техническими объектами (корабли, самолёты, производственные линии и т.п.). В состав таких ВСРВ входят сотни устройств, объединённых десятками каналов передачи данных. В настоящей диссертации рассматриваются ВСРВ жёсткого реального времени, в которых вычислительным работам и работам по передаче данных сопоставляются директивные сроки, не подлежащие нарушению. Разработка подобных ВСРВ является сложным процессом и требует применения специализированных подходов; существенный вклад в сложность разработки вносит необходимость обеспечения работы ВСРВ в реальном времени.

ВСРВ для управления сложными техническими объектами часто являются малосерийными в силу немногочисленности управляемых объектов (например, спутник связи). Трудоёмкость разработки таких ВСРВ вносит существенный вклад в стоимость каждого образца ВСРВ. В связи с этим актуальна автоматизация процесса разработки ВСРВ.

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

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

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

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

При этом предъявляются следующие требования к решению:

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

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

На настоящую работу оказали влияние предложенные в [33, 34] подходы к модификации параметров ВСРВ в случае невозможности построения корректных расписаний функционирования ВСРВ. Необходимо отметить, что ни эти подходы, ни предложенные в [35, 36, 37], не учитывают ряд требований к расписаниям, существенных для каналов с централизованным управлением.

Основные результаты диссертационной работы заключаются в следующем:

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

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

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

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

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

Во второй главе представлена формальная модель предметной области, включающая такие понятия, как набор периодических заданий, набор работ, расписание. В рамках этой модели дана формальная постановка задачи Рост обеспечения совместимости требований к расписанию. Эта задача поставлена в виде задачи математического программирования.

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

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

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

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

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

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

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

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

1 ОПИСАНИЕ ПРОБЛЕМЫ

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

Основные результаты диссертационной работы заключаются в следующем:

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

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

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

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

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

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

• использование целевой функции, отличной от линейной; в частности:

- кусочно-линейной функции с различными значениями коэффициентов с, на различных участках интервала [xflin; х™ах];

- функции, содержащей отдельный константный штраф сг° за сам факт изменения значения требования относительно начального значения х-;

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

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

Ещё одним важным направлением дальнейших исследований является расширение класса систем, для которых формулируется и решается задача обеспечения совместимости требований. Это могут быть, в частности:

• каналы с распределённым управлением [38-44];

• однопроцессорные вычислительные узлы27 [5, 14];

• одноприборные системы, в которых выполнение заданий конвейеризовано например, кольцо с арбитражем FC-AL [68]), в связи с чем длительность выполнения последовательности заданий отлична от суммы длительностей этих

28 заданий и зависит от порядка следования заданий ;

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

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

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

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат физико-математических наук Балашов, Василий Викторович, 2010 год

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

2. Бахрушин Н. И., Догадкин В. А., Колодцева М. В. и др. Универсальная корабельная система управления // Патент РФ на полезную модель №47540, 27.08.2005.

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

4. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990.-486 с.

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

6. Гуз Д. С. Разработка точных и приближенных алгоритмов составления расписаний и синтеза систем жесткого реального времени : дис. . канд. физ.-мат. наук : 05.13.18/МФТИ.-М„ 2005. 132 с.

7. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. М.: ФИЗМАТЛИТ, 2005. - 368 с.

8. Растригин Л. А. Статистические методы поиска. -М.: Наука, 1968. 376 с.

9. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы. М.: ФИЗМАТЛИТ, 2006. - 320 с.

10. Беллман Р. Динамическое программирование. — М.: Изд-во иностранной литературы, 1960. -400 с.

11. Коган Д. И. Задачи и методы конечномерной оптимизации. Часть 3. Динамическое программирование и дискретная многокритериальная оптимизация.- Нижний Новгород: Изд-во Нижегородского университета, 2004. 157 с.

12. Уоссермен Ф. Нейрокомпьютерная техника: Теория и практика. — М.: Мир, 1992. -240 с.

13. Трекин А. Г. Структурный синтез вычислительной системы с помощью генетических алгоритмов : дис. . канд. физ.-мат. наук : 05.13.11 / МГУ им. М. В. Ломоносова. М., 2002. - 111 с.

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

15. Ильин В. А., Ким Г. Д. Линейная алгебра и аналитическая геометрия. М.: Изд-во Московского университета, 2002. — 320 с.

16. ГмурманВ. Е. Теория вероятностей и математическая статистика. М.: Высшая школа, 2003.-479 с.

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

18. ГОСТ 23501.101-87. Системы автоматизированного проектирования. Основные положения. Введ. 01.07.1988 - М. : Изд-во стандартов, 2001.- 11 с.

19. Кремер Н. Ш. Теория вероятностей и математическая статистика. — М.: Юнити, 2004. 573 с.

20. Чистяков В. П. Курс теории вероятностей. М.: Наука, 1978. - 224 с.

21. Guide to Digital Interface Standards for Military Avionic Applications : Technical report ASSC/110/6/2-ISSUE 3 // Avionics Systems Standardization Committee (ASSC).- UK, 2006. 249 p.

22. 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 p.

23. Stewart D. В., Arora G. A Tool for Analyzing and Fine Tuning the Real-Time Properties of an Embedded System // IEEE Trans. Software Engineering. 2003. - Vol. 29, No. 4.-P. 311-326.

24. Park J., Ryu M., Hong S., Bello L. L. Rapid Performance Re-engineering of Distributed Embedded Systems via Latency and k-level diagonal search // Journal of Parallel and Distributed Computing. 2006. - Vol. 66, Issue 1. - P. 19-31.

25. Chien S., Gratch J. Producing Satisfying Solutions to Scheduling Problems: An Iterative Constraint Relaxation Approach // Proc. 2nd International Conference on Artificial Intelligence Planning Systems (AIPS'94). -2006. P. 78-87.

26. BambhaN. K., Bhattacharyya S. S., Teich J., Zitzler E. Hybrid Global/Local Search for Dynamic Voltage Scaling in Embedded Multiprocessors // Proc. 9th International Symposium on Hardware/Software Codesign. 2001. - P. 243-248.

27. IEEE 802.3-2008. IEEE Standard for Information technology Specific requirements - Part 3: Carrier Sense Multiple Access with Collision Detection (CMSA/CD) Access Method and Physical Layer Specifications // IEEE Standards Association. - 2008.

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

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

30. IEEE Std 960-1993. FASTBUS Module High-Speed Data Acquisition and Control System // Institute of Electrical & Electronics Engineering (IEEE). 1994. - 352 p.

31. ISO 11898-4:2004. Road vehicles Controller area network (CAN) - Part 4: Time-triggered communication // International Organization for Standardization (ISO). - 2004. -32 p.

32. FlexRay Communications System Protocol Specification. Version 2.1 //FlexRay Consortium. 2005. - 245 p.

33. Media Oriented System Transport (MOST) Specification. Rev. 3.0 //MOST Cooperation. 2008. - 233 p.

34. Balashov V. V., Kostenko V. A., Smeliansky R. L. et al. A Tool System for Automatic Scheduling of Data Exchange in Real-Time Distributed Embedded Systems // Proc. 7th IEEE International Symposium on Computer Networks (ISCN'06). 2006. -P. 179-184.

35. Blazewicz J., Ecker K., Pesch E., Schmidt G., Weglarz J. Handbook on Scheduling: From Theory to Applications. Springer, 2007. - 647 p.

36. Liu C. L., Layland J. W. Scheduling Algorithms for Multiprogramming in a Hard-RealTime Environment//Journal of the ACM. -1973. Vol. 20, No. 1. - P. 46-61.

37. Audsley N. С., Burns A., Richardson M. F., Wellings A. J. Hard Real-Time Scheduling: The Deadline Monotonic Approach // Proc. 8th IEEE Workshop on Real-Time Operating Systems and Software. 1991. - P. 135-138.

38. Jeffay K., Donald F., Stanat D. F., Martel C. U. On Non-Preemptive Scheduling of Periodic and Sporadic Tasks // Proc. 12th IEEE Real-Time Systems Symposium. 1991. -P. 129-139.

39. Tindell K. W., Burns A., Wellings A. J. An Extendible Approach for Analyzing Fixed-Priority Hard Real-Time Tasks // Journal of Real-Time Systems. 1994. - Vol. 6, No. 2. -P. 133-152.

40. Bate I.J. Scheduling and Timing Analysis for Safety Critical Real-Time Systems : Ph.D. thesis / University of York. York, UK, 1998. - 245 p.

41. Katcher D. I., Arakawa H., Strosnider J. K. Engineering and Analysis of Fixed Priority Schedulers // IEEE Trans, on Software Engineering. 1993. - Vol. 19, No. 9. - P. 920-934.

42. Arora G. Automated Analysis And Prediction of Timing Parameters in Embedded Real-Time Systems Using Measured Data : M.Sc. thesis (advisor: Stewart D. B.) / University of Maryland. Maryland, USA, 1997. - 78 p.

43. Sjodin M., Hansson H. Improved Response Time Analysis Calculations // Proc. 19th IEEE Real-Time Symposium. 1998. - P. 399^108.

44. Pollex V., KoIImann S., Albers K., Slomka F. Improved Worst-Case Response-Time Calculations by Upper-Bound Conditions // Proc. Conference on Design Automation and Test in Europe (DATE'09). 2009. - P. 105-110.

45. Sun J. Fixed-Priority End-To-End Scheduling in Distributed Real-Time Systems : Ph.D. thesis // University of Illinois at Urbana-Champaign. -Champaign, IL, USA, 1997. 183 P.

46. Peng Z. Synthesis of Fault-Tolerant Schedules with Transparency/Performance Tradeoffs For Distributed Embedded Systems // Proc. Conference on Design Automation and Test in Europe (DATE'06). 2006. - P. 706-711.

47. Pop Т., Pop P., Eles P., Peng Z. Analysis and Optimisation of Hierarchically Scheduled Multiprocessor Embedded Systems // International Journal of Parallel Programming. 2008. -Vol. 36, No. 1.-P. 37-67.

48. Standard Template Library: Containers. HTML] (http://www.cplusplus.com/reference/stl/).

49. Glover F., Laguna F. Tabu search. Norwell, MA, USA: Kluwer Academic Publishers, 1997.-408 p.

50. Kirkpatrick S., Gelatt C. D., Vecchi, M. P. Optimization by Simulated Annealing //Science. 1983.-No. 4598.-P. 671-680.

51. Wah B. W., Chen Y. Hybrid Constrained Simulated Annealing and Genetic Algorithms for Nonlinear Constrained Optimization // Proc. IEEE Congress on Evolutionary Computation. -2001.-P. 925-932.

52. Barr R., Golden B. L., Kelly J. P., Resende M. G. C., Stewart W. R. Designing and Reporting on Computational Experiments with Heuristic Methods // Journal of Heuristics.- 1995. Vol. 1, No. 1.-P. 9-32.

53. Mason R. L., Gunst R. F., Hess J. L. Statistical Design and Analysis of Experiments, with Applications to Engineering and Science. 2nd edition. - Wiley, 2003. - 760 p.

54. Мок A. K. Fundamental design problems of distributed systems for the hard-real-time environment : Ph.D. thesis / Massachusetts Institute of Technology. Cambridge, MA, USA, 1983.- 186 p.

55. Balashov V. V., Kostenko V. A., Smeliansky R. L. A Tool System for Automatic Scheduling of Data Exchange in Real-Time Distributed Avionics Systems // Proc. 2nd European Conference for Aerospace Sciences. 2007. - Электрон, опт. диск (CD-ROM).

56. WxWidgets Cross-Platform GUI Library. HTML] (http://wxwidgets.org/).

57. ISO/IEC 14165-122:2005. Information technology Fibre Channel - Part 122: Arbitrated Loop-2 (FC-AL-2) // International Organization for Standardization (ISO). - 2005.- 144 p.

58. Unified Modeling Language Specification. Version 1.4.2. PDF] (http://www.omg.org/docs/formal/05-04-01 .pdf).