Герт-сетевой анализ временных характеристик работы узлов распределенных систем обработки информации тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Письман, Дмитрий Михайлович

• Письман, Дмитрий Михайлович
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Письман, Дмитрий Михайлович

Введение.

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, код по ЕСПД 03524577.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. Сбор информации о вычислительных узлах системы ведет либо программное обеспечение управления системой обработки информации, либо проводится по лог-файлам истории работы узла системы. Оценку ожидаемого времени выполнения задачи при непрерывной бесперебойной работе на конкретном узле и оценку ресурсов, необходимых для выполнения вычислений, производит исследователь, исходя из внутренней структуры задачи.

Заключение

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Письман, Дмитрий Михайлович, 2006 год

1. Авербах, Л.И., Воропаев, В.И., Гельруд Я.Д. Планирование работ проекта с учетом приведенной стоимости. Электронный ресурс. / Публикации Российской Ассоциации Управления Проектами "СОВНЕТ", 2001.— Режим доступа: http://www.sovnet.ru/pages/casm5.rar

2. Аврамчук, Е.Ф., Вавилов, А.А., Емельянов, С.В. и др. Технология системного моделирования.—М.: Машиностроение; Берлин: Техник, 1988.— ISBN 5-217-00150-Х.

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-94774-175-Х. — 636 с.

6. МГУ им. М.В. Ломоносова, 2005. с. 330-336. — ISBN 5-89407-230-1. — Режим доступа: http://lvk.cs.msu.su/mco/mso2005-full.doc

7. Букатов, А.А., Дацюк, В.Н., Жегуло, А.И. Программирование многопроцессорных вычислительных систем. — Ростов-на-Дону: ЦВВР, 2003. ISBN 5-94153-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. Доррер, Г.А. Методы анализа вычислительных систем: Учеб. пособие для студентов направления 552800 и специальности 220400 всех форм обучения. — Красноярск, СибГТУ, 2000 г.

17. Зализняк, В.Е. Основы научных вычислений. Введение в численные методы для физиков: Учеб. пособие для студентов естественно-научных и технических специальностей высших учебных заведений. — М.: Едиториал УРСС, 2002. — 296 с.: ил. — ISBN 5-354-00138-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.9287628406/view.

23. Королюк, B.C., Турбин, А.Ф. Полумарковские процессы и их приложения. — Киев: Наукова думка, 1975. — 184 с.

24. Корячко, В. П., Шибанов, А. П., Шибанов, В. А. Численный метод нахождения закона распределения выходной величины GERT-сети. // Информационные технологии. 2001. № 7 — М.: Машиностроение, с. 16-21.

25. Котов В.Е. Сети Петри.— М.: Наука. Главная редакция физико-математической литературы, 1984.

26. В.А. Сойфера. Самара, 2004.С.151-159.— Режим доступа: http://www.ipsi.smr.ru/hpc-2004/tezisy.pdf

27. Ларионов, А. М., Майоров, С.А., Новиков, Г. И. Вычислительные комплексы, системы и сети. Л.: ЭНЕРГОАТОМИЗДАТ, 1987.

28. Письман Д.М. Анализ временных параметров сетевых моделей на базе модифицированной ГЕРТ-сети. // Проблемы машиностроения и автоматизации. 2006,№ I.e. 18-26.

29. Письман Д.М. Использование стохастически заданного параметра времени выполнения работ в МКП и ПЕРТ и расчет данных сетей при помощи модифицированных ГЕРТ-сетей. // Фундаментальные исследования. 2006, № 2. с. 44-45.

30. Письман Д.М. Сравнение производительности прямого и обратного алгоритмов расчета модифицированной ГЕРТ-сети. // Фундаментальные исследования. 2006, № 2. с. 45-47.

31. Письман Д.М., Слободин М.Ю. Оценка вероятности завершения расчетов задачи в условиях ограниченности времени для вычислительного кластера Condor при помощи модифицированной ГЕРТ-сети. // Современные наукоёмкие технологии. 2005, № 8. с. 30-31.

32. Письман Д.М., Шабалин С.А. Алгоритм расчета модифицированной ГЕРТ-сети. // Успехи современного естествознания. 2005, № 11. с. 36-37.

33. Письман, Д.М. Библиотека для расчета модифицированной ГЕРТ-сети. // Компьютерные учебные программы и инновации. № 6(7), 2005. с. 15.

34. Письман, Д.М. Библиотека для расчета модифицированной ГЕРТ-сети. — М.: ВНТИЦ, 2005. — № .03524577.01083-01, Per. № ОФАП 5068.

35. Предсказатель производительности DVM-программ (Предиктор). Руководство пользователя. Июнь, 2000 г. Электронный ресурс. — Режим доступа: http://www.kiam.ru/dvm/dvmhtm 1107/rus/usr/predictor/predUGr.html

36. Родин, А.В., Бурцев, В.Л. Классификации распределенных систем? Электронный ресурс. / Московский инженерно-физический институт (государственный университет). — Режим доступа: http://www.gridclub.ru/library/publication.2006-02-07.3586958006/view

37. Самарский, А.А., Гулин, А.В. Численные методы: Учеб. пособие для вузов. — М.: Наука, 1989. —432 с. — ISBN 5-02-013996-3.

38. Трохов, Н.Н. Оптимизация технологи управления опасными производствами: Автореф. диссертации на соискание ученой степени кандидата технических наук. Красноярск, НИИ СУВПТ, 2002.

39. Филлипс, Д., Гарсиа-Диас, А. Методы анализа сетей. М.: Мир, 1984.

40. Царев, Р.Ю. Семенько Т.И., Гаврилов Е.С. Модели формирования и алгоритмы распределенной обработки информации и управления : учеб. пособие. Красноярск: ИПЦ КГТУ, 2005. 240 с.

41. Шибанов, А.П. Нахождение закона распределения выходной величины GERT-сети большой размерности. // Информационные технологии. 2002. № 1 — М.: Машиностроение.

42. Шнитман, В. Современные высокопроизводительные компьютеры. Электронный ресурс. / Информационно-аналитические материалы Центра Информационных Технологий, 1996. — Режим доступа: http://www.citforum.ru/hardware/svk/contents.shtml.

43. Шпаковкий, Г.И., Серикова, Н.В., Программирование для многопроцессорных систем в стандарте MPI — Минск: БГУ, 2002.

44. Modelling and Evaluation of Computer and Communication Systems (MMB & PGTS 04 Dresden September 2004). 2004.

45. Condor Version 6.6.10 Manual / Condor Team, University of Wisconsin-Madison. — Режим доступа: http://www.cs.wisc.edu/condor/manual/v6.6/

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

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

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

49. Neumann, К. Stochastic Project Networks. Temporal Analysis, Scheduling and Cost Minimization : Lecture Notes in Economics and Mathematical Systems. Berlin : Springer-Verlag, 1990. - ISBN 3-540-52664-1.

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

51. Thompson, W.J. Computing for scientists and engineers. — NY: John Wiley & Sons, Inc., 1992. — ISBN 0-471-54718-2.

52. Yuan, Shi. Reevaluating Amdahl's Law and Gustafson's Law (ABSTRACT). Электронный ресурс. / Temple University. Computer and Information Sciences

53. Department.— Philadelphia, 1996.— Режим доступа:http://www.cis.temple.edu/~shi/docs/amdahl/amdahl.htm.

54. Процедура ОРассчитатьСеть(\Л/)

55. Выходной переметр W множество реализаций МГ-сетиначало процедуры

56. Для v1. из V, i от 1 до |V|Лг

57. Для vs1. из S, i от 1 до |S|

58. ОПостроитьРеализации (vr, vs1., iPrs, iDFs, Wt)

59. S множество стоков МГ-сетиvr узел-источник МГ-сети, iPrs, iDFs - начальные значения параметров в узле-источнике1. W = W + Wtтар.,'конец процедуры^

60. Процедура ОПостроитьРеализации(уз, vc, Prs, DFs, W).

61. Входные параметры: vs узел-источник подсети; vc - текущий узел;

62. Prs, DFs параметры узла-источника сети. Выходные параметры: W - множество графов реализации сети.начало процедуры1. W=0r-дада—►x.v = vs, x.Prs = Prs, x.DFs = DFs, W = {{x}}нет-И 2

63. Для vj. из VC.P, j от 1 до |VC.P|

64. ОПостроитьРеализации (vs, vj., Prs, DFs, Wt)1. W1 =W1 +wt1 rvd.j5 110; \ Для w1. из W1, i от 1 до |W111. X1.\ f=Vs

65. РассчитатьДугу (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о

66. Для каждого выбора w21. из W2K1. Ч.i от 1 до |vc.P| (выбор всех возможных вариантов множества w2 из множества множеств W2)

67. РассчитатьДугу (w21.T.v, vc, w2i.T.Prs, w2[i].T.DFs, Prep], DFs[i])x.v = vc

68. Расчитать параметры узла графа реализацииx.Prs и x.DFs по множеству графов {w21.} и графу wk., используя формулы (2.39), (2.40) и (2.48)vc.a = vc.a -1