Эффективность толерантной распределенной вычислительной системы при выполнении двухтипных задач тема диссертации и автореферата по ВАК РФ 05.13.15, кандидат технических наук Наинг Лин Аунг

• Наинг Лин Аунг
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Наинг Лин Аунг

Введение.

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

1.1. Особенности распределенных вычислительных систем.

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

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

1.4. Архитектура РВС.

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

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

1.5.2 Модель оценки производительности.

1.5.3. Интегрированная модель производительности ТРВС.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.5. Результаты моделирования.

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

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

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

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

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

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

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

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

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

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

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

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

1. Определение функционирования ТРВС при выполнении двухтипных задач.

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

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

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

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

6. Проведение имитационного моделирования ТРВС на основе системы моделирования GPSS для оценки предлагаемых решений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации

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

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

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

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

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

1. Предложена обобщенная имитационная модель РВС на основе системы моделирования GPSS.

2. Рассмотрены оценки производительности системы и время выполнения моделирования.

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

Толерантная распределенная вычислительная система (ТРВС) играет главную роль в решении многих задач.

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

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

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

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

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

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

Таким образом, в работе:

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

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

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

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

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

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

2] Хританков А.С., Посыпкин М.А. Анализ эффективности распределенных вычислительных систем при решении больших задач - Московский Физико-Технический Институт, Центр Грид-технологий и распределенных вычислений, ИСА РАН.

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

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

5] МИНОГИН А. В. Построение адаптивной математической модели восстановления распределенных вычислительных систем.-Московский физико-технический институт, 2009.

6] Брехов О. М., Ти Хан. Время выполнения апгрейда программного обеспечения БВСРВ.// Труды XVII международного научно-технического семинара. Сентябрь 2008г., Алушта. - Редакционно-издательский центр ГУАП, 2008, с. 189-190.

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

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

9] http://www.ieee.org/

10] http://www.computer.org/portal/site/ieeecs/index.jsp

11]Шрайбер Т. Дж. Моделирование на GPSS / Пер. с англ. - М.: Машиностроение, 1980. - 592 с.

12] Шенон Р. Имитационное моделирование - искусство и наука.: Пер. с англ. -М.: Мир, 1978.

13] Разработка САПР. В 10 кн. Кн. 9. Имитационное моделирование: Практ. пособие / В.М.Черненький; - М.: Высш. шк., 1990.

14] Бусленко М.П. Математическое моделирование производственных процессов на цифровых вычислительных машинах. - М.: Наука, 1964. - 364 с.

15] Моделирование сложных дискретных систем на ЭВМ третьего поколения: (Опыт применения GPSS) / Голованов О.В., Дуванов С.Г.,Смирнов В.Н. -М.:Энергия, 1978.- 160 с.

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

18]Шилдт Г., Полный справочник по С, 4-ое издание.: Пер. с англ. - М.: Издательский дом «Вильяме», 2005.

19] N. Elnozahy, D. В. Johnson, and Y.-M. Wang, "A survey of rollback-recovery protocols in message-passing systems," Technical Report CMU-CS-96-181, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, Oct. 1996.

20] Working Group on Grid Information Services at the Global Grid Forum. http://www.gridforum.org/IGIS/GIS.htm.

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

22] S.J. Pratt" The Alchemy Model: a model for homogeneous and heterogeneous distributed computing system," School of Information Science Hercantile House Hampshire Terrace Postsmouth POl 2EG U.K.

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

24] Banino, J .S ., "Architecture of the Chorus Distributed System" distributed Computing Systems : Synchronisation, Control and Communication, ed PAKER, Y, VERJUS, J-P, Academic Press, pp .251-264, 1983 . ■

25] Rashid, R .F., Robertson, G .G ., "Accent: A communication oriented network operating system kernel", AQ1 Operating Systems Review, Vo 1 15, ND 5, pp 64-75, 1981 .

26] Brownbridge, D .R., Marshall, L .F Randell, В ., "The Newcastle Connection or UNIXes of the World Unite!", Software Practice and Experience, Vol. 12, pp 1147-1162, 1982.

27] Bartlett, J ,F ., " A Nonstop Kernel " , ACM Operating Systems Review , Val. 15, ND 5, pp 22-29, 1981 .

28] Dijkstra, E .W.," The Structure of the "THE" - Multiprogramming System" , Comm . А .С .M ., Vol 11, Ns 5, pp 341-346, 1968 .

29] Liskov, В .H ., "The Design of the 4&nus Operating System", Comm . ACM . Vol 15, No 3, pp 144-149, 1972 .

30] Watston, R .W ., "Distributed System Architecture Model", Distributed Systems, ed . Lampson, В .W ., Paul, M . Siegert, H .J ., Springer-Verlag , pp 10-43, 1981 .

31] Lazowska, E .D ., et. al., "The Architecture of the EDEN System", AC M Operating Systems Review, Vol 15, No 5, pp 148-159, 1981 .

32] Blair, G .S ., et. al., "MIMAS - a network operating system for Strathnet" , 3rd International Conference on Distributed Computing Systems, Octobe r 1982.

33] Birrell, A .D ., Nelson, В J . " Implementing Remote Procedure Calls" , ACM Trans . Computer Systems, bl. 2, ND 1, pp 39-59, 1984 .

34] Szalas, A ., Szczepanska, D. "Exception handling in parallel computations" , AQ1, SIGPLAN Notices, Vol. 20, No 10, pp 95-104, 1985 .

35] Needham, R .M ., Herbert, A J . " The Cambridge Distributed Computing System " Addison-Wesley, 1982 .

36] Zjermann, H ., "OSI Reference Model - The ISO Model of Architecture for Open Systems Interconnection", IEEE Trans . Com. ., Vol. COM-28 , pp . 425-432, 1980 .

37] 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-Performance Computational Grid Environments. Parallel Computing, 2002. to appear.

38] A. Amoroso, K. Marzullo, and A. Ricciardi. Wide-Area Nile: A Case Study of a Wide-Area Data-Parallel Application. In Proceedings o] the 18th International Conference on Distributed Computing Systems (ICDCS), Amsterdam, Netherlands, pages 506-515, May 1998.

39] P. Avery and I. Foster. The GriPhyN Project: Towards Petascale Virtual Data Grids. http://www.griphyn, org, 2001.

40] P. Avery, I. Foster, R. Gardner, H. Newman, and A. Szalay. An International Virtual-Data Grid Laboratory for Data Intensive Science. http://www.griphyn, org, 2001.

41] G. Banavar, T. Chandra, B. Mukherjee, J. Nagarajarao, R. Strom, and D. Sturman. An Efficient Multicast Protocol for Content-Based Publish-Subscribe Systems. In Proceedings o.f the 19th IEEE International Conference on Distributed Computing Systems (ICDCS), 1998.

42] G. Banavar, M. Kaplan, K. Shaw, R. Strom, D. Sturman, and W. Tao. Information Flow Based Event Distribution Middleware. In Proceedings o.f the 19th IEEE International Conference on Distributed Computing Systems, Workshops on Electronic Commerce and Web-based Applications, 1999.

43] С. Baru, R. Moore, and M. Rajasekar, A. Wan. The SDSC Storage Resource Broker. In Proceedings o.f CASCON'98, Toronto, Canada, Nov. 1998.

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] F. Berman, R. Wolski, S. Figueira, J. Schopf, and G. Shao. Application Level Scheduling on Distributed Heterogeneous Networks. In Proceedings of Supercomputing'96, November 1996.

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

47] A. Carzaniga, D. Rosenblum, and A. Wolf. Challenges for Distributed Event Services: Scalability vs. Expressiveness. In Proceedings o] the ICSE'99 Workshop on Engineering Distributed Objects (EDO'99),1999.

48] A. Carzaniga, D. Rosenblum, and A. Wolf. Interfaces and Algorithms for a Wide-Area Event Notification Service. Technical Report CU-CS-888-99, Department of Computer Science, University of Colorado, Oct. 1999

49] 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.

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

51] A. Chervenak, E. Deelman, I. Foster, A. Iamnitchi, C. Kesselman, W. Hoschek, P. Kunszt, M. Ripeanu, B. Schwartzkopf, H. Stockinger, K. Stockinger, and B. Tierney. Giggle: A Framework for Constructing Scalable Replica Location Service. In Proceedings of Supercomputing'02, Nov 2002.

52] A. Chervenak, I. Foster, C. Kesselman, C. Salisbury, and S. Tuecke. The Data Grid: Towards and Architecture for the Distributed Management and Analysis of

Large Scientific Data Sets. Journal of Network and Computer Applications, 23(3):187-200, 2000.

53] Common Information Model, Distributed Management Task Force, Inc. http://www.dmtf.org/standards/standardcim.php.

54] G. Cugola, E. Di Nitto, and A. Fuggetta. Exploiting an Event-Based Infrastructure to Develop Complex Distributed Systems. In Proceedings of the 20th International Conference on Software Engineering (ICSE'98), Apr. 1998.

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

56] K. Czajkowski, I. Foster, C. Kesselman, V. Sanger, and S. Tuecke. SNAP: A Protocol for Negociating Service Level Agreements and Coordinating Resource Management in Distributed Systems. In Proceedings of the 8th Workshop on Job scheduling Strategies for Parallel Processing, July 2002.

57] The DO Experiment. http://www-d0, fnal.gov.

58] D. Dfillman, W. Hoschek, J. Jean-Martinez, A. Samar, B. Segal, H. Stockinger, and K. Stockinger.Models for Replica Synchronisation and Consistency in a Data Grid. In Proceedings of the 10th IEEE International Symposium on High Performance Distributed Computing (HPDC-IO), August 2001.

59] European Datagrid Webpage. http://eu-datagrid.web, cern. ch.

60] 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.

61] S. Fitzgerald, I. Foster, C. Kesselman, G. von Laszewski, W. Smith, and S. Tuecke. A Directory Service for Configuring High-Performance Distributed Computations. In Proceedings of the 6th IEEE International Symposium on High Performance Distributed Computing (HPDC-6), August 1997.

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

63] I. Foster and C. Kesselman, editors. The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufmann Publishers, Inc., San Francisco, USA, 1999.

64] 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.

65] I. Foster, C. Kesselman, and S. Tuecke. The Anatomy of the Grid: Enabling Scalable Virtual Organizations. International Journal of High Performance Computing Applications, 15(3), 2001.

66] I. Foster, J. VSckler, M. Wilde, and Y. Zhao. Chimera: A Virtual Data system for Representing, Querying, and Automating Data Derivation. In Proceedings of the 14th International Conference on Scientific and Statistical Database Management, Edinburgh, July 2002.

67] Брехов О. M., Наинг Лин Аунг. Оценка производительности распределенной вычислительной среды при выполнении разнотипных задач. //Труды XVII международного научно-технического семинара. Сентябрь 2008г., Алушта. -Редакционно-издательский центр ГУАП, с. 189.

68] Наинг Лин Аунг. Производительность распределенной вычислительной среды при выполнении разнотипных задач. //Всероссийская конференция молодых ученых и студентов «Информационные технологии в авиационной и космической технике-2008». 21-24 апреля 2008г.Москва. Тезисы докладов.-М. :Изд-во МАИ-ПРИНТ, 2008. - 123 с.

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

70] Globus Project, http://www.globus.org.

J. Gray, P. Helland, O. O'Neil, and D. Shasha. The Dangers of Replication and a

Solution. In Proceedings of ACM SIGMOD, pages 173-182, 1996.

О. M. Group. CORBA Services: Common Object Service Specification.

Technical report, Object Management Group, July 1998.

The Gryphon Project. http://www.research, ibm. com/gryphon.