Барьерная синхронизация
Многие задачи можно решить с помощью итерационных алгоритмов, которые последовательно вычисляют приближения к решению и завершаются, когда получен окончательный ответ или достигнута заданная точность вычислений (как во многих численных методах). Обычно такие алгоритмы работают с массивами чисел, и на каждой итерации одни и те же действия выполняются над всеми элементами массива. Следовательно, для синхронного параллельного вычисления отдельных частей решения можно использовать параллельные процессы. Мы уже видели несколько примеров такого рода; гораздо больше их представлено в следующем разделе и дальнейших главах.
Основным свойством большинства параллельных итерационных алгоритмов является зависимость результатов каждой итерации от результатов предыдущей. Один из способов построить такой алгоритм — реализовать тело каждой итерации, используя операторы со. Если не учитывать завершимость и считать, что на каждой итерации выполняется n задач, получим такой общий вид алгоритма.
while (true) { со [i = 1 to n]
104 Часть 1. Программирование с разделяемыми переменными
код решения задачи i; ос }
К сожалению, этот подход весьма неэффективен, поскольку оператор со порождает п процессов на каждой итерации. Создать и уничтожить процессы намного дороже, чем реализовать их синхронизацию. Поэтому альтернативная структура алгоритма делает его намного эффективнее — процессы создаются один раз в начале вычислений, а потом синхронизируются в конце каждой итерации.
process Worker[i = 1 to n] { while (true) {
код решения задачи i; ожидание завершения всех п задач; } }
Точка задержки в конце каждой итерации представляет собой барьер, которого для продолжения работы должны достигнуть все процессы, поэтому этот механизм называется барьерной синхронизацией. Барьеры могут понадобиться в конце циклов, как в данном примере, или на промежуточных стадиях, как будет показано ниже.
Далее разработано несколько реализаций барьерной синхронизации, использующих различные способы взаимодействия процессов, и описано, при каких условиях лучше всего ис-• пользовать каждый тип барьера.
3.4.1. Разделяемый счетчик
Простейший способ описать требования к барьеру — использовать разделяемый целочисленный счетчик, скажем, count с нулевым начальным значением. Предположим, что есть п рабочих процессов, которые должны собраться у барьера. Когда процесс доходит до барьера, он увеличивает значение переменной count. Когда значение счетчика count станет равным n, все процессы смогут продолжить работу. Получаем следующий код.
(3.11) int count = 0;
process Worker[i = 1 to n] { while (true) {
код реализации задачи i; (count = count + 1;) (await (count == n);) } }
Оператор await можно реализовать циклом с активным ожиданием. При наличии неделимой инструкции типа fa ("извлечь и сложить"), определенной в разделе 3.3, этот барьер можно реализовать следующим образом.
FA(count,!) ;
while (count != n) skip;
Однако данный код не вполне соответствует поставленной задаче. Сложность состоит втом, что значением count должен быть 0 в начале каждой итерации, т.е. count нужно обнулять каждый раз, когда все процессы пройдут барьер. Более того, она должна иметь значение о перед тем, как любой из процессов вновь попытается ее увеличить.
Эту проблему можно решить с помощью двух счетчиков, один из которых увеличивается до n, а другой уменьшается до 0. Их роли меняются местами после каждой стадии. Однако использование разделяемых счетчиков приводит к чисто практическим трудностям. Во-первых, увели-
Глава 3. Блокировки и барьеры 105
чивать и уменьшать их значения нужно неделимым образом. Во-вторых, когда в программе (3.11) процесс приостанавливается, он непрерывно проверяет значение переменной count. В худшем случае п-1 процессов будут ожидать, пока последний процесс достигнет барьера. В результате возникнет серьезный конфликт обращения к памяти, если только программа не выполняется на мультипроцессорной машине с согласованной кэш-памятью.
Но даже в этом слу чае значение счетчика count непрерывно изменяется, и необходимо постоянно обновлять каждый кэш. Таким образом, реализация барьера с использованием счетчиков возможна, только если на целевой машине есть неделимые инструкции увеличения и согласованная кэш-память с эффективным механизмом обновления. Кроме того, число n должно быть относительно мало.
3.4.2. Флаги и управляющие процессы
Один из способов избежать конфликтов обращения к памяти — реализовать счетчик count с помощью n переменных, значения которых прибавляются к одному и тому же значению. Пусть, например, есть массив целых arrive [l:n] с нулевыми начальными значениями. Заменим операцию увеличения счетчика count в программе (3.11) присваиванием arrive [ i ] = 1. Тогда глобальным инвариантом станет такой предикат, count == (arrive[l] + ... + arrivefn])
Если элементы массива arrive хранятся в разных строках кэш-памяти (для их бесконфликтной записи процессами), то конфликтов обращения к памяти не будет.
В программе (3.11) осталось реализовать оператор await и обнулить элементы массива arrive в конце каждой итерации. Оператор await можно было бы записать в таком виде.
(await ((arrivefl] + ... + arrivetn]) == n);)
lo в таком случае снова возникают конфликты обращения к памяти, причем это решение акже неэффективно, поскольку сумму элементов arrive [ i ] теперь постоянно вычисляет каждый ожидающий процесс Worker.
Обе проблемы — конфликтов обращения к памяти и обнуления массива — можно ре-иить, используя дополнительный набор разделяемых значений и еще один процесс, Соог-Jinator. Пусть каждый процесс Worker вместо того, чтобы суммировать элементы массива irrive, ждет, пока не станет истинным единственное логическое значение. Пусть соп-:inue[l:n] — дополнительный массив целых с нулевыми начальными значениями. После того как Worker [ i ] присвоит 1 элементу arrive [ i ], он должен ждать, пока значением переменной continue [ i ] не станет 1.
(3.12) arrive [i] = 1;
(await (continueti] == 1);)
Процесс Coordinator ожидает, пока все элементы массива arrive не станут равны 1, затем присваивает значение 1 всем элементам массива continue.
(313) for [i = 1 to n] (await (arrive[i] == 1);) for [i = 1 to n] continueti] = 1;
Операторы await в (3.12) и (3.13) можно реализовать в виде циклов while, поскольку каждый из них ссылается только на одну разделяемую переменную. В процессе Coordinator для ожидания установки всех элементов arrive можно использовать оператор for. Поскольку для продолжения процессов Worker должны быть установлены все элементы arrive, процесс Coordinator может проверять их в любом порядке. Конфликтов обращения к памяти теперь не будет, поскольку процессы ожидают изменения различных переменных, каждая из которых может храниться в своей строке кэш-памяти.
106 Часть 1 Программирование с разделяемыми переменными
Переменные arrive и continue в программах (3.12) и (3.13) являются примерами так называемого флага (флажка). Его устанавливает (поднимает) один процесс, чтобы сообщить другому о выполнении условия синхронизации. Дополним программы (3.12) и (3.13) кодом, который сбрасывает флаги (присваивая им значение 0) для подготовки к следующей итерации. При этом используются два основных правила.
(3.14) Правила синхронизации с помощью флагов: а) флаг синхронизации сбрасывается только процессом, ожидающим его установки; б) флаг нельзя устанавливать до тех пор, пока не известно точно, что он сброшен.
Первое правило гарантирует, что флаг не будет сброшен, пока процесс не определит, что он установлен. В соответствии с этим правилом в (3.12) флаг continue [ i] должен сбрасываться процессом Worker [ i], а обнулять все элементы массива arrive в (3.13) должен Coordinator. В соответствии со вторым правилом один процесс не устанавливает флаг, пока он не сброшен другим. В противном случае, если другой синхронизируемый процесс в дальнейшем ожидает повторной установки флага, возможна взаимная блокировка.
В (3.13) это означает, что Coordinator должен сбросить arrive [i] перед установкой continue [i]. Coordinator может сделать это, выполнив еще один оператор for после первого for в (3.13). Coordinator может также сбросить arrive [i] сразу после того, как дождался его установки. Добавив код сброса флагов, получим барьер с управляющим (листинг 3.12).
Хотя в программе 3.12 барьерная синхронизация реализована так, что конфликты обращения к памяти исключаются, у данного решения есть два нежелательных свойства Во-первых, нужен дополнительный процесс. Синхронизация с активным ожиданием эффективна, если только каждый процесс выполняется на отдельном процессоре, так что процессу Coordinator нужен свой собственный процессор. Но, возможно, было бы лучше использовать этот процессор для другого рабочего процесса.
Второй недостаток использования управляющего процесса состоит в том, что время выполнения каждой итерации процесса Coordinator, и, следовательно, каждого экземпляра барьерной синхронизации пропорционально числу процессов Worker. В итерационных алгоритмах часто все рабочие процессы имеют идентичный код. Это значит, что если каждый
Глава 3. Блокировки и барьеры 187
рабочий процесс выполняется на отдельном процессоре, то все они подойдут к барьеру примерно в одно время. Таким образом, все флаги arrive будут установлены практически одновременно. Однако процесс Coordinator проверяет флаги в цикле, по очереди ожидая, когда каждый из них будет установлен.
Обе проблемы можно преодолеть, объединив действия управляющего и рабочих процессов так, чтобы каждый рабочий процесс был одновременно и управляющим. Организуем рабочие процессы вдерево (рис. 3.1). Сигнал о том, что процесс подошел к барьеру (флаг arrive[i]), отсылается вверх по дереву, а сигнал о разрешении продолжения выполнения (флаг continue [i])— вниз. Узел рабочего процесса ждет, когда к барьеру подойдут его сыновья, после чего сообщает родительскому узлу о том, что он тоже подошел к барьеру.
Когда все сыновья корневого узла подошли к барьеру, это значит, что все остальные рабочие узлы тоже подошли к барьеру. Тогда корневой узел может сообщить сыновьям, что они могут продолжить выполнение. Те, в свою очередь, разрешают продолжить выполнение своим сыновьям, и так далее. Специфические действия, которые должен выполнить узел каждого вида, описаны в листинге 3.13. Операторы await в данном случае можно реализовать в виде циклов активного ожидания.
Реализация, приведенная в листинге 3.13, называется барьером с объединяющим деревом, поскольку каждый процесс объединяет результаты работы своих сыновних процессов и отправляет родительскому. Этот барьер использует столько же переменных, сколько и "централизованная" версия с управляющим процессом, но он намного эффективнее при больших п, поскольку высота дерева пропорциональна Iog2n.
Объединяющее дерево можно сделать еще эффективнее, если корневой узел будет отправлять единственное сообщение, которое разрешает продолжать работу всем остальным узлам. Например, узлы могут ждать, пока корневой узел не установит флаг continue. Сбрасывать флаг continue можно двумя способами. Первый способ — применить двойную буферизацию, т.е. использовать два флага продолжения и переключаться между ними. Второй способ — изменять смысл флага продолжения, т.е. на четных циклах ждать, когда его значением станет 1, а на нечетных — 0.
108 Часть 1. Программирование с разделяемыми переменными
3.4.3. Симметричные барьеры
В барьере с объединяющим деревом процессы играют разные роли. Промежуточные узлы дерева выполняют больше действий, чем листья или корень. Кроме того, корневой узел должен ждать, пока сигналы о прибытии пройдут через все дерево. Если все процессы работают по одному алгоритму и выполняются на отдельных процессорах, то к барьеру они подойдут примерно одновременно. Таким образом, если все процессы по пути к барьеру выполняют одну и ту же последовательность действий, то они могут пройти барьер с одинаковой скоростью.
В этом разделе представлены симметричные барьеры, особенно удобные на многопроцессорных машинах с разделенной памятью и неоднородным временем доступа к памяти.
Симметричный барьер для n процессов строится из пар простых двухпроцессных барьеров. Чтобы создать двухпроцессный барьер, можно использовать метод "управляющий-рабочий", но тогда действия двух процессов будут различаться. Вместо этого можно создать полностью симметричный барьер. Пусть каждый процесс при достижении им барьера устанавливает собственный флаг. Если w [ i ] и w [ j ] — два процесса, то симметричный барьер для них реализуется следующим образом.
Последние три строки каждого процесса исполняют роли, о которых было сказано выше. Первая же строка на первый взгляд может показаться лишней, поскольку в ней задано просто ожидание сброса собственного флага процесса. Однако она необходима, чтобы не допустить ситуацию, когда процесс успеет вернуться к барьеру и установить собственный флаг до того, как другой процесс сбросит флаг на предыдущем использовании барьера. Итак, чтобы программа соответствовала правилам синхронизации флагами (3.14), необходимы все четыре строки программы.
Теперь необходимо решить вопрос, как объединить экземпляры двухпроцессных барьеров, чтобы получить барьер для п процессов. В частности, нужно построить схему связей так, чтобы каждый процесс в конце концов знал о том, что остальные процессы достигли барьера. Лучше всего для этого подойдет некоторая бинарная схема соединений, размер которой пропорционален числу Iog2n.
Пусть Worker [I :n] — массив процессов. Если n является степенью 2, то процессы можно объединить по схеме, показанной на рис. 3.2. Этот тип барьеров называется барьером-бабочкой (butterfly barrier) из-за схемы связей, аналогичной схеме соединений в преобразовании Фурье, которая похожа на бабочку. Как видно из рисунка, барьер-бабочка состоит из Iog2n уровней. На разных уровнях процесс синхронизируется с разными процессами.
На уровне s процесс синхронизируется с процессом на расстоянии 2"\ Когда каждый процесс прошел через все уровни, до барьера дошли все процессы и могут быть продолжены. Дело в том, что каждый процесс прямо или косвенно синхронизируется со всеми остальными. (Если число n не является степенью 2, то барьер-бабочку можно построить, используя наименьшую степень 2, которая больше п. Отсутствующие процессы заменяются существующими, хотя это и не очень эффективно.)
Другая схема соединений показана на рис. 3.3. Она лучше, Поскольку может быть использована при любых n (не только степенях 2). Здесь также несколько уровней, и на уровне s рабочий процесс синхронизируется с процессом на расстоянии 2*~'. На каждом двухпроцессном барьере
В реализации барьера для п процессов, независимо от используемой схемы соединений, важно избежать состояния гонок, которое может возникнуть при использовании нескольких экземпляров базового двухпроцессного барьера. Рассмотрим барьер-бабочку (см. рис. 3.2). Предположим, что есть только один массив переменных-флагов и они используются, как указано в(3.15). Пусть процесс1 приходит к первому уровню и устанавливает флаг arrive [1]. Пусть процесс 2 — медленный, и еще не достиг первого уровня, а процессы 3 и 4 дошли до первого уровня барьера, установили флаги, сбросили их друг у друга и прошли на второй уровень. На втором уровне процесс 3 должен синхронизироваться с процессом 1, поэтому он ожидает установки флага arrive [1]. Флаг уже установлен, поэтому процесс 3 сбрасывает флаг arrive [1] и переходит на уровень 3, хотя этот флаг был установлен для процесса 2. Таким образом, в результате работы сети некоторые процессы пройдут барьер раньше, чем должны, а другие будут вечно ожидать перехода на следующий уровень. Та же проблема может возникнуть и при использовании барьера с распространением (см. рис. 3.3).
Описанные ошибки синхронизации являются следствием того, что используется только один набор флагов для каждого процесса.
Для решения этой проблемы можно воспользоваться своим собственным набором флагов для каждого уровня барьера для п процессов, но лучше присваивать флагам больше значений.
Если флаги целочисленные, их можно использовать как возрастающие счетчики, которые
запоминают количество уровней барьера, пройденных каждым процессом. Начальное значе-
каждого флага— 0. Каждый раз, когда рабочий процесс i приходит на новый уровень
ьера, он увеличивает значение счетчика arrive [i]. Затем рабочий процесс i определяет
мер процесса-партнера j на текущем уровне и ожидает, пока значение arrive [ j ] не станет, как минимум, таким же, как значение arrive [ i ]. Это описывается следующим кодом.
# код барьера для рабочего процесса i for [s = 1 to num_stages] {
arrive[i] = arrive[i] + 1;
определить соседа j на уровне s
while (arrivefj] < arrive[i]) skip; }
Таким способом рабочий процесс i убеждается, что процесс j зашел, как минимум, так же далеко. Описанный подход к использованию возрастающих счетчиков и уровней позволяет избе-жагь состояния гонок, избавляет от необходимости для процесса ожидать переустановку соб-юнного флага (первая строка кода (3.15)) и переустанавливать флаг другого процесса последняя строка кода(3.15)). Таким образом, каждый уровень каждого барьера— это всего и строки кода. Единственный недостаток этого способа — счетчики все время возрастают, поэтому теоретически возможно их переполнение. Однако на практике это крайне маловероятно.
110 Часть 1. Программирование с разделяемыми переменными
Подведем итог темы барьеров. Наиболее прост и удобен для небольшого числа процессов барьер-счетчик, но при условии, что существует неделимая инструкция "извлечь и сложить". Симметричный барьер наиболее эффективен для машин с разделяемой памятью, поскольку все процессы выполняют один и тот же код, а в идеальном случае — с одинаковой скоростью. (На машинах с распределенной памятью часто более эффективным является барьер с древовидной структурой, сокращающий взаимодействие между процессами.) При любой структуре барьера основная задача — избежать состояния гонок.Это достигается с помощью либо множества флагов (по одному на каждый уровень), либо возрастающих счетчиков.
