Разработка методов математического прогнозирования и динамического управления решением взаимосвязанных задач в распределенных и несимметричных параллельных вычислительных системах тема диссертации и автореферата по ВАК РФ 05.13.15, кандидат технических наук Случанко, Евгений Алексеевич

  • Случанко, Евгений Алексеевич
  • кандидат технических науккандидат технических наук
  • 2002, Москва
  • Специальность ВАК РФ05.13.15
  • Количество страниц 118
Случанко, Евгений Алексеевич. Разработка методов математического прогнозирования и динамического управления решением взаимосвязанных задач в распределенных и несимметричных параллельных вычислительных системах: дис. кандидат технических наук: 05.13.15 - Вычислительные машины и системы. Москва. 2002. 118 с.

Оглавление диссертации кандидат технических наук Случанко, Евгений Алексеевич

Введение

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендованный список диссертаций по специальности «Вычислительные машины и системы», 05.13.15 шифр ВАК

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Похожие диссертационные работы по специальности «Вычислительные машины и системы», 05.13.15 шифр ВАК

Заключение диссертации по теме «Вычислительные машины и системы», Случанко, Евгений Алексеевич

Выводы по главе 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.

Список литературы диссертационного исследования кандидат технических наук Случанко, Евгений Алексеевич, 2002 год

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.

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