Устройство и процедура барьерной синхронизации процессов в мультикомпьютерах тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат технических наук Иванов, Александр Александрович

• Иванов, Александр Александрович
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Иванов, Александр Александрович

ВВЕДЕНИЕ

1. ЗАДАЧИ СИНХРОНИЗАЦИИ В ПАРАЛЛЕЛЬНЫХ СИСТЕМАХ

1.1. Архитектура современных параллельных систем

1.2. Межпроцессорное взаимодействие в параллельных системах

1.3. Задача синхронизации и подходы к ее решению

1.4. Методы барьерной синхронизации 48 Выводы

2. ПРОЦЕДУРА БАРЬЕРНОЙ СИНХРОНИЗАЦИИ И АЛГОРИТМ 55 ВЗАИМОДЕЙСТВИЯ СИНХРОНИЗИРУЕМЫХ ПРОЦЕССОВ

2.1. Модель параллельной системы

2.2. Содержательная характеристика и формализованное 58 представление задачи обеспечения синхронизации

2.3. Характеристика процедуры синхронизации

2.4. Алгоритм взаимодействия синхронизируемых процессов

2.5. Примеры использования процедуры синхронизации

Выводы 3. УСТРОЙСТВО СИНХРОНИЗАЦИИ НА ОСНОВЕ СОЗДАННОЙ 67 ПРОЦЕДУРЫ

3.1. Функциональная организация матричной МРР-системы

3.2. Анализ работы системы при рассмотрении соответствующих 80 режимов функционирования процессоров

Выводы

4. ДОКАЗАТЕЛЬСТВО КОРРЕКТНОСТИ СОЗДАННОЙ 100 ПРОЦЕДУРЫ И ОЦЕНКА ПРЕИМУЩЕСТВ РАЗРАБОТАННОЙ ПРОЦЕДУРЫ И УСТРОЙСТВА

4.1. Представление процедуры синхронизации в виде сети Петри

4.2 Доказательство корректности процедуры синхронизации

4.3 Аналитическая оценка аппаратной сложности устройства 105 синхронизации

4.4 Аналитическая оценка созданной процедуры синхронизации

4.5 Экспериментальная оценка созданной процедуры 107 синхронизации

Ф 4.5.1. Постановка эксперимента

4.5.2. Архитектура экспериментальных программных средств

4.5.3. Результаты эксперимента

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

Актуальность работы. Одним из перспективных архитектурных подклассов параллельных вычислительных систем (ВС) являются мультикомпьютеры с распределенной памятью (МРР-системы). Отличительная особенность таких систем - разделение физической памяти между процессорами (модулями) и организация их взаимодействия через коммуникационную сеть. Примерами подобных МРР-систем являются Cray ТЗЕ и 0rigin2000.

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

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

Объект исследования — параллельные вычислительные процессы в МРР-системах с матричной топологией с незамкнутыми границами.

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

В настоящее время известно широкое разнообразие подходов к барьерной синхронизации в МРР-системах (J. R. Anderson, Т. A. Johnson, R. R. Hoare, Т. Muhammad и др.). Разработаны многочисленные варианты их реализации, как программные, так и аппаратные. При этом наиболее широко представлены решения программного уровня (Dissemination barrier, Butterfly barrier, Tree-based barriers и др.)- Аппаратные решения, обладающие значительно большим быстродействием, пока не получили широкого распространения (DBM, Cyclical Cascade Barrier, СМ-5 Barrier Control Network и др.)- Известные аппаратные решения носят, как правило, централизованный характер и не являются распределенными (DBM, Cyclical Cascade Barrier), что ограничивает возможность включения в систему новых процессоров (усложняет наращивание системы).

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

Работа выполнена при поддержке гранта Министерства образования РФ «Столетовские гранты-2003», а также в рамках совместных работ с ОКБ «Авиаавтоматика» по договору №1.121.03 от 22 августа 2003 года. Основная часть диссертационной работы выполнена в рамках плана научно-исследовательских работ Курского государственного технического университета по единому заказ-наряду Министерства образования Российской Федерации в 1998-2005 годах, утвержденному начальником управления планирования и финансирования научных исследований.

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

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

1. Сравнительный анализ существующих процедур барьерной синхронизации в МРР-системах.

2. Разработка распределенной децентрализованной аппаратно-ориентированной процедуры барьерной синхронизации.

3. Доказательство корректности разработанной процедуры на основе аппарата сетей Петри.

4. Исследование зависимости времени синхронизации от числа процессоров системы и числа синхронизируемых процессов, а также анализ аппаратной сложности устройства синхронизации.

Методы исследования. При решении поставленных задач использовались методы теории множеств, теории графов, теории вероятностей, теории проектирования ЭВМ, теории автоматов и математической статистики. Экспериментальные исследования проводились на основе библиотеки классов имитационного моделирования и визуальной среды программирования, разработанных на кафедре ВТ КурскГТУ под руководством доц. Зотова И.В.

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

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

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

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

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

1. Созданная процедура обеспечивает синхронизацию произвольного множества процессов за время порядка 1 мкс, что в 5 раз меньше, чем в лучших известных аппаратных решениях.

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

3. Упрощение наращиваемости системы (включение в МРР-систему новых процессоров и узловых блоков управления синхронизации) достигнуто за счет однотипности узловых блоков и регулярности межузловых связей.

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

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

Техническое решение устройства синхронизации в МРР-системе выполнено на уровне изобретения (патент № 2249849).

Реализация и внедрение.

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

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

Основные положения диссертационной работы докладывались и получили положительную оценку на НТК «Распознавание-2003» (г. Курск,

2003), НТК «Образование, наука, производство» (г. Белгород, 2004), НТК «КЛИН-2004» (г. Ульяновск, 2004).

Публикации.

Результаты диссертационной работы отражены в 5 публикациях, в числе которых 1 статья и 1 патент на изобретение.

На защиту выносятся:

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

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

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

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

Объем и структура работы.

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 131 страницу текста и поясняется 21 рисунком и 2 таблицами; список литературы включает 60 наименований; приложения содержат 40 страниц.

Заключение диссертации по теме «Элементы и устройства вычислительной техники и систем управления», Иванов, Александр Александрович

Выводы

1. Выявлены 2-ограниченность и живость сети Петри, что позволило доказать корректность процедуры барьерной синхронизации.

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

3. Экспериментально на имитационной модели установлено отсутствие зависимости времени организации синхронизации от числа синхронизируемых процессов. Полученные числовые значения сопоставлены с известными аналогами, в результате чего установлено 5-кратное преимущество разработанного решения.

ЗАКЛЮЧЕНИЕ

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

Получены следующие результаты:

1. Проведен анализ существующих процедур барьерной синхронизации для МРР-систем, позволивший сделать вывод о необходимости разработки распределенной децентрализованной аппаратно-ориентированной процедуры барьерной синхронизации, удовлетворяющей требованиям минимизации времени синхронизации и аппаратной сложности.

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

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

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

5. Исследована зависимость времени организации синхронизации от числа процессоров системы и числа синхронизируемых процессов. Полученные числовые значения сопоставлены с известными аналогами, в результате чего установлено 5-кратное преимущество разработанного решения.

Список литературы диссертационного исследования кандидат технических наук Иванов, Александр Александрович, 2005 год

1. Some Computer Organisations and Their Effectiveness Text. / Flynn M. // IEEE Trans. Computers. 1972. V.21. N 9. P.948-960

2. Completing an MIMD Multiprocessor Taxonomy Text. / Johnson E.E. // Computer Architecture News. 1988. V. 16. N 2. P.44-48.

3. Корхов Архитектуры и топологии многопроцессорных вычислительных систем. Электронный ресурс. / А. Богданов, В. Мареев, Е. Станкова, В. // http://www.informika.ru

4. A cluster structure as an interconnection network for large multimicrocomputer systems Text. / Wu S.B., Liu M.T. // IEEE Transactions on Computers, 1981. vol. C. 30, № 4. PP. 254-264.

5. A survey of interconnection networks Text. / Feng T.-Y. // IEEE Computer, 1981. vol.14, № 12. PP. 12-27

6. Степанян С.О. Коммуникационные сети в многопроцессорных ЭВМ Текст. // Автоматика и вычислительная техника, 1987. № 3. С. 31-43.

7. The binary tree as an interconnection network: applications of multiprocessor systems and VLSI Text. / Horowitz E., Zorat A. // IEEE Transactions on Computers, 1981. vol. C. 30, № 4. PP. 247-253.л

8. Design of HM p a hierarchical multimicroprocessor for general-purpose applications Text. / Schin K.G., Lee Y.-H., Sasidhar J. // IEEE Transactions on Computers, 1982. vol. C. 31, № 11. PP. 10451053.

9. X-tree: a tree structured multiprocessor computer architecture Text. / Despain A.M., Patterson D.A. // Proceedings of 5th Symp. on Computer Architecture, Palo Alto, Calif., 1978. PP. 144-151.

10. Design and Implementation of a Packet Switched Routing Chip Text. / Kupta P., McKeown N. // Proceedings of Hot Interconnects 6. Stanford, 1998. PP. 77-84.

11. Topological properties of hypercubes Text. / Saad Y., Schults M.U. // IEEE Transactions, 1988. vol. C. 37, № 7. PP. 867-872.

12. Электронный ресурс. //www.parallel.ru

13. Апраксин Ю.К. Алгоритмы маршрутизации для сетей с коммутацией сообщений Текст. / Апраксин Ю.К., Запевалин

14. A.А., Кирюхин В.В. // Автоматика и вычислительная техника, 1982. №2. С. 87-92.

15. Practical algorithms for online routing on fixed and reconfigurable meshes Text. / Herbordt M.C., Corbertt J.C., Weems C.C. // J. Paral. Distrib. Comput., 1994. vol.20, No.3. PP. 341-356.

16. Packet routing on grids of processors Text. / Kunde M. // Lecture Notes in Computer Science, New York: Springer-Verlag, 1998. vol.401. PP. 129-136.

17. Лукьянов А.В. Адаптивное управление маршрутизацией в коммуникационных сетях с коммутацией пакетов Текст. / Лукьянов А.В., Первозванский А.А. // Автоматика и вычислительная техника, 1983. №1. С. 60-65.

18. Шеметов В.В. Гибридные алгоритмы маршрутизации для информационно-вычислительных сетей Текст. // Автоматика и вычислительная техника, 1986. №1. С. 50-53.

19. Шеметов В.В. Децентрализованные алгоритмы маршрутизации для коммуникационных сетей с коммутацией пакетов Текст. // Автоматика и вычислительная техника, 1985. №6. С. 17-26.

20. Cray ТЗЕ Users Guide. 2-nd edition Text. / Juha Haataja, Ville Savolainen // 1998, Center for Scientific Computing, Finland

21. И.В. Зотов Организация и синтез микропрограммных мультимикроконтроллеров Текст. / И.В. Зотов, В.А. Колосков,

22. B.C. Титов, К.А. Сапронов, А.П. Волков // Курск: Изд-во «Курск», 1999. 59 с.

23. Дийкстра Э. Взаимодействие последовательных процессов Текст. // Языки программирования. М.: Мир, 1972 - С.9-86.

24. Synchronization techniques for distributed systems: an overview Text. / Mee V.J., Hura G.S. // Microelectron. Reliab. 1992. -Vol.32, No. 1/2.-PP. 175-197.

25. Synchronization with eventcounts and sequencers Text. / Reed D.P. // Commun. ACM. 1979. - Vol.22, No. 2. - PP. 115-123.

26. Simulation and Analysis of Barrier Synchronization Methods Final Report Text. / James R. Anderson // May 29, 1995 Advisor: David Lilja EE5492H Spring Quarter 1995

27. Cyclical cascade chains: a dynamic barrier synchronization mechanism for multiprocessor systems Text. / T. A. Johnson, R. R. Hoare // University of Pittsburgh, Department of Electrical Engineering Pittsburgh,PA 15261 2001

28. Hardware Barrier Synchronization For A Cluster Of Personal Computers Text. / Tariq Muhammad // Master of Science in Electrical Engineering May 1995

29. Barrier synchronization for distributed memory massively parallel processing systems Text. / Oberlin, Steven M. // US5434995: Dec. 10, 1993 24p.

30. Subset Barrier Synchronization on a Private-Memory Parallel System Text. / A. Feldmann, T. Gross, D. O'Hallaron, T. Strieker // Commun. ACM 1992.

31. Патент 2168198 Российская Федерация, МПК7 G06F9/28 Микроконтроллерная сеть / Зотов И.В. // заявл. 13.09.1999; опубл. 27.05.2001, БИ №15 21 с.

32. Харченко B.C. Декомпозиция параллельных матричных схем алгоритмов в задачах синтеза микроконтроллерных сетей Текст. / Харченко B.C., Кальченко С.Б., Сазонов А.Е. // АВТ. — 1990. — №4. — С. 81-89.

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

34. Питерсон Дж. Теория сетей Петри и моделирование систем Текст. // Пер. с англ. М.: Мир - 1984. - С. 8-14.

35. Электронный ресурс. // http://www.myri.com/

36. Советов Б.Я. Моделирование систем Текст. / Советов Б.Я., Яковлев С.А. // М.: Высшая школа, 2001. 273 с.

37. Иванов А.А. Процедура передачи сообщений в коммутаторе однородной вычислительной системы Текст. / Иванов А.А., Зотов И.В. // «Распознавание-2003»: Сборник материалов VI Международной конференции. Курск, 2003. Ч. 2 С.227-229 .

38. Иванов А.А. Децентрализованная аппаратная модель барьерной синхронизации для матричных вычислительных систем Текст. / Иванов А.А. // Образование, наука и призводство: материалы Международного студенческого форума. Белгород. 2004. С. 34.

39. Патент 2249849 Российская Федерация, МПК7 G06F15/163. Модуль для обмена сообщениями / Иванов А.А., Зотов И.В., Анпилогов Е.Г., Ефремов В.В.; заявитель и патентообладатель

40. КурскГТУ. № 2003129963/09; заявл. 08.10.2003; опубл. 10.04.2005, Бюл. №10. - Зс.

41. Zero-Cost Synchronization in a Modified BSP Model Text. / R.D. Alpert, J.F. Philbin. // Technical report, NEC Research Institute, 1997.

42. Practical Barrier Synchronization Text. / J.M.D. Hill, D.B. Skillicorn. // Technical Report PRG-TR-16-96, Oxford University Computing Laboratory, 1996.

43. Communication structures for large networks of microcomputers Text. / Wittie L.D // IEEE Transactions on Computers, 1981. vol. C.30, №4. PP. 264-273.

44. The cube-connected connected cycles: a versatile network for parallel computation Text. / Perparata P.P., Vuillemin J. // Commun. OfACM., 1981. vol. 24, №5. PP. 300-309.

45. A survey of interconnection methods for reconflgurable parallel processing systems Text. / Siegel H.J., McMillen R.J., Mueller P.T. // In: AFIPS Conf. Proc., Washington, D.C., 1979. vol.29. №2. PP. 108115.

46. Кристофидес H. Теория графов. Алгоритмический подход Текст. //М.: Мир, 1978. 432 с.

47. Корн Г. Справочник по математике для научных работником иинженеров Текст. / Корн Г., Корн Т. // М.: Наука, 1968. 720 с.

48. Степанян С.О. Коммуникационные сети в многопроцессорных ЭВМ Текст. // Автоматика и вычислительная техника, 1987. № 3. С. 31-43.

49. Communication structures for large networks of microcomputers Text. / Wittie L.D. // IEEE Transactions on Computers, 1981. vol. C. 30, №4. PP. 264-273.

50. Comparing barrier algorithms Text. / Arenstorf N., Jordan H. // Parallel Computing 12,2- 1989, 157-170.

51. The butterfly barrier Text. / Brooks E. // International Journal Parallel Programming 15,4 1987, 295-307.

52. Subset barrier synchronization: Communication models and implementation Text. / Feldmann A. //Tech. Rep. CMU-CS-92-136, School of Computer Science, Carnege Mellon University, 1992.

53. Two algorithms for barrier synchronization Text. / Yensgen D., Finkel R., Manberg U. // International Journal on Parallel Programming 17, 1 1988, 1-17.

54. Barrier MIMD architecture: Design and compilation Text. / CTKeefe M., Dietz H. // Tech. Rep. TR-EE 90-50, School of Electrical Engineering Purdue University, August 1990.

55. Two-Phase Barrier: A Synchronization Primitive for Improving the Processor Utilization Text. / I. Jung, J. Hyun, J. Lee, J. Ma // International Journal of Parallel Programming, Vol. 29, No.6, 2001.

56. Fast, Contention-Free Combining Tree Barriers Text. / M.L. Scott, J.M. Mellor-Crummey // International Journal of Parallel Programming, 22(4): 449-481, 1994.

57. Communicable Memory and Lazy Barriers for Bulk Synchronous Parallelism in BSPk Text. / A. Fahmy, A. Heddaya // Technical Report BU-CS-96-012, Boston University, 1996.

58. Questions and Answers about BSP Text. / D.B. Skillicorn, J.M.D. Hill, W.F. McColl // Technical Report PRG-TR-15-96, Oxford University Computing Laboratory, 1996.

59. Object-Oriented Aggregate Networks, doctoral thesis Text. / R. Hoare // School of Electrical and Computer Engineering. West Lafayette, IN: Purdue University, 1993.

60. Highly Parallel Computing Text. / G. Almasi, A. Gottlieb // Second Edition. Redwood City, CA: The Benjamin/Cummings Publishing Company, Inc., 1994.

61. ClusterNet: An Object-Oriented Cluster Network Text. / R. Hoare // Inetrnational Parallel and Distirbuted Processing Symposium, Workshop on Personal Computers based Networks of Workstations, Cancun, Mexico, 2000.