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

• Рыбин, Сергей Владимирович
• кандидат технических наук
• 2000

Оглавление диссертации кандидат технических наук Рыбин, Сергей Владимирович

Введение.

Глава 1. Обзор предметной области.

1.1. Обзор литературных источников.

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

1.2.1. Конвейерная и векторная обработка.

1.2.2. Машины типа SIMD.

1.2.3. Машины типа MIMD.

1.2.4. Многопроцессорные машины с SIMD-процессорами.

1.2.5. Современные тенденции использования архитектур многопроцессорных систем.

1.3. Процессоры и процессорные элементы в МПВС.

1.4. Организация взаимодействия процессоров в МПВС.

1.4.1. Механизм передачи сообщений.

1.4.2. Общее поле памяти.

1.5. Аппаратные средства взаимодействия.

1.5.1. Электронные интерфейсы.

1.5.2. Оптические интерфейсы.

1.6. Организация памяти в МПВС.

1.6.1. Модели связи и архитектуры памяти.

1.6.2. Механизм обмена.

1.6.3. Мультипроцессорная когерентность кэш-памяти.

1.7. Моделирование многопроцессорных вычислительных систем.

1.7.1. Модели вычислительных систем.

1.7.2. Модели нагрузок.

1.8. Определение объектов исследования.

1.9. Класс решаемых задач.

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

1.11 .Выводы по главе 1.

Глава 2. Разработка математической модели МПВС.

2.1. Концептуальное описание МПВС.

2.2. Модель процессорного модуля.

2.3. Модель коммуникационного слоя.

2.3.1. Топология «Кольцо».

2.3.2. Топология d-мерный тор.

2.3.3. Топология «Звезда».

2.3.4. Протокол взаимодействия.

2.3.5. Сравнительный анализ топологий.

2.4. Структура подсистемы памяти.

2.5. Математическая модель вычислительной задачи.

2.5.1. Описание вычислительной задачи.

2.5.2. Объёмы информации и интенсивности информационных потоков.

2.5.3. Формулировка математической модели вычислительной задачи.

2.6. Выводы по главе 2.

Глава 3. Построение программно-аналитической модели МПВС.

3.1. Постановка задачи построения программно-аналитической модели МПВС.

3.2. Структура модели.

3.3. Модель подсистемы памяти.

3.3.1. Описание изменений состояний памяти.

3.4. Модель устройств ввода-вывода МПВС.

3.5. Модель задания.

3.5.1. Схема задания.

3.5.2. Классы заданий.

3.6. Модель коммуникационного слоя.

3.7. Выводы по главе 3.

Глава 4. Постановка модельного эксперимента.

4.1. Постановка задачи модельного эксперимента.

4.2. Проведение модельного эксперимента.

4.2.1. Моделирование четырёхуровневой архитектуры памяти.

4.2.2. Моделирование трёхуровневой архитектуры памяти.

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

4.4. Методика построения и анализа архитектуры МПВС.

4.4.1. Назначение и область применения методики.

4.4.2. Порядок применения методики.

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

4.5. Выводы по главе 4.

Выводы.

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

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

В работе формулируются вероятностные математические модели взаимодействия процессорных элементов для высокоскоростной сети различной топологии, как-то: «Кольцо», «d-мерный тор» и «Звезда» с коммутатором. По архитектуре памяти, рассматриваемые вычислительные системы относятся к DSM системам.

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

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

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

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Рыбин, Сергей Владимирович

Работа определяет процесс построения архитектур многопроцессорных вычислительных систем, взаимодействие компонентов которых происходит по средством высокоскоростной оптической сети.По результатам анализа предметной области выбраны направления науч ных исследований в рамках достижения цели настоящей работы. Для задач по строения МПВС это - архитектура MIMD, по классификации Флина, использо вание микропроцессоров при построении ПЭ, организация памяти в DSM архи тектуре и использование оптических интерфейсов для расширения полосы про пускания межпроцессорных каналов связи. Для задач анализа МПВС - это ве роятностные аналитические математические модели вычислительных систем.В работе вводится понятие коммуникационного слоя, как интерфейса для взаимодействия ПЭ. Использование понятия коммуникационного слоя позволя ет выделить ресурсы вычислительной системы, используемые для взаимодей ствия ПЭ и исследовать МПВС с этой точки зрения.Разработана распределённая, автоматически управляемая четырёхуровне вая иерархическая память и алгоритм её работы с использованием механизмов страничной организации и виртуальной памяти. Предложенный способ объеди нения распределённой памяти является одним из существенных элементов на учной новизны работы и позволяет упростить аппаратную поддержку органи зации DSM архитектуры за счёт встроенной функциональности микропроцес соров и сервисов операционной системы.Для получения характеристик производительности МПВС сформулирова ны математические модели ПЭ, коммуникационного слоя для топологий типа «Кольцо», «d-мерный тор» и «Звезда» и многопроцессорной вычислительной системы в целом. Определён порядок формулирования и определения ММ вы числительных нагрузок. Модели являются главным теоретическим аппаратом, лежащим в основе задачи исследования.В силу невозможности полного аналитического решения уравнений, опи сывающих модели МПВС и её нагрузки, построена программно-аналитическая модель МПВС с аналитическим описанием больших фрагментов, на основании разработанной концептуальной модели. Для этого при разработке модели был создан модифицированный метод численного расчёта для задач оценки эффек тивности программ, содержащих вероятностные схемы с повторяющимися процессами. Метод позволяет эффективно решать ряд матричных дифференци альных уравнений. Характеристики метода исследованы на матрицах размерно сти порядка 10 . Возможности метода существенно шире области его примене ния в рамках данной работы и могут быть использованы для работы с широким спектром алгоритмов и случайных процессов.Моделирование проводилось для процесса решения задачи управления войсками в условиях ведения боевых действий в крупном населённом пункте.Для этого были разработаны соответствующие математическая модель и мо дель задания. Результаты моделирования показывают рост производительности подсистемы памяти при использовании разработанной архитектуры памяти по сравнению с существующими. Этот рост быстродействия вызван наличием бы строго слоя памяти коммуникационных адаптеров, размещение коммуникаци онного адаптера на локальной шине процессора, в отличие от стандартного се тевого адаптера на системной шине и, наконец, алгоритмом объединения про цессорных модулей, осуществляемых на разных уровнях памяти.В конце работы показан порядок практического применения полученной методики построения и анализа архитектуры МПВС. Таким образом, работа содержит анализ предметной области, постановку задачи исследования, синтез математических и программно-аналитической мо делей, а также практическое применение результатов анализа и синтеза в виде методики построения и анализа архитектуры МПВС.

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

1. Основы теории управления войсками / Под ред. П.К.Алтухова.-М.: Воениздат, 1984.-221 с.

2. Амосов А.А., Дубинский Ю.А., Копчёнова Н.В. Вычислительные методы для инженеров.-М.:Высшая школа, 1994. - 544 с.

3. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численые методы.- М.:Наука, Гл. Ред. Физ.-мат. лит., 1987. - 600 с.

4. Исследование операций: В 2 т. / Р.Браун, Р.Мэзон, Э.Фламгольц и др., Пер. с англ.: Под ред. Дж. Моудера, Элмаграби.-М.:Мир, 1981. -Т. 1.-677 с.

5. Воеводин В.В., Математические основы параллельных вычислений.-М.: Издательство МГУ, 1991. - 345 с.

6. Воеводин В.В., Капитонова А.П. Методы описания и классификации архитектур вычислительных систем.-М.:Изд-во Моск. ун-та, 1994.-73 с.

7. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. - М.:Наука, Гл. Ред. Физ.-мат. Лит., 1984. - 320 с.

8. Вентцель Е.С. Теория вероятностей. - М.:Наука, 1969. - 576 с.

9. Гантмахер Ф.Р. Теория матриц. - М.:Наука, Гл. Ред. Физ.-мат. лит., 1988.-552 с. Ю.Грин Д., Кнут Д. Математические методы анализа алгоритмов. -М.:Мир, 1987.-119С.

10. ГГудман С, Хидетниеми Введение в разработку и анализ алгоритмов. -М.:Мир, 1981.-368

11. Дал У., Дейкстра Э., Хоар К. Структурное программирование. - М.:Мир, 1975.-247С.

12. Иванов Д.А., Савельев В.П., Шеманский П.В. Основы управления войсками в бою. - М.:Воениздат, 1977. - 389 с. М.Каханер Д., Моулер К., Нэш Численные методы и математическое обеспечение : Пер. с англ. - М.:Мир, 1998. - 575 с.

13. Управление войсками: Учебное пособие для вузов. - М.:ВВА, 1991. - 250 с.

14. Клейнрок Л. Теория массового обслуживания. - М.: Машиностроение, 1979.-432 с. П.Колмогоров А.Н. Теория информации и теория алгоритмов. - М.: Наука, 1987.-304 с.

15. Кнут Д.Э. Искусство программирования для ЭВМ: В 2 т. - М.Мир, 1976.-Т. 1.-734 с.

16. Ланкастер П. Теория матриц : Пер. с англ. - М.:Наука, Гл. Ред. Физ.- мат. лит., 1982. - 272 с.

17. Локуциевский О.В., Гавриков М.Б. Начала численного анализа. - М.:ТООЯнус, 1995.-581 с.

18. Основы теории вычислительных систем / Под ред. А.Майорова - М.:Высшая школа, 1978. - 408 с.

19. Майзер X., Эйджин Н., Тролл Р. Исследование операций: В 2 т. : Пер. с англ. / Под ред. Дж.Моудера, Элмаграби. - М.:Мир, 1981. - Т. 1. -712 с.

20. Марков А.А. Вероятностные оценки эффективности исполнения рекурсивных профамм // Вестник МГТУ. Приборостроение. -1996. - № 2. -С. 86-92.

21. Марков А.А. Повторяющиеся, параллельные и перекрёстные процессы в задачах оценки эффективности исполнения программ // Вестник МГТУ. Приборостроение. - 1997. - № 2. - 93-112.

22. Марков А.А. Вычислительные особенности и алгоритмическая сложность задач оценки эффективности исполнения повторяющихся процессов // Информационные технологии. - 1997. - Вып. 8. - 6-16.

23. Марков А.А. Моделирование информационно-вычислительных процессов. - М.:Изд-во МГТУ им. Н.Э.Баумана, 1999. - 358 с.

24. Мескон М.Х., Альберт М., Хедоури Ф. Основы менеджмента : Пер. с англ. - М.:Дело ЛТД, 1995. - 704 с.

25. Парлетт Б, Симметричная проблема собственных значений. Численные методы : Пер. с англ., - М.:Мир, 1983. - 384 с.

26. Рыбин СВ. Коммуникация интеллектуальных объектов в информационных системах с помощью ограниченного естественного языка // Ком-пьюЛог. - 1998. - № 2. - 47-55.

27. Тихонов В.И., Миронов М.А. Марковские процессы. - М.: Советское радио, 1977.-488 с.

28. Трауб Дж., Вожьняковский X. Общая теория оптимальных алгоритмов : Пер. с англ. - М.: Мир, 1983. - 382 с.

29. Уолрэнд Дж. Введение в теорию сетей массового обслуживания : Пер. с англ. - М.: Мир, 1993. - 336 с.

30. Феррари. Д. Оценка производительности вычислительных систем : Пер. с англ. - М.: Мир, 1981. - 576 с.

31. Хемминг Р.В. Численные методы для научных работников и инженеров : Пер. с англ. - М.: Наука, 1972. - 400 с.

32. Хорн Р., Джонсон Ч. Матричный анализ : Пер. с англ. - М.: Мир, 1989.-655 с.

33. Шнитман В. Современные высокопроизводительные компьютеры. -М.: Издательство МГУ, 1996. - 120 с.

34. Шоу А. Логическое проектирование операционных систем : Пер. с англ.-М.: Мир, 1981.-360 с.

35. CCITT. Recommendation G.957: Optical interfaces for equipments and systems relating to the synchronous digital hierarchy. - Geneva, 1990. - 29 p.

36. CCITT. Recommendation G.958: Digital line systems based on the synchronous digital hierarchy for use on optical fiber cables. - Geneva, 1990. - 23 p.

37. Gheith Ali Abandah. Tools for Characterization Distributed Shared Memory Applications // Computer System Laboratory, HP Laboratories. - 1996. -ReportHPL-96-157.-26p.

38. Gheith Ali Abandah. Characterizing Shared-Memory Applications: A Case Study of the NAS Parallel Benchmarks // Computer System Laboratory, HP 1.aboratories. - 1997. - Report HPL-97-24. - 21 p.

39. Gheith Ali Abandah, Edward S. Davidson. Origin 2000 Design Enhancements for Communication Intensive Applications // PACT'98. - Paris, 1998.-10 p.

40. Bogineni K. Design and Performance Analysis of Optically Interconnected Parallel Computers: PhD thesis. - NY: State University of New York at Buffalo, 1993.-21 p.

41. Bogineni K., Dowd P.W. An optically interconnected distributed shared memoiy system: Architecture and performance analysis // International Journal on High Speed Computing. - 1992. -Vol. 4. - P . 179-212.

42. Brackett C.A. Dense wavelength division multiplexing networks: Principles and applications // IEEE Journal on Selected Areas of Communications, I990.-Vol. 8 . -P . 948-964.

43. Design Optimization for High-speed Per-address Two-level Branch Predictors / I-Cheng K. Chen, Chin-Chieh Lee, Matt Postiff, Trevor Mudge. -MI: University of Michigan, 1997. - 9 p.

44. Flynn M. Some Computer Organizations and Their Effectiveness // IEEE Trans. Computers, 1972. - Vol. 21, № 9. - P. 948-960.

45. Dowd P.W., Bogineni K. Performance and simulation techniques for optically interconnected distributed shared memory computer systems // Proc. International Conference on Simulation in Engineering Education. - 1992. -P. 31-35.

46. Dowd P.W., Bogineni K., Aly K.A., Perreault J. Hierarchical scalable pho tonic architectures for high-performance processor interconnection // IEEE Transactions on Computers. - 1993. - Vol.42. - P. 1105-1120.

47. Dowd P.W. Optical interconnections for computer communications // IBM Corporation. - 1989. -Tech. Rep. TR01.A961. - 56 p.

48. Dowd P.W., I-Shyan Hwang. Memory and Network Architecture Interaction in an Optically Interconnected Distributed Shared Memoiy System. -NY: State University of New York at Buffalo, 1994. - 29 p.

49. Dragone C, Edwards C, Kistler R. Integrated optics nxn multiplexer on sili con // IEEE Photonic Technology Letters. - 1991. - Vol. 3. -P. 896-899.

50. Rod Fatoohi. Performance Evaluation of Communication Networks for Dis tributed Computing // NASA Ames Research Center Moffett Field, Califor nia. - 1995. - Report NAS-95-009. - 18 p.

51. Rod Fatoohi. Performance Evaluation of Communication Software Systems for Distributed Computing // NASA Ames Research Center Moffett Field, California. - 1996. - Report NAS-96-006. - 15 p.

52. PVM: Parallel Virtual Machine - A User's Guide and Tutorial for Network Parallel Computing/ Al Geist, Adam Beguelin, Jack Dongarra and etc. -Cambridge, Massachusetts, London, England: The MIT Press, 1994. - 279 p.

53. Green P. Fiber Optic Networks. - NY: Prentice Hall, 1993. - 170 p.

54. The Performance of the Intel TFLOPS Supercomputer / Greg Henry, Pat Fay, Ben Cole and etc. // Intel Technology Journal. - 1998. - Ql. - 11 p.

55. Bruce L. Jacob, Trevor N. Mudge. A Look at Several Memory Management Units, TLB-Refill Mechanisms, and Page Table Organizations // ASPLOS. -(CA, USA). - 1998. - VIII 10/98. - 12 p.

56. Bruce L. Jacob, Trevor N. Mudge. Notes on Calculating Computer Performance // University of Michigan. - 1995. - Tech Report CSE-TR-231-95. -10 p.

57. Jacob B.L., Mudge T.N. Software-Managed Address Translation // Proc. Third Int'l Symp. High Performance Computer Architecture (HPCA-3). -1.os Alamitos (Calif.), 1997.-P. 156-167.

58. An Analytical Model for Designing Memory Hierarchies / Bruce L. Jacob, Peter M. Chen, Seth R. Silverman and etc // IEEE Transactions on computers. - 1996. - Vol. 45, № 10. - P. 100-116.

59. Kane G., Heinrich J. MIPS RISC Architecture. - Englewood Cliffs (N.J.): Prentice-Hall, 1992. - 150 p.

60. Krishnamurthy E.V. Parallel Processing Principles and Practice. - NY:Addison-Wesley Pub. Company, 1989. - 250 p.

61. James Laudon, Daniel Lenoski. The SGI Origin: A ccNUMA Highly Scalable Server. - Mountain View (California): Silicon Graphics, Inc, 1998. -l i p .

62. John H. Mathews, Numerical methods for Mathematics, Science, and Engineering: Second Edition. - Englewood Cliffs (NJ): Prentice hall Inc., 1992. -170 p.

63. John H. Mathews, Pascal Programming Guidebook for Numerical methods. - Englewood Cliffs (NJ): Prentice hall Inc., 1995. - 73 p.

64. MIPS RIOOOO Microprocessor User's Manual: Version 2.0. - Mountain View (California): MIPS Technologies Inc., 1997. - 254 p.

65. MPI: A Message-Passing Interface Standard. - Knoxvill (Tennessee): University of Tennessee, 1995. -239 p.

66. Pentium Processor User's Manual. - USA:Intel Coфoration, 1993. - 272 p.

67. Mudge T.N., Al-Sadoun H.B. A semi-markov model for the performance of multiple-bus systems // IEEE Transactions on Computers. - 1985. - Vol. C-34 . -P . 934-942.

68. MPI: The complete reference / Marc Snir, Steve Otto, Steven Huss- 1.ederman, etc. - Cambridge (Massachusetts) - London (England): The MIT Press, 1996.-350 p.

69. Andrew Sohn, Rupak Biswas. Communication Studies of DMP and SMP Machines // NASA Ames Research Center Moffett Field (California). -1997. - Report NAS-97-005. - 16 p.

70. Using MATLAB. - USA: MathWorks Inc., 1998. - 276 p.

71. Abdul Waheed, Jerry Yan. Performance Modeling and Measurement of Parallelized Code for Distributed Shared Memory Multiprocessors // NASA Ames Research Center Moffett Field (California). - 1998. - Report NAS-98-012.-22 p.