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

Герт-сетевой анализ временных характеристик работы узлов распределенных систем обработки информации

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

Одним из видов таких систем являются распределенные гетерогенные вычислительные отказоустойчивые системы для высокопроизводительных вычислений (системы обработки высокой пропускной способности, high throughput computing), такие как Х-СОМ, Legion или Condor. Такие системы объединяют в единую вычислительную среду распределенные гетерогенные вычислительные ресурсы, причем в качестве узлов… Читать ещё >

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

Содержание

  • 1. Различные подходы к анализу временных характеристик функционирования узлов гетерогенных систем обработки информации
    • 1. 1. Составление расписания загрузки узлов системы с использованием методов теории оптимизации
    • 1. 2. Моделирование функционирования распределенной системы обработки информации при помощи сетей Петри и их расширений
    • 1. 3. Марковские цепи и стохастические сети
    • 1. 4. Конвейерные модели
    • 1. 5. Методы разработки и адоптации программ для выполнения в распределенной системе обработки информации
    • 1. 6. Проблемы оценки временных характеристик распределенных гетерогенных систем обработки информации
      • 1. 6. 1. ГРИД (GRID)
      • 1. 6. 2. Распределенная гетерогенная система обработки информации, использующая в качестве вычислительных узлов персональные компьютеры пользователей во время простоя
    • 1. 7. Выводы
  • 2. Математическая модели стохастической ГЕРТ-сети и МГ-сети
    • 2. 1. Математическая модель ГЕРТ-сети
    • 2. 2. Математическая модель модифицированной ГЕРТ-сети
    • 2. 3. Выводы
  • 3. Алгоритмы расчета МГ-сети
    • 3. 1. Принятые обозначения
    • 3. 2. Обратный алгоритм расчета МГ-сети
    • 3. 3. Прямой алгоритм расчета МГ-сети
    • 3. 4. Численные методы, используемые для расчета и обработки результатов МГ-сети
    • 3. 5. Сравнение производительности прямого и обратного алгоритмов расчета МГ-сети
    • 3. 6. Выводы
  • 4. Анализ временных характеристик работы узлов распределенной системы обработки информации при помощи МГ-сетей с использованием среды проведения исследований MGNetwork
    • 4. 1. Среда проведения исследований MGNetwork
    • 4. 2. Анализ временных характеристик работы узлов распределенной системы обработки информации при помощи МГ-сетей
    • 4. 3. Выводы

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

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

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

Одним из видов таких систем являются распределенные гетерогенные вычислительные отказоустойчивые системы для высокопроизводительных вычислений (системы обработки высокой пропускной способности, high throughput computing), такие как Х-СОМ, Legion или Condor. Такие системы объединяют в единую вычислительную среду распределенные гетерогенные вычислительные ресурсы, причем в качестве узлов, обрабатывающих информацию, могут выступать персональные компьютеры пользователей во время простоя.

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

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

Предметом исследования являются временные характеристики работы вычислительных узлов системы обработки информации.

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

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

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

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

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

1. Модифицирован математический аппарат стохастических ГЕРТ-сетей. Полученная модификация позволяет: проводить расчет стохастической ГЕРТ-сети с использованием произвольного числа дополнительных вещественных и стохастических параметров узла стохастической ГЕРТ-сетипричем, условная вероятность выполнения исходящей дуги узла задана произвольной функцией, вычислимой в момент активации узла.

2. Разработаны прямой и обратный алгоритмы расчета модифицированных ГЕРТ-сетей. Произведено аналитическое сравнение их производительности.

3. Предложены модели модифицированной ГЕРТ-сети, позволяющие выполнять оценку времени выполнения задачи на узле распределенной гетерогенной системы обработки информации с использованием резервного копирования состояния задачи и без него.

4. Предложены рекомендации по распределению ресурсов системы обработки информации для обеспечения эффективного управления выполнением приоритетных задач.

Значение для теории. Созданная модифицированная ГЕРТ-сеть позволяет проводить оценки временных характеристик (или иных аддитивных параметров) систем, представимых в виде стохастической ГЕРТ-сети типа «работа на дуге», где продолжительность выполнения «работы» задана вещественной случайной величиной.

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

Значение для практики. Предложенные в работе процедуры анализа временных характеристик работы узлов распределенной системы обработки информации позволяют:

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

— проводить оценку производительности и доступности узлов системы, принимать решения о мерах по повышению производительности узлов системы;

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

Создана среда проведения исследований, позволяющая выполнять расчет временных характеристик модифицированных ГЕРТ-сетей с использованием прямого и обратного алгоритмов.

Достоверность полученных результатов подтверждается тестированием и оценкой результатов применения разработанной среды проведения исследований и модифицированных ГЕРТ-сетей, а также согласованностью расчетных и экспериментальных данных.

Реализация результатов работы. Разработанная среда проведения исследований и модуль расчета модифицированных ГЕРТ-сетей зарегистрированы в Отраслевом фонде алгоритмов и программ (Per. № 5068, код по ЕСПД 3 524 577.01083−01), что делает ее доступной для широкого круга специалистов по методам анализа стохастических сетей.

Созданная система расчета функции распределения случайной величины времени выполнения задачи использовалась при работе с распределенной гетерогенной системой обработки информации Condor. На защиту выносятся:

— математический аппарат модифицированных ГЕРТ-сетей;

— прямой и обратный алгоритмы расчета модифицированных ГЕРТ-сетей;

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

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

Апробация работы. Основные положения и результаты работы прошли всестороннюю апробацию на всероссийских научно-практических конференциях. В том числе на ежегодной Всероссийской III конференции «Технические науки и современное производство» (2005 г., Лутраки, Греция), Всероссийской заочной электронной конференции Российской академии естествознания «Современные телекоммуникационные и информационные технологии» (2005 г.), Всероссийской VI научной конференции «Успехи современного естествознания» (2005 г. Сочи), Всеросийской III научной конференции с международным участием «Приоритетные направления развития науки, технологий и техники» (2005 г., Хургада, Египет), Всероссийской заочной электронной конференции Российской академии естествознания «Новые информационные технологии и системы» (2005 г.).

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

4.3 Выводы.

1. Среда проведения исследований MGNetwork:

— позволяет проводить расчеты МГ-сетей, используя прямой и обратный алгоритмы МГ-сети, прямую свертку или свертку, используя БПФ;

— открытый формат XML документа, описывающий структуру сети, может быть создан в любом текстовом редакторе и позволяет в дальнейшем создать специализированное программное обеспечение визуальному построению МГ-сети- / J—з.

I/ -4.

1 i.

2 7 /.

J.

— г.

— возможность экспорта полученных результатов и их последующего анализа при помощи другого ПО;

— возможность трассировки реализаций позволяет проводить анализ результатов и поиск их причин.

2. Результаты расчета моделей выполнения задач в режимах с резервным копированием (Standard) и без него (Vanilla) распределенной гетерогенной системы обработки информации Condor, построенные при помощи МГ-сетей, согласуется с экспериментальными результатами и позволяет оценивать эффективность применения того или иного узла для выполнения какой-либо задачи. В частности, построенные модели помогают распределять задачи по срочности (или приоритетности) между узлами системы, эффективнее использовать имеющиеся узлы.

3. Сбор информации о вычислительных узлах системы ведет либо программное обеспечение управления системой обработки информации, либо проводится по лог-файлам истории работы узла системы. Оценку ожидаемого времени выполнения задачи при непрерывной бесперебойной работе на конкретном узле и оценку ресурсов, необходимых для выполнения вычислений, производит исследователь, исходя из внутренней структуры задачи.

Заключение

.

В диссертации представлен математический аппарат модифицированных ГЕРТ-сетей, предложены прямой и обратный алгоритмы их расчета, рассмотрены методы анализа временных характеристик узлов распределенной гетерогенной обработки информации, построенные на базе модифицированных ГЕРТ-сетей, и предложены подходы к обеспечению эффективной обработки информации приоритетных задач.

Дальнейшая работа может проводиться в следующих направлениях:

— ослабление ограничений, вводимых для модифицированных ГЕРТ-сетей, и создание соответствующих алгоритмов их расчета;

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

Практическим результатом работы является среда проведения исследований, позволяющая рассчитывать модифицированные ГЕРТ-сети и производить дальнейшую обработку результатов.

Показать весь текст

Список литературы

  1. , Л.И., Воропаев, В.И., Гельруд Я. Д. Планирование работ проекта с учетом приведенной стоимости. Электронный ресурс. / Публикации Российской Ассоциации Управления Проектами «СОВНЕТ», 2001.— Режим доступа: http://www.sovnet.ru/pages/casm5.rar
  2. , Е.Ф., Вавилов, А.А., Емельянов, С.В. и др. Технология системного моделирования.—М.: Машиностроение- Берлин: Техник, 1988.— ISBN 5−217−150-Х.
  3. , А.Н., Воеводин, В.В. Методика измерения основных характеристик программно-аппаратной среды. / ВВС ДВО РАН. — Режим доступа: http://www.dvo.ru/bbc/benchmarks.html
  4. Е.А., Дегтерев А. С., Ерыгин Ю.В. GERT-сетевой анализ производственных процессов Электронный ресурс. / Электронный журнал «ИССЛЕДОВАНО В РОССИИ», 2004, с. 2571−2576.— Режим доступа: http://zhurnal.ape.relarn.ru/articles/2004/240.pdf.
  5. , Н.С., Жидков, Н.П., Кобельков Г. М. Численные методы. — 3-е изд. — М.: Бином. Лаборатория знаний, 2004. — ISBN 5−94 774−175-Х. — 636 с.
  6. МГУ им. М. В. Ломоносова, 2005. с. 330−336. — ISBN 5−89 407−230−1. — Режим доступа: http://lvk.cs.msu.su/mco/mso2005-full.doc
  7. , А.А., Дацюк, В.Н., Жегуло, А. И. Программирование многопроцессорных вычислительных систем. — Ростов-на-Дону: ЦВВР, 2003. ISBN 5−94 153−062−5.
  8. Е.С. Теория вероятностей.— 8-е изд., стер.— М.: Высш. шк., 2002. — 575 с.
  9. Е.С., Овчаров Л. А. Теория вероятностей и ее инженерные приложения. Учеб. пособие для втузов. — 2-е изд., стер. — М.: Высш. шк., 2000. —480 с.
  10. , В., Филамофитский, М. Суперкомпьютер на выходные. Электронный ресурс. // Открытые системы, № 05, 2003.— Режим доступа: http://www.osp.ru/os/2003/05/043.htm
  11. , В.И., Гельруд, Я.Д. Использование ЦАСМ при управлении проектами. Электронный ресурс. / Публикации Российской Ассоциации Управления Проектами «СОВНЕТ», 2001.— Режим доступа: http://www.sovnet.ru/pages/casm4.rar
  12. , И.Н. Оптимизационные сетевые модели формирования циклических технологических процессов: Автореф. диссертации на соискание ученой степени кандидата технических наук. Красноярск, САА, 2000.
  13. А.С., Письман Д.М. GERT-сетевой анализ времени выполнения задачи на неспециализированном гетерогенном кластере. // Фундаментальные исследования. 2005, № 4. с. 79−80.
  14. А.С., Письман Д. М. Оценка времени изготовления деталей на конвейере, допускающем устранение брака в процессе производства при помощи модифицированной ГЕРТ-сети. // Современные наукоёмкие технологии. 2005, № 7. с. 87−89.
  15. , Н.Н. Многокомпонентная сетевая модель формирования алгоритмов распределенной обработки и управления в АСУ: Автореф. диссертации на соискание ученой степени кандидата технических наук. Красноярск, НИИ СУВПТ, 2004.
  16. , Г. А. Методы анализа вычислительных систем: Учеб. пособие для студентов направления 552 800 и специальности 220 400 всех форм обучения. — Красноярск, СибГТУ, 2000 г.
  17. , В.Е. Основы научных вычислений. Введение в численные методы для физиков: Учеб. пособие для студентов естественно-научных и технических специальностей высших учебных заведений. — М.: Едиториал УРСС, 2002. — 296 с.: ил. — ISBN 5−354−138−2.
  18. Р.Г. Стронгина. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2001. с. 80−83.— Режим доступа: http://www.software.unn.ac.ru/ccam/files/Seminar/Seminarl.pdf
  19. В.П., Сутягин М. В., Быстрикова В. А. Кластеризация вычислительных систем и вопросы их катастрофоустойчивости // Автоматизация и управление в машиностроении. № 18, 2002.
  20. , И.В., Письман, Д.М., Слободин, М. Ю. Модели оценки времени выполнения задачи на кластере с последовательной и параллельной архитектурой обмена данными. // Системы управления и информационные технологии. № 3 (20), 2005. с. 58−62.
  21. , И.В., Царев, Р.Ю. Моделирование и оптимизация параллельных процессов в информационно-управляющих системах: учеб. пособие. Красноярск: ИПЦ КГТУ, 2003. — 111 с.
  22. , В.Н., Корягин, Д. А. Организация ресурсов ГРИД. Электронный ресурс. — М., 2004. — Режим доступа: http://www.gridclub.ru/library/publication.2004-ll-29.9 287 628 406/view.
  23. , B.C., Турбин, А.Ф. Полумарковские процессы и их приложения. — Киев: Наукова думка, 1975. — 184 с.
  24. , В. П., Шибанов, А. П., Шибанов, В. А. Численный метод нахождения закона распределения выходной величины GERT-сети. // Информационные технологии. 2001. № 7 — М.: Машиностроение, с. 16−21.
  25. В.А. Сойфера. Самара, 2004.С.151−159.— Режим доступа: http://www.ipsi.smr.ru/hpc-2004/tezisy.pdf
  26. , А. М., Майоров, С.А., Новиков, Г. И. Вычислительные комплексы, системы и сети. Л.: ЭНЕРГОАТОМИЗДАТ, 1987.
  27. Д.М. Анализ временных параметров сетевых моделей на базе модифицированной ГЕРТ-сети. // Проблемы машиностроения и автоматизации. 2006,№ I.e. 18−26.
  28. Д.М. Использование стохастически заданного параметра времени выполнения работ в МКП и ПЕРТ и расчет данных сетей при помощи модифицированных ГЕРТ-сетей. // Фундаментальные исследования. 2006, № 2. с. 44−45.
  29. Д.М. Сравнение производительности прямого и обратного алгоритмов расчета модифицированной ГЕРТ-сети. // Фундаментальные исследования. 2006, № 2. с. 45−47.
  30. Д.М., Слободин М. Ю. Оценка вероятности завершения расчетов задачи в условиях ограниченности времени для вычислительного кластера Condor при помощи модифицированной ГЕРТ-сети. // Современные наукоёмкие технологии. 2005, № 8. с. 30−31.
  31. Д.М., Шабалин С. А. Алгоритм расчета модифицированной ГЕРТ-сети. // Успехи современного естествознания. 2005, № 11. с. 36−37.
  32. , Д.М. Библиотека для расчета модифицированной ГЕРТ-сети. // Компьютерные учебные программы и инновации. № 6(7), 2005. с. 15.
  33. , Д.М. Библиотека для расчета модифицированной ГЕРТ-сети. — М.: ВНТИЦ, 2005. — № .3 524 577.01083−01, Per. № ОФАП 5068.
  34. Предсказатель производительности DVM-программ (Предиктор). Руководство пользователя. Июнь, 2000 г. Электронный ресурс. — Режим доступа: http://www.kiam.ru/dvm/dvmhtm 1107/rus/usr/predictor/predUGr.html
  35. , А.В., Бурцев, В.Л. Классификации распределенных систем? Электронный ресурс. / Московский инженерно-физический институт (государственный университет). — Режим доступа: http://www.gridclub.ru/library/publication.2006−02−07.3 586 958 006/view
  36. , А.А., Гулин, А.В. Численные методы: Учеб. пособие для вузов. — М.: Наука, 1989. —432 с. — ISBN 5−02−13 996−3.
  37. , Н.Н. Оптимизация технологи управления опасными производствами: Автореф. диссертации на соискание ученой степени кандидата технических наук. Красноярск, НИИ СУВПТ, 2002.
  38. , Д., Гарсиа-Диас, А. Методы анализа сетей. М.: Мир, 1984.
  39. , Р. Ю. Семенько Т.И., Гаврилов Е. С. Модели формирования и алгоритмы распределенной обработки информации и управления : учеб. пособие. Красноярск: ИПЦ КГТУ, 2005. 240 с.
  40. , А.П. Нахождение закона распределения выходной величины GERT-сети большой размерности. // Информационные технологии. 2002. № 1 — М.: Машиностроение.
  41. , В. Современные высокопроизводительные компьютеры. Электронный ресурс. / Информационно-аналитические материалы Центра Информационных Технологий, 1996. — Режим доступа: http://www.citforum.ru/hardware/svk/contents.shtml.
  42. , Г. И., Серикова, Н.В., Программирование для многопроцессорных систем в стандарте MPI — Минск: БГУ, 2002.
  43. Modelling and Evaluation of Computer and Communication Systems (MMB & PGTS 04 Dresden September 2004). 2004.
  44. Condor Version 6.6.10 Manual / Condor Team, University of Wisconsin-Madison. — Режим доступа: http://www.cs.wisc.edu/condor/manual/v6.6/
  45. Foster, Ian. What is the Grid? A Three Point Checklist. Электронный ресурс. / Argonne National Laboratory & University of Chicago. July 20, 2002. — Режим доступа: http://www-fp.mcs.anl.gov/~foster/Articles/WhatIsTheGrid.pdf.
  46. German, Reinhard. Non-Markovian Analysis. Lectures on Formal Methods and Performance Analysis, First EEF/Summer School on Trends in Computer Science. Heidelberg: Springer, 2001, (LNCS Bd. 2090), S. 156−182.
  47. Litzkow, M., Livny, M., Mutka, M., Condor A Hunter of Idle Workstations, Proceedings of the 8th International Conference of Distributed Computing Systems, June 1988. — Режим доступа: http://www.cs.wisc.edu/condor/doc/icdcsl988.pdf
  48. Neumann, К. Stochastic Project Networks. Temporal Analysis, Scheduling and Cost Minimization: Lecture Notes in Economics and Mathematical Systems. Berlin: Springer-Verlag, 1990. — ISBN 3−540−52 664−1.
  49. Pfister G. Sizing Up Parallel Architectures. DataBase Programming & Design OnLine. Электронный ресурс. May 1998.— Режим доступа: http://www.dbpd.com/vault/9805feat.htm, http://www.citforum.ru/hardware/articles/art5.shtml.
  50. Thompson, W.J. Computing for scientists and engineers. — NY: John Wiley & Sons, Inc., 1992. — ISBN 0−471−54 718−2.
  51. Yuan, Shi. Reevaluating Amdahl’s Law and Gustafson’s Law (ABSTRACT). Электронный ресурс. / Temple University. Computer and Information Sciences
  52. Department.— Philadelphia, 1996.— Режим доступа: http://www.cis.temple.edu/~shi/docs/amdahl/amdahl.htm.
  53. Процедура ОРассчитатьСеть (Л/)
  54. Выходной переметр W множество реализаций МГ-сетиначало процедуры
  55. Для v1. из V, i от 1 до |V|Лг
  56. Для vs1. из S, i от 1 до |S|
  57. ОПостроитьРеализации (vr, vs1., iPrs, iDFs, Wt)
  58. S множество стоков МГ-сетиvr узел-источник МГ-сети, iPrs, iDFs — начальные значения параметров в узле-источнике1. W = W + Wtтар.,'конец процедуры^
  59. Процедура ОПостроитьРеализации (уз, vc, Prs, DFs, W).
  60. Входные параметры: vs узел-источник подсети- vc — текущий узел-
  61. Prs, DFs параметры узла-источника сети. Выходные параметры: W — множество графов реализации сети. начало процедуры1. W=0r-дада—>x.v = vs, x. Prs = Prs, x. DFs = DFs, W = {{x}}нет-И 2
  62. Для vj. из VC. P, j от 1 до |VC.P|
  63. ОПостроитьРеализации (vs, vj., Prs, DFs, Wt)1. W1 =W1 +wt1 rvd. j5 110- Для w1. из W1, i от 1 до |W111. X1. f=Vs
  64. РассчитатьДугу (w1.T.v, vs, wi.T.Prs, w[i]. T. DFs, x[i]. Prs, x[i]. DFs)1 1. W = W + M (w1., xi.) w1., iо
  65. Для каждого выбора w21. из W2K1. Ч. i от 1 до |vc.P| (выбор всех возможных вариантов множества w2 из множества множеств W2)
  66. РассчитатьДугу (w21.T.v, vc, w2i.T.Prs, w2[i]. T. DFs, Prep], DFs[i])x.v = vc
  67. Расчитать параметры узла графа реализацииx. Prs и x. DFs по множеству графов {w21.} и графу wk., используя формулы (2.39), (2.40) и (2.48)vc.a = vc. a -1
Заполнить форму текущей работой

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