Производительность толерантной распределенной вычислительной сети с переменным числом модулей тема диссертации и автореферата по ВАК РФ 05.13.15, кандидат технических наук Чжо Ту Тхайк

• Чжо Ту Тхайк
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Чжо Ту Тхайк

Введение.

1. Распределенная вычислительная система.;.;.

1.1 Функциональная Распределенная Вычислительная Система.

1.2 Многомашинная.система.

1.3 Классификация распределенных вычислительных систем.

1.4 Требования к распределенным системам;.

1.5 Проблемы проектирования РВС.'

1.6 Модели эффективности РВС.

1.7 Постановка задачи.

1.8^ Выводыпо первой главе.

2. Производительность толерантной распределенной вычислительной^сети с переменным числом модулей:.;.:.!.:.24<

2.1\ Постановка задачи.'.

2.2 Система дифференциальных уравнений для изучения переходного процесса поведения РВС.:.

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

2:311. Точное решение:.

2.3.2. Реализация схемы определения вероятностей

2.3:3. Числовой пример:.

2.4 Приближенное решение. 46>

2.411 .Система уравнении.'.

2.4.2. Оценка эффективности приближенной модели.

2.5 Выводы по второй главе.

3. Анализ оценки производительности гетерокопийной ТРВС при выполнении двухтипных задач.

3.1 Развитие аналитической модели оценки индексов производительности . гетерокопийиой толерантной распределенной вычислительной системы ГеТРВС

3.2 Модель времени выполнения двухтипных функциональных задач в зависимости от числа ВМ ГеТРВС.

3.3 Конечно-разностное уравнение.

3.4 Переходной режим функционирования.

3.5 Стационарный режим функционирования.

3.6 Оценка производительности - среднее число задач и среднее время выполнения задач.

3.7 Экспериментальные результаты.

3.8 Выводы по третьей главе.

4. Имитационное моделирование распределенной вычислительной системы

4.1 Алгоритм моделирования.

4.2 Распечатка программы.

4.3 Анализ результатов моделирования.

4.4 Выводы по четвертой главе.

Введение диссертации (часть автореферата) на тему «Производительность толерантной распределенной вычислительной сети с переменным числом модулей»

Актуальность темы

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

Проблемами создания и оценки качества ТРВС занимались ряд российских и зарубежных исследователей: Левин В.К., Корнеев В В., Топорков В. В.', Hasan Sozer, J:, Israel Koren,, С. Mani Krishna, J.-C. Laprie и др.

Однако; ряд проблем требуют дополнительного исследования, особенно это связано» с ТРВС, в которых учитывается переменное число вычислительных модулей (ВМ) и переменное число задач рабочих и служебных.

Переменное число ВМ) обусловлено тем, ВМ может находиться в одном из трех возможных состояниях: не работоспособном, работоспособном - рабочем и работоспособном - контролируемом. Так же предполагается возможность восстановления работоспособностиВМ. Неработоспособное состояние ВМ может быть обусловлено1 не возможностью выполнения! функциональных, задач или телекоммуникационной' его недоступностью. Периоды* временной телекоммуникационной недоступности модулей являются' естественными для мобильных ТРВС, в частности, для ТРВС, образующих космические (спутниковые) группировки. В свою очередь, в* работоспособном состоянии, ВМ может выполнять рабочие и. служебные задачи. Выполнение служебных задач должно1 быть связано с обеспечением толерантности вычислительных систем.

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

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

Цель диссертационной работы

Целью диссертационной работы является оценка эффективности ТРВС при выполнении двухтипных задач с динамическим изменением- числам вычислительных модулей.

Поставленная цель определяет следующие основные задачи диссертационной работы:

1. Определение функционирования толерантной распределенной вычислительной сети с переменным числом ВМ, вычислительные модули' которой могут находиться в одном из трех возможных состояниях: работоспособном -рабочем и работоспособном - контролируемом и не работоспособном (из-за функционального отказа или телекоммуникационной не доступности) с возможностью восстановления работоспособности ВМ.

2. Разработка модели ТРВС с переменным числом ВМ.

3. Получение решения для не стационарного'и стационарного случаев поведения ТРВС с переменным числом ВМ.

4. Разработка приближенной пригодной по точности модели ТРВС с переменным числом ВМ.

5. Определение функционирования параметрической гетерокопийной (разнокопйной) толерантной распределенной вычислительной системы (ГеТРВС) при выполнении двухтипных задач, требующих для поддержания отказоустойчивости фиксированного, но произвольного, числа ВМ в соответствии с числом копий для каждого типа задач.

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

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

Методы исследования

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

Математические модели представлены в виде компьютерных программ на языке программирования MatLab ,С++ ,С# и математических расчетов в Excel.

Имитационные модели построены на основе системы моделирования GPSS.

На защиту выносятся следующие положения:

1. Аналитические модели ТРВС с переменным числом ВМ, вычислительные модули которой могут находиться в одном из трех возможных состояниях: работоспособном - рабочем и работоспособном — контролируемом и неработоспособном с возможностью восстановления работоспособности ВМ для стационарного и переходного режимов функционирования.

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

Научная новизна

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

1. На основе предложенной модели выполнена оценка эффективности распределенной^ вычислительной сети с переменным числом ВМ.

2. Получены решения« для не стационарного и стационарного случаев поведения PBG. Для не стационарного случая решение представлено- в преобразованиях. Лапласа, для не стационарного случая решение представлено1 в виде рекуррентной процедуры особенно эффективной для большого числа ВМ!.

3. Предложена приближенная модель*ТРВС с переменным .числом ВМ: На основе полученных решений, выполнена оценка точности приближенной модели, по ' отношению к точной модели. Показана пригодность по точности приближенной, модели. Скорость, вычислений по приближенной модели увеличена в.О(п/2) раз по отношению к точной модели.

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

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

6. Выполнена оценка производительности - среднее число задач и среднее время выполнения задач параметрической ГеТРВС.

Достоверность полученных в диссертационной работе результатов подтверждается:

• Корректностью использования адекватного математического аппарата;

• Достаточной апробацией материалов диссертации;

• Сравнением результатов аналитических и имитационных моделей

Практическая значимость

1. Определена эффективность ТРВС в условиях переменного числа ВМ.

2. Определена эффективность ТРВС в зависимости от параметров выполняемых задач.

Реализация результатов работы

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

Апробация работы

Основные положения и результаты диссертационного исследования докладывались автором и обсуждались: на всероссийской конференции молодых ученых и студентов «Информационные технологии в авиационной и космической технике» (Москва, 2010г.) и на 10-й Международной конференции «Авиация и космонавтика - 2011», 8-10 ноября 2011 года.

Публикации

Основные материалы диссертационной работы опубликованы в 2 печатных работах.

Структура и объем диссертации

Диссертация состоит из введения, четырёх глав, заключения, библиографического списка из 70 наименований и приложения (включающего - 2 части). Работа изложена на 137 страницах, содержит 15 таблиц и 29 рисунка.

Заключение диссертации по теме «Вычислительные машины и системы», Чжо Ту Тхайк

4.4 Выводы по четвертой главе

1. Предложена обобщенная имитационная модель параметрической ГеТРВС при выполнении двухтипных задач на основе системы моделирования ОРЗБ.

2. Рассмотрены оценки производительности параметрической ГеТРВС и время выполнения моделирования.

3. Показана согласованность результатов имитационного и аналитического моделирования - среднее число задач и среднее время выполнения задач.

Заключение

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

На основе предложенной модели выполнена оценка эффективности распределенной вычислительной сети с переменным числом ВМ.

Получены решения для, не стационарного и стационарного случаев поведения РВС. Для не стационарного случая решение представлено в преобразованиях Лапласа, для не стационарного случая решение представлено в виде рекуррентной процедуры особенно эффективной для большого числа ВМ.

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

Определено функционирование параметрической гетерокопийной ТРВС ГеТРВС при выполнении двухтипных задач.

Предложена модель оценки эффективности параметрической ГеТРВС при выполнении двухтипных задач.

Рассмотрены модель оценки переходного и стационарного режимов функционирования параметрической ГеТРВС при выполнении двухтипных задач.

Выполнена оценка производительности - среднее число задач и среднее время выполнения задач параметрической ГеТРВС.

Список литературы диссертационного исследования кандидат технических наук Чжо Ту Тхайк, 2011 год

1. Артамонов Г.Т., Брехов OlM. Аналитические вероятности модели функционирования ЭВМ.- Москва.: Энергия,1978.

2. Алтаев A.A. ;Имитационное моделирование на языке GPSS / Сост.- Улан-Удэ, Изд-во ВСГТУ, 2001. 122 с.

3. Брехов О. М. Аналитическая оценка производительности многопроцессорных вычислительных систем с динамическим изменением вычисляемых процессов. А и Т, 1995, 2, с. 141-154.

4. Брехов О. М., Наинг Лин Аунг. Модель оценки индексов производительности вычислительной, сети при выполнении разнотипных задач. //Журнал «Вестник МАИ» 2009г. Т.(16), №(3), с. 101-109.

5. Брехов О. М., Чжо Ту Тхайк. Производительность толерантной распределенной вычислительной сети, с переменным числом модулей// Журнал «Вестник МАИ»-20011г. Т.(18), №(3), с. 251-265.

6. Белов A.A., Воронцов Д.В., Дубровицкий и др. Малый космический аппарат «Астрогон Вулкан» гиперспектрального мониторинга высокого разрешения. М.: Институт проблем механики РАН, 2003. Пр-726. 34 с.

7. Белов A.A., Воронцов Д.В., Зубков Б.В. и др. Прототип распределенной бортовой вычислительной системы. М.: ИКИ РАН, 2003. Пр-2097. 26 с.

8. Белов A.A., Воронцов Д.В., Зубков Б.В. и др. Программное обеспечение прототипа распределенной бортовой вычислительной системы. М.: ИКИ ?АЩ 2003; Пр-2093. 26 с.

9. Богданов A.B., Мо Тун Тун , РАЗРАБОТКА РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ И ЗАПУСК ПРИЛОЖЕНИЙ В. ГЕТЕРОГЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СРЕДЕ XVE Всероссийская научно-методическая! конференция , Санкт-Петербург, 2009;

10. Варжапетян А. Г.;Имитационное моделирование на GPSS/H: учебное пособие / ГУАП. — СПб., 2007: — 384 с.

11. Грушин Д.А., Поспелов А.И. , Система моделирования Grid: реализация и возможности применения (ИСП РАН), Москва ,2010 .

12. Демкин В.П., Старчснко A.B. , РАСПРЕДЕЛЕННЫЕ ВЫЧИСЛЕНИЯ: ПРИНЦИПЫ И ТЕХНОЛОГИИ XVI Всероссийская научно-ме годическая конференция , Санкт-Петербург, 2009:

13. Ильин В; А., Позняк Г. Линейная алгебра: Учебник для вузов: 6-е изд., стер. - М.: ФИЗМАТЛИТ, 2004.

14. Корсуков А. С. Инструментальный комплекс для разработки и применения гетерогенных распределенных вычислительных сред.- Москва. ИДСТУ СО РАН, 2009:

15. Корнеев В .В., Семенов Д.В. Распределенный метапланировщик Грид.// вычислительные методы и программирование. 2010. Т. 11

16. Кулаков Ю.А, Русанова О.В, Шевело А.П : "Иерархический способпланирования для GRID" // УДК 683.03 .

17. Коваленко Д.В., Сидоров Д.П., Федосин С.А. , Применение распределенных вычислительных систем для факторизации больших чисел Тезисы международного семинара. "Супервычисления и математическое моделирование". - Саров, 2002, С.53-56.

18. Лебеденко Е.В., к.т.н Логинов И.В. (Академия Федеральной службы охраны

19. Российской Федерации, Орел) Оптимизация Модели Распределенной Гетерогенной Вычислительной Системы, Используемой для Планирования Обработки Запросов// Многопроцессорные вычислительные системы 2009. №3(21).

20. Леонид Бараш, , Grid Computing ~ новая парадигма Internet-вычислений -журнал (Компьютерное Обозрение) ITC.UA , 2001 .

21. Миногин А. В. Построение адаптивной математической модели восстановления распределенных вычислительных систем.-Московский физико-технический институт, 2009.

22. Матов В.И., Артамонов Г.Т., Брехов О.М.,Голубков Ю.А., Иыуду К.А., Ткачев O.A., Чугаев Б.Н., Шаповалов Ю.В. Теория проектирования вычислительных машин, систем и сетей.- Москва.:Издательство МАИ, 1999.-460с.

23. Норенков И.П. Разработка САПР.- М, МГТУ им.Баумана, 1994

24. Окольнишников Виктор Васильевич. Разработка средств распределенного имитационного моделирования для многопроцессорных вычислительных систем : диссертация. д-ра техн. наук : 05.13.18 Новосибирск, 2006 , 427 -432.

25. Павский В .А., Павский К.В.: Анализ эффективности функционирования распределённых вычислительных систем в режиме, решения задач потока с отказами // Вестник СибГУТИ. 2010. № 2

26. Погребной В.К. .-АВТОМАТИЗИРОВАННОЕ ПРОЕКТИРОВАНИЕ РАСПРЕДЕЛЁННЫХ СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ // Издательство Томского политехнического университета,2011 г.

27. Сидоров Д-П., Коваленко Д.В. Факторизация больших чисел распределенными вычислениями Материалы научной конференции "XXX Огаревские чтения" (естественные и технические науки); - Саранск: Ковылк. тип., 2001.-С.230-232.

28. Топорков- В. В. Модели распределенных вычислений. -М.:ФИЗМАТЛИТ,2004.-320 с. ISBN 5-9221-0495-0;

29. Фирсов K.M., Фазлиев А.З., Чеснокова Т.Ю., Козодоева Е.М. , Распределенная; информационно-вычислительная система «Атмосферная

30. Окольнишников Виктор Васильевич. Разработка средств распределенного имитационного моделирования для многопроцессорных вычислительных систем : диссертация. д-ра техн. наук : 05.13.18 Новосибирск, 2006 , 427 -432.

31. Павский В.А., Павский К.В.: Анализ эффективности функционирования распределённых вычислительных систем в режиме решения задач потока с отказами // Вестник СибГУТИ. 2010. № 2

32. Топорков В. В. Модели распределенных вычислений. — М.:ФИЗМАТЛИТ,2004. -320 с. ISBN 5-9221-0495-0.

33. Фирсов K.M., Фазлиев А.З., Чеснокова Т.Ю., Козодоева Е.М. , Распределенная информационно-вычислительная система «Атмосфернаярадиация»- журнал (ОПТИКА АТМОСФЕРЫИ ОКЕАНА) , 2010 -23 , 393399.

34. Хорощевский В.Г.: Распределённые системы- с программируемой структурой// Вестник СибГУТИ 2010. No.2.

35. Шрайбер Т.Д. Моделирование на GPSS. М.: Машиностроение,!980!

36. Якобовский М.В., РАСПРЕДЕЛЕННЫЕ СИСТЕМЫ' И СЕТИ МГТУ "Станкин", 2000 .

37. Ratxcore , Гарантированно защищенные распределенные системы — Киберзащита Информационная безопасность в киберпространстве, 2009 .

38. Alain Girault, Eric Rutten : Modeling Fault-tolerant Distributed1 Systems for Discrete Controller Synthesis // Electronic Notes in'Theoretical Computer Science 133 (2005) 81-100.

39. A. Chervenak, P. Foster, C. Kesselman, C. Salisbury, and S. Tuecke. The Data Grid: Towards and Architecture for the Distributed Management and Analysis of1.rge Scientific Data Sets. Journal of Network and Computer Applications, 23(3): 187-200, 2000.

40. B. Allcock, J. Bester, J. Bresnahn, A. Chervenak, I. Foster, C. Kesselman, S. Meder, V. Nefedova,D. Quesnel, and S. Tuecke. Data Management and Transfer in High-Pcrformance Computational; Grid Environments. Parallel Computing, 2002. to appear.

41. Common Information; Model, Distributed Management Task Force, Inc. http://www.dmtf.org/ standards/standarcfcim.php:

42. Enslow, P ., "What is a 'Distributed' Processing System ? " , Computer Vol . 11, ND 1, pp 13-21, 1978 .

43. European Datagrid Webpage. http://eu-datagrid.web, cern. ch.102

44. F. Berman. The Grid, Blueprint .for a New computing Infrastructure, chapter 12. Morgan Kaufmann Publishers, Inc., 1998. Edited by Ian Foster and Carl Kesselman.

45. Getting started with GPSS/H. Руководство по применению системы GPSS/H. Wolverine Software Corporation, 1998.

46. Grumbach, S.; Zhilin Wu; Distributed tree decomposition of graphs and applications .to verification // Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW), 2010 IEEE International Symposium .

47. H. Casanova, A. Legrand, D. Zagorodnov, and F. Berman. Heuristics for Scheduling Parameter Sweep Applications in Grid Environments. In Proceedings of the 9th Heterogeneous Computing Workshop (HCW'OO), pages 349-363, May 2000.

48. Hongxue XU, Hong ZHENG, Xiuying GUO ¡Modular architecture model of CSCD system //Front. Mech. Eng. China 2010, 5(4): 470-475

49. I. Foster. The Grid: A New Infrastructure for 21st Century Science. Physics Today, 55(2):42, February 2002.

50. I. Foster, C. Kesselman, J. Nick, and S. Tuecke. The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration. Available at http://www, globus, org, 2002.

51. K. Czajkowski, S. Fitzgerald, I. Foster, and C. Kesselman. Gridinformation Services for Distributed Resource Sharing. In Proceedings of the 10th IEEE International Symposium on High Performance Distributed Computing (HPDC- I O), August 2001:

52. R. Butler, D. Engert, I. Foster, C. Kesselman, and S. Tuecke. Design and Deployment of a National-Scale Authentication Infrastructure. IEEE Computers, 33(12):60-66, 2000.

53. Working Group on Grid Information) Services at the Global Grid Forum; http://www.gridf0rum.0rg/l GIS/GIS.htm.

54. Watston, R?. W., "Distributed System; Architecture Model " , Distributed Systems, ed . Eampson, B .W ., Paul; M . Siegert, H .J ., Springer-Verlag, pp 10-43,1981v.

55. Y. Chen, R. Katz, and J. Kubiatowicz. Dynamic Replica Placement for Scalable Content Delivery. In proceedings of the First International Workshop on Peer-to-Peer Systems (IPTPS 2002), March 2002.

56. Zhimin Yang, Boying Zhang, Jiangpeng Dai, Adam C. Champion- Dong Xuan and Du Li: A Distributed Mobile System for Social Networking in Physical? Proximity IEEE International: Conference on Distributed Computing Systems 2010:

57. Z. Fei. A Novel Approach to Managing Consistency in Content Distribution Networks. In Proceedings of Web Caching and Content Distribution Workshop (WCW'01), Boston, MA, June 2001.