Устройство и процедура барьерной синхронизации процессов в мультикомпьютерах
Диссертация
При построении МРР-систем особую значимость приобретает создание процедур и средств координации вычислительных процессов, параллельно протекающих в разных процессорах (параллельных процессов). Их эффективность существенно влияет на многие важные характеристики системы, включая производительность, аппаратно-программную сложность и гибкость. Проведен анализ существующих процедур барьерной… Читать ещё >
Содержание
- 1. ЗАДАЧИ СИНХРОНИЗАЦИИ В ПАРАЛЛЕЛЬНЫХ СИСТЕМАХ
- 1. 1. Архитектура современных параллельных систем
- 1. 2. Межпроцессорное взаимодействие в параллельных системах
- 1. 3. Задача синхронизации и подходы к ее решению
- 1. 4. Методы барьерной синхронизации
- Выводы
- 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. Результаты эксперимента
Список литературы
- Some Computer Organisations and Their Effectiveness Text. / Flynn M. // IEEE Trans. Computers. 1972. V.21. N 9. P.948−960
- Completing an MIMD Multiprocessor Taxonomy Text. / Johnson E.E. // Computer Architecture News. 1988. V. 16. N 2. P.44−48.
- Корхов Архитектуры и топологии многопроцессорных вычислительных систем. Электронный ресурс. / А. Богданов, В. Мареев, Е. Станкова, В. // http://www.informika.ru
- 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.
- A survey of interconnection networks Text. / Feng T.-Y. // IEEE Computer, 1981. vol.14, № 12. PP. 12−27
- Степанян С.О. Коммуникационные сети в многопроцессорных ЭВМ Текст. // Автоматика и вычислительная техника, 1987. № 3. С. 31−43.
- 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.л
- 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. 10 451 053.
- 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.
- Design and Implementation of a Packet Switched Routing Chip Text. / Kupta P., McKeown N. // Proceedings of Hot Interconnects 6. Stanford, 1998. PP. 77−84.
- Topological properties of hypercubes Text. / Saad Y., Schults M.U. // IEEE Transactions, 1988. vol. C. 37, № 7. PP. 867−872.
- Электронный ресурс. //www.parallel.ru
- Апраксин Ю.К. Алгоритмы маршрутизации для сетей с коммутацией сообщений Текст. / Апраксин Ю. К., Запевалин
- A.А., Кирюхин В. В. // Автоматика и вычислительная техника, 1982. № 2. С. 87−92.
- 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.
- Packet routing on grids of processors Text. / Kunde M. // Lecture Notes in Computer Science, New York: Springer-Verlag, 1998. vol.401. PP. 129−136.
- Лукьянов А.В. Адаптивное управление маршрутизацией в коммуникационных сетях с коммутацией пакетов Текст. / Лукьянов А. В., Первозванский А. А. // Автоматика и вычислительная техника, 1983. № 1. С. 60−65.
- Шеметов В.В. Гибридные алгоритмы маршрутизации для информационно-вычислительных сетей Текст. // Автоматика и вычислительная техника, 1986. № 1. С. 50−53.
- Шеметов В.В. Децентрализованные алгоритмы маршрутизации для коммуникационных сетей с коммутацией пакетов Текст. // Автоматика и вычислительная техника, 1985. № 6. С. 17−26.
- Cray ТЗЕ Users Guide. 2-nd edition Text. / Juha Haataja, Ville Savolainen // 1998, Center for Scientific Computing, Finland
- И.В. Зотов Организация и синтез микропрограммных мультимикроконтроллеров Текст. / И. В. Зотов, В. А. Колосков,
- B.C. Титов, К. А. Сапронов, А. П. Волков // Курск: Изд-во «Курск», 1999. 59 с.
- Дийкстра Э. Взаимодействие последовательных процессов Текст. // Языки программирования. М.: Мир, 1972 — С.9−86.
- Synchronization techniques for distributed systems: an overview Text. / Mee V.J., Hura G.S. // Microelectron. Reliab. 1992. -Vol.32, No. ½.-PP. 175−197.
- Synchronization with eventcounts and sequencers Text. / Reed D.P. // Commun. ACM. 1979. — Vol.22, No. 2. — PP. 115−123.
- Simulation and Analysis of Barrier Synchronization Methods Final Report Text. / James R. Anderson // May 29, 1995 Advisor: David Lilja EE5492H Spring Quarter 1995
- 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 15 261 2001
- Hardware Barrier Synchronization For A Cluster Of Personal Computers Text. / Tariq Muhammad // Master of Science in Electrical Engineering May 1995
- Barrier synchronization for distributed memory massively parallel processing systems Text. / Oberlin, Steven M. // US5434995: Dec. 10, 1993 24p.
- Subset Barrier Synchronization on a Private-Memory Parallel System Text. / A. Feldmann, T. Gross, D. O’Hallaron, T. Strieker // Commun. ACM 1992.
- Патент 2 168 198 Российская Федерация, МПК7 G06F9/28 Микроконтроллерная сеть / Зотов И. В. // заявл. 13.09.1999- опубл. 27.05.2001, БИ № 15 21 с.
- Харченко B.C. Декомпозиция параллельных матричных схем алгоритмов в задачах синтеза микроконтроллерных сетей Текст. / Харченко B.C., Кальченко С. Б., Сазонов А. Е. // АВТ. — 1990. — № 4. — С. 81−89.
- Питерсон Дж. Теория сетей Петри и моделирование систем Текст. // Пер. с англ. М.: Мир — 1984. — С. 8−14.
- Электронный ресурс. // http://www.myri.com/
- Советов Б.Я. Моделирование систем Текст. / Советов Б. Я., Яковлев С. А. // М.: Высшая школа, 2001. 273 с.
- Иванов А.А. Процедура передачи сообщений в коммутаторе однородной вычислительной системы Текст. / Иванов А. А., Зотов И. В. // «Распознавание-2003»: Сборник материалов VI Международной конференции. Курск, 2003. Ч. 2 С.227−229 .
- Иванов А.А. Децентрализованная аппаратная модель барьерной синхронизации для матричных вычислительных систем Текст. / Иванов А. А. // Образование, наука и призводство: материалы Международного студенческого форума. Белгород. 2004. С. 34.
- Патент 2 249 849 Российская Федерация, МПК7 G06F15/163. Модуль для обмена сообщениями / Иванов А. А., Зотов И. В., Анпилогов Е. Г., Ефремов В.В.- заявитель и патентообладатель
- КурскГТУ. № 2 003 129 963/09- заявл. 08.10.2003- опубл. 10.04.2005, Бюл. № 10. — Зс.
- Zero-Cost Synchronization in a Modified BSP Model Text. / R.D. Alpert, J.F. Philbin. // Technical report, NEC Research Institute, 1997.
- Practical Barrier Synchronization Text. / J.M.D. Hill, D.B. Skillicorn. // Technical Report PRG-TR-16−96, Oxford University Computing Laboratory, 1996.
- Communication structures for large networks of microcomputers Text. / Wittie L. D // IEEE Transactions on Computers, 1981. vol. C.30, № 4. PP. 264−273.
- 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.
- 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. 108 115.
- Кристофидес H. Теория графов. Алгоритмический подход Текст. //М.: Мир, 1978. 432 с.
- Корн Г. Справочник по математике для научных работником иинженеров Текст. / Корн Г., Корн Т. // М.: Наука, 1968. 720 с.
- Степанян С.О. Коммуникационные сети в многопроцессорных ЭВМ Текст. // Автоматика и вычислительная техника, 1987. № 3. С. 31−43.
- Communication structures for large networks of microcomputers Text. / Wittie L.D. // IEEE Transactions on Computers, 1981. vol. C. 30, № 4. PP. 264−273.
- Comparing barrier algorithms Text. / Arenstorf N., Jordan H. // Parallel Computing 12,2- 1989, 157−170.
- The butterfly barrier Text. / Brooks E. // International Journal Parallel Programming 15,4 1987, 295−307.
- Subset barrier synchronization: Communication models and implementation Text. / Feldmann A. //Tech. Rep. CMU-CS-92−136, School of Computer Science, Carnege Mellon University, 1992.
- Two algorithms for barrier synchronization Text. / Yensgen D., Finkel R., Manberg U. // International Journal on Parallel Programming 17, 1 1988, 1−17.
- 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.
- 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.
- Fast, Contention-Free Combining Tree Barriers Text. / M.L. Scott, J.M. Mellor-Crummey // International Journal of Parallel Programming, 22(4): 449−481, 1994.
- 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.
- 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.
- Object-Oriented Aggregate Networks, doctoral thesis Text. / R. Hoare // School of Electrical and Computer Engineering. West Lafayette, IN: Purdue University, 1993.
- Highly Parallel Computing Text. / G. Almasi, A. Gottlieb // Second Edition. Redwood City, CA: The Benjamin/Cummings Publishing Company, Inc., 1994.
- 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.