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

Введение

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

1.1. Эффективная производительность параллельных управляющих вычислительных систем (ВС) и методы оценки времени выполнения комплексов независимых и взаимосвязанных работ.

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

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

Глава 2. Математические модели для прогнозирования времени выполнения комплексов взаимосвязанных работ (КВР) в параллельных ВС с распределенной структурой.

2.1. Базовая математическая модель функционирования параллельных ВС с распределенной структурой.

2.2. Прогнозирование времени выполнения реальных КВР в распределенных ВС со статическим планированием работ по процессорам.

2.3. Модификация базовой математической модели для распределенных ВС с параллельными коммуникациями.

2.4. Модификация базовой математической модели для прогнозирования времени выполнения КВР на уровне фрагментов его работ.

Выводы по главе 2.

Глава 3. Аппарат выбора контрольных работ и назначения контрольных событий для управления выполнением КВР.

3.1. Исходные данные.

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные материалы работы докладывались на XXVIII и XXIX Международных конференциях «Информационные технологии в науке, образовании, телекоммуникации, бизнесе» (1Т+8Е'2001 и 1Т+8Е'2002), на ХП1, ХЫП, XI.IV и XI., V научных конференциях Московского физико-технического института «Современные

Выводы по главе 4

1. На основе методологии [70 - 72] математического прогнозирования времени выполнения комплексов взаимосвязанных работ (КВР), впервые решена задача формальной оценки и выбора критериев (дисциплин) динамической диспетчеризации работ КВР - из априорно заданного набора критериев - по процессорам неоднородных многопроцессорных вычислительных систем (МВС) для каждого конкретного КВР, задаваемого пользователем, - с целью минимизации времени выполнения заданного КВР в МВС, включающей разнотипные процессоры различной производительности.

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

Глава 5. Программные реализации разработанных математических моделей и алгоритмов

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

Конкретно автором диссертации разработаны следующие программные модули:

- модуль задания структуры графа КВР;

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

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

- модуль статистики.

Все модули запрограммированы на языке Visual Basic 6.0 и реализованы на ЭВМ класса IBM PC.

Модуль задания структуры графа КВР предназначен для ввода в программу начальных данных. В этом модуле вводятся начальные данные при использовании алгоритма прямого стохастического моделирования [57]. В качестве исходных данных используются:

- параметры параллельной ВС — число типов обслуживающих приборов (процессоров ВС). Например, для СМО по рис. 1.2 это число равно 1, так как в ней присутствуют только ОП для работ первого типа. Для СМО по рис. 2.2 число типов ОП равно 2, поскольку в ней присутствуют, как ОП для работ первого типа, так и ОП для работ второго типа. Также задается число обслуживающих приборов для каждого типа. Например, для СМО по рис. 2.2 число ОП первого типа равно 2, а число ОП второго типа равно 1. При рассмотрении СМО с параллельными коммуникациями, по рис. 2.8, число ОП второго типа становится равным 2.

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

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

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. С. 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. // "IEEE 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. " Washington D.C. 1986. p. 89-96.

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

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

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

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

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

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

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

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

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

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

32. Клейнрок Л. Вычислительные системы с очередями. М.: Мир. 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. V6. N4. Pp. 249-260.

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

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

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

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

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

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

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

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

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. Шенборт И.М., Алиев В.М. Оптимизация структуры распределенных АСУ технологическими процессами. // Измерения, контроль, автоматизация. 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. Бочаров П.П., Прейдунов Ю.В. Прогнозирование выполнения сложных программных комплексов на параллельных вычислительных системах. // Автоматика и телемеханика.1. MS1992. 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.429р.

58. D. Haban, Shin К,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 Francisco, 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. 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ш

63. Operating Systems // Operating Systems Rev. July 1989. P. 54-71.

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

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

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

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

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

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

71. Случанко E.A., Помазов E.B. Математическая модель для прогнозирования выполнения задач в распределенных вычислительных системах // Тез. докл. XLII научн. конф. МФТИ "Современные проблемы фундаментальных и прикладных наук". 1999. Москва. Часть 2. С. 51.

72. Еналиев A.M., Игнатущенко В.В., Помазов Е.В., Случанко Е.А. Методы математического прогнозирования времени выполнения сложных наборов задач в параллельных вычислительных системах с распределенной структурой // АиТ. 2002. № 10.1. С. 154-176.

73. Tindell R.W., Burns A. and Welling A.J. Allocation Hard Real-Time Tasks: An NP-Hard Problem Made Easy // The Journal of Real-Time Systems. 1992. № 4. P. 145-165.

74. Keqin Li, Yi Pan. Probabilistic Analysis of Scheduling Precedence Constrained Parallel Tasks on Multicomputers with Contiguous Processor Allocation // IEEE Trans, on Computers. Vol. 49. № 10. Oct. 2000. P. 1021-1030.

75. Клушин Ю.С. Точные методы прогнозирования времени выполнения сложных программных комплексов на параллельных компьютерах. Канд. дисс. ИПУ РАН. 1998.

76. Topsuoglu Н., Hariri S., Wu V.-Y. Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing // IEEE Trans, on Parallel and Distrib. Syst. Vol. 13. No 3. March 2002. P.260-274.