Помощь в написании студенческих работ
Антистрессовый сервис

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

Диссертация: Разработка методов динамического управления параллельными вычислительными процессами на основе статического прогнозирования их выполнения
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

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

Содержание

  • Глава I. Методы исследования функционирования параллельных вычислительных систем с учетом параметров взаимосвязанных задач
    • 1. 1. Эффективная производительность параллельных вычислительных систем и методы оценки времени выполнения комплексов взаимосвязанных работ
    • 1. 2. Проблема прогнозирования времени выполнения задач в параллельных вычислительных системах
    • 1. 3. Постановка задачи диссертационной работы
  • Глава II. Методология использования статического прогнозирования для динамического управления параллельными вычислительными процессами
    • 2. 1. Исходные данные и математические модели
    • 2. 2. Динамическое управление надежным выполнением КВР
    • 2. 3. Динамическое уточнение статических прогнозов
    • 2. 4. Выводы по главе II
  • Глава III. Модификации методики прогнозирования и управления выполнением КВР в параллельных ВС
    • 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. A.C., Левнер Е. В. Проектирование моделей и методов теории расписаний в задачах оптимального планирования на грузовом транспорте. // Автоматика и телемеханика. 1989. N1.
  7. Л.Б., Крейнин A.A. Анализ влияния аппаратных конфликтов на производительность мультипроцессорных систем. // Управляющие системы и матттины. 1981. N2. С. 42−47.
  8. E.H. Организация распределения задач в вычислительных системах, обеспечивающая их отказоустойчивость. // Автоматика и вычислительная техника. 1985. N1.C. 5−14.
  9. E.H., Ковалев В. Ш. Об одном методе повышения живучести локальных сетей ЭВМ. // Автоматика и вычислительная техника. 1983. N5. С. 42−44.
  10. .А. Расчет характерисик и планирование параллельных вычислительных процессов. М.: Радио и связь. 1983. 272 с.
  11. Основы теории вычислительных систем. Под ред. С. А. Майорова. М.: Высшая школа. 1978.
  12. Бусленко М. П Моделирование сложных систем. М.: Наука. 1968.
  13. A.A., Мальц Э. А. Статическое моделирование систем массового обслуживания. М.: Советское радио. 1978. 248 с.
  14. О.Н., Гурин H.H., Коган Я. А. Оценка качества и оптимизация вычислительных систем. М.: Наука. 1982.
  15. A.A. Влияние прерываний конвейера на эффективность многопроцессорных систем. // Электронное моделирование. 1987. N2. С. 17−20.
  16. И.А., Островский И. А. К вопросу о предварительной оценке загрузки процессора и времени реакции в системе коллективного пользования. // Рукоп.Деп. в ИНФОРМПРИБОР. N 4045- пр87. Деп. от 25. 1987.
  17. Г. Т., Брехов О. М. Аналитические вероятностные модели функционирования ЭВМ. М.: Энергия. 1978.
  18. Bogurovic N. Process scheduling procedure for a class of real-time computer systems. // «ШЕЕ Trans, and electron.» 1987. V. 34. N1. p. 29−34.
  19. 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.
  20. .Н., Хохловский B.H. Планирование параллельных вычислений в децентрализованной микропроцессорной системе реального времени. «Изв. Ленинград, эл. тех. инст.» 1987. N389. с. 31−33.
  21. .Г. Некоторые алгоритмы планирования вычислений в детерминированных вычислительных системах реального времени. М.: ВЦ АН СССР. 1987. 57 с.
  22. А.Г. Операционные модели и планирование параллельных вычислений в многопроцессорной системе реального времени. Управляющие системы и машины. 1983. N3. С. 18−22.
  23. С.А., Новиков Г. И. Структуры электронных вычислительных систем. Л.: Машиностроение. 1979.
  24. Д. Оценка производительности вычислительных систем. М.: Мир. 1981.
  25. В.Г., Аладышев В. П., Винниченко А. И. Анализ производительности мультипрограммных ЭВМ. М.: Финансы и статистика. 1984.
  26. В.В. Сравнительный анализ оценок производительности различных ЭВМ. // Вопросы радилэлектроники. Серия ЭВТ. 1977. Вып. 5.
  27. Г. Т. Развитие методов оценки производительности ВС. В кн.: Тезисы Всесоюзного совещания «Высокопроизводительные вычислительные системы». М. ИПУ. 1984.
  28. Chu W.W., Leung К.К. Module replication and assisgment for real-time distributed processing system. // «Proc. IEEE». 1987. 75. N5. Pp. 547−562.
  29. Ю.М., Казанцев П. Н. Некоторые вопросы эффективности процессора с разделением вычислительных ресурсов. // Управляющие системы и машины. 1973. N2.
  30. JI. Вычислительные системы с очередями. М.: Мир. 1979.
  31. П.М., Николаев А. В. Аналитическая модель для оценки производительности МВС. // Автоматика и вычислительная техника. 1982. N4.
  32. 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.
  33. Realiability analysis of two-unit cold standby redundant system with administrative delay and no priority in repair. // «Microelectron Relaib». 1986. V26. Pp. 847−850.
  34. B.A., Додонов А. Г., Клименко В. Г. Математическое моделирование информационно-вычислительных сетей. // «Ин-т проблем моделирования в энергетике АН УССР. Препр.». 1987. N60.
  35. Н.В. Оценка и прогнозирование надежности вычислительных средств с учетом процессов контроля, диагностирования, восстановления, технического обслуживания. М.: Машиностроение. 1985. 48 с.
  36. .П., Сидоров Л. А. Модель надежности систем с комбинированным резервом времени и случайным режимом использования. Автоматика и телемеханика. 1988. N10.
  37. Л.П., Кударенко А. А., Пивоваров И. В., Тересков В. А., Тимофеев Г. С. Метод анализа одного класса систем массового обслуживания и его использования для оценки производительности МВС. // Программирование. 1986. N12.
  38. В.М. Оптимизация структуры многопроцессорной вычислительной системы. Автоматика и телемеханика. 1986. N12.9*1
  39. H.A. Анализ производительности специализированных вычислительных устройств с помощью потоковых моделей. // Рукопись деп. В ЦНИИТЭ Приборостроения. N4001-пр. 87.
  40. Э.А. Программное обеспечение параллельных процессов. М.: Наука. 1987.
  41. A.A., Недзельский Д. А. Анализ функционирования мультипроцессорных систем с перестраиваемой структурой в переменном режиме. // Управляющие системы и машины. 1984. N1.
  42. Sahner Robin A., Trivedi Kishor S. Performance and reliability analysis using directed acyclic graphs. // «IEEE trans. Software Eng». 1987. 13. N10. Pp. 1105−1114.
  43. И.М., Алиев B.M. Оптимизация структуры распределенных АСУ технологическими процессами. // Измерения, контроль, автоматизация. 1988. N1(65). С. 74−80.
  44. Reiter R. Scheduling parallel computations. // J. ACM. 1968. V.5. N14. Pp. 590−599.
  45. Д.А. Введение в теорию вычислительных систем. М.: Сов.радио. 1972. 280 с.
  46. A.A., Амбарцумян A.A., Тепляков A.B., Прейдунов Ю. В. Графовые модели комплексов взаимосвязанных работ. // Деп. ВИНИТИ. N587-B90.
  47. В.М., Амбарцумян A.A., Маргалиташвили A.A., Прейдунов Ю. В. Аналитические оценки эффективности диспетчеризации параллельных работ в многопроцессорных вычислительных системах. // Деп. ВИНИТИ. N375-B88.
  48. П.П., Прейдунов Ю. В. Оценка времени выполнения комплекса работ на параллельной вычислительной системе. // Системный анализ и информатика. Сб. Научных трудов. М.: Изд-во УДН, 1991. С. 29−41.
  49. A.A. Исследование эффективности функционирования параллельных вычислительных ресурсов на заданных комплексах взаимосвязанных работ. Канд. диссертация. М.: Ин-т проблем управления РАН, 1990.
  50. П.П., Прейдунов Ю. В. Прогнозирование выполнения сложных программных комплексов на параллельных вычислительных системах. // Автоматика и телемеханика. 1992. N12. С. 148−154.
  51. В.В., Клушин Ю. С. Прогнозирование выполнения сложных программных комплексов на параллельных компьютерах: прямое стохастическое моделирование. // Автоматика и теллемеханика. 1994. N11. С. 142−157.
  52. А.И. Асимптотический анализ неоднородной сетевой модели многопроцессорных и многотерминальных систем. // Автоматика и телемеханика. 1994. N2. С. 161−171.
  53. Богуславский Л. Б, Ляхов А. И. Методы оценки производительности многопроцессорных и многотерминальных систем. М.: Наука, 1992. 213 с.
  54. Д.С. Планирование вычислений в системах жесткого реального времени (обзор и перспективы).// Вычислительная техника. Системы. Управление. 1991. N6. С.4−51.
  55. Monitoring and debugging of distributed real-time systems. IEEE Computer Society Press, 1995. 429p.
  56. 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.
  57. Мок 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.
  58. 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.
  59. B.B., Тепляков A.B. Об эффективности временного резервирования параллельных вычислительных процессов// АиТ. 1994. № 6. С. 15 466. Natarajan S., Zhao W. Issues in Building Dynamic Real-Time Systems // IEEE Software. Sept. 1992. P. 16−21.
  60. Stancovic J., Ramamritham K. The Spring Kernel: A New Paradigm for Real-Time Operating Systems // Operating Systems Rev. July 1989. P. 54−71.
  61. Liu J.W.S. et al. Algorithms for Scheduling Imprecise Computation // Computer. May 1991. P. 58−68.
  62. 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.
  63. 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.
  64. B.B., Подшивалова И. Ю. Динамическое управление параллельными вычислительными процессами на основе статического прогнозирования их вьшолнения. // АиТ. 1997. № 5. С. 160−173.
  65. 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.
  66. В.В.Игнатущенко, И. Ю. Подшивалова. Динамическое управление надежным выполнением параллельных вычислительных процесссов для систем реального времени. // АиТ. 1999. № 6.
  67. Кук С.О., Подшивалова И. Ю. Прогнозирование вьшолнения сложных программных комплексов в условиях сбоев компонент параллельной ВС. // Тезисы докладов XL
  68. Юбилейной научной конференции Московского физико-технического института. Выпуск1. 28−29 ноября 1997 г. Долгопрудный. С. 33.
  69. И.Ю. Прогнозирование выполнения сложных программных комплексов при неисправностях в параллельных ВС. // Тезисы докладов XLI научной конференции Московского физико-технического института. Часть П. 27−28 ноября 1998 г. Долгопрудный. С. 40.
  70. Дж., Оттенштейн К., Уоррен Дж. Граф программных зависимостей и его применение в оптимизации // Сб. Векторизация программ: теория, методы, реализация. М.: Мир, 1991. С. 141—182.
  71. Э.А. Введение в теорию анализа и распараллеливания программ в процессе трансляции. М.: Наука, 1981.
  72. 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.
Заполнить форму текущей работой

Сессия? Спокойно!