Введение. Функционирование многопроцессорных вычислительных систем (МВС) предполагает координацию параллельных процессов, размещенных в различных модулях системы. Одной из стандартных форм подобной координации является барьерная синхронизация. Она обеспечивает согласование моментов завершения и запуска групп процессов в определенной точке программы, называемой барьером. Эффективная реализация данной процедуры влияет на многие характеристики МВС: производительность, наращиваемость, отказоустойчивость.
Требования к средствам синхронизации. Определим формальные требования к средствам барьерной синхронизации:
где 
– среднее время синхронизации; 
– комбинаторная гибкость средств синхронизации; 
– структурная сложность средств синхронизации (
– предельно допустимое значение).
Время определяется как средний интервал между моментом достижения барьера всеми процессами барьерной группы до момента активизации последнего из них. Поскольку полностью исключить барьеры из параллельных программ невозможно, снижение времени при разработке механизмов барьерной синхронизации носит определяющее значение для повышения производительности МВС. Особенно это характерно для систем с мелкоблочным (fine-grained) параллелизмом.
Комбинаторную гибкость средств синхронизации можно формально представить как отношение числа допустимых вариантов размещения синхронизируемых процессов в МВС к общему числу таких вариантов. Наилучшим показателем является 
, при котором допускается произвольное расположение синхронизируемых процессов. Снижение комбинаторной гибкости усложняет задачу размещения синхронизируемых процессов и вступает в противоречие со стандартами параллельного программирования (OpenMP, MPI).
Величина характеризует основные аспекты сложности средств синхронизации и может включать в себя аппаратную сложность 
, коммуникационную сложность 
, суммарное число операторов в составе системных утилит, количество передаваемых сообщений и т.п. При реализации аппаратной поддержки синхронизации для многопроцессорных систем на кристалле структурная сложность характеризуется площадью кристалла, занимаемого подсистемой синхронизации.
Помимо представленных существенными характеристиками средств барьерной синхронизации являются наращиваемость и топологическая универсальность. Наращиваемость оценивается объёмом схемных изменений в средствах синхронизации при добавлении/удалении процессорных модулей, а топологическая универсальность заключается в возможности использования средств синхронизации в МВС с различной топологией.
Классификация и анализ средств барьерной синхронизации.
Существует множество оригинальных моделей, обеспечивающих барьерную синхронизацию. Все их можно разделить на три группы: программные, аппаратные, гибридные.
Программные решения барьерной синхронизации реализуются исключительно на программном уровне с использованием различных алгоритмов взаимодействия. Данные решения, как правило, для синхронизации используют разделяемый счетчик (массив счетчиков) [1,2], программное дерево [3,4] или поэтапные алгоритмы взаимодействия [5]. Использование программных решения упрощает реализацию синхронизации, так как при этом используются стандартные программные средства МВС. Кроме этого, программные модели не зависят от топологии системы, что увеличивает их гибкость и переносимость. Однако, реализация программной синхронизации в системах, основанных на различных технологиях обмена данными или различными аппаратными особенностями, требует корректировки и/или разработки новых решений (механизм барьерной синхронизации для систем с беспроводной сетью [6], реализация барьерной синхронизации для мультипроцессоров CELL [7]). Главными недостатками программных средств является более низкая скорость работы (высокое значение ) и значительная дополнительная нагрузка на сеть передачи данных.
Гибридные средства барьерной синхронизации характеризуются модификацией сетевых маршрутизаторов МВС, управляющих передачей пакетов, путем добавления специальных аппаратных блоков, берущих на себя функции частичной обработки барьерных сообщений и/или конфигурации барьерной группы. Подавляющее большинство гибридных решений для обеспечения барьерной синхронизации модифицирует существующую коммуникационную сеть согласно виртуальной барьерной топологии (независимо от физической топологии МВС) [8, 9, 10]. При этом либо настраиваются пути передачи сообщений по фиксированным линиям связи [8, 9], либо лини связи, обеспечивающие прямое соединение участников синхронизации [10]. Данные решения используют имеющуюся протоколы передачи данных, вследствие этого их недостатком является снижение в той или иной мере пропускной способности коммуникационной сети. Время синхронизации подобных решений зависит от текущей интенсивности использования сети передачи данных. Кроме этого построение виртуального дерева увеличивает начальную задержку синхронизации.
Аппаратные решения барьерной синхронизации предполагают реализацию процедуры синхронизации на основе специализированных барьерных процессоров и/или координирующих сред с особыми протоколами взаимодействия. Для этого в большинстве случаев используются аппаратные счетчики [11] или деревья логических элементов И [12, 13]. В МВС с общей памятью довольно часто используются аппаратные контроллеры или фильтры [14, 15], подсоединяемые к подсистеме памяти и отслеживающие запросы к разделяемым счетчикам синхронизации, однако они применимы только к небольшим системам. Отдельно можно выделить решения с использование специальной логики (схемы с использованием монтажного И [16], G-line [17]). Аппаратные решения обеспечивают максимальное быстродействие (минимальное значение ), однако характеризуются рядом недостатков. Централизованные устройства [11] нарушают однородность системы, усложняя ее наращивание и негативно сказываясь на отказоустойчивости. Невысокая комбинаторная гибкость многих решений [12, 16, 17] усложняет задачу планирования процессов и противоречит стандартам параллельного программирования. Введение большого числа дополнительных физических линий связи между процессорами [16], увеличивает суммарную площадь соединений и задержку распространения сигнала на кристалле СБИС (большое значение ). Кроме того, многие известные аппаратные процедуры синхронизации привязаны к конкретной топологии МВС [14 - 17], что ограничивает область их применения.
Заключение. В работе сформулированы требования к средствам барьерной синхронизации, приведена их классификация. В ходе анализа выявлены достоинства и недостатки существующих программных, аппаратных и гибридных решений. Программные средства барьерной синхронизации, обладая высокой гибкостью и простотой реализации, являются наиболее медленными. Повысить быстродействие возможно путем аппаратной поддержки процедур синхронизации. Добавление аппаратных блоков в сетевые маршрутизаторы позволяет увеличить скорость синхронизации, однако оказывает значительное влияние на пропускную способность сети передачи данных. Аппаратные процессоры и сети барьерной синхронизации обеспечивают максимальное быстродействие, позволяя значительно повысить производительность МВС. При этом недостатки, характерные для большинства аппаратных решений, ограничивают круг их применения.
Литература:
1. Патент №7512951B1 США, МКИ 7 G06F9/46. Barrier synchronization object for multi-threaded application / R. Marejca (США). – №10/641172; заявлено 14.08.03; опубл. 31.03.09. – 13 c.
2. Патент №2005/0050374 A1 США, МКИ 7 G06F 12/00. Method for synchronizing processors in a multiprocessors system / T. Nakamura, N. Sukegawa (Япония). – №10/894064; заявлено 20.07.2004; опубл. 03.03.2005. – 14 c.
3. Tzeng, N.-F. Distributed Shared Memory Systems with Improved Barrier Synchronization and Data Transfer [Текст] / N.-F. Tzeng, A. Kongmunvattana // Proceedings of the 11th international conference on Supercomputing, Vienna, Austria. P. 148 – 155. 1997. Publisher: ACM New York, NY, USA.
4. Mamidala, A.R. Efficient barrier and allreduce on InfiniBand clusters using hardware multicast and adaptive algorithms [Текст] / A.R. Mamidala, J. Liu, D.K. Panda // Proceedings of the 2004 IEEE International Conference on Cluster Computing, 2004. P. 135 – 144.
5. Эндрюс, Г.Р. Основы многопоточного, параллельного и распределенного программирования.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 512 с.
6. Tzeng, N.-F. Efficient Barrier Synchronization on Wireless Computing Systems [Текст] / N.-F. Tzeng, B. Kasula, H. Wu // 11th International Conference on Parallel and Distributed Systems (ICPADS'05), July 2005. Vol. 1. P. 782 – 788.
7. Bai, S. Barrier Synchronization for CELL Multi-Processor Architecture [Текст] / S. Bai, Q. Zhou, R. Zhou, L. Li // Ubi-Media Computing, Lanzhou, July 31 2008-Aug. 1 2008. P. 155 – 158.
8. Патент №5721921 США, МКИ 6 G06F13/38, 15/16. Barrier and eureka synchronization architecture for multiprocessors / R.E. Kessler, S.M. Oberlin, G.M. Thorson (США). – №450251; заявлено 25.05.95; опубл. 24.02.98. – 37 c.
9. Патент №6085303 США, МКИ 7 G06F15/16. Serialized race-free virtual barrier network / G.Thorson, R.S.Passint, S.L.Scott (США). – №972010; заявлено 17.11.97; опубл. 04.07.2000. – 22 c.
10. Sartori, J. Low-overhead, high-speed multi-core barrier synchronization [Текст] / J. Sartori, R. Kumar // High Performance Embedded Architectures and Compilers, Lecture Notes in Computer Science, 2010. Vol. #5952. P. 18-34.
11. Патент №6216174 B1 США, МКИ 7 G06F15/80. System and method for fast barrier synchronization / S.L. Scott, R.E. Kessler (США). – №09/162673; заявлено 29.09.98; опубл. 10.04.2001. – 10 c.
12. Патент №5434995 США, МКИ 6 G06F15/16, 15/80. Barrier synchronization for distributed memory massively parallel processing systems / S.M.Oberlin, E.C.Fromm (США). – №165265; заявлено 10.12.93; опубл. 18.07.95. – 25 c.
13. Патент №7444385 США, МКИ 7 G06F15/16. Global interrupt and burrier network / M.A. Blumrich, D. Chen, P.W. Coteus и др. (США). – №10/468997; заявлено 25.02.02; опубл. 28.10.08. – 10 c.
14. Sampson, J. Fast synchronization for chip multiprocessors [Текст] / J.Sampson, R.González, J.-F.Collard [et al] // SIGARCH Computer Architecture News. 2005. Vol.33, №4. P. 64-69.
15. Monchiero, M. Efficient synchronization for embedded on-chip multiprocessors / M. Monchiero, G. Palermo, C. Silvano, O. Villa // IEEE Transactions on very large scale integration (VLSI) systems, October 2006. Vol. 14, №10. – P. 1049-1062.
16. Delgado M., Kofuji S. A distributed barrier synchronization solution in hardware for 2D-mesh multicomputers // Proc. 3rd Intl Conf. High Performance Computing, Dec. 19-22 1996. IEEE: 1996. P. 368-373.
17. Abellan, J.L. Efficient and scalable barrier synchronization for many-core CMPs [Текст] / J.L. Abellan, J. Fernandez, M.E. Acacio // Proceedings of the 7th ACM international conference on Computing frontiers, Bertinoro, Italy, 2010. – P. 73-74.
