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

• Юхта, Павел Валерьевич
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Юхта, Павел Валерьевич

Введение.

1. Анализ современных подходов при планировании вычислительного процесса в системах реального времени.

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

1.1.1. Классификация методов планирования.

1.1.2. Планирование в однопроцессорных системах реального времени.

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

1.1.4. Планирование в распределенных системах.

1.2. Особенности организации вычислительного процесса в навигационных комплексах.

1.3. Постановка проблемы планирования в навигационных комплексах.

1.4. Выводы.

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

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

2.1.1. Планирование независимых задач.

2.1.2. Планирование независимых задач при заданных директивных сроках.

2.1.3. Планирование зависимых задач.

2.1.4. Планирование в вычислительной подсистеме гидроакустического лага.

2.2. Разрешимые случаи иерархических систем.

2.3. Построение для распределенных иерархических систем из разрешимых классов оптимальных планов при заданных директивных сроках.

2.4. Выводы.

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

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

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

3.3. Метод многопоточного планирования вычислительного процесса в навигационных комплексах.

3.4. Выводы.

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

4.1. Анализ функционального программного обеспечения НК.

4.2. Построение плана вычислительного процесса НК.

4.3 Анализ корректности плана вычислительного процесса НК с использованием имитационного моделирования.

4.4. Выводы.

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

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

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

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

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

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

Материалы диссертации докладывались на международных научно-технических конференциях «Кибернетика и высокие технологии XXI века» (Воронеж, 2007, 2009 г.г.), на 3-й Всероссийской научно-технической конференции «Методы и средства обработки информации» МСО-2009 (Москва, 2009), на XXVI конференции памяти выдающегося конструктора гироскопических приборов H.H. Острякова (Санкт-Петербург, 2008 г.), на IX, X, XI и XII конференциях молодых ученых «Навигация и управление движением» (Санкт-Петербург, 2007, 2008, 2009 и 2010 гг.).

По материалам диссертации опубликовано 15 работ, из них 2 статьи в научно-технических журналах, рекомендуемых ВАК, 5 докладов в материалах проводимой в Санкт-Петербурге конференции молодых ученых «Навигация и управление движением», 2 доклада в сборниках трудов международной научно-технической конференции в г. Воронеж, 1 доклад в сборнике Всероссийской научно-технической конференции «Методы и средства обработки информации» МСО-2009, г. Москва.

На защиту выносятся следующие научные результаты:

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

- результаты анализа эффективности субоптимального метода однопоточного планирования вычислительного процесса для распределенных систем реального времени с иерархическим отношением предшествования для решаемых задач;

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

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

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

4.4. Выводы

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

1. Произведен анализ функционального программного обеспечения НК «Симфония» и осуществлено его преобразование к виду, удобному для планирования.

2. Сформирован план вычислительного процесса с использованием «Системы автоматизации разработки плана вычислительного процесса».

3. Произведен анализ полученного плана с помощью стенда моделирования «ДИАНА» с целью определения временных запасов для потоков при различной неопределенности длительности выполнения задач.

Заключение

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Юхта, Павел Валерьевич, 2010 год

1. Анучин О.Н., Емельянцев Г.И. Интегрированные системы ориентации и навигации для морских подвижных объектов. — СПб.: ЦНИИ «Электроприбор», 2003. 388 с.

2. Вентцель, Е. С. Исследование операций. — М.: Советское радио. -1972.- 552 с.

3. Воеводин, В. В. Параллельные вычисления/ В. В. Воеводин, Вл. В. Воеводин. СПб.: БХВ-Петербург, 2002. - 608 с.

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

5. Дмитриев, С.П. Оценка сдвига частоты в доплеровском измерителе скорости путем идентификации модели принятого сигнала / С. П. Дмитриев, А. И. Соколов // Гироскопия и навигация. — 2006. — №1. — С. 2128.

6. Дубовик, Е. 08ЕК операционная система для автомобильной электроники. // Современная Электроника. - 2010. - №2. - С. 10-11.

7. Зыков А. А. Основы теории графов М.: Наука, 1987. — 383с.

8. Каляев, А. В. Многопроцессорные системы с программируемой архитектурой. М.: Радио и связь. - 1984. - 240 с.

9. Колесов, Н. В. Планирование вычислительного процесса в иерархических системах / Н. В. Колесов, М. В. Толмачева // Теория и системы управления. 2007. - № 2. - С. 5-12.

10. Конвей, Р.В. Теория расписаний. / Р. В. Конвей, В. Л. Максвелл, Л. В. Миллер М.: Наука. - 1975. - 320 с.

11. Костенко В. А. Задача построения расписания при совместном проектировании аппаратных и программных средств // Программирование. — 2002.-№3.-С. 64-80.

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

13. Левин, В. И. Структурно-логические методы исследования сложных систем с применением ЭВМ. М.: Наука. - 1987. — 304 с.

14. Левин, В. И. Оптимизация расписаний в М-стадийной системе с неопределенными временами обработки. // Автоматика и телемеханика. — 2002.- №2.-С. 125- 136.

15. Мирецкий, И. Ю. Синтез субоптимальных расписаний для систем последовательного типа //Изв. РАН. Т и СУ. 2002. - № 1. - С. 137 - 144.

16. Операционная система реального времени QNX Neutrino 6.3. Системная архитектура: Пер. с англ. СПб.: БХВ-Петербург, 2006. — 336 с.

17. Павлов, А. М. Организация перспективных систем информационного обмена: характеристики и ограничения // Изв. РАН. ТиСУ.- 2002. № 6. - С. 123-130.

18. Смелянский, Р. Л. Модель функционирования распределенных вычислительных систем. // Вестн. Московского университета, Сер. 15, Вычислительная математика и кибернетика. 1990. - № 3. - С. 3- 21.

19. Столингс, В. Операционные системы. М.: Изд. Дом «Вильяме», 2002. - 844 с.

20. Танаев, В. С. Теория расписаний. Многостадийные системы. / В. С. Танаев, Ю. Н. Сотсков, В. А. Струсевич М.: Наука. - 1989. - 328 с.

21. Теория расписаний и вычислительные машины / Под ред. Э. Г. Коффмана. М.: Наука. - 1984. - 334 с.

22. Таненбаум, Э. Современные операционные системы. 2-е изд. -СПБ.: Питер, 2002. - 1040 с.

23. Таненбаум, Э. Архитектура компьютера. 5-е издание. — СПб.: Питер, 2007. - 844 с.

24. Топорков, В. В. Модели распределенных вычислений. М.: Физматлит, 2004. - 316 с.

25. Хорошевский, В. Г. Архитектура вычислительных систем. — М.: МГТУ им. Н.Э. Баумана, 2005. 512 с.

26. Юхта, П.В. Программные средства для разработки и исследования вычислительного процесса в навигационном комплексе / П. В. Юхта, М. В. Толмачева // Гироскопия и навигация. 2007. - №2. - С. 105.

27. Юхта, П. В. Исследование эффективности алгоритма планирования вычислительного процесса в иерархической системе / П. В. Юхта, М. В. Толмачева // Гироскопия и навигация. 2007. - №2. — С. 104105.

28. Юхта, П.В. Построение расписаний решения задач с заданными директивными сроками // Гироскопия и навигация. 2008. — №2. - С. 88.

29. Юхта, П.В. Планирование вычислений в управляющих системах реального времени / П. В. Юхта, Н. В. Колесов, М. В. Толмачева // Управление и информационные технологии: сб. 5-й науч. конф., 2008. Т. 2. -С. 43-48

30. Юхта, П. В. Построение расписаний решения задач с заданными директивными сроками // Навигация и управление движением: материалы докл. X конф. молодых ученых, СПб, 11-14 2008 г. / ГНЦ РФ ЦНИИ "Электроприбор" СПб, 2009 г. - С. 174-179.

31. Юхта, П. В. Планирование вычислительного процесса в многопроцессорных системах при заданных для решаемых задач директивных сроках / П. В. Юхта, Н. В. Колесов, М. В. Толмачева // Вестник компьютерных и информационных технологий. 2009. - № 6. - С. 31-37.

32. Юхта, П. В. Опыт применения программной среды ДИАНА для моделирования и интеграции бортовых вычислительных систем / П. В. Юхта и и др. // Гироскопия и навигация. 2009. - № 2. - С. 48-55.

33. Юхта, П. В. Исследование чувствительности вычислительного процесса в системах реального времени к его параметрам// Гироскопия и навигация. 2009. - № 2. - С. 88.

34. Юхта П.В. Свидетельство о государственной регистрации программы для ЭВМ №2010613554. Система автоматизации разработки плана вычислительного процесса, 2010.

35. Andersson В., Baruah S. and Jonsson J., Static-priority scheduling on multiprocessors. // Proceedings of the 22nd IEEE Real-Time Systems Symposium, London, pp. 193-202, December 2001.

36. Baruah S., Buttazzo G., Gorinsky S., Lipari G. Scheduling periodic task systems to minimize output jitter. // Proceedings of the Sixth International Conference on Real-Time Computing Systems and Application, pp. 62-69 1999.

37. Berstis V. Fundamentals of Grid Computing. // Redbooks paper. IBM. 2002. 28 p.

38. Blazewicz J., Scheduling dependent tasks with different arrival times to meet deadline. // Modeling and Performance Evaluation of Computer Systems, North Holland, Amsterdam, pp. 57-65, 1977.

39. Blazewicz J., Ecker K. Multiprocessor Task Scheduling with Resource Requirements // Real-Time Systems, vol. 6. pp 37—53, 1994.

40. Brucker P., Jurisch В., and Sievers B. A branch and bound algorithm for the job-shop scheduling problem.// Discrete Applied Mathematics, vol. 49(1-3), pp. 107-127, 1994.

41. Brucker P. Scheduling Algorithms. // Springer. 2007 371 p.

42. J. Carlier and E. Pinson. An algorithm for solving the job-shop problem. //Management Science, vol. 35(2), pp. 164-176, 1989.

43. Cheng A.M.K. Real-Time Systems. Scheduling, Analysis, and Verification. // John Wiley & Sons, Inc., Hoboken, New Jersey. 2002. 266 p.

44. Cottet F., Kaiser J., Mammeri Z. Scheduling in Real-Time Systems. // John Wiley & Sons Ltd. 2002. 266p.

45. Dertouzos M.L. and Mok A.K.L., Multiprocessor on-line scheduling of hard real-time tasks. // IEEE Transactions on Software Engineering, vol. 15(12), pp. 1497-1506, 1989.

46. Dhall S.K., Scheduling periodic-time critical jobs on single processor and multiprocessor computing systems, PhD thesis, University of Illinois, ApriL 1977.

47. Gendy Ayman K., Pont Michael J. Automatically Configuring Time-Triggered Schedulers for Use With Resource-Constrained, Single-Processor Embedded Systems // IEEE Transactions on industrial informatics, vol. 4, № 1, pp. 37-46, 2008.

48. Jayachandran P., Tarek F. Abdelzaher. Delay composition in preemptive and non-preemptive real-time pipelines. // Real-Time Systems vol. 40(3), pp. 290-320, 2008.

49. Johnson S.M. Optimal two-and-three-stage production schedules with set-up times included. // Naval Research Logistic Quaterly, vol; 1, pp. 61-68, 1954.

50. Kats V., Levner E. Cyclic scheduling of operations for a part type in an FMS handled by a single robot: a parametric critical-path approach.// The International Journal of FMS, vol. 10 (2), pp. 129-138, 1998.

51. Kleinrock, L., and R. R. Muntz: Processor Sharing Queueing Models of Mixed Scheduling Disciplines for Time Shared System. // Journal of the ACM (JACM), vol. 19 (3), 1972.

52. Kopetz K. Real-Time Systems. Design Principles for Distributed Embedded Applications. // Kluwer Academic, Dordrecht, 1997. 356p.

53. Levner E. Multiprocessor Scheduling. Theory and Applications. // I-Tech Education and Pablishing, Vienna, Austria, 2007. — 436 p.

54. Liu J.W.S. Real-Time Systems.// Prentice Hall, Englewood Cliffs, NJ, 2000. 600p.

55. Liu C.L. and Layland J.Wi Scheduling algorithms for multiprogramming in a hard real-time environment. // J. ACM, vol. 20, № 1, pp. 40-61, 1973.

56. 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.

57. McNaughtan R., Scheduling with deadlines and loss functions. // Management Science, vol. 6, pp. 1-12, 1959.

58. Mok 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.

59. Muth, J. F., Thompson, G. L. Industrial Scheduling. // Englewood Cliffs, N. J.: Prentice-Hall, 1963

60. Marco Di Natale, J.A. Stankovic. Scheduling Distributed Real-Time Tasks with Minimum Jitter.// IEEE Transactions on computers, vol. 49, № 4, pp. 303-316, 2000.

61. Michael L. Pinedo. Scheduling. Theory, Algorithms, and Systems. // Springer. 2008 671 p.

62. Sahni S.K., Preemptive scheduling with due dates. // Operational Research, vol. 27(5), pp. 925-934, 1979.

63. Stankovic J.A. Distributed real-time computing: the next generation. // Technical Report TR92-01, University of Massachusetts, 1992.

64. Stankovic John A., M. Spuri, K. Ramemritham, G.C. Buttazzo. Deadline Scheduling for Real-Time Systems. // Kluwer Academic Publishers, London, 1998.-273 p.

65. Tindell K., Burns A., and Wellings A. Allocating Real-Time Tasks (an NP-Hard Problem Made Easy). // Real-Time Systems, vol. 4(2), pp. 145-165, 1992.

66. Wang Ji-Bo, Zun-Quan Xia. Scheduling jobs under decreasing linear deterioration. // Information Processing Letters, vol. 94(2), pp. 63-69, 2005.

67. Wang Ji-Bo. Flow shop scheduling problems with decreasing linear deterioration under dominant machines. // Computers and Operations Research, vol. 37(7), pp. 2043-2058, 2007.

68. Xiliang Zhong and Cheng-Zhong Xu. Energy-Aware Modeling and Scheduling for Dynamic Voltage Scaling with Statistical Real-Time Guarant // IEEE Transactions on Computers, vol. 56(3), pp. 358-372, 2005.