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

Введение.

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

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

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

1.3. Постановка задачи диссертационной работы.

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

2.1. Исходные данные и математические модели.

2.2. Динамическое управление надежным выполнением КВР.

2.3. Динамическое уточнение статических прогнозов.

2.4. Выводы по главе II.

Глава Ш. Модификации методики прогнозирования и управления выполнением КВР в параллельных ВС.

3.1. Прогнозирование выполнения КВР при непредусмотренных состояниях системы.

3.2. Имитационные эксперименты по проверке Правил сравнения состояний.

3.3. Статическое прогнозирование и динамическое управление процессами для КВР с логическими ветвлениями между работами.

3.4. Выводы по главе Ш

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

4.1. Модуль задания графа КВР.

4.2. Модуль определения состояний обрывающегося марковского процесса при выполнении конкретного КВР.

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

4.4. Модуль имитационного моделирования выполнения КВР.

4.5. Модуль статистики.

4.6. Выводы по главе IV.

Выводы по диссертационной работе.

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

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

Формально под прогнозированием выполнения конкретного комплекса работ понимается стохастическая оценка (в статике) времени Т его реализации (среднее значение, дисперсия, функция распределения Т) и определение вероятности выполнения комплекса за время, не большее заданного директивного времени Г^, — на параллельной ВС с заданной структурой, конфигурацией и производительностью ее ресурсов.

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные материалы работы докладывались на XXXIX научной конференции Московского физико-технического института, Долгопрудный, 1996г., на ХЬ Юбилейной научной конференции Московского физико-технического института, Долгопрудный, 1997г., на ХЫ научной конференции Московского физико-технического института, Долгопрудный ,1998г.

Публикации. Основное содержание диссертационной работы изложено в шести опубликованых научных работах [71, 72,74,75, 76,77].

Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 98 стр., содержит список литературы из 80 наименований.

Выводы по диссертационнной работе

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

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

2. Динамическое управление выполнением КВР по предлагаемой методологии сводится к выбору алгоритмов управления дообслуживанием КВР в зависимости от реальных временных параметров завершения некоторых работ КВР (контрольных событий). Алгоритмы выбираются на основе сопоставления реальных временных параметров процессов с верхними (наиболее "пессимистическими") стохастическими оценками наступления контрольных событий по "таблице прогнозов" вьшолнения КВР.

1. Головкин Б.А. Вычислительные системы с большим числом процессоров. М.: Радио и связь. 1995.

2. Игнатущенко В.В. Организация структур управляющих многопроцессорных вычислительных систем. М.: Энергоиздат. 1984.

3. Башарин Г.П., Богуславский Л.Б., Штейнберг В.И. Анализ конфликтов в общей памяти мультипроцессорных систем. // Автоматика и вычислительная техника. 1980. N6. Стр. 2732.

4. Итенберг А.И. Аналитические исследования эффективности взаимодействия вычислительного ядра многопроцессорной вычислительной системы с периферийными процессорами. // Автореферат кандидатской диссертации. М.: ИПУ РАН. 1988.

5. Вайрадян A.C., Коровин A.B., Удалов В.Н. Эффективное функционирование управляющих мультипроцесссорных систем. М.: Радио и связь. 1984. 328 с.

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

7. Белинский A.C., Левнер Е.В. Проектирование моделей и методов теории расписаний в задачах оптимального планирования на грузовом транспорте. // Автоматика и телемеханика. 1989. N1.

8. Богуславский Л.Б., Крейнин A.A. Анализ влияния аппаратных конфликтов на производительность мультипроцессорных систем. // Управляющие системы и матттины. 1981. N2. С. 42-47.

9. Турута E.H. Организация распределения задач в вычислительных системах, обеспечивающая их отказоустойчивость. // Автоматика и вычислительная техника. 1985. N1.C. 5-14.

10. Турута E.H., Ковалев В.Ш. Об одном методе повышения живучести локальных сетей ЭВМ. // Автоматика и вычислительная техника. 1983. N5. С. 42-44.

11. Головкин Б.А. Расчет характерисик и планирование параллельных вычислительных процессов. М.: Радио и связь. 1983. 272 с.

12. Основы теории вычислительных систем. Под ред. С.А.Майорова. М.: Высшая школа. 1978.

13. Бусленко М.П Моделирование сложных систем. М.: Наука. 1968.

14. Лифшиц A.A., Мальц Э.А. Статическое моделирование систем массового обслуживания. М.: Советское радио. 1978. 248 с.

15. Авен О.Н., Гурин H.H., Коган Я.А. Оценка качества и оптимизация вычислительных систем. М.: Наука. 1982.

16. Заболотный A.A. Влияние прерываний конвейера на эффективность многопроцессорных систем. // Электронное моделирование. 1987. N2. С. 17-20.

17. Калинин И.А., Островский И.А. К вопросу о предварительной оценке загрузки процессора и времени реакции в системе коллективного пользования. // Рукоп.Деп. в ИНФОРМПРИБОР. N 4045- пр87. Деп. от 25. 1987.

18. Артамонов Г.Т., Брехов О.М. Аналитические вероятностные модели функционирования ЭВМ. М.: Энергия. 1978.

19. Такагн X., Богуславский Л.Б. Библиография книг по анализу очередей и оценке производительности вычислительных систем. // Автоматика и вычислительная техника. 1993. N3. С. 22-40.

20. Bogurovic N. Process scheduling procedure for a class of real-time computer systems. // "ШЕЕ Trans, and electron." 1987. V. 34. N1. p. 29-34.

21. Woodbory Michael H. Analysis of the execution time of real-time tasks. // "Real-time sys. Sy., New Orleans, La, Dec. 2-4,1986. Proc. " Waschington D.C. 1986. p. 89-96.

22. Калмыков Б.Н., Хохловский B.H. Планирование параллельных вычислений в децентрализованной микропроцессорной системе реального времени. "Изв. Ленинград, эл. тех. инст." 1987. N389. с. 31-33.

23. Сушков Б.Г. Некоторые алгоритмы планирования вычислений в детерминированных вычислительных системах реального времени. М.: ВЦ АН СССР. 1987. 57 с.

24. Ярусов А.Г. Операционные модели и планирование параллельных вычислений в многопроцессорной системе реального времени. Управляющие системы и машины. 1983. N3. С. 18-22.

25. Майоров С.А., Новиков Г.И. Структуры электронных вычислительных систем. Л. : Машиностроение. 1979.

26. Феррари Д. Оценка производительности вычислительных систем. М.: Мир. 1981.

27. Литвин В.Г., Аладышев В.П., Винниченко А.И. Анализ производительности мультипрограммных ЭВМ. М.: Финансы и статистика. 1984.

28. Пржиялковский В.В. Сравнительный анализ оценок производительности различных ЭВМ. // Вопросы радилэлектроники. Серия ЭВТ. 1977. Вып. 5.

29. Артамонов Г.Т. Развитие методов оценки производительности ВС. В кн.: Тезисы Всесоюзного совещания "Высокопроизводительные вычислительные системы". М. ИПУ. 1984.

30. Chu W.W., Leung К.К. Module replication and assisgment for real-time distributed processing system. // "Proc. IEEE". 1987. 75. N5. Pp. 547-562.

31. Сокол Ю.М., Казанцев П.Н. Некоторые вопросы эффективности процессора с разделением вычислительных ресурсов. // Управляющие системы и машины. 1973. N2.

32. Клейнрок JI. Вычислительные системы с очередями. М.: Мир. 1979.

33. Петров П.М., Николаев А.В. Аналитическая модель для оценки производительности МВС. // Автоматика и вычислительная техника. 1982. N4.

34. Geist R., Stevenson D., Aiien R. The perceived effect of breakdown and repair on the performance of multiprocessor system. // "Performance Evaluation." 1986. Y6. N4. Pp. 249-260.

35. Realiability analysis of two-unit cold standby redundant system with administrative delay and no priority in repair. // "Microelectron Relaib". 1986. V26. Pp. 847-850.

36. Быков B.A., Додонов А.Г., Клименко В.Г. Математическое моделирование информационно-вычислительных сетей. // "Ин-т проблем моделирования в энергетике АН УССР. Препр.". 1987. N60.

37. Лубков Н.В. Оценка и прогнозирование надежности вычислительных средств с учетом процессов контроля, диагностирования, восстановления, технического обслуживания. М.: Машиностроение. 1985. 48 с.

38. Креденцер Б.П., Сидоров Л.А. Модель надежности систем с комбинированным резервом времени и случайным режимом использования. Автоматика и телемеханика. 1988. N10.

39. Лобанов Л.П., Кударенко А.А., Пивоваров И.В., Тересков В.А., Тимофеев Г.С. Метод анализа одного класса систем массового обслуживания и его использования для оценки производительности МВС. // Программирование. 1986. N12.

40. Борисенко В.М. Оптимизация структуры многопроцессорной вычислительной системы. Автоматика и телемеханика. 1986. N12.9*1

41. Скрипкин H.A. Анализ производительности специализированных вычислительных устройств с помощью потоковых моделей. // Рукопись деп. В ЦНИИТЭ Приборостроения. N4001-пр. 87.

42. Трахтенгерц Э.А. Программное обеспечение параллельных процессов. М. : Наука. 1987.

43. Заболотный A.A., Недзельский Д.А. Анализ функционирования мультипроцессорных систем с перестраиваемой структурой в переменном режиме. // Управляющие системы и машины. 1984. N1.

44. Sahner Robin A., Trivedi Kishor S. Performance and reliability analysis using directed acyclic graphs. // "IEEE trans. Software Eng". 1987. 13. N10. Pp. 1105-1114.

45. Шенборт И.М., Алиев B.M. Оптимизация структуры распределенных АСУ технологическими процессами. // Измерения, контроль, автоматизация. 1988. N1(65). С. 74-80.

46. Reiter R. Scheduling parallel computations. // J. ACM. 1968. V.5. N14. Pp. 590-599.

47. Поспелов Д.А. Введение в теорию вычислительных систем. М.: Сов.радио. 1972. 280 с.

48. Маргалиташвили A.A., Амбарцумян A.A., Тепляков A.B., Прейдунов Ю.В. Графовые модели комплексов взаимосвязанных работ. // Деп. ВИНИТИ. N587-B90.

49. Борисенко В.М., Амбарцумян A.A., Маргалиташвили A.A., Прейдунов Ю.В. Аналитические оценки эффективности диспетчеризации параллельных работ в многопроцессорных вычислительных системах. // Деп. ВИНИТИ. N375-B88.

50. Бочаров П.П., Прейдунов Ю.В. Оценка времени выполнения комплекса работ на параллельной вычислительной системе. // Системный анализ и информатика. Сб. Научных трудов. М.: Изд-во УДН, 1991. С. 29-41.

51. Маргалиташвили A.A. Исследование эффективности функционирования параллельных вычислительных ресурсов на заданных комплексах взаимосвязанных работ. Канд. диссертация. М.: Ин-т проблем управления РАН, 1990.

52. Бочаров П.П., Прейдунов Ю.В. Прогнозирование выполнения сложных программных комплексов на параллельных вычислительных системах. // Автоматика и телемеханика. 1992. N12. С. 148-154.

53. Игнатущенко В.В., Клушин Ю.С. Прогнозирование выполнения сложных программных комплексов на параллельных компьютерах: прямое стохастическое моделирование. // Автоматика и теллемеханика. 1994. N11. С. 142-157.

54. Ляхов А.И. Асимптотический анализ неоднородной сетевой модели многопроцессорных и многотерминальных систем. // Автоматика и телемеханика. 1994. N2. С. 161-171.

55. Богуславский Л.Б , Ляхов А.И. Методы оценки производительности многопроцессорных и многотерминальных систем. М.: Наука, 1992. 213 с.

56. Гершуни Д.С. Планирование вычислений в системах жесткого реального времени (обзор и перспективы).// Вычислительная техника. Системы. Управление. 1991. N6. С.4-51.

57. Monitoring and debugging of distributed real-time systems. IEEE Computer Society Press, 1995. 429p.

58. D.Haban, Shin K.J. Application of real-time monitoring to scheduling tasks with random execution times. IEEE Computer Society Press, 1995. P.368-383.

59. Мок A.K., Liu G. Early detection of timing constraint violation at runtime // Proc. Of 18-th IEEE Real-Time Systems Symposium (RTSS'97), San Fransisco, USA, December 3-5,1997.

60. Puschner P., Nossal R. Testing the results of static worst-case execution time analysis // Proc. Of 19-th IEEE Real-Time Systems Symposium (RTSS'98), Madrid, Spain, December 2-4, 1998.

61. Игнатущенко B.B., Тепляков A.B. Об эффективности временного резервирования параллельных вычислительных процессов// АиТ. 1994. №6. С. 15466. Natarajan S., Zhao W. Issues in Building Dynamic Real-Time Systems // IEEE Software. Sept. 1992. P. 16-21.

62. Stancovic J., Ramamritham K. The Spring Kernel: A New Paradigm for Real-Time Operating Systems // Operating Systems Rev. July 1989. P. 54-71.

63. Liu J.W.S. et al. Algorithms for Scheduling Imprecise Computation // Computer. May 1991. P. 58-68.

64. Marlin C., Ransom K., Zhao W. An integrated environment for the development and analysis of hard real-time systems // Real-Time Programming. Oxford: Pergamon Press, 1992. P.27-32.

65. Gopinath P., Schwan K. Chaos: Why One Cannot Have Only an Operating Systems for Real-Time Application // Operating Systems Rev. July 1989. P. 106-125.

66. Игнатущенко B.B., Подшивалова И.Ю. Динамическое управление параллельными вычислительными процессами на основе статического прогнозирования их вьшолнения. // АиТ. 1997. № 5. С. 160-173.

67. Ignatushchenko V.V. A principle of dynamic control of parallel computing processes on the basis of static forecasting // Proc. of the 10-th Int. Conf. on Parallel and Distributed Computing Systems (PDCS-97). New Orleans, USA, Oct. 1997. P. 593-597.

68. В.В.Игнатущенко, И.Ю. Подшивалова. Динамическое управление надежным выполнением параллельных вычислительных процесссов для систем реального времени. // АиТ. 1999. №6.

69. Кук С.О., Подшивалова И.Ю. Прогнозирование вьшолнения сложных программных комплексов в условиях сбоев компонент параллельной ВС. // Тезисы докладов XL

70. Юбилейной научной конференции Московского физико-технического института. Выпуск1. 28-29 ноября 1997г. Долгопрудный. С. 33.

71. Подшивалова И.Ю. Прогнозирование выполнения сложных программных комплексов при неисправностях в параллельных ВС. // Тезисы докладов XLI научной конференции Московского физико-технического института. Часть П. 27-28 ноября 1998г. Долгопрудный. С. 40.

72. Ферранте Дж., Оттенштейн К., Уоррен Дж. Граф программных зависимостей и его применение в оптимизации // Сб. Векторизация программ: теория, методы, реализация. М.: Мир, 1991. С. 141—182.

73. Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ в процессе трансляции. М.: Наука, 1981.

74. Oudshoorn M.J., Huang L. Conditional task scheduling on loosely-coupled distributed processors // Proc. of the 10-th Int. Conf. on Parallel and Distributed Computing Systems (PDCS-97). New Orleans, USA, Oct. 1997. P. 136-140.