Алгоритмы, параллельные по данным

В алгоритмах, параллельных по данным, несколько процессов выполняют один и тот же код и работают с разными частями разделяемых данных. Для синхронизации выполнения от­дельных фаз процессов используются барьеры. Этот тип алгоритмов теснее всего связан с синхронными мультипроцессорами, или SIMD-машинами, т.е. машинами с одним потоком инструкций и многими потоками данных (single instruction, multiple data— SIMD). В SIMD-машинах аппаратно поддерживаются мелкомодульные вычисления и барьерная синхрониза­ция. Однако алгоритмы, параллельные по данным, полезны и в асинхронных мультипроцес­сорных машинах при условии, что затраты на барьерную синхронизацию с лихвой компенси­руются высокой степенью параллелизма процессов.

В данном разделе разработаны решения, параллельные по данным, для трех задач: час­тичное суммирование массива, поиск конца связанного списка и итерационный метод Якоби для решения дифференциальных уравнений в частных производных. Они иллюстрируют ос­новные методы, используемые в алгоритмах, параллельных по данным, и барьерную синхро­низацию. В конце раздела описаны многопроцессорные SIMD-машины и показано, как они помогают избежать взаимного влияния процессов и, следовательно, избавиться от необходи­мости программирования барьеров. Эффективной реализации алгоритмов, параллельных по данным, на машинах с разделяемой и распределенной памятью посвящена глава 11.

3.5.1. Параллельные префиксные вычисления

Часто бывает нужно применить некоторую операцию ко всем элементам массива. Напри­мер, чтобы вычислить среднее значение числового массива а [n], нужно сначала сложить все элементы массива, а затем разделить сумму на п. Иногда нужно получить средние значения для всех префиксов а [ 0 : i] массива. Для этого нужно вычислить суммы всех префиксов. Та­кой тип вычислений очень часто встречается, поэтому, например, в языке APL есть даже спе­циальные операторы редукции ("сворачивания") reduce и просмотра scan. SIMD-машины с массовым параллелизмом вроде Connection Machine обеспечивают аппаратную реализацию операторов редукции для упаковки значений в сообщения.

В данном разделе показано, как параллельно вычисляются суммы всех префиксов масси­ва. Эта операция называется параллельным префиксным вычислением. Базовый алгоритм может быть использован с любым ассоциативным бинарным оператором (сложение, умножение, логические операторы, вычисление максимума и другие). Поэтому параллельные префикс­ные вычисления используются во многих приложениях, включая обработку изображений, матричные вычисления и анализ регулярных языков (см. упражнения в конце главы).

Пусть дан массив а [n] и нужно вычислить sum[n], где sum[ i] означает сумму первых 1 элементов массива а. Очевидный способ последовательного решения этой задачи — пройти по элементам двух массивов.

sum [ 0]   = а [ 0 ] ; for   [i =  1 to n-1]

sum[i]   =  sum[i-l]   + a[i];

Глава 3. Блокировки и барьеры                                                                                                   111

На каждой итерации значение а [ i ] прибавляется к уже вычисленной сумме предыдущих i-l элементов.

Теперь посмотрим, как этот алгоритм можно распараллелить. Если нужно просто найти сумму всех элементов, можно выполнить следующее. Сначала параллельно сложить пары элементов массива, например, складывать а [ 0 ] и а [ 1 ] синхронно с другими парами. После этого (тоже параллельно) объединить результаты первого шага, например, сложить сумму а [ 0 ] и а [ 1 ] с суммой а [ 2 ] и а [ 3 ] параллельно с вычислением других частичных сумм. Ес­ли этот процесс продолжить, то на каждом шаге количество просуммированных элементов будет удваиваться. Сумма всех элементов массива будет вычислена за flog2n] шагов. Это луч­шее, что можно сделать, если элементы обрабатываются парами.

Для параллельного вычисления сумм всех префиксов можно адаптировать описанный ме­тод удвоения числа обработанных элементов. Сначала присвоим всем элементам sum [ i ] значения a [i]. Затем параллельно сложим значения sum[i-l] и sum[i] для всех i >= 1, т.е. сложим все элементы, которые находятся на расстоянии 1.


Теперь удвоим расстояние и сложим элементы sum [i-2] с sum [ i ], на этот раз для всех i >= 2. Если продолжать уд­ваивать расстояние, то после [log2n] шагов будут вычислены все частичные суммы. Следую­щая таблица иллюстрирует шаги алгоритма для массива из шести элементов.



В листинге 3.14 представлена реализация этого алгоритма. Каждый процесс сначала ини­циализирует один элемент массива sum, а затем циклически вычисляет частичные суммы. Про­цедура barrier (i), вызываемая в программе, реализует точку барьерной синхронизации, ар­гумент i — идентификатор вызывающего процедуру процесса. Выход из процедуры происходит, когда все n процессов выполнят команду barrier. В теле процедуры может быть использован один из алгоритмов, описанных в предыдущем разделе. (Для этой задачи барьеры можно опти­мизировать, поскольку на каждом шаге синхронизируются только два процесса.)



112                                               Часть 1. Программирование с разделяемыми переменными



sum[i] должен сохранить копию его старого значения. Инвариант цикла SUM определяет, какая часть префикса массива а просуммирована на каждой итерации.

Как уже было отмечено, этот алгоритм можно изменить для использования с любым ассо­циативным бинарным оператором. Для этого достаточно поменять оператор, преобразующий элементы массива sum. Выражение для комбинирования результатов записано в виде old [ i-d] + sum[i], поэтому бинарный оператор не обязан быть коммутативным. Программу 3.14 можно адаптировать и для числа процессов меньше n; тогда каждый процесс будет отвечать за объединение частичных сумм полосы массива.

3.5.2. Операции со связанными списками

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


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

Предположим, что есть связанный список, содержащий не более n элементов. Связи хранятся в массиве link [n], а данные — в массиве data [n]. На начало списка указывает еще одна пере­менная, head. Если элемент i является частью списка, то или head == i, или link[ j ] == i для некоторого j от 0 до п-1. Поле link последнего элемента списка является указателем "в ни­куда" (пустым), что обозначается null. Предположим, что поля link элементов вне списка также пусты, а список уже инициализирован. Ниже приводится пример такого списка.



 Задача состоит в том, чтобы найти конец списка. Стандартный последовательный алго­ритм начинает работу с начала списка head и следует по ссылкам, пока не найдет пустой ука­затель. Последний из просмотренных элементов и есть конец списка. Время работы этого алгоритма пропорционально длине списка. Однако поиск конца списка можно выполнить за время, пропорциональное логарифму его длины, если использовать алгоритм, параллельный по данным, и метод удвоения из предыдущего раздела.

Каждому элементу списка назначается процесс Find. Пусть end[n] — разделяемый мас­сив целых чисел. Если элемент i является частью списка, то задача процесса F ind [ i ] — при­своить переменной end [ i] значение, равное индексу последнего элемента списка, в против­ном случае процесс Find[i] должен присвоить end[i] значение null. Чтобы не рассмат­ривать частные случаи, допустим, что список содержит хотя бы два элемента.

В начале работы каждый процесс присваивает элементу end [ i ] значение 1 ink [ i ], т.е. ин­декс следующего элемента списка (если он есть). Таким образом, массив end в начале работы воспроизводит схему связей списка. Затем процессы выполняют ряд этапов.


На каждом этапе процесс рассматривает элемент с индексом end [ end [i]]. Если элементы end [end [i]] nend[i] — не пустые указатели, то процесс присваивает элементу end[i] значение end [end [i] ]. Таким образом, после первого цикла переменная end[i] будет указывать на элемент списка, находящийся на расстоянии в две связи от начального (если такой есть). После двух циклов значение end [ i ] будет указывать на элемент списка, удаленный на четыре связи (опять-таки, если он существует). После [log2n] циклов каждый процесс найдет конец списка.



В листинге 3.15 представлена реализация этого алгоритма. Поскольку метод программи­рования тот же, что и для параллельных префиксных вычислений, структура алгоритма такая же, как в листинге 3.14. barrier (i) — это вызов процедуры, реализующей барьерную син­хронизацию процесса 1. Инвариант цикла FIND определяет, на что указывает элемент масси­ва end [ i ] до и после каждой итерации. Если конец списка находится от элемента i на рас­стоянии не более 2Л~1

связей, то в дальнейших итерациях значение end [ i ] не изменится.

Для иллюстрации работы алгоритма рассмотрим следующий список из шести элементов.



114                                              Часть 1 Программирование с разделяемыми переменными

3.5.3. Сеточные вычисления: итерация Якоби

Многие задачи обработки изображений или научного моделирования решаются с помощью так называемых сеточных вычислений. Они основаны на использовании матрицы точек (сетки), на­ложенной на область пространства. В задаче обработки изображений матрица инициализируется значениями пикселей (точек), а целью является поиск чего-то вроде множества соседних пикселей с одинаковой интенсивностью. В научном моделировании часто используются приближенные ре­шения дифференциальных уравнений в частных производных; в этом случае граничные элементы матрицы инициализируются краевыми условиями, а цель состоит в приближенном вычислении значений в каждой внутренней точке. (Это соответствует поиску устойчивого решения уравнения.) В любом случае, сеточные вычисления имеют следующую общую схему.



инициализировать матрицу; whilе   (еще не завершено)   {

для каждой точки вычислить новое значение;

проверить условие завершения; }

Обычно на каждой итераций новые значения точек вычисляются параллельно.

В качестве конкретного примера приведем простое решение уравнения Лапласа для двух­мерного случая: Д2 = 0. (Это дифференциальное уравнение в частных производных; подробно­сти— в разделе 11.1.) Пусть grid[n+l,n+l] — матрица точек. Границы массива grid (левый и правый столбцы, верхняя и нижняя строки) представляют края двухмерной области. Сетке, наложенной на область, соответствуют nхn внутренних элементов массива grid. Задача — вы­числить устойчивые значения внутренних точек. Для уравнения Лапласа можно использовать метод конечных разностей типа итераций Якоби. На каждой итерации новое значение каждой внутренней точки вычисляется как среднее значение четырех ее ближайших соседей.

В листинге 3.16 представлены сеточные вычисления для решения уравнения Лапласа с помощью итераций Якоби. Для синхронизации шагов вычислений вновь применяются барьеры. Каждая итерация состоит из двух основных шагов: обновление значений newgrid с проверкой на сходимость и перемещение содержимого массива newgrid в массив grid. Для того чтобы новые сеточные значения зависели только от старых, используются две мат­рицы. Вычисления можно закончить либо после фиксированного числа итераций, либо при достижении заданной точности, когда новые значения newgrid будут отличаться от значе­ний grid не более, чем на EPSILON. Разности можно вычислять параллельно, но с после­дующим объединением результатов. Это можно сделать с помощью параллельных префикс­ных вычислений; решение оставляется читателю (см. упражнения в конце главы).



Глава 3. Блокировки и барьеры                                                                                                15

Алгоритм в листинге 3.16 правилен, но в некоторых отношениях слишком упрощен. Во-"яервых, массив newgrid копируется в массив grid на каждой итерации.


Было бы намного эффективнее "развернуть" цикл, чтобы на каждой итерации сначала обновлялись значения, переходящие из grid в newgrid, а затем — из newgrid в grid. Во-вторых, лучше использо­вать алгоритм последовательной сверхрелаксации, сходящийся быстрее. В-третьих, програм­ма в листинге 3.16 является слишком мелкомодульной для асинхронных мультипроцессоров. Поэтому гораздо лучше разделить сетку на блоки и каждому блоку назначить один процесс (и процессор). Все эти нюансы подробно рассмотрены в главе 11, где показано, как эффек­тивно выполнять сеточные вычисления и на мультипроцессорах с разделяемой памятью, и на машинах с распределенной памятью.

3.5.4. Синхронные мультипроцессоры

В асинхронном мультипроцессоре все процессоры выполняют разные процессы с потен­циально разными скоростями. Такие мультипроцессоры называются MIMD-машинами (multiple instruction — multiple data, много команд — много данных), поскольку имеют не­сколько потоков команд и данных, т.е. состоят из нескольких независимых процессоров. Обычно предполагается именно такая модель выполнения.

MIMD-машины являются наиболее гибкими мультипроцессорами, поэтому используют­ся чаще других. Однако в последнее время стали доступными и синхронные мультипроцессо­ры (SIMD-машины), например, Connection Machine (начало 1990-х) или машины Maspar (середина-конец 1990-х). В SIMD-машине несколько потоков данных, но только один поток инструкций. Все процессоры синхронно выполняют одну и ту же последовательность команд. Это делает SIMD-машины особенно подходящими для алгоритмов, параллельных по дан­ным. Например, алгоритм 3.14 вычисления всех частичных сумм массива для SIMD-машины упрощается следующим образом.



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


При присваивании значения элементу sum [ i ] каждый процесс(ор) извлекает из массива sum старые значения элементов перед тем, как присваивать новые. По этой причине параллельные инструкции присваивания на SIMD-машине становятся неделимыми, в ре­зультате чего исключаются некоторые источники взаимного влияния процессов.

Создать SIMD-машину с большим числом процессоров технологически намного проще, чем построить MIMD-машину с массовым параллелизмом. Это делает SIMD-машины привлека­тельными для решения больших задач, в которых можно использовать алгоритмы, параллель­ные по данным. С другой стороны, SIMD-машины являются специализированными, т.е. в лю­бой момент времени вся машина выполняет одну программу. (Это основная причина, по кото­рой интерес к SIMD-машинам невелик.) Кроме того, программисту нелегко все время загружать каждый процессор полезной работой. В приведенном выше алгоритме, например, все меньше и меньше процессоров на каждой итерации обновляют элементы sum [ i ], но все они

116                                               Часть 1 Программирование с разделяемыми переменными

должны вычислять значение условия в операторе if. Если условие не выполняется, то процесс приостанавливается, пока все остальные не обновят значения элементов массива sum. Таким образом, время выполнения оператора if — это общее время выполнения всех ветвей, даже если какая-то из них не затрагивается. Например, время выполнения оператора if /then/else на каж­дом процессоре — это сумма времени вычисления условия, выполнения then- или else-ветви.

3.6. Параллельные вычисления с портфелем задач

Как указано в предыдущем разделе, многие итерационные задачи могут быть решены с помощью программирования, параллельного по данным. Решение рекурсивных задач, ос­нованное на принципе "разделяй и властвуй", можно распараллелить, выполняя рекурсив­ные вызовы параллельно, а не последовательно, как было показано в разделе 1.5.

В данном разделе представлен еще один способ реализации параллельных вычислений, в котором используется так называемый портфель задач. Задача является независимой еди­ницей работы.


Задачи помещаются в портфель, разделяемый несколькими рабочими процес­сами. Каждый рабочий процесс выполняет следующий основной код. while   (true)   {

получить задачу из портфеля ; if   (задач болыиенет)

break;        #  выход их цикла while

выполнить задачу, возможно, порождая новые задачи; }

Этот подход можно использовать для реализации рекурсивного параллелизма; тогда задачи будут представлены рекурсивными вызовами. Его также можно использовать для решения итеративных проблем с фиксированным числом независимых задач.

Парадигма портфеля задач имеет несколько полезных свойств. Во-первых, она весьма проста в использовании. Достаточно определить представление задачи, реализовать портфель, запрограм­мировать выполнение задачи и выяснить, как распознается завершение работы алгоритма. Во-вторых, программы, использующие портфель задач, являются масштабируемыми в том смысле, что их можно использовать с любым числом процессоров; для этого достаточно просто изменить коли­чество рабочих процессов. (Однако производительность программы при этом может и не изме­няться.) И, наконец, эта парадигма упрощает реализацию балансировки нагрузки. Если длитель­ности выполнения задач различны, то, вероятно, некоторые из задач будут выполняться дольше других. Но пока задач больше, чем рабочих процессов (в два—три раза), общие объемы вычисле­ний, осуществляемых рабочими процессорами, будут примерно одинаковыми.

Ниже показано, как с помощью портфеля задач реализуется умножение матриц и адап­тивная квадратура. При умножении матриц используется фиксированное число задач. В адаптивной квадратуре задачи создаются динамически. В обоих примерах для защиты дос­тупа к портфелю задач применяются критические секции, а для обнаружения окончания — барьероподобная синхронизация.

3.6.1. Умножение матриц

Вновь рассмотрим задачу умножения матриц а и Ь размером n x п. Это требует вычис­ления п2 промежуточных произведений, по одному на каждую комбинацию из строки а и столбца Ь.


Каждое промежуточное умножение — это независимое вычисление, которое можно выполнить параллельно. Предположим, однако, что программа будет выполняться на машине с числом процессоров PR. Тогда желательно использовать PR рабочих процессов, по одному на каждый процессор. Чтобы сбалансировать вычислительную загрузку, процессы

Глава 3. Блокировки и барьеры                                                                                    117r

должны вычислять примерно поровну промежуточных произведений. В разделе 1.4 каждому рабочему процессу часть вычислений назначалась статически. В данном случае воспользуем­ся портфелем задач, и каждый рабочий процесс будет захватывать задачу при необходимости. Если число PR намного меньше, чем n, то подходящий для задания объем работы — одна или несколько строк результирующей матрицы с. (Это ведет к разумной локализации матриц а и с с учетом того, что данные в них хранятся по строкам.) Для простоты используем оди­ночные строки. В начальном состоянии портфель содержит n задач, по одной на строку. За­дачи могут быть расположены в любом порядке, поэтому портфель можно представить про­стым перечислением строк.

int  nextRow =   0;

Рабочий процесс получает задачу из портфеля, выполняя неделимое действие

{ row = nextRow;   nextRow++;   )

Здесь row — локальная переменная. Портфель пуст, когда значение row не меньше п. Неде­лимое действие в указанной строке программы — это еще один пример вытягивания билета. Его можно реализовать с помощью инструкции "извлечь и сложить", если она доступна, или блокировок для защиты критической секции.

В листинге 3.17 представлена схема программы. Предполагается, что матрицы инициализи­рованы. Рабочие процессы вычисляют внутренние произведения обычным способом. Про­грамма завершается, когда все рабочие процессы выйдут из цикла while. Для определения этого момента можно воспользоваться разделяемым счетчиком done с нулевым начальным зна­чением. Перед тем как рабочий процесс выполнит оператор break, он должен увеличить значе­ние счетчика в неделимом действии.


Если нужно, чтобы последний рабочий процесс выводил результаты, в конец кода каждого рабочего процесса можно добавить следующие строки. if (done == n)

напечатать матрицу с;



118                                               Часть 1 Программирование с разделяемыми переменными

ной точностью равна большей, то приближение считается достаточно хорошим. Если нет, большая задача делится на две подзадачи, и процесс повторяется.

Парадигму портфеля задач можно использовать для реализации адаптивной квадратуры. Задача представляет собой отрезок для проверки; он определяется концами интервала, зна­чениями функции в этих точках и приближением площади для этого интервала. Сначала есть одна задача — для всего отрезка от а до Ь.

Рабочий процесс циклически получает задачу из портфеля и выполняет ее. В отличие от программы умножения матриц, в данном случае портфель задач может быть (временно) пуст, и рабочий процесс вынужден задерживаться до получения задачи. Кроме того, выполнение од­ной задачи обычно приводит к возникновению двух меньших задач, которые рабочий процесс должен поместить в портфель. Наконец, здесь гораздо труднее определить, когда работа будет завершена, поскольку просто ждать опустошения портфеля недостаточно. (Действительно, как только будет получена первая задача, портфель станет пустым.) Вместо этого можно считать, что работа сделана, если портфель пуст и каждый рабочий процесс ждет получения новой задачи.

В листинге 3.18 показана программа для адаптивной квадратуры, использующая портфель задач. Он представлен очередью и счетчиком. Еще один счетчик отслеживает число простаи­вающих процессов. Вся работа заканчивается, когда значение переменной size равно нулю, а счетчика idle — п. Заметим, что программа содержит несколько неделимых действий. Они нуж­ны для защиты критических секций, в которых происходит доступ к разделяемым переменным. Все неделимые действия, кроме одного, безусловны, поэтому их можно защитить блокировками. Однако оператор await нужно реализовать с помощью более сложного протокола, описанного в разделе 3.2, или более мощного механизма синхронизации типа семафоров или мониторов.



Программа в листинге 3. 18 задает чрезмерное использование портфеля задач. В частности, решая создать две задачи, рабочий процесс помещает их в портфель, затем выполняет цикл и получает оттуда новую задачу (возможно, ту же, которую только что поместил туда). Вместо этого можно заставить рабочий процесс помещать одну задачу в портфель, а другую оставлять себе для выполнения. Когда портфель заполнится до состояния, обеспечивающего сбалансиро­ванную вычислительную загрузку, следовало бы заставить рабочий процесс выполнять задачу полностью, используя последовательную рекурсию, а не помещать новые задачи в портфель.

Алгоритмы передачи маркера

В этом разделе описывается передача маркера — еще одна модель взаимодействия про­цессов. Маркер — это особый тип сообщений, который можно использовать для передачи разрешения или сбора информации о глобальном состоянии. Использование маркера для передачи разрешения иллюстрируется простым распределенным решением задачи крити­ческой секции. Сбор информации о состоянии демонстрируется в процессе разработки двух алгоритмов, позволяющих определить, завершились ли распределенные вычисления. Еще один пример приводится в следующем разделе (см. также историческую справку и уп­ражнения).

9.6.1. Распределенное взаимное исключение

Задача о критической секции (КС) возникла в программах с разделяемыми переменными. Однако она встречается и в распределенных программах, если какой-нибудь разделяемый ре­сурс используется в них с исключительным доступом. Это может быть, например, линия свя­зи со спутником. Кроме того, задача КС обычно является частью большей задачи, такой как обеспечение согласованности распределенного файла или системы баз данных.

Первый способ решения задачи КС — использовать активный монитор, разрешающий доступ к КС. Для многих задач вроде реализации блокировки файлов это самый простой и эффективный метод. Второй способ решения этой задачи — использовать распределенные семафоры, реализованные так, как описано в предыдущем разделе. Этот способ приводит к децентрализованному решению, в котором все процессы одинаковы, но для каждой опера­ции с семафором необходим обмен большим количеством сообщений, поскольку операция broadcast должна быть подтверждена.

Здесь задача решается третьим способом — с помощью кольца передачи маркера (token nng). Это децентрализированное и справедливое решение, как и решение с использованием распределенных семафоров, но оно требует обмена намного меньшим количеством сообще­ний. Кроме того, базовый метод можно обобщить для решения других задач синхронизации.

Пусть User [ 1: п ] — это набор прикладных процессов, содержащих критические и некри­тические секции.
Как всегда, нужно разработать протоколы входа и выхода, которые выпол­няются перед КС и после нее. Протоколы должны обеспечивать взаимное исключение, от­сутствие блокировок и ненужных задержек, а также возможность входа (справедливость).

Поскольку у пользовательских процессов есть своя работа, нам не нужно, чтобы они за­нимались передачей маркера. Используем набор дополнительных процессов Helper [ 1: п], по одному для каждого пользовательского процесса. Вспомогательные процессы образуют кольцо (рис. 9.3). Маркер циркулирует от процесса Helper [ 1 ] к процессу Helper [2 ] и так далее до процесса Helper [n], который передает его процессу Helper [1]. Получив маркер,

354                                                                        Часть 2. Распределенное программирование

Helper [i] проверяет, не собирается ли входить в КС его клиент User[i]. Если нет, Helper [ i ] передает маркер. Иначе Helper [ i ] сообщает процессу User [ i ], что он может войти в КС, и ждет, пока процесс User [ i ] не выйдет из нее. После этого Helper [ i ] пере­дает маркер. Таким образом, вспомогательные процессы работают совместно, чтобы обеспе­чить постоянное выполнение следующего предиката.

Решение в листинге 9.12 является справедливым (при условии, что процессы когда-нибудь выходят из критических секций). Причина в том, что маркер циркулирует непре­рывно, и как только он оказывается у процесса Helper[i], процесс Userfi] получает разрешение войти в КС (если хочет). Фактически то же самое происходит и в физической сети с передачей маркера. Однако при программной передаче маркера, вероятно, лучше добавить некоторую задержку во вспомогательных процессах, чтобы он двигался по кольцу медленней. (В разделе 9.7 представлен еще один алгоритм исключения на основе передачи маркера. Там маркеры не циркулируют непрерывно.)

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


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

9.6.2. Как определить окончание работы в кольце

Окончание работы последовательной программы обнаружить легко. Так же легко опреде­лить, что параллельная программа завершилась на одном процессоре — каждый процесс за­вершен или заблокирован и нет ожидающих операций ввода-вывода. Но не просто обнару­жить, что закончилась распределенная программа, поскольку ее глобальное состояние не видно ни одному процессору. Кроме того, даже если все процессоры бездействуют, могут су­ществовать сообщения, передаваемые между ними.

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

Пусть в распределенных вычислениях есть процессы (задачи) Т[1.-п] и массив каналов взаимодействия ch [1 :п]. Пока предположим, что процессы образуют кольцо, по которому проходит их взаимодействие. Процесс T[i] получает сообщения только из своего канала ch[i] и передает их только в следующий канал ch[i%n+l]. Таким образом, Т[1] передает сообщения только Т [ 2 ], Т [ 2 ] — только Т [ 3 ] и так далее до Т [n ], передающего сообщения Т[1]. Как обычно, предполагается, что сообщения от каждого процесса его сосед по кольцу получает в порядке их передачи.

В любой момент времени процесс может быть активным или простаивать (бездействовать). Вначале активны все процессы. Процесс бездействует, если он завершен или приостановлен оператором получения сообщения. (Если процесс временно приостанав­ливается, ожидая окончания операции ввода-вывода, он считается активным, поскольку он еще не завершен и через некоторое время снова будет запущен.) Получив сообщение, бездей­ствующий процесс становится активным.


Таким образом, распределенные вычисления за­кончены, если выполняются следующие два условия:

DTERM:  все процессы бездействуют л нет передаваемых сообщений

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

356                                                                            Часть 2. Распределенное программирование

Наша задача — перенести алгоритм определения окончания работы на любые распределен­ные вычисления, основываясь только на предположении о том, что процессы в вычислении взаимодействуют по кольцу. Окончание — это свойство глобального состояния, объединяющего состояния отдельных процессов и содержание каналов передачи сообщений. Таким образом, чтобы определить момент окончания вычислений, процессы должны взаимодействовать.

Пусть один маркер передается по кольцу в специальных сообщениях, не являющихся ча­стью вычислений. Процесс, удерживающий маркер, передает его дальше и становится без­действующим. (Если процесс закончил свои вычисления, он бездействует, но продолжает участвовать в алгоритме обнаружения завершения работы.)

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

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



Допустим, что вначале маркер находится у процесса т [ 1 ]. Когда Т [ 1 ] становится без­действующим, он инициирует алгоритм обнаружения окончания работы, передавая маркер процессу Т [2]. Возвращение маркера к Т[1] означает, что вычисления закончены, если Т [ 1 ] был непрерывно бездействующим с момента передачи им маркера процессу Т [ 2 ]. Дело в том, что маркер проходит по тому же кольцу, по которому идут обычные сообщения, а все сообщения доставляются в порядке их отправки. Таким образом, если маркер возвра­щается к т [ 1 ], значит, ни одного обычного сообщения уже не может быть нигде в очереди или в пути. По сути, маркер "очищает" каналы, проталкивая перед собой все обычные со­общения.

Уточним алгоритм. Во-первых, с каждым процессом свяжем цвет: синий (холодный), если процесс бездействует, и красный (горячий), если он активен. Вначале все процессы активны, поэтому окрашены красным. Получая маркер, процесс бездействует, поэтому становится си­ним, передает маркер дальше и ждет следующее сообщение. Получив позже обычное сооб­щение, процесс станет красным. Таким образом, процесс, окрашенный в синий цвет, передал маркер дальше и остался бездействующим.

Во-вторых, с маркером свяжем значение, которое показывает количество пустых каналов, если Т[1] остается бездействующим. Пусть это значение хранится в переменной token. Становясь бездействующим, Т [ 1 ] окрашивается в синий цвет, присваивает token значение О и передает маркер процессу Т [ 2 ]. Получая маркер, Т [ 2 ] бездействует (при этом канал сп[2] может быть пустым). Поэтому Т [2] становится синим, увеличивает значение token до 1 и передает маркер процессу Т [ 3 ]. Все процессы Т [ i ] по очереди становятся синими и увеличивают token перед тем, как передать дальше.

Описанные правила передачи маркера перечислены в листинге 9.13. Их выполнение га­рантирует, что условие RING является глобальным инвариантом. Инвариантность RING следует из того, что, если процесс Т [1] окрашен в синий цвет, значит, с момента передачи маркера никаких обычных сообщений он не передавал, и, следовательно, ни в одном из каналов, пройденных маркером, нет обычных сообщений.


Кроме того, все соответствую­щие процессы остались бездействующими с тех пор, как получили маркер. Таким образом, если Т[1] остался синим, снова получив маркер, то все остальные процессы тоже окраше­ны в синий цвет, а каналы — пусты. Следовательно, т [ 1 ] может объявить, что вычисления закончены.



9.6.3. Определение окончания работы в графе

В предыдущем разделе предполагалось, что все взаимодействия происходят по кольцу. В общем случае структура взаимодействия распределенной программы образует произволь­ный ориентированный граф. Узлы графа представляют процессы в вычислениях, а дуги — пу­ти взаимодействия. Два процесса связаны дугой, если первый из них передает данные в ка­нал, из которого их считывает второй.

Предположим, что граф связей является полным, т.е. между любыми двумя процессами есть одна дуга. Как и ранее, есть п процессов Т [ 1: n ] и каналов ch [ 1: n ], и каждый Т [ i ] по­лучает данные из собственного канала ch [ i ]. Однако теперь каждый процесс может посы­лать сообщения только в канал ch [ i ].

Учитывая вышесказанное, расширим предыдущий алгоритм определения окончания ра­боты. Полученный в результате алгоритм можно использовать в любой сети, имеющей пря­мые линии взаимодействия между любыми двумя процессорами. Его легко распространить на произвольные графы взаимодействия и многоканальные связи (см. упражнения).

Определить окончание работы в полном графе сложнее, чем в кольце, поскольку сообще­ния могут идти по любой дуге Рассмотрим, например, полный граф из трех процессов (рис. 9.4). Пусть процессы передают маркер только от Т [ 1 ] к Т [ 2 ], затем к Т [3 ] и обратно к т [ 1 ]. Допустим, процесс т [ 1 ] получает маркер и становится бездействующим; следова­тельно, он передает маркер процессу Т [2}. Становясь бездействующим, Т [2 ] передает мар­кер Т [ 3 ]. Но перед получением маркера Т [ 3 ] может передать процессу Т [ 2 ] обычное сооб­щение. Таким образом, когда маркер возвращается к Т [ 1 ], нельзя сделать вывод о том, что вычисления завершены, даже если т [ 1 ] оставался непрерывно бездействующим.



Основным в кольцевом алгоритме (см. листинг 9.13) является то, что все взаимодействия проходят по кольцу, поэтому маркер "проталкивает" обычные сообщения, проходя все дуги кольца. Этот алгоритм можно обобщить для полного графа, обеспечив проход маркера по ка­ждой дуге (маркер должен многократно посетить каждый процесс). Если каждый процесс ос­тается непрерывно бездействующим с момента предыдущего получения маркера, то можно прийти к выводу, что вычисления завершены.

Как и раньше, процессы окрашиваются в красный или синий цвет (вначале — в красный). Получая обычное сообщение, процесс становится красным, а получая маркер, — блокируется в ожидании следующего сообщения из своего входного канала. Поэтому процесс окрашива­ется в синий цвет (если он еще не был синим) и передает маркер. (Как и раньше, заканчивая свои обычные вычисления, процесс продолжает обрабатывать сообщения с маркером.)

358                                                                            Часть 2 Распределенное программирование

Любой полный граф содержит цикл, в который входят все его дуги (некоторые узлы могут включаться несколько раз). Пусть С — цикл графа взаимодействия, а nс — его длина. Каждый процесс отслеживает порядок, в котором исходящие из него дуги встречаются в цикле с. По­лучив маркер по одной дуге цикла с, процесс передает его по следующей. Это гарантирует, что маркер пройдет по каждой дуге графа взаимодействия.



Как и раньше, маркер имеет значение, говорящее о количестве пройденных бездействующих процессов и, следовательно, каналов, которые могут быть пустыми. Но из приведенного выше примера видно, что в полном графе бездействующий процесс снова может стать активным, даже если бездействующим остается процесс Т [ 1 ]. Таким образом, чтобы делать вывод об окончании вычислений, нужен другой набор правил передачи маркера и другой глобальный инвариант.

Маркер начинает движение с любого процесса и имеет начальное значение 0. Когда этот процесс впервые становится бездействующим, он окрашивается в синий цвет и передает мар­кер по первому ребру цикла С.


Получив маркер, процесс совершает действия, представлен­ные в листинге 9.14. Если при получении маркера процесс окрашен в красный цвет (с момен­та последнего получения маркера он был активным), он становится синим и присваивает маркеру token значение О перед тем, как передать его по следующему ребру цикла С. Таким образом, алгоритм обнаружения окончания программы перезапускается. Но если при полу­чении маркера процесс окрашен в синий цвет, т.е. с момента последнего получения маркера непрерывно бездействовал, то перед передачей маркера процесс увеличивает его значение.



Глава 9 Модели взаимодействия процессов                                                                        359

числения закончены. В этот момент известно, что последние пс каналов, пройденные марке­ром, были пустыми. Поскольку бездействующий процесс только передает маркер, а значение маркера увеличивает, только если бездействовал с момента прошлого получения маркера, можно наверняка сказать, что все каналы пусты и все процессы бездействуют. В действитель­ности все вычисления завершились уже к тому моменту, когда маркер начал свой последний проход по графу. Но ни один процесс не может это установить до тех пор, пока маркер не сделает еще один полный цикл по графу, чтобы убедиться в том, что все процессы остались бездействующими и все каналы — пустыми. Таким образом, после завершения всех вычисле­ний маркер должен пройти по циклу как минимум дважды: на первом проходе процессы ста­новятся синими, а на втором — проверяется, не поменяли ли они цвет.

Алгоритмы пульсации

Модель портфеля задач полезна для решения задач, которые возникают при использова­нии стратегии "разделяй и властвуй" или требуют фиксированного числа независимых задач. Парадигму пульсации можно применять во многих итерационных приложениях, параллельных по данным. Например, ее можно использовать, когда данные разделяются между рабочими процессами, каждый из которых отвечает за изменение определенной части данных, причем но­вые значения зависят от данных из этой же части или непосредственно прилегающих частей. Среди таких приложений — сеточные вычисления, возникающие при обработке изображений или решении дифференциальных уравнений в частных производных, и клеточные автоматы, используемые при моделировании таких процессов, как лесной пожар или биологический рост. Предположим, что есть массив данных. Каждый рабочий процесс отвечает за определен­ную часть данных и строится по следующей схеме.

process worker[w =  1  to numWorkers]   { декларации локальных переменных; инициализация локальных переменных; wh i 1 е   (не выполнено)   { send значения соседям; receive значения от соседей; обновить локальные значения; } }

334                                                                            Часть 2. Распределенное программирование

Этот тип межпроцессного взаимодействия называется алгоритмом пульсации, поскольку дей­ствия рабочих процессов напоминают работу сердца: расширение при отправке информации, сокращение при сборе новой информации, затем обработка информации и повторение цикла.

Если данные образуют двухмерную сетку, их можно разделить на полосы или блоки. При делении на полосы получим вектор рабочих процессов, у каждого из которых (кроме двух крайних) будет по два соседа. При делении на блоки получим матрицу рабочих процессов, и у каждого из них будет от двух до восьми соседей, в зависимости от положения блока в мас­сиве данных (внутри, на границе или в углу) и количества соседних значений, необходимых для обновления значений в блоке.
Трехмерные массивы данных можно делить аналогичным образом на плоскости, прямоугольные призмы или кубы.

Взаимодействие по схеме send-receive в алгоритме пульсации приводит к появлению "нечеткого" барьера между рабочими процессами. Напомним, что барьер — это точка син­хронизации, которой должны достичь все рабочие процессы перед тем, как продолжить рабо­ту. В итерационных вычислениях барьер не позволяет начать новую итерацию, пока все рабо­чие процессы не закончат предыдущую. Чтобы новая фаза обновления значений не начина­лась до того, как все процессы завершат предыдущую фазу, используется обмен сообщениями. Рабочие процессы, которые не являются соседями, могут порознь проводить больше одной итерации, но для соседних процессов это запрещено. Настоящий барьер здесь не нужен, поскольку рабочие процессы разделяют данные только со своими соседями.

Далее разрабатываются алгоритмы пульсации для двух задач: выделения областей (пример обработки изображений) и игры "Жизнь" (пример клеточного автомата). Дополнительные примеры приложений есть в упражнениях и в главе 11.

9.2.1. Обработка изображений: выделение областей

Изображение — это представление картинки; обычно оно состоит из матрицы чисел. Эле­мент изображения называется пикселем (от англ, picture element — pixel, элемент картины), и его значение представляет собой интенсивность света или цвет.

Существует множество операций обработки изображений, и каждая из них может выиг­рать от распараллеливания. Более того, одна и та же операция иногда применяется к потоку изображений. Операции обработки изображений бывают точечными (работают с отдельными пикселями, как, например, при контрастировании), локальными (обрабатывают группы пик­селей, как при сглаживании или подавлении шумов) и глобальными (над всеми пикселями, например, при кодировании или декодировании).

Рассмотрим локальную операцию, которая называется выделением областей. Пусть изо­бражение представлено матрицей image [m, n] целых чисел.


Для простоты предположим, что каждый пиксель имеет значение 1 (освещено) или 0 (не освещено). Его соседями считаются пиксели, расположенные сверху, снизу, слева и справа. (У пикселей в углах изображения по два соседа, на границах — по три.)

Задача выделения области состоит в поиске областей освещенных пикселей и присвоении каждой найденной области уникальной метки. Два освещенных пикселя принадлежат одной области, если являются соседями. Рассмотрим, например, следующее изображение, в кото­ром освещенные пиксели сигнала обозначены точками, а неосвещенные — пробелами.

Глава 9. Модели взаимодействия процессов                                                                        335

В изображении есть три области. "Кривая" в правом нижнем углу не образует область, по­скольку ее точки соединены по диагоналям, а не горизонтальным или вертикальным линиям.16

Метки областей хранятся во второй матрице label [m, n]. Вначале каждая точка изобра­жения получает уникальную метку вроде линейной функции m* i+j от координат точки i и j. Окончательное значение элементов массива label [i, j ] должно быть равно максимальной из начальных меток в области, содержащей точку (i, j).

Естественный способ решения этой задачи — итерационный алгоритм. На каждой итера­ции просматриваются все точки и их соседи. Если текущий пиксель и его сосед имеют значе­ние 1, то меткой пикселя становится максимальная из меток его и соседа. Эти действия мож­но выполнять для всех пикселей параллельно, поскольку метки никогда не уменьшаются.

Алгоритм завершается, если в течение итерации не изменяется ни одна метка. Обычно области достаточно компактны, и алгоритм прекращает работу примерно через О(т) итера­ций. Однако в худшем случае потребуется О(т*п) итераций, поскольку область может "виться" по всему изображению.

В данной задаче пиксели независимы, поэтому можно использовать m*n параллельных задач. Это решение подходит для SIMD-машины с массовым параллелизмом, но для MIMD-машины такие маленькие задачи использовать неэффективно.


Предположим, что есть MIMD-машина с р процессорами, и m кратно р. Тогда было бы правильно решать задачу вы­деления областей, разделив изображение на р полос или блоков пикселей и назначив для ка­ждой полосы или блока отдельный рабочий процесс. Используем деление на полосы — оно проще программируется и требует меньшего числа сообщений, чем деление на блоки, по-. скольку у рабочих процессов меньше соседей. (На машинах, организованных как сетки или кубы, было бы эффективней использовать блоки точек, поскольку сеть связи в таких маши­нах поддерживает одновременные передачи сообщений.)

Каждый рабочий процесс вычисляет метки пикселей своей полосы. Для этого ему нужна собственная полоса изображения image и полоса матрицы меток label, а также значения граничных элементов полос, расположенных над и под его полосой. Поскольку области могут накрывать границы блоков, процесс должен взаимодействовать со своими соседями. Для этого на каждой итерации процесс обменивается метками пикселей на границах своей поло­сы с двумя соседями, а затем вычисляет новые метки.

В листинге 9.3, а показана схема рабочего процесса. После инициализации локальных пе­ременных рабочий процесс обменивается значениями на границе своей части матрицы im­age с соседями. Сначала он отправляет граничные значения соседу сверху и соседу снизу, за­тем получает значения от соседа снизу и от соседа сверху. Для обмена используются два мас­сива каналов first и second. Как показано на схеме, рабочие процессы 1 и Р представляют собой частные случаи, поскольку у них есть только по одному соседу.

В начале каждого повторения цикла while соседи-рабочие обмениваются граничными значениями своих частей массива label, используя описанную выше схему передачи сооб­щений. Затем они обновляют метки пикселей своей полосы. Код обновления мог бы обра­щаться к каждому пикселю один раз или выполняться циклически, пока изменяются метки в полосе. Последний способ приводит к меньшему числу сообщений для обмена метками между рабочими процессами, повышая производительность за счет уменьшения доли вычис­лений, необходимых для взаимодействия.



В этом приложении рабочий процесс не может сам определить, когда нужно завершить работу. Даже если на итерации не было локальных изменений, могли изменяться метки вдругой полосе, а соответствующие им пиксели могли принадлежать области, захватываю­щей несколько полос. Вычисления заканчиваются, только если не изменяются метки во всем изображении. (В действительности это происходит на одну итерацию раньше, но определить это сразу невозможно.)

16 Неявно предполагается, что область состоит из более, чем одного пикселя. — Прим. ред.



Для определения момента завершения программы используется управляющий процесс (листинг 9.3, б). (Его функции мог бы выполнять один из рабочих процессов, но для упроще­ния кода используется отдельный процесс.) В конце каждой итерации все рабочие процессы передают управляющему сообщения, указывающие, изменялись ли метки каждым из процес­сов. Управляющий процесс объединяет сообщения и отсылает рабочим ответ. Для этих взаи­модействий используются каналы result и answer [n].

^Листинг 9.3. б. Выделение областей: управляющий процесс

chan result(bool);  # для результатов от рабочих процессов

process Coordinator {

bool chg, change = true; while (change) { change = false;

# посмотреть, были ли изменения в полосах for [i = 1 to P] {

receive result(chg); change = change or chg; }

# разослать ответ всем рабочим процессам for [i = 1 to P]

send answer[i](change); }

2________________________________________________________

Глава 9. Модели взаимодействия процессов                                                                      337

Для проверки завершения работы с помощью управляющего процесса на одной итерации нужно обменяться 2 *Р сообщениями. Если бы ответ управляющего процесса мог рассылать­ся сразу всем рабочим, то было бы достаточно р+1 сообщений. Однако в обоих случаях время работы управляющего процесса составляет О(Р), поскольку он получает сообщения с резуль­татами по одному. Используя дерево управляющих процессов, общее время их работы можно снизить до 0(log2P).


Еще лучше, если доступна операция редукции (сведения) для глобаль­ного сбора сообщений, например, операция MPi_AllReduce из библиотеки MPI. В резуль­тате упростится код программы и, возможно, повысится производительность, в зависимости от того, как реализована библиотека MPI на данной машине.

9.2.2. Клеточный автомат: игра "Жизнь"

Многие биологические и физические системы можно промоделировать в виде набора объектов, которые с течением времени циклически взаимодействуют и развиваются. Некото­рые системы, особенно простые, можно моделировать с помощью клеточных автоматов. (Более сложная система— гравитационное взаимодействие— рассматривается в главе 11.) Основная идея — разделить пространство физической или биологической задачи на отдель­ные клетки. Каждая клетка — это конечный автомат. После инициализации все клетки сна­чала совершают один переход в новое состояние, затем второй переход и т.д. Результат каж­дого перехода зависит от текущего состояния клетки и ее соседей.

Здесь клеточный автомат использован для моделирования так называемой игры "Жизнь". Дано двухмерное поле клеток. Каждая клетка либо содержит организм (жива), либо пуста (мертва). Бэтой задаче каждая клетка имеет восемь соседей, которые расположены сверху, снизу, слева, справа и по четырем диагоналям от нее. У клеток в углах по три соседа, а на границах — по пять.

Игра "Жизнь" происходит следующим образом. Сначала поле инициализируется. Затем каждая клетка проверяет состояние свое и своих соседей и изменяет свое состояние в соот­ветствии со следующими правилами.

•    Живая клетка, возле которой меньше двух живых клеток, умирает от одиночества.

•    Живая клетка, возле которой есть две или три живые клетки, выживает еще на одно поколение.

•    Живая клетка, возле которой находится больше трех живых клеток, умирает от пе­ренаселения.

•    Мертвая клетка, рядом с которой есть ровно три живых соседа, оживает.

Этот процесс повторяется некоторое число шагов (поколений).



Листинг 9. 4 содержит схему программы для имитации игры "Жизнь". Процессы взаимо­действуют с помощью парадигмы пульсации. На каждой итерации клетка посылает сообще­ния каждому из соседей и получает сообщения от них, после чего обновляет свое состояние в соответствии с приведенными правилами. Как обычно при использовании алгоритма пуль­сации, для процессов не нужна жесткая пошаговая синхронизация, но соседи никогда не опережают друг друга более, чем на одну итерацию.

Для простоты каждая клетка запрограммирована как процесс, хотя поле можно разделить на полосы или блоки клеток. Также не учтены особые случаи угловых и граничных клеток. Каждый процесс eel I [ i, j ] получает сообщения из элемента exchange [ i, j ] матрицы ка­налов связи, а отсылает сообщения в соседние элементы матрицы exchange. (Напомним, что каналы буферизуются, а операция send — неблокирующая.) Читателю было бы полезно реализовать эту программу с отображением состояния клеток в графической форме.

было бы объявить как first [1-.P-1] и second [2 :Р]. — Прим. ред.

Алгоритмы рассылки

В предыдущем разделе мы показали, как рассылать информацию по сети, имеющей структуру графа. В большинстве локальных сетей процессоры разделяют такой канал взаимо­действия, как Ethernet или эстафетное кольцо (token ring). Каждый процессор напрямую свя­зан со всеми остальными. Такие сети связи часто поддерживают специальный сетевой при­митив — операцию рассылки broadcast, которая передает сообщение от одного процессора всем остальным. Независимо от того, поддерживается ли рассылка сообщений аппаратно, она обеспечивает полезную технику программирования.

Пусть Т[п] — массив процессов, a ch[n] — массив каналов (по одному на процесс). Процесс Т [ i ] рассылает сообщение т, выполняя оператор broadcast ch(m);

При выполнении broadcast в каждый канал ch[i], включая канал процесса T[i], поме­щается копия сообщения т. Получается тот же результат, что и при выполнении кода

Глава 9. Модели взаимодействия процессов                                                                    349

со  [i = I to n] send ch[i](m);

Процессы получают рассылаемые и передаваемые напрямую сообщения, используя примитив receive.

Сообщения, рассылаемые одним и тем же процессом, помещаются в очереди каналов в порядке их рассылки. Однако операция broadcast не является неделимой. Например, со­общения, разосланные двумя процессами А и в, могут быть получены другими процессами в разных порядках. (Реализация неделимой рассылки сообщений описана в статьях, указан­ных в исторической справке.)

Примитив broadcast можно использовать для рассылки информации, например, для обмена данными о состоянии процессоров в локальных сетях. Также с его помощью можно решать задачи распределенной синхронизации. В этом разделе разработан алгоритм рассылки для поддержки распределенной реализации семафоров. Основой распределенных семафоров, как и многих других децентрализованных протоколов синхронизации, является полное упо­рядочение событий взаимодействия. Итак, вначале представим реализацию логических часов и их использование для упорядочения событий.

9.5.1. Логические часы и упорядочение событий

Действия процессов в распределенной программе можно разделить на локальные (чтение и запись переменных) и операции взаимодействия (передача и прием сообщений). Локаль­ные операции не оказывают прямого влияния на другие процессы, а операции взаимодейст­вия— оказывают, передавая информацию и синхронизируясь. Операции взаимодействия, таким образом, в распределенной программе являются важными событиями. Термин событие далее в тексте указывает на выполнение операторов send, broadcast или receive.

Если два процесса А и в выполняют локальные операции, то отследить относительный порядок выполнения их операций нельзя. Но если А передает (или рассылает) сообщение процессу В, то передача в А должна произойти перед соответствующим приемом сообщения вв. Если В затем передает сообщение процессу С, то передача в В должна произойти раньше, чем соответствующий прием в С. Кроме того, поскольку в В прием предшествует передаче, четыре события взаимодействия вполне упорядочены: передача сообщения из А, его прием в В, передача из В и, наконец, прием в С. Таким образом, происходит-перед является транзи­тивным отношением между причинно связанными событиями.

Хотя причинно связанные события вполне упорядочены, все множество событий в распре­деленной программе упорядочено лишь частично. Причина в том, что одна последовательность событий, не связанная с другой (например, операции взаимодействия между различными мно­жествами процессов), может происходить после нее, перед ней или одновременно с ней.

Если бы существовали единые центральные часы, то события взаимодействия можно бы­ло бы полностью упорядочить, назначив каждому уникальную метку времени. Передавая со­общение, процесс мог бы считывать с часов время и присоединять значение времени к сооб­щению. Получая сообщение, процесс также мог бы прочитать значение времени и записать, когда было получено сообщение. При условии, что точность часов позволяет различать время любой передачи и соответствующего приема сообщения, у события, произошедшего перед другим событием, значение метки времени будет меньше.


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

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

350                                                                            Часть 2. Распределенное программирование

ная синхронизация невозможна. Существуют алгоритмы синхронизации часов (см. истори­ческую справку) для поддержания "достаточно хорошего", но не абсолютного их согласова­ния. Итак, нам нужен способ имитации физических часов.

Логические часы — это простой целочисленный счетчик, который увеличивается при воз­никновении события. Предположим, что отдельные логические часы с нулевым начальным значением есть у каждого процесса. Допустим также, что в каждом сообщении есть специ­альное поле — метка времени. Значения логических часов увеличиваются в соответствии со следующими правилами.

Правила изменения значения логических часов. Пусть А— процесс с логическими часами 1с. Процесс А обновляет значение 1с так:

1.  передавая или рассылая сообщение, А присваивает его метке времени текущее значе­ние переменной 1с и увеличивает 1с на 1;

2.  получая сообщение с меткой времени ts, А присваивает переменной 1с максимальное из значений Icnts+lH затем увеличивает 1с на 1.

Поскольку А увеличивает 1с после каждого события, у всех сообщений, передаваемых этим процессом, будут разные, возрастающие метки времени. Поскольку событие получения при­дает 1с значение, которое больше метки времени в полученном сообщении, у любого сооб­щения, посылаемого процессом А в дальнейшем, будет большая метка времени.

Используя логические часы, с каждым событием можно связать их значение следующим образом.


Значение часов для события передачи сообщения — это метка времени в сообще­нии, т.е. локальное значение переменной 1с в начале передачи. Для события получения — это значение 1с после того, как оно установлено равным максимальному из значений 1с и ts+1, но до того, как оно будет увеличено получающим процессом.

Применение указанных выше правил гарантирует, что, если событие а происходит перед событием Ь, то значение часов, связанное с а, будет меньше, чем значение, связанное с Ь. Это определяет частичный порядок на множестве причинно связанных событий программы. Если каждый процесс имеет уникальный идентификатор, то полностью упорядочить все события можно, используя для событий с одинаковыми метками времени меньший идентификатор процесса, в котором происходит одно из них.

9.5.2. Распределенные семафоры

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

Семафор s обычно представляется неотрицательным целым числом. Выполнение опера­ции Р (s) задерживается, пока значение s не станет положительным, а затем оно уменьшает­ся. Выполнение операции V(s) увеличивает значение семафора. Таким образом, число за­вершенных операций Р в любой момент времени не больше, чем число завершенных опера­ций V плюс начальное значение s. Поэтому для реализации семафора необходимы способы подсчета операций Р и V и задержки операций Р. Кроме того, процессы, "разделяющие" се­мафор, должны взаимодействовать так, чтобы поддерживать инвариант семафора s >= О, даже если состояние программы является распределенным.

Эти требования можно соблюсти, если процессы будут рассылать сообщения о своем же­лании выполнить операции Р или v и по полученным сообщениям определять, когда можно продолжать. Для этого у каждого процесса должна быть локальная очередь сообщений mq и логические часы 1с, значение которых изменяется в соответствии с представленными выше



Глава 9. Модели взаимодействия процессов                                                                        351

правилами. Для имитации выполнения операций Р и V процесс рассылает сообщение всем пользовательским процессам, в том числе и себе. Сообщение содержит идентификатор про­цесса, дескриптор типа операции (POP или vop) и метку времени. Меткой времени каждой копии сообщения является текущее значение часов 1с.

Получив сообщение pop или VOP, процесс сохраняет его в своей очереди mq. Эта очередь поддерживается отсортированной в порядке возрастания меток времени сообщений; сооб­щения с одинаковыми метками сортируются по идентификаторам отославших их процессов. Допустим пока, что каждый процесс получает все сообщения в порядке их рассылки и воз­растания их меток времени. Тогда каждый процесс будет точно знать порядок передачи со­общений POP и VOP, сможет подсчитать количество соответствующих операций Р и v и под­держивать истинным инвариант семафора.

К сожалению, операция broadcast не является неделимой. Сообщения, разосланные двумя разными процессами, могут быть получены другими процессами в разных порядках. Более того, сообщение с меньшей меткой времени может быть получено после сообщения с большей меткой. Однако разные сообщения, разосланные одним и тем же процессом, будут получены другими процессами в порядке их рассылки этим процессом, и у сообщений будут возрастающие метки времени. Эти свойства следуют из таких фактов: 1) выполнение опера­ции broadcast — это то же, что параллельное выполнение операций send, которое, как мы считаем, обеспечивает упорядоченную и надежную доставку сообщения, 2) процесс увеличи­вает значение своих логических часов после каждого события взаимодействия.

То, что последовательные сообщения имеют возрастающие метки времени, дает нам способ принятия синхронизирующих решений. Предположим, что очередь сообщений процесса mq со­держит сообщение m с меткой времени ts. Тогда, как только процесс получит сообщение с большей меткой времени от любого другого процесса, он гарантированно уже никогда не уви­дит сообщения с меньшей меткой времени.


В этот момент сообщение m становится полностью подтвержденным. Кроме того, если сообщение m полностью подтверждено, то и все сообщения, находящиеся перед ним в очереди mq, тоже полностью подтверждены, поскольку их метки вре­мени еще меньше. Поэтому часть очереди mq, содержащая полностью подтвержденные сообще­ния, является стабильным префиксом: в нее никогда не будут вставлены новые сообщения.

При каждом получении сообщения POP или VOP процесс должен рассылать подтвер­ждающее сообщение (дек), чтобы его получили все процессы. Сообщения АСК имеют обыч­ные метки времени, но не добавляются в очереди сообщений процессов. Их используют про­сто для того, чтобы определить момент полного подтверждения обычного сообщения из оче­реди mq. (Если не использовать сообщений АСК, процесс не сможет определить, что сообщение полностью подтверждено, пока не получит более поздних сообщений POP или VOP от всех остальных процессов. Это замедлит работу алгоритма и приведет к блокировке, если какой-нибудь пользователь не захочет выполнить операции Р или V.)

Чтобы реализация распределенных семафоров была завершенной, каждый процесс ис­пользует локальную переменную s для представления значения семафора. Получая сообще­ние аск, процесс обновляет стабильный префикс своей очереди сообщений mq. Для каждого сообщения VOP процесс увеличивает значение s и удаляет это сообщение. Затем процесс просматривает сообщения POP в порядке возрастания меток времени. Если s > 0, процесс уменьшает значение s и удаляет сообщение POP. Таким образом, каждый процесс поддержи­вает истинность следующего предиката, который является инвариантом цикла процесса.

DSEM-.   s  >= 0 л mq упорядочена по меткам времени в сообщениях

Сообщения POP обрабатываются в порядке их появления в стабильном префиксе, чтобы все процессы принимали одинаковые решения о порядке завершения операций Р. Хотя процес­сы могут находиться на разных стадиях обработки сообщений POP и VOP, все они обрабаты­вают полностью подтвержденные сообщения в одном и том же порядке.



352                                                                            Часть 2. Распределенное программирование

Алгоритм распределенных семафоров представлен в листинге 9.11. Пользовательские про­цессы — это обычные прикладные процессы. У каждого пользователя есть один вспомогатель­ный процесс; вспомогательные процессы взаимодействуют друг с другом для реализации опера­ций р и V. Пользовательский процесс инициирует операцию Р или V, связываясь со своим вспо­могательным процессом (помощником). Выполняя операцию Р, пользователь ждет, пока его помощник не разрешит ему продолжать. Каждый помощник рассылает сообщения POP, VOP и аск другим помощникам и управляет локальной очередью сообщений по описанному выше алгоритму. Все сообщения для помощников передаются или рассылаются по массиву каналов se-mop. Для добавления метки времени к сообщениям все процессы поддерживают локальные часы.



Глава 9. Модели взаимодействия процессов                                                                            353

Распределенные семафоры можно использовать для синхронизации процессов в распре­деленных программах точно так же, как и обычные семафоры в программах с разделяемыми переменными (глава 4). Например, их можно использовать для решения таких задач взаим­ного исключения, как блокировка файлов или записей базы данных. Можно использовать тот же базовый подход (рассылка сообщений и упорядоченные очереди) для решения других за­дач; некоторые из них описаны в исторической справке и упражнениях.

Если алгоритмы рассылки используются для принятия синхронизирующих решений, в этом должны участвовать все процессы. Например, процесс должен "услышать" все осталь­ные процессы, чтобы определить, когда сообщение полностью подтверждается. Это значит, что алгоритмы рассылки не очень хорошо масштабируются для взаимодействия большого числа процессов и их нужно модифицировать, чтобы сделать устойчивыми к ошибкам.

Алгоритмы типа "зонд-эхо"

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

Поиск в глубину (Depth-first search — DPS) — один из классических алгоритмов последо­вательного программирования для обхода всех узлов дерева или графа. Стратегия DFS в дере­ве-для каждого узла дерева посетить его узлы-сыновья и после этого вернуться к родитель­скому узлу. Этот вид поиска называется "поиск в глубину", поскольку каждый путь поиска сначала доходит вниз до узла-листа и лишь затем поворачивает; например, первым будет пройден путь от корня дерева к его крайнему слева листу. В графе общего вида, у которого могут быть циклы, используется тот же подход, нужно только помечать уже пройденные уз­лы, чтобы проходить по ребрам, выходящим из узла, только по одному разу.

В этом разделе описана парадигма (модель) "зонд-эхо" для распределенных вычислений в гра­фах. Зонд — это сообщение, передаваемое узлом своему преемнику; эхо — последующий ответ. По­скольку процессы выполняются параллельно, зонды передаются всем преемникам также парал­лельно. Модель "зонд-эхо", таким образом, является параллельным аналогом модели DFS. Сна­чала модель зонда будет проиллюстрирована на примере рассылки информации всем узлам сети. Затем при разработке алгоритма построения топологии сети будет добавлено понятие эха.

344                                                                            Часть 2. Распределенное программирование

9.4.1. Рассылка сообщений в сети

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

Предположим, что один узел-источник S должен разослать сообщение всем узлам сети. (Точнее, процессу, выполняемому на узле S, нужно разослать сообщение процессам, выпол­няемым на всех остальных узлах.) Например, на узле s может выполняться сетевой управляю­щий процесс, которой должен передать новую информацию о состоянии всем остальным узлам.

Если все остальные узлы являются соседями S, рассылка сигнала реализуется тривиально: узел S должен просто напрямую отправить сообщение каждому узлу. Однако в больших сетях узел обычно имеет лишь небольшое количество соседей. Узел S может послать сообщение со­седям, а они в свою очередь должны будут передать его своим соседям и так далее. Итак, нам нужен способ рассылки зонда всем узлам.

Предположим, что узел S имеет локальную копию топологии сети. (Позже будет показа­но, как ее вычислить.) Топология представлена симметричной матрицей логических значе­ний, ее элемент topology [ i, j ] имеет значение "истина", если узлы i и j соединены, и "ложь" — в противном случае.

Для эффективной рассылки сообщения узел S должен сначала создать остовное дерево се­ти с собой в качестве корня этого дерева. Остовное дерево графа — это дерево, в которое вхо­дят все узлы графа, а ребра образуют подмножество ребер графа. На рис. 9.2 показан пример такого дерева; узел S находится слева. Сплошными линиями обозначены ребра остовного де­рева, а пунктирными — остальные ребра графа.



По данному остовному дереву t узел S может разослать сообщение т, передав его вместе с t всем своим сыновним узлам. Получив сообщение, каждый узел просматривает дерево t, чтобы определить свои сыновние узлы, после чего передает им всем сообщение m и дерево t. Остовное дерево передается вместе с сообщением т, поскольку иначе все узлы, кроме S, не будут знать, какое дерево использовать. Полный алгоритм приведен в листинге 9.7. Посколь­ку t — остовное дерево, в конце концов сообщение попадет во все узлы. Кроме того, каждый узел получит сообщение только один раз от своего родительского узла в дереве t. Для запуска рассылки сообщения используется отдельный процесс initiator в узле S, благодаря чему процессы Node на всех узлах идентичны.





346                                                                           Часть 2. Распределенное программирование

По алгоритму рассылки с помощью остовного дерева передается п-1 сообщений — по од­ному на каждое ребро между родительским и сыновним узлами остовного дерева.


По алгорит­му, использующему множества соседей, через каждую связь сети нужно передать два сообще­ния, по одному в каждом направлении. Точное число сообщений зависит от топологии сети, но в общем случае оно будет намного больше, чем п-1. Например, если топология сети представ­ляет собой дерево, в корне которого находится узел-источник, будут переданы 2 (п-1) сообще­ний. Для полного графа, в котором есть связи между всеми узлами, потребуется п (п-1) со­общений. Однако в алгоритме с множествами соседей узлу-источнику не нужно знать тополо­гию сети или строить остовное дерево. По существу, остовное дерево строится динамически, оно состоит из связей, по которым проходят первые копии сообщения т. Кроме того, в этом алго­ритме сообщения короче, поскольку в каждом из них не нужно передавать остовное дерево.

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

9.4.2. Построение топологии сети

Для применения эффективного алгоритма рассылки сообщений (см. листинг 9.7) необхо­димо заранее знать топологию сети. Здесь показано, как ее построить. Вначале каждому узлу известна лишь его локальная топология, т.е. связи с соседями. Задача в том, чтобы собрать воедино все локальные топологии, поскольку их объединение является общей топологией сети.

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


Затем он мо­жет, например, построить остовное дерево и разослать топологию всем остальным узлам.

Вначале предположим, что топология сети ациклична. Сеть является неориентированным графом, поэтому ее структура — дерево. Пусть узел S — это корень дерева и инициирующий узел. Тогда топологию можно собрать следующим образом. Сначала узел S передает зонды всем своим сыновним узлам. Когда эти узлы получают зонд, они передают его своим сынов­ним узлам и т.д. Таким образом, зонды распространяются по всему дереву и в конце концов достигают его листьев. Поскольку у листьев нет сыновних узлов, начинается фаза эха. Каж­дый лист отсылает эхо, содержащее множество соседних узлов, своему родительскому узлу. После получения эха от всех сыновей узел объединяет эти ответы со своим собственным множе­ством соседей и передает полученные данные своему родительскому узлу. В конце концов кор­невой узел получит эхо от каждого из своих сыновей. Объединение этих данных будет содержать всю топологию сети, поскольку начальный сигнал достигнет каждого узла, а каждый эхо-ответ содержит множество, состоящее из отвечающего узла, всех его соседей и их потомков.

Полный алгоритм "зонд-эхо" для^ сбора топологии сети в дереве приведен в листинге 9.9. Фаза зонда, по существу, является алгоритмом рассылки сообщения из листинга 9.8, за ис­ключением того, что сообщения-зонды идентифицируют отправителя. Фаза эха возвращает информацию о локальной топологии вверх по дереву. Алгоритмы узлов не вполне симмет­ричны, поскольку экземпляр процесса Nodetp], выполняемый в узле S, должен знать, что нужно отослать эхо процессу-инициатору.

Листинг 9.9. Алгоритм "зонд-эхо" для сбора топологии дерева

type graph = bool [n,n];

chan probe[n](int sender);

chan echo[n](graph topology)    # фрагменты топологии



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


Однако, поскольку в сети есть циклы, а узлы работают параллельно, два соседа могут отослать зонды друг другу почти одновременно. На все зонды, кроме первого, эхо может быть отправ­лено немедленно. Если узел получает последующие зонды во время ожидания эха, он сразу отсылает эхо с пустой топологией (этого достаточно, поскольку локальные связи узла будут содержаться в эхе-ответе на первый зонд). В конце концов узел получит эхо в ответ на каж­дый зонд и передает эхо узлу, от которого получил первый зонд. Эхо содержит объединение данных о связях узла вместе со всеми остальными полученными данными.

Обобщенный алгоритм "зонд-эхо" построения топологии сети показан в листинге 9.10. Поскольку узел может получать последующие зонды во время ожидания эха, в один канал объединяются два типа сообщений. (Если бы они приходили по разным каналам, узлу нужно было использовать оператор empty и проводить опрос, чтобы решить, какой тип сообщения принять. Можно было бы использовать рандеву, выделив зонды и эхо в отдельные операции.) Корректность алгоритма вытекает из следующих фактов. Поскольку сеть является связ­ной, каждый узел рано или поздно получит зонд. Взаимоблокировка не возникает, поскольку на каждый зонд посылается эхо-ответ (на первый зонд — перед завершением процесса Node, на остальные — сразу после их получения). Это позволяет избежать буферизации исходящих сообщений в каналах probe_echo. Последнее эхо, переданное узлом, содержит локальный набор соседей. Следовательно, объединение множеств соседей в конце концов достигает процесса Node [ S ], передающего топологию процессу initiator. Как и в листинге 9.8, свя­зи, по которым проходят первые зонды, образуют динамически создаваемое остовное дерево. Топология сети возвращается вверх по остовному дереву; эхо от каждого узла содержит топо­логию поддерева, корнем которого является этот узел.

Асинхронная передача сообщений

В этом разделе представлены две реализации асинхронной передачи сообщений. В первой из них к ядру для разделяемой памяти из главы 6 добавлены каналы и примитивы передачи сооб­щений. Эта реализация подходит для работы на одном процессоре или на мультипроцессоре с раз­деляемой памятью. Во второй реализации ядро с разделяемой памятью дополнено до распределен­ного ядра, которое может работать в многопроцессорной системе или в сети из отдельных машин.

10.1.1. Ядро для разделяемой памяти

Каждый канал программы представлен в ядре дескриптором канала. Дескриптор канала содержит заголовки списков сообщений и заблокированных процессов. В списке сообщений находятся сообщения, поставленные в очередь; в списке блокированных процессов — про­цессы, ожидающие получения сообщений. Хотя бы один из этих списков всегда пуст, по­скольку, если есть доступное сообщение, процесс не блокируется, а если есть заблокирован­ный процесс, то сообщения не ставятся в очередь.

Дескриптор создается с помощью примитива ядра createChan, который вызывается по одному разу для каждой декларации chan в программе до создания процессов. Массив кана­лов создается либо вызовом примитива createChan для каждого элемента, либо одним вы­зовом примитива createChan с параметром, указывающим размер массива. Примитив cre­ateChan возвращает имя (индекс или адрес) дескриптора.

376                                                                            Часть 2. Распределенное программирование

Оператор send реализован с помощью примитива sendChan. Сначала процесс-отправитель вычисляет выражения и собирает значения в единое сообщение, которое обычно записывает в стек выполнения процесса, передающего сообщение. Затем вызывается примитив sendChan; его аргументами являются имя канала (возвращенное из вызова createChan) и само сообще­ние. Примитив sendChan сначала находит дескриптор канала. Если в списке заблокированных процессов есть хотя бы один процесс, то оттуда удаляется самый старый процесс, а сообщение копируется в его адресное пространство.
После этого дескриптор процесса помещается в список готовых к работе. Если заблокированных процессов нет, сообщение необходимо сохранить в списке сообщений дескриптора, поскольку передача является неблокирующей операцией, и, следовательно, отправителю нужно позволить продолжать выполнение.

Пространство для сохраненного сообщения можно выделять динамически из единого буферного пула, или с каждым каналом может быть связан отдельный коммуникационный буфер. Однако асинхронная передача сообщений поднимает важный вопрос реализации: что, если пространство ядра исчерпано? У ядра есть два выхода: либо остановить выполне­ние программы из-за переполнения буфера, либо заблокировать передающий процесс, по­ка не появится достаточно места.

Остановка программы — это решительный шаг, поскольку свободное пространство может вскоре и появиться, но программист сразу получает сигнал о том, что сообщения производятся быстрее, чем потребляются (это обычно говорит об ошибке). С другой сто­роны, блокировка передающего процесса нарушает неблокирующую семантику оператора send и усложняет ядро, создавая дополнительный источник блокировок. И здесь автор па­раллельной программы не может ничего предполагать о скорости и порядке выполнения процессов. Ядра операционных систем блокируют отправителей сообщений и при необхо­димости выгружают заблокированные процессы из памяти в файл подкачки, поскольку должны избегать отказов системы. Однако для языков программирования высокого уровня приемлемым выбором является остановка программы.

Оператор receive реализуется с помощью примитива receiveChan. Его аргументами являются имя канала и адрес буфера сообщений. Действия примитива receiveChan дуаль­ны действиям примитива sendChan. Сначала ядро находит дескриптор, соответствующий выбранному каналу, затем проверяет его список сообщений. Если список не пуст, первое сооб­щение из него удаляется и копируется в буфер сообщений получателя. Если список сообщений пуст, процесс-получатель добавляется в список заблокированных процессов.


Получив сообще­ние, процесс- адресат распаковывает сообщение из буфера в соответствующие переменные.

Четвертый примитив, emptyChan, используется для реализации функции empty (ch). Он просто находит дескриптор и проверяет, не пуст ли список сообщений. В действительно­сти структуры данных ядра находятся не в защищенной области, и выполняемый процесс может сам проверять свой список сообщений. Критическая секция не нужна, поскольку про­цессу нужно просмотреть только заголовок списка сообщений.

В листинге 10.1 показаны схемы всех четырех примитивов. Эти примитивы добавлены к однопроцессорному ядру (см. листинг 6.1). Значением executing является адрес дескрип­тора процесса, выполняемого в данный момент, a dispatcher — это процедура, планирую­щая работу процессов на данном процессоре. Действия примитивов sendChan и re­ceiveChan очень похожи на действия примитивов Р и V в семафорном ядре (см. лис­тинг 6.4). Основное отличие состоит в том, что дескриптор канала содержит список сообщений, тогда как дескриптор семафора — только его значение.

Ядро в листинге 10.1 можно изменить для работы на мультипроцессоре с разделяемой памятью, используя методику, описанную в разделе 6.2. Основное требование состоит в том, что структуры данных ядра нужно хранить в памяти, доступной всем процессорам, а для защиты критических секций кода ядра, дающих доступ к разделяемым данным, ис­пользовать блокировки.

10.1.2. Распределенное ядро

Покажем, как для поддержки распределенного выполнения расширить ядро с разделяе­мой памятью. Главная идея — дублировать ядро, помещая по одной его копии на каждую ма­шину, и обеспечить взаимодействие копий с помощью сетевых примитивов.

В распределенной программе каждый канал хранится на отдельной машине. Предполо­жим пока, что у канала может быть сколько угодно отправителей и только один получатель. Тогда дескриптор канала было бы логично поместить на ту же машину, на которой выполня­ется получатель. Процесс, выполняемый на этой машине, обращается к каналу так же, как



378                                                                            Часть 2. Распределенное программирование

и при использовании ядра с разделяемой памятью. Но процесс, выполняемый на другой ма­шине, не может обращаться к каналу напрямую; для этого должны взаимодействовать два яд­ра, выполняемых на этих машинах. Ниже будет описано, как изменить ядро с разделяемой памятью и как для реализации распределенной программы использовать сеть.

На рис. 10.1 показана структура распределенного ядра. Ядро, выполняемое на каждой машине, содержит дескрипторы каналов и процессы, расположенные на данной машине. Как и раньше, в каждом ядре есть обработчики локальных прерываний для вызовов супервизора (внутренние ловушки), таймеры и устройства ввода-вывода. Сеть связи является особым ви­дом устройства ввода-вывода. Таким образом, в каждом ядре есть обработчики прерывания сети и процедуры, которые читают из сети и записывают в нее.



В качестве конкретного примера рассмотрим типичный доступ в сети Ethernet. Контрол­лер Ethernet состоит из двух независимых частей (для записи и для чтения). С каждой из этих частей в ядре связан обработчик прерывания. Прерывание записи устанавливается, когда операция записи завершается; сам контроллер следит за доступом к сети. Прерывание чтения устанавливается на процессоре, получающем по сети сообщение.

Примитив ядра, выполняемый в результате вызова из прикладного процесса, при переда­че сообщения на другую машину вызывает процедуру ядра netWrite. Она имеет три аргу­мента: процессор назначения, вид сообщения (см. ниже) и само сообщение. Сначала проце­дура netWrite получает буфер, форматирует сообщение и записывает его в буфер. Затем, ес­ли записывающая часть сетевого контроллера свободна, инициируется запись; в противном случае буфер добавляется в очередь запросов на запись. В обоих случаях происходит выход из netWrite. Позже при возникновении прерывания записи связанный с ним обработчик ос­вобождает буфер сообщения, которое только что было записано.


Если очередь записи не пус­та, обработчик прерывания инициирует следующую сетевую запись.

Ввод из сети обычно обрабатывается в обратном порядке. Когда к ядру приходит сообще­ние, вызывается обработчик прерывания чтения из сети. Сначала он сохраняет состояние выполняющегося процесса, затем выделяет новый буфер для следующего входного сетевого сообщения. Наконец обработчик чтения распаковывает первое поле сообщения, чтобы опре­делить его вид, и вызывает соответствующий виду примитив ядра."

В листинге 10.2 схематически представлены процедуры сетевого интерфейса. К ним отно­сятся обработчики сетевых прерываний и процедура netWrite. Обработчик пе-

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



;

Для простоты предполагается, что передача по сети происходит без ошибок, и, следова­тельно, не нужно подтверждать получение сообщений или передавать их заново. Также игно­рируется проблема исчерпания области буфера для входящих или исходящих сообщений. На практике для ограничения числа сообщений в буфере используется управление потоком. Ссылки на литературу, в которой описаны эти темы, даны в исторической справке.

Канал может храниться локально или удаленно, поэтому его имя должно состоять из двух полей: номера машины и индекса или смещения. Номер машины указывает, где хранится де-

380                                                                            Часть 2 Распределенное программирование

скриптор; индекс определяет положение дескриптора в ядре указанной машины. Примитив createChan также нужно дополнить аргументом, указывающим, на какой машине нужно создать канал.


Выполняя примитив createChan, ядро сначала проверяет этот аргумент. Ес­ли канал находится на той же машине, ядро создает канал (как в листинге 10.1). В противном случае ядро блокирует выполняемый процесс и передает на удаленную машину сообщение create_chan. Это сообщение содержит идентификатор выполняемого процесса. В конце концов локальное ядро получит сообщение chan_done, которое говорит о том, что на уда­ленной машине канал создан. Сообщение содержит имя канала и указывает процесс, для ко­торого создан канал. Как показано в листинге 10.2, обработчик netRead_handler, получая это сообщение, вызывает еще один примитив ядра, chanDone, который снимает блокировку процесса, запросившего создание канала, и возвращает ему имя созданного канала.

Демон ядра на другой стороне сети, получив сообщение create_chan, вызывает примитив remoteCreate. Этот примитив создает канал и возвращает сообщение CHAN_DONE первому ядру. Таким образом, при создании канала на удаленной машине выполняются следующие шаги.

•    Прикладной процесс вызывает локальный примитив createChan.

•    Локальное ядро передает сообщение create_chan удаленному ядру.

•    Обработчик прерывания чтения в удаленном ядре получает это сообщение и вызывает примитив remoteCreate удаленного ядра.

•    Удаленное ядро создает канал и передает сообщение CHAN_DONE локальному ядру.

•    Обработчик прерывания чтения в локальном ядре получает это сообщение и вызывает примитив chanDone, запускающий прикладной процесс.

В распределенном ядре нужно также изменить примитив sendChan. Примитив send-Chan здесь будет намного проще, чем createChan, поскольку операция передачи send яв­ляется асинхронной. В частности, если канал находится на локальной машине, примитив sendChan должен выполнить такие же операции, как в листинге 10.1. Если канал находится на удаленной машине, примитив sendChan передает на эту машину сообщение SEND. В этот момент выполняемый процесс может продолжить работу. Получив сообщение SEND, удален­ное ядро вызывает примитив remoteSend, который, по существу, выполняет те же действия, что и (локальный) примитив sendChan.


Его отличие состоит лишь в том, что входящее со­общение уже записано в буфер, поэтому ядру не нужно выделять для него новый буфер.

В листинге 10.3 схематически представлены примитивы распределенного ядра. Примити­вы receiveChan и emptyChan по сравнению с листингом 10.1 не изменились, поскольку у каждого канала есть только один получатель, причем расположенный на той же машине, что и канал. Однако если это не так, то для взаимодействия машины, на которой был вызван примитив receiveChan или empty, и машины, на которой расположен канал, нужны до­полнительные сообщения. Это взаимодействие аналогично взаимодействию при создании канала — локальное ядро передает сообщение удаленному ядру, которое выполняет прими­тив и возвращает результаты локальному ядру.





10.2. Синхронная передача сообщений

Напомним, что при синхронной передаче сообщений примитивы send и receive явля­ются блокирующими: пытаясь взаимодействовать, процесс должен сначала подождать, пока

382                                                                        Часть 2. Распределенное программирование

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

Ниже будет показано, как реализовать синхронную передачу сообщений с помощью асинхронной, а затем — как реализовать операторы ввода, вывода и защищенные операторы взаимодействия библиотеки CSP, используя специальный учетный процесс (clearinghouse process). Вторую реализацию можно адаптировать для реализации пространства кортежей Linda (см. раздел 7.7). В исторической справке в конце главы даны ссылки на децентрализо­ванные реализации; см. также упражнения.

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

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


Например, исходный процесс S передает сообщение процессу назначения D, выполняя операцию

synch_send(D, expressions);

Процесс назначения ждет получения сообщения из любого источника при выполнении опе­ратора

synch_receive(source,   variables);

Когда процессы доходят до выполнения этих операторов, идентификатор отправителя и зна­чения выражений передаются в виде сообщения от процесса S процессу D. Затем эти данные записываются в переменные source и variables соответственно. Получатель, таким обра­зом, узнает идентификатор отправителя сообщения.

Описанные примитивы можно реализовать с помощью асинхронной передачи сообще­ний, используя три массива каналов: sourceReady, destReady и transmit. Первые два массива используются для обмена управляющими сигналами, а третий — для передачи дан­ных. Каналы используются, как показано в листинге 10.4. Процесс-получатель ждет сообще­ния из своего элемента массива sourceReady; сообщение идентифицирует отправителя. За­тем получатель разрешает отправителю продолжить передачу, и передается само сообщение.

Код в листинге 10.4 обрабатывает отправку в указанное место назначения и прием сооб­щения из любого источника. Если обе стороны должны всегда называть друг друга, то в лис­тинге 10.4 не нужны каналы sourceReady, а получатель может просто передавать отправи­телю сигнал о готовности к получению сообщения. Оставшихся операций передачи и приема вполне достаточно для синхронизации двух процессов. С другой стороны, если процесс-получатель может называть источник или принимать сообщения из любого источника, ситуа­ция становится намного сложнее. (Такая возможность есть в библиотеке MPI.) Тогда либо нужно иметь отдельный канал для каждого пути взаимодействия и опрашивать каналы, либо получающий процесс должен проверять каждое сообщение и сохранять те из них, которые он еще не готов принять. Читателю предоставляется задача изменить реализацию, чтобы она об­рабатывала описанную ситуацию (см. упражнения в конце главы).



Листинг 10.4. Синхронное взаимодействие с использованием асинхронных сообщений

разделяемые переменные:

chan sourceReady[n](int);              # готовность отправителя

chan destReady[n]();                        # готовность получателя

chan transmit[n](byte msg[*]);   # передача данных



10.2.2. Реализация защищенного взаимодействия с помощью учетного процесса

Вновь предположим, что есть n процессов, но они взаимодействуют и синхронизируются с помощью операторов ввода и вывода языка CSP (см. раздел 7.6). Напомним, что они имеют такой вид.

Source?port (переменные) ;                 # оператор ввода

Destination 'port (выражения) ;         #  оператор вывода

Эти операторы согласуются, когда процесс Destination выполняет оператор ввода, а про­цесс Source — оператор вывода, имена портов одинаковы, переменных и выражений поров­ну, и их типы совпадают.

В языке CSP также представлено защищенное взаимодействие с недетерминированным порядком. Напомним, что операторы защищенного взаимодействия имеют следующий вид. В;   С  ->  S;

Здесь В — необязательное логическое выражение (защита), С — оператор ввода или вывода, as— список операторов. Операторы защищенного взаимодействия используются внутри операторов i f или do для выбора из нескольких возможных взаимодействий.

Основное в реализации операторов ввода, вывода и защищенных операторов — объеди­нить в пары процессы, желающие выполнить согласованные операторы взаимодействия. Для подбора пар используется специальный "учетный процесс" СН ("clearinghouse"). Пусть обычный процесс Рг собирается выполнить оператор вывода, в котором про­цессом назначения является Р:, а процесс Р3 — операцию ввода с pj. в качестве источника. Предположим, что имя порта и типы сообщений совпадают. Эти процессы взаи­модействуют с учетным процессом и между собой, как показано на рис. 10.2. Каждый из процессов Рх и Р-, пере­дает учетному процессу СН сообщение, описывающее же­лаемое взаимодействие.


Процесс сн сначала сохраняет ;

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



384                                                                            Часть 2. Распределенное программирование

Чтобы уточнить программную структуру на рис. 10.2, нужен канал для каждого пути взаи­модействия. Один канал используется для сообщений от обычных процессов к учетному. Эти сообщения содержат шаблоны, описывающие возможные варианты согласованных операто­ров. Каждому обычному процессу для возвращения сообщений от учетного процесса нужен канал ответа. Наконец, нужен один канал данных для каждого обычного процесса, содержа­щего операторы ввода; такие каналы используются другими обычными процессами.

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

Доходя до выполнения операторов ввода, вывода или операторов защищенного взаимо­действия, обычные процессы передают учетному шаблоны. Эти шаблоны используются для подбора соответствующих пар операторов. Каждый шаблон имеет четыре поля. direction,   source,   destination,   port

Для операторов вывода поле направления (direction) имеет значение OUT, для операторов ввода— IN. Источник (source) и приемник (destination) — это идентификаторы отпра­вителя и желаемого получателя (для вывода) или желаемого отправителя и получателя (для ввода).


Поле порт (port) содержит целое число, которое однозначно определяет порт и, сле­довательно, типы данных операторов ввода и вывода. Каждому типу порта в исходном тексте программы должен соответствовать определенный номер. Это значит, что каждому явному имени порта должно быть назначено уникальное целочисленное значение, как и для каждого безымянного порта. (Напомним, что имена портов используются в исходной программе, по­этому номера портов можно присвоить статически во время компиляции программы.)

Листинг 10.5 содержит объявления разделяемых типов данных и каналов взаимодействия, а также код, выполняемый обычными процессами при достижении операторов ввода и выво­да. Выполняя незащищенный оператор взаимодействия, процесс передает учетному процессу один шаблон и ждет ответа. Найдя согласующийся вызов (как описано ниже), учетный про­цесс передает ответ. Получив его, процесс-отправитель передает выражения оператора выво­да в процесс назначения, который записывает их в переменные своего оператора ввода.





Используя защищенный оператор взаимодействия, процесс сначала должен проверить каждую защиту. Для каждого истинного выражения защиты процесс создает шаблон и добав­ляет его в множество t. После вычисления всех выражений защиты процесс передает множе­ство t учетному процессу и ждет ответа. (Если t пусто, процесс просто продолжает работу.) Полученный ответ указывает процесс, выбранный для взаимодействия, и направление этого взаимодействия. Если направление OUT, процесс отсылает сообщение другому процессу, иначе ждет получения данных. После этого процесс выбирает соответствующий защищенный оператор и выполняет его. (Предполагается, что полей direction и who достаточно, чтобы определить, какой из операторов защищенного взаимодействия был выбран учетным процес­сом в качестве согласованного. В общем случае для этого нужны также порт и типы данных.)

В листинге 10.6 представлен учетный процесс СН. Массив pending содержит по одному набору шаблонов для каждого обычного процесса.


Если pending[i] не пусто, обычный процесс i блокируется в ожидании согласованного оператора взаимодействия. Получая но­вое множество t, процесс СН сначала просматривает один из шаблонов, чтобы определить, какой из процессов s передал его. (Если в шаблоне указано направление OUT, то источником является процесс s; если указано направление IN, то s —приемник.) Затем учетный процесс сравнивает элементы множества t с шаблонами в массиве pending, чтобы увидеть, есть ли согласование. По способу своего создания два шаблона являются согласованными, если их направления противоположны, а порты и источник с приемником одинаковы. Если СН нахо­дит соответствие с некоторым процессом i, он отсылает ответы процессам s и i (в ответах каждому процессу сообщаются идентификатор другого процесса и направление взаимодейст­вия). В этом случае процесс СН очищает элемент pending [ i ], поскольку процесс i больше не заблокирован. Не найдя соответствия ни для одного шаблона во множестве t, процесс СН сохраняет t в элемент pending [s], где s — передающий процесс.

Листинг 10.6. Централизованный учетный процесс

# декларации глобальных типов и канале, как в листинге 10.5 process СН {



Глава 10 Реализация языковых механизмов                                                                             387

ловии, что в программе не может быть взаимных блокировок. Пусть элемент, с которого начинает­ся поиск, указывается значением целочисленной переменной start. Получая новый набор шаб­лонов, процесс СН сначала просматривает элемент pending [ s tart ], затем pending [ s tart+1 ] и т.д. Как только процесс start получает шанс взаимодействия, учетный процесс СН увеличивает значение переменной start до индекса следующего процесса с непустым множеством ожидания. Тогда значение переменной s tar t будет циклически проходить по индексам процессов (при усло­вии, что процесс start не блокируется навсегда). Таким образом, каждый процесс периодически будет получать шанс быть проверенным первым.

Барьерная синхронизация

Многие задачи можно решить с помощью итерационных алгоритмов, которые последова­тельно вычисляют приближения к решению и завершаются, когда получен окончательный ответ или достигнута заданная точность вычислений (как во многих численных методах). Обычно такие алгоритмы работают с массивами чисел, и на каждой итерации одни и те же действия выполняются над всеми элементами массива. Следовательно, для синхронного па­раллельного вычисления отдельных частей решения можно использовать параллельные про­цессы. Мы уже видели несколько примеров такого рода; гораздо больше их представлено в следующем разделе и дальнейших главах.

Основным свойством большинства параллельных итерационных алгоритмов является за­висимость результатов каждой итерации от результатов предыдущей. Один из способов по­строить такой алгоритм — реализовать тело каждой итерации, используя операторы со. Если не учитывать завершимость и считать, что на каждой итерации выполняется 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, поскольку каждый из них ссылается только на одну разделяемую переменную. В процессе Coordina­tor для ожидания установки всех элементов arrive можно использовать оператор for. По­скольку для продолжения процессов Worker должны быть установлены все элементы ar­rive, процесс 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) должен Coordi­nator. В соответствии со вторым правилом один процесс не устанавливает флаг, пока он не сброшен другим. В противном случае, если другой синхронизируемый процесс в дальнейшем ожидает повторной установки флага, возможна взаимная блокировка.


В (3.13) это означает, что Coordinator должен сбросить arrive [i] перед установкой continue [i]. Coordi­nator может сделать это, выполнив еще один оператор for после первого for в (3.13). Co­ordinator может также сбросить arrive [i] сразу после того, как дождался его установки. Добавив код сброса флагов, получим барьер с управляющим (листинг 3.12).



Хотя в программе 3.12 барьерная синхронизация реализована так, что конфликты обра­щения к памяти исключаются, у данного решения есть два нежелательных свойства Во-первых, нужен дополнительный процесс. Синхронизация с активным ожиданием эффектив­на, если только каждый процесс выполняется на отдельном процессоре, так что процессу Co­ordinator нужен свой собственный процессор. Но, возможно, было бы лучше использовать этот процессор для другого рабочего процесса.

Второй недостаток использования управляющего процесса состоит в том, что время вы­полнения каждой итерации процесса 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 приходит к первому уровню и устанавливает флаг ar­rive [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. Программирование с разделяемыми переменными

Подведем итог темы барьеров. Наиболее прост и удобен для небольшого числа процессов барьер-счетчик, но при условии, что существует неделимая инструкция "извлечь и сложить". Симметричный барьер наиболее эффективен для машин с разделяемой памятью, поскольку все процессы выполняют один и тот же код, а в идеальном случае — с одинаковой скоростью. (На машинах с распределенной памятью часто более эффективным является барьер с древо­видной структурой, сокращающий взаимодействие между процессами.) При любой структуре барьера основная задача — избежать состояния гонок.Это достигается с помощью либо мно­жества флагов (по одному на каждый уровень), либо возрастающих счетчиков.

Библиотеки параллельного программирования

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

При создании программ с разделяемыми переменными на языке С обычно используют стандартную библиотеку Pthreads. При использовании обмена сообщениями стандартными считаются библиотеки MPI и PVM; обе они имеют широко используемые общедоступные реа­лизации, которые поддерживают как С, так и Фортран. ОрепМР является новым стандартом программирования с разделяемыми переменными, который реализован основными производите­лями быстродействующих машин. В отличие от Pthreads, ОрепМР является набором директив компилятора и подпрограмм, имеет связывание, соответствующее языку Фортран, и обеспечивает поддержку вычислений, параллельных по данным. Далее в разделе показано, как запрограммиро­вать метод итераций Якоби с помощью библиотек Pthreads и MPI, а также директив ОрепМР.

12.1.1. Учебный пример: Pthreads

Библиотека Pthreads была представлена в разделе 4.6, где рассматривались подпрограммы для использования потоков и семафоров. В разделе 5.5 были описаны и проиллюстрированы подпро­граммы для блокировки и условных переменных. Эти механизмы можно использовать и в про­грамме, реализующей метод итераций Якоби (листинг 12.1) и полученной непосредственно из программы с разделяемыми переменными (см. листинг 11.2). Как обычно в программах, исполь­зующих Pthreads, главная подпрограмма инициализирует атрибуты потока, читает аргументы из командной строки, инициализирует глобальные переменные и создает рабочие процессы. По­сле того как завершаются вычисления в рабочих процессах, главная программа выдает результаты.

Программа в листинге 12.2 содержит три функции: main, Coordinator и Worker. Пред­полагается, что выполняются все numWorkers+1 экземпляров программы. (Они запускаются с помощью команд, специфичных для конкретной версии MPI.) Каждый экземпляр начина­ется с выполнения подпрограммы main, которая инициализирует MPI и считывает аргумен­ты командной строки.
Затем в зависимости от номера (идентификатора) экземпляра из main шзывается либо управляющий процесс Coordinator, либо рабочий Worker.

Каждый процесс worker отвечает за полосу "точек. Сначала он инициализирует обе свои гетки и определяет своих соседей, left и right. Затем рабочие многократно обмениваются с соседями краями своих полос и обновляют свои точки. После numlters циклов обмена-обновления каждый рабочий отправляет строки своей полосы управляющему процессу, вы­числяет максимальную разность между парами точек на своей полосе и, наконец, вызывает MPl_Reduce, чтобы отправить mydiff управляющему процессу.

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

454                                                      Часть 3. Синхронное параллельное программирование

программу MPl_Reduce, чтобы получить и сократить максимальные разности, вычисленные каждым рабочим процессом. Заметим, что аргументы в вызовах MPi_Reduce одинаковы и в рабочих, и в управляющем процессах. Предпоследний аргумент COORDINATOR задает, что редукция должна происходить в управляющем процессе.

12.1.3. Учебный пример: ОрепМР

ОрепМР — это набор директив компилятора и библиотечных подпрограмм, используемых для выражения параллельности с разделением памяти. Прикладные программные интерфей­сы (APIs) для ОрепМР были разработаны группой, представлявшей основных производите­лей быстродействующего аппаратного и программного обеспечения. Интерфейс Фортрана был определен в конце 1997 года, интерфейс C/C++ — в конце 1998, но стандартизация обо­их продолжается. Интерфейсы поддерживают одни и те же функции, но выражаются по-разному из-за лингвистических различий между Фортраном, С и C++.

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


Директивы можно добавлять постепенно, поэтому ОрепМР обеспечивает распараллеливание существующего программного обеспечения. Эти свойства ОрепМР отличают ее от библиотек Pthread и MPI, которые содержат подпрограммы, вызываемые из последовательной программы и компонуе­мые с нею, и требуют от программиста вручную распределять работу между процессами.

Ниже описано и проиллюстрировано использование ОрепМР для Фортран-программ. Вначале представлена последовательная программа для метода итераций Якоби. Затем в нее добавлены директивы ОрепМР, выражающие параллельность. В конце раздела кратко описа­ны дополнительные директивы и интерфейс C/C++.

В листинге 12.3 представлен эскиз последовательной программы для метода итераций Яко­би. Ее синтаксис своеобразен, поскольку программа написана с использованием соглашений Фортрана по представлению данных с фиксированной точкой. Строки с комментариями начи­наются с буквы с в первой колонке, а декларации и операторы — с колонки 7. Дополнительные комментарии начинаются символом !. Все комментарии продолжаются до конца строки.

Последовательная программа состоит из двух подпрограмм: main и jacobi. В подпро­грамме main считываются значения п (размер сетки с границами) и maxiters (максимальное число итераций), а затем вызывается подпрограмма jacobi. Значения дан­ных хранятся в общей области памяти и, следовательно, неявно передаются из main в ja­cobi. Это позволяет jacobi распределять память для массивов grid и new динамически.

В подпрограмме jacobi реализован последовательный алгоритм, представленный выше влистинге 11.1. Основное различие между программами в листингах 12.3 и 11.1 обусловлено син­таксическим отличием псевдо-С от Фортрана. В Фортране нижняя граница каждой размерности массива равна 1, поэтому индексы внутренних точек матриц по строкам и столбцам принимают значения от 2 до п-1. Кроме того, Фортран сохраняет матрицы в памяти машины по столбцам, по­этому во вложенных циклах do сначала выполняются итерации по столбцам, а затем по строкам.



В ОрепМР используется модель выполнения "разветвление-слияние" (fork-join). Вначале существует один поток выполнения. Встретив одну из директив parallel, компилятор вставляет код, чтобы разделить один поток на несколько подпотоков. Вместе главный поток и подпотоки образуют так называемое множество рабочих потоков. Действительное количест­во рабочих потоков устанавливается компилятором (по умолчанию) или определяется поль­зователем — либо статически с помощью переменных среды (environment), либо динамиче­ски с помощью вызова подпрограммы из библиотеки ОрепМР.

Чтобы распараллелить программу с помощью ОрепМР, программист сначала определяет части программы, которые могут выполняться параллельно, например циклы, и окружает их директивами parallel и end parallel. Каждый рабочий поток выполняет этот код, обра­батывая разные подмножества в пространстве итераций (для циклов, параллельных по дан­ным) или вызывая разные подпрограммы (для программ, параллельных по задачам). Затем в программу добавляются дополнительные директивы для синхронизации потоков во время выполнения. Таким образом, компилятор отвечает за разделение потоков и распределение ра­боты между ними (в циклах), а программист должен обеспечить достаточную синхронизацию.

В качестве конкретного примера рассмотрим следующий последовательный код, в кото­ром внутренние точки grid и new инициализируются нулями.





Каждая директива компилятора начинается с ! $отр. Первая определяет начало параллель­ного цикла do. Вторая дополняет первую, что обозначено добавлением символа & к ! $отр. Во второй директиве сообщается, что во всех рабочих потоках n, grid и new являются разде­ляемыми переменными, a i и j — локальными. Последняя директива указывает на конец па­раллельного цикла do и устанавливает точку неявной барьерной синхронизации,

В данном примере компилятор разделит итерации внешнего цикла do (no j) и назначит их рабочим процессам некоторым способом, зависящим от реализации.


Чтобы управлять назначением, программист может добавить предложение schedule. В ОрепМР поддержи­ваются различные виды назначения, в том числе по блокам, по полосам (циклически) и динамически (портфель задач). Каждый рабочий поток будет выполнять внутренний цикл do (no i) для назначенных ему столбцов.

В листинге 12.4 представлен один из способов распараллеливания тела подпрограммы j acobi с использованием директив ОрепМР. Основной поток разделяется на рабочие пото­ки для инициализации сеток, как было показано выше. Однако maxdif f инициализируется в основном потоке. Инициализация maxdif f перенесена, поскольку ее желательно выпол­нить в одном потоке до начала вычислений максимальной погрешности. (Вместо этого мож­но было бы использовать директиву single, обсуждаемую ниже.)

После инициализации разделяемых переменных следует директива parallel, разде­ляющая основной поток на несколько рабочих. В следующих двух предложениях указано, ка­кие переменные являются общими, а какие — локальными. Каждый рабочий выполняет главный цикл. В цикл добавлены директивы do для указания, что итерации внешних циклов, обновляющие grid и new, должны быть разделены между рабочими. Окончания этих циклов обозначены директивами end do, которые также обеспечивают неявные барьеры.

После главного цикла (который завершается одновременно всеми рабочими) использует­ся еще одна директива do, чтобы максимальная погрешность вычислялась параллельно. В этом разделе maxdif f используется в качестве переменной редукции, поэтому к директиве do добавлено предложение reduction. Семантика переменной редукции такова, что каждое обновление является неделимым (в данном примере с помощью функции max). В действи­тельности ОрепМР реализует переменную редукции, используя скрытые переменные в каж­дом рабочем потоке; значения этих переменных "сливаются" неделимым образом в одно на неявном барьере в конце распараллеленного цикла.

Программа в листинге 12.4 иллюстрирует наиболее важные директивы ОрепМР.


Библио­ тека содержит несколько дополнительных директив для распараллеливания, синхронизации и управления рабочей средой (data environment). Например, для обеспечения более полного управления синхронизацией операторов можно использовать следующие директивы.

critical    Выполнить блок операторов как критическую секцию. atomic         Выполнить один оператор неделимым образом.

Глава 12. Языки, компиляторы, библиотеки и инструментальные средства                       457

s ingle        В одном рабочем потоке выполнить блок операторов. barrier      Выполнить барьер, установленный для всех рабочих потоков.

В ОрепМР есть несколько библиотечных подпрограмм для запросов к рабочей среде и управ­ления ею. Например, есть подпрограммы установки числа рабочих потоков и его динамиче­ского изменения, а также определения идентификатора потока.



458                                                      Часть 3 Синхронное параллельное программирование

Ключевое слово pragma обозначает директиву компилятора. Поскольку в С вместо циклов do для определенного количества итераций используются циклы for, эквивалентом дирек­тивы do в С является

pragma omp  for clauses.

В интерфейсе C/C++ нет директивы end. Вместо нее блоки кода заключаются в фигурные скобки, обозначающие область действия директив.

Блокировки и барьеры

_______________________________Глава 3

Блокировки и барьеры

Напомним, что в параллельных программах используются два основных типа синхрони­зации: взаимное исключение и условная синхронизация. В этой главе рассмотрены критиче­ские секции и барьеры, показывающие, как программировать эти типы синхронизации. За­дача критической секции связана с программной реализацией неделимых действий; эта зада­ча возникает в большинстве параллельных программ. Барьер — это точка синхронизации, оторой должны достигнуть все процессы перед тем, как продолжится выполнение одного из их. Барьеры необходимы во многих синхронных параллельных программах.

Взаимное исключение обычно реализуется посредством блокировок, которые защищают ритические секции кода. В разделе 3.1 определена задача критической секции и представле-ю крупномодульное решение, использующее оператор await для реализации блокировки. i разделе 3.2 разработаны мелкомодульные решения с использованием так называемых цик-ических блокировок (spin lock). В разделе 3.3 представлены три решения со справедливой тратегией: алгоритмы разрыва узла, билета и поликлиники. Эти разные решения иллюстри->уют различные подходы к решению данной задачи и имеют разные быстродействия и свой-:тва справедливости. Решения задачи критической секции также важны, поскольку их можно (спользовать для реализации операторов await и, следовательно, произвольных неделимых действий. Как это сделать, показано в конце раздела 3.2.

Во второй половине данной главы представлены три способа выполнения параллельных вычислений: барьерная синхронизация, алгоритмы, параллельные по данным, и так назы­ваемый портфель задач. Как было отмечено ранее, многие задачи можно решить синхронны­ми итерационными алгоритмами, в которых несколько идентичных процессов итеративно обрабатывают разделяемый массив. Алгоритмы этого типа называются алгоритмами, парал­лельными по данным, поскольку разделяемые данные обрабатываются параллельно и синхрон­но.
В таком алгоритме каждая итерация обычно зависит от результатов предыдущей итера­ции. Следовательно, в конце итерации более быстрый процесс должен ожидать более мед­ленные, чтобы начать следующую итерацию. Такой тип точки синхронизации называется барьером. В разделе 3.4 описываются различные способы реализации барьерной синхрониза­ции и обсуждается согласование их быстродействия. В разделе 3.5 приведено несколько при­меров алгоритмов, параллельных по данным и использующих барьеры, а также кратко описа­на архитектура синхронных мультипроцессоров (SIMD-машин), которые специально при­способлены для реализации алгоритмов, параллельных по данным. Поскольку SIMD-машины выполняют инструкции в блокированном шаге на каждом процессоре, они автома­тически реализуют барьеры после каждой машинной инструкции.

В разделе 3.6 представлен другой полезный метод выполнения параллельных вычислений, называемый портфелем задач. Этот подход можно использовать для реализации рекурсивного параллелизма и итерационного параллелизма при фиксированном числе независимых задач. Важное свойство парадигмы "портфель задач" состоит в том, что она облегчает сбалансиро­ванную загрузку, т.е. гарантирует, что все процессоры выполняют примерно равные объемы ра­боты. В парадигме "портфель задач" использованы блокировки для реализации "портфеля" ибарьероподобная синхронизация для определения того, что вычисления окончены.

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

88                                                Часть 1. Программирование с разделяемыми переменными

истинным. Достоинство синхронизации с активным ожиданием состоит в том, что для ее реализа­ции достаточно машинных инструкций современных процессоров. Активное ожидание неэффек­тивно при разделении процессора несколькими процессами (когда их выполнение перемежается), но, когда каждый процесс выполняется на отдельном процессоре, оно эффективно.


Многие годы для высокопроизводительных научных вычислений использовались большие мультипроцессоры. В настоящее время на рабочих станциях и даже на персональных компьютерах становятся обыч­ными небольшие мультипроцессоры (с двумя-четырьмя ЦПУ). Как будет показано в разде­ле 6.2, в ядре операционных систем для мультипроцессоров используется синхронизация с ак­тивным ожиданием. Более того, синхронизацию с активным ожиданием использует само аппа­ратное обеспечение — например, при передаче данных по шинам памяти и локальным сетям.

Библиотеки программ для мультипроцессорных машин включают процедуры для блоки­ровок и иногда для барьеров. Эти библиотечные процедуры реализуются с помощью методов, описанных в данной главе. Две такие библиотеки представлены в конце главы 4 (Pthreads) и главе 12 (ОрепМР).

3.1. Задача критической секции

Задача критической секции — это одна из классических задач параллельного программи­рования. Она стала первой всесторонне изученной проблемой, но интерес к ней не угасает, '• поскольку критические секции кода есть в большинстве параллельных программ. Кроме того, решение этой задачи можно использовать для реализации произвольных операторов await. В данном разделе задача определена и разработано ее крупномодульное решение. В следую­щих двух разделах построены мелкомодульные решения, иллюстрирующие различные спосо­бы решения этой задачи с использованием разных типов машинных инструкций.

В задаче критической секции n процессов многократно выполняют сначала критическую, а затем некритическую секцию кода. Критической секции предшествует протокол входа, а следует за ней протокол выхода. Таким образом, предполагается, что процесс имеет следующий вид: process  CS[i  =   1  to n]   { while   (true)   { протокол входа; критическая секция; протокол выхода; некритическая секция; } }

Каждая критическая секция является последовательностью операторов, имеющих доступ к некоторому разделяемому объекту. Каждая некритическая секция — это еще одна последо­вательность операторов.


Предполагается, что процесс, вошедший в критическую секцию, обязательно когда- нибудь из нее выйдет; таким образом, процесс может завершиться только вне критической секции. Наша задача— разработать протоколы входа и выхода, которые удовлетворяют следующим четырем свойствам.

(3.1)    Взаимное исключение. В любой момент времени только один процесс может выполнять свою критическую секцию.

(3.2)    Отсутствие взаимной блокировки (живая блокировка). Если несколько процессов пыта­ются войти в свои критические секции, хотя бы один это осуществит.

(3.3)    Отсутствие излишних задержек. Если один процесс пытается войти в свою критиче­скую секцию, а другие выполняют свои некритические секции или завершены, перво­му процессу разрешается вход в критическую секцию.

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

Глава 3 Блокировки и барьеры                                                                                        

Первые три свойства являются свойствами безопасности, четвертое — свойством живучести. Для взаимного исключения плохим является состояние, когда два процесса находятся в своих критических секциях. Для отсутствия взаимной блокировки плохим является состояние, ко­гда все процессы ожидают входа, но ни один не может этого сделать. (В решении с активным ожиданием это называется отсутствием живой блокировки, поскольку процессы работают, но навсегда зациклены.) Для отсутствия излишних задержек плохим является состояние, когда один-единственный процесс, пытающийся войти в критическую секцию, не может этого сде­лать, даже если все остальные процессы находятся вне критических секций. Возможность входа является свойством живучести, поскольку зависит от стратегии планирования (об этом ниже).

Тривиальный способ решения задачи критической секции состоит в ограничении каждой кри­тической секции угловыми скобками, т.е. в использовании безусловных операторов await. Из се­мантики угловых скобок сразу следует условие (3.2) — взаимное исключение.


Другие три свойства будут удовлетворяться при безусловно справедливой стратегии планирования, поскольку она га­рантирует, что процесс, который пытается выполнить неделимое действие, соответствующее его критической секции, в конце концов это сделает, независимо от действий других процессов. Одна­ко при таком "решении" возникает вопрос о том, как реализовать угловые скобки.

Все четыре указанных свойства важны, однако наиболее существенным является взаим­ное исключение. Таким образом, сначала мы сосредоточимся на нем, а затем узнаем, как обеспечить выполнение остальных. Для описания свойства взаимного исключения необхо­димо определить, находится ли процесс в своей критической секции. Чтобы упростить запись, построим решение для двух процессов, CS1 и CS2; оно легко обобщается для п процессов.

Пусть inl и in2 — логические переменные с начальным значением "ложь". Когда про­цесс CS1 (CS2) находится в своей критической секции, переменной inl (in2) присваивается значение "истина". Плохое состояние, которого мы будем стараться избежать, — если и inl, и in2 имеют значение "истина". Таким образом, нам нужно, чтобы для любого состояния выполнялось отрицание условия плохого состояния.

MUTEX:   -i(inl л in2)

Как сказано в разделе 2.7, предикат MUTEXдолжен быть глобальным инвариантом. Для этого он должен выполняться в начальном состоянии и после каждого присваивания переменным ml и in2. В частности, перед тем, как процесс CS1 войдет в критическую секцию, сделав тем самым inl истинной, он должен убедиться, что in2 ложна. Это можно реализовать с помо­щью следующего условного неделимого действия.

(await   (>in2)   inl  =  true;)

Процессы симметричны, поэтому во входном протоколе процесса CS2 используется анало­гичное условное неделимое действие. При выходе из критической секции задерживаться ни к чему, поэтому защищать операторы, которые присваивают переменным inl и in2 значе­ние "ложь", нет необходимости.



Решение показано в листинге 3.1. По построению программа удовлетворяет условию вза­имного исключения. Взаимная блокировка здесь не возникнет: если бы каждый процесс был заблокирован в своем протоколе входа, то обе переменные, и inl, и in2, были бы истинны­ми, а это противоречит тому, что в данной точке кода обе они ложны. Излишних задержек также нет, поскольку один процесс блокируется, только если другой находится в критической секции, поэтому нежелательные паузы при выполнении программы не возникают. (Все эти свойства программ можно доказать формально, использовав метод исключения конфигура­ций, представленный в разделе 2\8.)

Наконец, рассмотрим свойство живучести: процесс, который пытается войти в критиче­скую секцию, в конце концов сможет это сделать. Если процесс CS1 пытается войти, но не может, то переменная in2 истинна, и процесс CS2 находится в критической секции. По предположению процесс в конце концов выходит из критической секции, поэтому перемен­ная in2 когда-нибудь станет ложной, а переменная защиты входа процесса CS1 — истинной.

90                                                 Часть 1. Программирование с разделяемыми переменными

Если процессу csi вход все еще не разрешен, это значит, что либо диспетчер несправедлив, либо процесс CS2 снова достиг входа в критическую секцию. В последнем случае описанный выше сценарий повторяется, так что когда-нибудь переменная in2 станет ложной. Таким об­разом, либо переменная in2 становится ложной бесконечно часто, либо процесс CS2 завер­шается, и переменная in2 принимает значение "ложь" и остается в таком состоянии. Для того чтобы процесс CS2 в любом случае входил в критическую секцию, нужно обеспечить справедливую в сильном смысле стратегию планирования. (Аргументы для процесса CS2 симметричны.) Напомним, однако, что справедливая в сильном смысле стратегия планиро­вания непрактична, и вернемся к этому вопросу в разделе 3.3.

3.2. Критические секции: активные блокировки



В крупномодульном решении, приведенном в листинге 3.1, используются две перемен­ные. При обобщении данного решения для n процессов понадобятся п переменных. Однако существует только два интересующих нас состояния: или некоторый процесс находится в сво­ей критической секции, или ни одного там нет. Независимо от числа процессов, для того, чтобы различить эти два состояния, достаточно одной переменной.

Пусть lock — логическая переменная, которая показывает, находится ли процесс в кри­тической секции, т.е. lock истинна, когда одна из inl или in2 истинна, в противном случае lock ложна. Таким образом, получим следующее условие:

lock ==   (inl v in2)

Используя lock вместо inl и in2, можно реализовать протоколы входа и выхода програм­мы 3.1 так, как показано в листинге 3.2.

Преимущество протоколов входа и выхода, показанных в листинге 3.2, по отношению к протоколам в листинге 3.1 состоит в том, что их можно использовать для решения задачи критической секции при любом числе процессов. Все они будут разделять переменную lock и выполнять одни и те же протоколы.



3.2.1. "Проверить-установить"

Использование переменной lock вместо inl и 1п2, показанное в листинге 3.2, очень важ­но, поскольку почти у всех машин, особенно у мультипроцессоров, есть специальная инструк­ция для реализации условных неделимых действий. Здесь применяется инструкция, называемая "проверить-установить".8 В следующем разделе будет использована еще одна подобная инст­рукция — "извлечь и сложить". Дополнительные инструкции описываются в упражнениях.

Инструкция "проверить-установить" (test and set — TS) в качестве аргумента получает разделяемую переменную lock и возвращает логическое значение. В неделимом действии инструкция TS считывает и сохраняет значение переменной lock, присваивает ей значение "истина", а затем возвращает сохраненное предыдущее значение переменной lock. Резуль­тат действия инструкции TS описывается следующей функцией:



(36)   bool  TS(bool  lock)   {

{ bool  initial  =  lock;   /*  сохранить начальное значение  */ lock =  true;                /*  установить  lock  */

return initial;   )         /*  возвратить  начальное значение  */ }

Используя инструкцию TS, можно реализовать крупномодульный вариант программы 3.2 по алгоритму, приведенному в листинге 3.3. Условные неделимые действия в программе 3.2 заменяются циклами. Циклы не завершаются, пока переменная lock не станет ложной, т.е. инструкция TS возвращает значение "ложь". Поскольку все процессы выполняют одни и те же протоколы, приведенное решение работает при любом числе процессов. Использование блокирующей переменной, как в листинге 3.3, обычно называется циклической блокировкой (spin lock), поскольку процесс постоянно повторяет цикл, ожидая снятия блокировки.

Программа в листинге 3.3 имеет следующие свойства. Взаимное исключение (3 2) обеспече­но если несколько процессов пытаются войти в критическую секцию, только один из них пер­вым изменит значение переменной lock сложного на истинное, следовательно, только один из

1 Напомним, что термин "установить" (без указания значения) обычно применяется в смысле "присвоитьзначение true (или 1)", а "сбросить" — "присвоить false (или 0)". — Прим. ред.

92                                                Часть 1 Программирование с разделяемыми переменными

процессов успешно завершит свой входной протокол и войдет в критическую секцию. Отсутст­вие взаимной блокировки (3.3) следует из того, что, если оба процесса находятся в своих входных протоколах, то lock ложна, и, следовательно, один из процессов войдет в свою критическую сек­цию. Нежелательные задержки (3.4) не возникают, поскольку, если оба процесса находятся вне своих критических секций, lock ложна, и, следовательно, один из процессов может успешно вой­ти в критическую секцию, если другой выполняет некритическую секцию или был завершен.



С другой стороны, выполнение свойства возможности входа (,3.5) не гарантируется.


Если используется справедливая в сильном смысле стратегия планирования, то попытки процесса войти в критическую секцию завершатся успехом, поскольку переменная lock бесконечно часто будет принимать значение "ложь". При справедливой в слабом смысле стратегии пла­нирования, которая встречается чаще всего, процесс может навсегда зациклиться в протоколе входа. Однако это может случиться, только если другие процессы все время успешно входят в свои критические секции, чего на практике быть не должно. Следовательно, решение в лис­тинге 3.3 должно удовлетворять условию справедливой стратегии планирования.

Решение задачи критической секции, аналогичное приведенному в листинге 3.3, может быть реализовано на любой машине, если у нее есть инструкция, проверяющая и изменяю­щая разделяемую переменную в одном неделимом действии. Например, в некоторых маши­нах есть инструкция инкремента (увеличения), которая увеличивает целое значение пере­менной и устанавливает код условия, указывающий, положительно ли значение результата. Используя эту инструкцию, можно построить протокол входа, основанный на переходе от нуля к единице. В упражнениях рассмотрены несколько типичных инструкций такого рода (Это любимый вопрос экзаменаторов1)

Построенное решение с циклической блокировкой и те решения, которые вы, возможно, составите сами, обладают свойством, которое стоит запомнить.

(3.7) Протоколы выхода в решении с циклической блокировкой. В решении задачи критиче­ской секции с циклической блокировкой протокол выхода должен просто присваивать разделяемым переменным их начальные значения.

В начальным состоянии (см. листинг 3.1) обе переменные inl и in2 ложны, как и перемен­ная lock (см. листинги 3.2 и 3.3).

3.2.2. "Проверить-проверить-установить"

Хотя решение в листинге 3.3 верно, эксперименты на мультипроцессорных машинах показывают его низкую производительность, если несколько процессов соревнуются за доступ к критической секции. Причина в том, что каждый приостановленный процесс не­прерывно обращается к разделяемой переменной lock.


Эта "горячая точка" вызывает

Глава 3. Блокировки и барьеры                                                                                               93.

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

К тому же инструкция TS при каждом вызове записывает значение в lock, даже если оно не изменяется. Поскольку в мультипроцессорных машинах с разделяемой памятью для уменьшения числа обращений к основной памяти используются кэши, ts выполняется го­раздо дольше, чем простое чтение значения разделяемой переменной. (Когда переменная за­писывается одним из процессоров, ее копии нужно обновить или сделать недействительными в кэшах других процессоров.)

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



Этот протокол называется "проверить-проверить-установить", поскольку процесс просто проверя­ет lock до тех пор, пока не появится возможность выполнения TS. В двух дополнительных циклах lock просто проверяется, так что ее значение можно прочесть из кэш-памяти, не влияя на другие процессоры. Таким образом, конфликты при обращении к памяти сокращаются, но не исчезают. Если флажок блокировки lock сброшен, то как минимум один, а возможно, и все приостанов­ленные процессы могут выполнить инструкцию TS, хотя продолжаться будет только один из них. Ниже мы опишем способы дальнейшего сокращения конфликтов обращения к памяти.

В листинге 3.4 представлено полное решение задачи критической секции, использующее входной протокол "проверить-проверить-установить". Как и ранее, протокол выхода просто очищает переменную lock.



3.2.3. Реализация операторов await

Любое решение задачи критической секции можно использовать для реализации безус­ловного неделимого действия (S; >, скрывая внутренние контрольные точки от других про­цессов.


Пусть CSenter — входной протокол критической секции, a CSexit — соответствующий выходной. Тогда действие (S;} можно реализовать так:

CSenter,

S; CSexit;

94                                                Часть 1. Программирование с разделяемыми переменными

Здесь предполагается, что все секции кода процессов, которые изменяют или ссылаются на переменные, изменяемые в S (или изменяют переменные, на которые ссылается S), защище­ны аналогичными входными и выходными протоколами. В сущности, скобки ( и) заменены процедурами CSenter и CSexit.

Приведенный выше образец кода можно использовать в качестве "кирпичика" для реали­зации операторов (await (В) S;). Напомним, что условное неделимое действие приоста­навливает процесс, пока условие в не станет истинным, после чего выполняется S. Когда на­чинается выполнение S, условие в должно быть истинным. Чтобы обеспечить неделимость всего действия, можно использовать протокол критической секции, скрывая промежуточные состояния в в. Для циклической проверки условия в, пока оно не станет истинным, можно использовать следующий цикл.

CSenter,

while   (!B)   {  ???  }

S;

CSexit;

Здесь предполагается, что критические секции всех процессов, изменяющих переменные, используемые в в или S, или использующих переменные, изменяемые в S, защищены такими же протоколами входа и выхода.

Остается выяснить, как реализовать тело цикла, указанного выше. Если тело выполняет­ся, значит, условие в было ложным. Следовательно, единственный способ сделать условие в истинным — изменить в другом процессе значения переменных, входящих в это условие. Предполагается, что все операторы, изменяющие эти переменные, находятся в критических секциях, поэтому, ожидая, пока условие в выполнится, нужно выйти из критической секции. Но для обеспечения неделимости вычисления в и выполнения S перед повторным вычисле­нием условия в необходимо вновь войти в критическую секцию. Возможным уточнением указанного выше протокола может быть следующее.



(3.8)     CSenter;

while   (!B)   {  CSexit; CSenter,  }

S;

CSexit;

Данная реализация сохраняет семантику условных неделимых действий при условии, что протоколы критических секций гарантируют взаимное исключение. Если используемая стра­тегия планирования справедлива в слабом смысле, то процесс, выполняющий (3.8), в конце концов завершит цикл при условии, что в когда-нибудь станет (и останется) истинным. Если стратегия планирования справедлива в сильном смысле, цикл завершится, если условие в становится истинным бесконечно часто.

Программа (3.8) верна, но не эффективна, поскольку процесс, выполняющий ее, по­вторяет "жесткий" цикл, постоянно выходя из критической секции и входя в нее, но не может продвинуться дальше, пока какой-нибудь другой процесс не изменит переменных в условии в. Это приводит к конфликту обращения к памяти, поскольку каждый приоста­новленный процесс постоянно обращается к переменным, используемым в протоколах критической секции и условии в.

Чтобы сократить количество конфликтов обращения к памяти, процесс перед повторной попыткой войти в критическую секцию должен делать паузу. Пусть Delay — некоторый код, замедляющий выполнение процесса. Тогда программу (3.8) можно заменить следующим про­токолом, реализующим условное неделимое действие.

(3.9)     CSenter;

while   С.В)   { CSexit; Delay; CSenter, }

S;

CSexit;

Глава 3 Блокировки и барьеры                                                                                               95

Кодом Delay может быть, например, пустой цикл, который выполняется случайное число раз. (Во избежание конфликтов памяти в цикле в коде Delay следует использовать только локаль­ные переменные.) Этот тип протокола "отхода" ("back-off") полезен и в самих протоколах CSenter; например, его можно использовать вместо skip в цикле задержки простого протоко­ла "проверить-установить" (см. листинг 3.3).

Если S состоит из одного оператора skip, протокол (3.9) можно упростить, опустив S.


Ес­ли условие В удовлетворяет свойству "не больше одного" (2.2), то оператор (await   (В);) можно реализовать в следующем виде, while   ('В)   skip;

Как упоминалось в начале этой главы, синхронизация с активным ожиданием часто при­меняется в аппаратном обеспечении. Фактически протокол, аналогичный (3.9), используется для синхронизации доступа в локальных сетях Ethernet. Чтобы передать сообщение, контрол­лер Ethernet отправляет его в сеть и следит, не возник ли при передаче конфликт с сообще­ниями, отправленными примерно в это же время другими контроллерами. Если конфликт не обнаружен, то считается, что передача завершилась успешно. В противном случае контроллер делает небольшую паузу, а затем повторяет передачу сообщения. Чтобы избежать состояния гонок, в котором два контроллера постоянно конфликтуют из-за того, что делают одинако­вые паузы, их длительность выбирается случайным образом из интервала, который удваива­ется при каждом возникновении конфликта. Такой протокол называется двоичным экспонен­циальным протоколом отхода. Эксперименты показывают, что протокол такого типа полезен также в (3.9) и во входных протоколах критических секций.

Дублируемые серверы

Опишем последнюю парадигму взаимодействия процессов — дублируемые серверы. Как уже говорилось, сервер — это процесс, управляющий некоторым ресурсом. Сервер можно дублировать, если есть несколько отдельных экземпляров ресурса; каждый сервер тогда управ­ляет одним из экземпляров. Дублирование также можно использовать, чтобы дать клиентам ил­люзию уникальности ресурса, когда в действительности экземпляров ресурса несколько. По-лобный пример был представлен при реализации дублирования файлов (см. раздел 8.4).

В этом разделе строятся два дополнительных решения задачи об обедающих философах  иллюстрируются два применения дублируемых серверов. Как обычно, в задаче есть пять философов и пять вилок, и для еды философу нужны две вилки. В виде распределенной про­граммы эту задачу можно решить тремя способами. Пусть РН— это процесс-философ, W— процесс-официант. В первом способе всеми пятью вилками управляет один процесс-официант (эта централизованная структура показана на рис. 9.5, а). Второй способ — распре­делить вилки, чтобы одной вилкой управлял один официант (распределенная структура на рис. 9.5, б). Третий способ — прикрепить официанта к каждому философу (децентрализованная структура на рис. 9.5, в). Централизованное решение было представлено з листинге 8.6, а распределенное и децентрализованное решения разрабатываются здесь.

• 9.7.1. Распределенное решение задачи об обедающих философах

Централизованное решение задачи об обедающих философах (см. листинг 8.6) свободно от блокировок, но не справедливо. Кроме того, узким местом программы может стать процесс-официант, поскольку с ним должны взаимодействовать все процессы-философы. Распределенное решение можно сделать свободным от блокировок, справедливым и не имеющим узкого места, но платой за это будет более сложный клиентский интерфейс и увеличение числа сообщений.

В листинге 9.15 приведено распределенное решение, в котором использована составная нотация из раздела 8.3. (Это приводит к короткой программе, хотя ее легко переписать с по­мощью только передачи сообщений или только рандеву.) Есть пять процессов-официантов, каждый из которых управляет одной вилкой.
Официант постоянно ожидает, пока философ возьмет вилку, а потом отдаст ее. Каждый философ, чтобы получить вилки, взаимодействует с двумя официантами. Чтобы не возникали блокировки, философы не должны выполнять одну и ту же программу. Вместо этого каждый из первых четырех философов берет левую, а затем правую вилки, а последний философ — сначала правую, а потом левую. Это решение очень похоже на решение с семафорами в листинге 4.6.

Распределенное решение в листинге 9.15 является справедливым, поскольку вилки за­прашиваются по одной, и вызовы операции get forks обслуживаются в порядке вызова. Та­ким образом, все вызовы операции getf orks в конце концов будут обслужены при условии, что философы когда-нибудь отдадут полученные вилки.

Глава 9. Модели взаимодействия процессов                                                                            361

9.7.2. Децентрализованное решение задачи об обедающих философах

Построим децентрализованное решение, в котором у каждого философа есть свой офици­ант. Схема взаимодействия процессов здесь похожа на использованную в задаче о дублируе­мых файлах (см. листинги8.1 и8.14). Алгоритм работы процессов-официантов— это еще один пример передачи маркера (маркерами являются пять вилок). Представленное здесь ре­шение можно адаптировать для управления доступом к дублируемым файлам или получить из него эффективное решение задачи распределенного взаимного исключения (см. упражнения).

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

Ключ к правильному решению — управлять вилками, избегая взаимных блокировок. Же­лательно, чтобы решение было справедливым. В данной задаче блокировка может возник­нуть, если официанту нужны две вилки, но он не может их получить.


Официант обязательно должен удерживать обе вилки, пока его философ ест, а если философ не ест, официант дол­жен быть готовым отдать вилки по первому требованию. Однако необходимо избегать ситуа­ции, когда вилка передается от одного официанта другому и обратно без использования.

Основная идея избавления от взаимных блокировок — официант должен отдать исполь­зованную вилку, но удерживать вилку, которую только что получил. Для этого, когда фило­соф начинает есть, официант помечает обе вилки как "грязные". Если вилка нужна другому официанту, и она уже грязная и не используется, первый официант моет вилку и отдает. Но грязную вилку можно использовать повторно, пока она не понадобится другому официанту.

Этот децентрализованный алгоритм приведен в листинге 9.16. (Из-за мытья вилок его часто называют "алгоритмом гигиеничных философов".) Решение запрограммировано с по­мощью составной нотации (см. раздел 8.3), поскольку его легче построить, используя и уда­ленные вызовы процедур, и рандеву, и передачу сообщений.

Желая поесть, философ вызывает операцию get forks, экспортируемую модулем. Опе­рация get forks реализована процедурой, чтобы скрыть, что получение вилок требует от­правки сообщения hungry и получения сообщения eat. Получая сообщение hungry, про­цесс-официант проверяет состояние двух вилок. Если обе вилки у него, философ получает разрешение поесть, а официант ждет, пока философ отдаст вилки.

Если у процесса-официанта нет двух нужных вилок, он должен их взять, используя для этого операции needL, needR, passL и passR. Когда философ голоден и его официанту нужна вилка, официант передает сообщение другому официанту, у которого есть эта вилка. Другой официант получает это сообщение, когда вилка уже грязная и не используется, и пе­редает вилку первому официанту. Операции needR и needL вызываются асинхронным вызо­вом send, а не синхронным call, поскольку одновременный вызов операций call двумя официантами может привести ко взаимной блокировке.



Для хранения состояния вилок каждый официант использует четыре переменные: haveL, haveR, dirtyL и dirtyR. Эти переменные инициализируются, когда в процессе Main вы­зываются операции forks модулей Waiter. Вначале официант 0 держит две грязные вилки, официанты 1-3 — по одной (правой) грязной вилке, а у официанта 4 вилок нет.

Во избежание взаимной блокировки вилки вначале распределяются принудительно, при­чем асимметрично, и все они грязные. Если бы, например, у каждого официанта вначале бы­ло по одной вилке, и все философы захотели есть, то каждый официант мог бы отдать свою вилку и затем удерживать полученную (взаимная блокировка!). Если бы какая-то вилка вна­чале была чистой, то официант не отдал бы эту удерживаемую вилку, пока философ не закон­чит есть; если процесс-философ завершился или философ никогда не захочет есть, то другой философ будет без конца ждать эту вилку.





Философы не будут голодать, поскольку официанты всегда отдают грязные вилки. Если одному официанту нужна вилка, которую держит второй, он в конце концов ее получит. Если вилка грязная и не используется, второй официант немедленно отдаст ее первому. Если вилка грязная и используется, то второй философ когда-нибудь закончит есть, и его официант от­даст вилку первому. Чистая вилка означает, что другой философ захотел есть, его официант только что взял вилку или ждет вторую. По тем же причинам второй официант когда-нибудь обязательно получит вторую вилку, поскольку нет состояния, в котором каждый официант держит чистую вилку и просит еще одну. (Это еще одна причина, по которой нужна асиммет­ричная инициализация официантов.)

Инструментальные средства параллельного программирования

В предыдущих разделах данной главы рассматривалась роль библиотек, компиляторе! и языков в создании параллельных программ для научных приложений. В процессе разработ­ки, оценки и использования параллельных программ широко применяются также многочис­ленные вспомогательные инструментальные программные средства. К ним относятся: ком­плекты эталонных программ проверки производительности, библиотеки для классов прило­жений (например адаптивные сети, линейная алгебра, разреженные матрицы или неоднородные вычисления) и базовые инструментальные средства (отладчики, параллельные генераторы случайных чисел, библиотеки параллельного ввода-вывода и другие).

В этом разделе описаны два дополнительных вида программного инструментария: для из­мерения и визуализации производительности приложений и для создания географически распределенных метавычислений. В последнем разделе представлен учебный пример по ме-такомпьютерной инфраструктуре Globus — одному из самых новых и амбициозных наборов инструментальных средств. В конце главы в исторической справке приведены ссылки на бо­лее подробную информацию по всем видам инструментов.

12.4.1. Измерение и визуализация производительности

Цель параллельных вычислений — решить задачу быстрее. Общее время, затраченное на вычисления, подсчитать легко. Намного труднее определить, где именно тратится время на вычисления, и, следовательно, определить узкие места. Решать проблемы такого рода помо­гает инструментарий для визуализации и измерения производительности.

Одним из первых инструментальных средств измерения производительности в параллель­ных вычислениях, особенно на машинах с распределенной памятью, был Pablo. Проект Pablo возник с появлением первых гиперкубических машин. Его продолжают развивать для расшире­ния возможностей и поддержки современных архитектур. Pablo является инфраструктурой для анализа производительности, позволяющей программисту исследовать приложения на различ­ных уровнях аппаратной и программной реализации.
Система проводит редукцию данных в ре­альном времени и представляет пользователю результаты несколькими способами. Для пред­ставления таблиц, схем, диаграмм и гистограмм используется статическая графика. Динамиче­ская графика позволяет наблюдать за развитием во времени, например, за фазами вычислений и взаимодействия. Динамическая графика основана на трассах событий с отметками времени, которые можно отображать в реальном времени или сохранять для дальнейшего просмотра.

Paradyn — более новый инструментарий для измерения производительности параллельных программ. Новизна Paradyn заключается в том, что изучение характеристик приложений является динамическим; оно автоматически включается при запуске программы и уточняется по ходу ее

Часть 3. Синхронное параллельное программирование

выполнения. Чтобы использовать Paradyn, разработчику приложения достаточно скомпоновать свою программу с библиотекой Paradyn. При запуске программы система Paradyn начинает поиск таких узких мест на высоком уровне, как чрезмерная блокировка при синхронизации, задержки в работе с памятью или при вводе-выводе. Обнаружив проблемы, Paradyn автоматически вставляет дополнительные средства, чтобы найти причины проблемы (вставка производится непосредст­венно в машинную программу). Paradyn представляет результаты пользователю в виде "консультации по производительности", в которой пытается ответить на три следующих вопро­са. Почему программа выполняется медленно? Где именно в программе есть проблемы с произ­водительностью? При каких условиях проблема возникает? Пользователь может сам искать от­веты на эти вопросы или позволить Paradyn провести полное автоматическое исследование.

И в Pablo, и в Paradyn используется графика, позволяющая разработчику делать видимы­ми аспекты производительности при выполнении программы. Графические пакеты исполь­зуются во многих приложениях, что позволяет программистам "увидеть" результаты по ходу вычислений. Например, при имитации движения п тел можно отображать на экране переме­щение тел или при моделировании потока жидкости использовать линии и цвета, чтобы ви­деть структуру и скорость потоков.


Еще один класс инструментов визуализации идет дальше и позволяет программисту управлять приложением, изменяя переменные программы по мере выполнения вычислений, и влиять на его дальнейшее поведение. Autopilot — пример недавно разработанного инструментария для управления вычислениями. Данные о производительно­сти в реальном времени, которые дает Autopilot, используются в связанной с ним системе Virtue, реализующей среду погружения (виртуальную реальность). Autopilot и Virtue реализо­ваны на основе частей набора инструментов Pablo. Они также используют систему Globus (описанную далее) для широкомасштабного взаимодействия.

12.4.2. Метакомпьютеры и метавычисления

Большинство параллельных вычислений выполняются на отдельных машинах с мульти­процессором или в группе машин, объединенных в локальную сеть. В идеале процессоры не выполняют другие приложения, и сеть изолирована от другой нагрузки. В локальных вычис­лительных сетях многие машины подолгу не заняты, например ночью. Периоды простоя можно продуктивно использовать, запуская "долгоиграющие" параллельные приложения, в частности, основанные на парадигме "управляющий-рабочие" (раздел 9.1). Такое исполь­зование поддерживается программной системой Condor, которая получила свое название от крупного хищника и ведет "охоту" на свободные машины в сети, захватывая их.

Метакомпьютер — это более общий и интегрированный набор вычислительных ресурсов. Метакомпьютер представляет собой группу компьютеров, объединенных с помощью высоко­скоростных сетей и программной инфраструктуры, создающих иллюзию единого вычисли­тельного ресурса. Эта концепция возникла в контексте высокопроизводительных вычисле­ний, поэтому термин "Метакомпьютер" считается синонимом сетевого виртуального супер­компьютера. На основе метакомпьютеров возможно создание многочисленных региональных, национальных и интернациональных вычислительных сетей, которые будут обеспечивать повсеместную и надежную вычислительную мощность подобно тому, как элек­тросети повсюду и бесперебойно обеспечивают электроэнергию.



Метакомпьютер ( или вычислительная сеть) образуется некоторым уровнем программного обеспечения, которое объединяет компьютеры и коммуникационные сети, создавая иллюзию одного виртуального компьютера. Еще один уровень программного обеспечения на вершине этой инфраструктуры обеспечивает метавычислительную среду, позволяющую приложениям использовать возможности метакомпьютера. Сущность и роли этих уровней программного обеспечения подобны обычным операционным системам, которые реализуют виртуальную машину на вершине аппаратных ресурсов и поддерживают набор инструментов, используе­мых прикладными программистами.

Глава 12. Языки, компиляторы, библиотеки и инструментальные средства                       481

Метавычисления обусловлены желанием некоторых пользователей иметь доступ к ресур­сам, недоступным в среде одномашинных вычислений. Это свойство присуще некоторым ти­пам приложений:30

•    распределенные сверхвычисления, которые связаны с решением задач больших объе­мов и не помещаются на одном суперкомпьютере или могут выиграть от выполнения их разных частей на разных компьютерных архитектурах;

•    настольные сверхвычисления, позволяющие пользователю, сидящему у рабочей стан­ции, визуализировать и даже вмешиваться в вычисления, выполняемые на удаленном суперкомпьютере, или получать доступ к удаленным данным, возможно, используя их в качестве входных для прикладной программы;

•    интеллектуальные программы, соединяющие пользователей с удаленными приборами (телескопами или электронными микроскопами), которые, в свою очередь, связаны с программой, запущенной на удаленном суперкомпьютере;

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

Конечно, построение таких метавычислительных сред — далеко не тривиальная задача. Не­обходимо решать много сложных проблем. Перечислим некоторые из них: автономность раз­ных сайтов, беспокойство пользователей по поводу защиты своих машин, многообразие ар­хитектуры компьютеров и их постоянное обновление, отсутствие единого устойчивого про­странства имен, ошибки в компонентах, несовместимость языков и операционных систем и т.д.



Одной из первых программных систем, поддерживающих метавычисления, была система Legion. Данный проект появился в 1993 г. и продолжает развиваться. Legion использует объ­ектно-ориентированный подход и реализацию, направленную на решение перечисленных выше проблем. В частности, в Legion определен ряд классов, охватывающих компоненты и возможности системы. Каждый компонент, включая машины, файловые системы, библио­теки и компоненты прикладных программ, инкапсулируется в объект, который является эк­земпляром одного из классов Legion. Legion предназначен для поддержки всемирного вирту­ального компьютера и всех перечисленных выше типов приложений.

Более умеренным вариантом метавычислительной системы является Schooner. Она под­держивает настольные суперкомпьютерные приложения. Ключевым аспектом Schooner явля­ется язык определения интерфейса, не зависящий от языка программирования и машины; он используется для генерации интерфейсного кода, связывающего программные и аппаратные компоненты в приложении. Другой ключевой аспект Schooner — система времени выполне­ния, которая поддерживает и статическую, и динамическую конфигурации компонентов в приложении. Например, если удаленная машина оказывается перегруженной во время работы приложения или еще одна машина в сети становится доступной, пользователь может дина­мически перестроить приложение, чтобы адаптировать его к произошедшим изменениям.

12.4.3. Учебные примеры: инструментальный набор Globus

Globus— это новый, чрезвычайно амбициозный проект, позволяющий конструировать обширное множество инструментальных средств для построения метавычислительных при­ложений. Руководителями данного проекта являются Ян Фостер (Ian Foster) из Argonne Na­tional Labs и Карл Кессельман (Carl Kesselman) из USC's Information Sciences Institute. Их со­вместные разработки буквально охватывают весь земной шар.

Цель проекта Globus — обеспечить базовый набор инструментов для разработки переноси­мых высокопроизводительных сервисов, поддерживающих метавычислительные приложения.



30 Список представлен руководителями проекта Globus Фостером и Кессельманом в [Foster and Kes­selman, 1997]. Проект Globus описан в следующем разделе.

482                                                      Часть 3. Синхронное параллельное программирование

Таким образом, Globus основывается на возможностях таких более ранних систем, как PVM, MPI, Condor и Legion, значительно их расширяя. Проект также связан с разработкой способов приме­нения высокоуровневых сервисов к изучению низкоуровневых механизмов и управлению ими.

Компоненты инструментального набора Globus изображены на рис. 12.4. Модули набора выполняются на верхнем уровне метакомпьютерной инфраструктуры и используются для реализации сервисов высокого уровня. Метакомпьютерная инфраструктура, или испыта­тельная модель, реализована программами, соединяющими компьютеры. Группой Globus были построены два экземпляра такой инфраструктуры. Первый, сетевой эксперимент I-WAY, был создан в 1996 г. Он объединил 17 узлов в Северной Америке, его использовали 60 групп для разработки приложений каждого из четырех классов, описанных в предыдущем разделе. Вторая метакомпьютерная инфраструктура GUSTO (Globus Ubiquitous Supercomputing Testbed) была построена в 1997 г. как прототип вычислительной сети, состоящей из 15 узлов, и впоследствии премирована за развитие быстродействующих распределенных вычислений.

Сервисы высокого уровня

Adaptive Wide Area Resource Environment (AWARE) — адаптивная распределенная среда ресурсов

Интерфейс MPI, языковые интерфейсы,

CAVE-среды и другие Другие сервисы

Legion, Corba и другие

Модули инструментального набора Globus взаимодействие

размещение и распределение ресурсов сервисы ресурсов информации аутентификация создание процессов доступ к данным

Метакомпьютерная инфраструктура I-WAY, GUSTO и другие

Рис. 12.4. Компоненты и структура инструментального набора Globus

Инструментальный набор Globus состоит из нескольких модулей (см. рис. 12.4).

•     Модуль взаимодействий обеспечивает эффективную реализацию многих механизмов взаимодействия, описанных в части 2, в том числе обмен сообщениями, их многоабо­нентскую доставку, удаленный вызов процедур и распределенную разделяемую па­мять.


В основе его лежит библиотека взаимодействий Nexus.

•     Модуль размещения и распределения ресурсов обеспечивает механизмы, позволяющие приложениям задавать запросы на ресурсы, распределять ресурсы, удовлетворяющие этим требованиям, и получать к ним доступ.

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

•     Модуль аутентификации обеспечивает механизмы, используемые для подтверждения подлинности пользователей и ресурсов. Эти механизмы, в свою очередь, используются как строительные блоки в сервисах, например, санкционирования доступа.

•     Модуль создания процессов инициирует новые вычисления, объединяет их с уже иду­щими вычислениями и управляет их завершением.

Глава 12. Языки, компиляторы, библиотеки и инструментальные средства                         483

• Модуль доступа к данным обеспечивает скоростной удаленный доступ к постоянной памяти, базам данных и параллельным файловым системам. Этот модуль использует механизмы библиотеки взаимодействий Nexus.

Модули набора Globus помогают реализовывать сервисы приложений высокого уровня. Одним из таких сервисов является так называемая адаптивная распределенная среда ресурсов — Adaptive Wide Area Resource Environment (AWARE). Она содержит интегрирован­ный набор сервисов, в том числе "допустимые метавычислениями" интерфейсы для реализа­ции библиотеки MPI, различные языки программирования и инструменты для создания вир­туальных сред (constructing virtual environments — CAVE). Среди сервисов высокого уровня есть и разработанные другими, включая упомянутую выше систему метавычислений Legion и реализации CORBA (Common Object Request Broker Architecture).

Инструментальный набор Globus — это новый развивающийся проект, так что его описа­ние изменяется по мере разработки приложений и поддержки сервисов. Заинтересованный читатель может получить информацию о текущем состоянии и последних достижениях про­екта Globus, посетив его Web-сайт по адресу www.globus. org.

Историческая справка

Как уже отмечалось, параллельное программирование возникло в 1960-х годах после по­явления независимых аппаратных контроллеров (каналов). Операционные системы были первыми программными системами, организованными как многопоточные параллельные программы. Исследование и первоначальные прототипы привели на рубеже 1960-х и 1970-х годов к современным операционным системам. Первые книги по операционным системам появились в начале 1970-х годов.

Создание компьютерных сетей привело в 1970-х годах к разработке распределенных систем. Изобретение в конце 1970-х сети Ethernet существенно ускорило темпы развития. Почти сразу появилось изобилие новых языков, алгоритмов и приложений; их создание стимулировалось развитием аппаратного обеспечения. Например, как только рабочие станции и локальные сети стали относительно дешевыми, была разработана модель вычис­лений типа клиент-сервер; развитие сети Internet привело к рождению языка Java, Web-броузеров и множества новых приложений.

Первые мультипроцессоры появились в 1970-х годах, и наиболее заметными из них были SIMD-мультипроцессоры Illiac, разработанные в университете Иллинойса. Первые машины были дорогими и специализированными, однако в течение многих лет трудоемкие научные вычисления выполнялись на векторных процессорах. Изменения начались в середине 1980-х годов с изобретения гиперкубовых машин в Калифорнийском технологическом институте и их коммерческой реализации фирмой Intel. Затем фирма Thinking Machines представила Con­nection Machine с массовым параллелизмом. Кроме того, фирма Cray Research и другие про­изводители векторных процессоров начали производство многопроцессорных версий своих машин. В течение нескольких лет появлялись и вскоре исчезали многочисленные компании и машины. Однако сейчас группа производителей машин достаточна стабильна, а высокопро­изводительные вычисления стали почти синонимом обработки с массовым параллелизмом.

В исторических справках следующих глав описываются разработки, связанные с сами­ми этими главами.

Одной из первых и наиболее влиятельных статей по параллельному программированию была статья Эдсгера Дейкстры [Dijkstra, 1965]. В ней представлены задача критической сек­ции и оператор parbegin, который позже стал называться оператором cobegin. Наш опе­ратор со является обобщением cobegin. В другой работе Дейкстры [Dijkstra, 1968] были представлены задачи о производителе и потребителе, об обедающих философах и некоторые другие, которые рассматриваются в следующих главах.

Арт Бернстайн [Bernstein, 1966] был первым, кто определил условия, достаточные для не­зависимости, и, значит, возможности параллельного выполнения двух процессов. Условия Бернстайна, как они и сейчас называются, выражены в терминах множеств ввода и вывода для каждого процесса; множество ввода содержит переменные, читаемые процессом, а мно­жество вывода — переменные, записываемые процессом. Три условия Бернстайна для неза­висимости двух процессов состоят в том, что пересечения множеств (вход, выход), (выход, вход) и (выход, выход) не пересекаются между собой. Условия Бернстайна также дают основу для анализа зависимости данных, выполняемого распараллеливающими компиляторами (эта тема описана в главе 12), В нашем определении независимости (2.1) использованы множества чтения и записи для каждого процесса, и переменная находится только в одном из этих мно­жеств для каждого процесса. Это приводит к более простому, но эквивалентному условию.

В большинстве книг по операционным системам показано, как реализация оператора при­сваивания с использованием регистров и мелкомодульных неделимых действий приводит к за­даче критических секций в параллельных программах. Современное аппаратное обеспечение гарантирует, что существует некоторый базовый уровень неделимости (обычно слово) для чте­ния и записи памяти. Статья Лампорта [Lamport, 1977b] содержит интересное обсуждение того, как реализовать неделимые чтение и запись "слов", если неделимым образом могут записываться и читаться только отдельные байты.

Впервые задача критической секции была описана Дейкстрой [Dijkstra, 1965]. Эту фунда­ментальную задачу изучали десятки людей, опубликовавших буквально сотни работ по данной теме. В данной главе были представлены четыре наиболее важных решения. (Рейнал [Raynal, 1986] написал целую книгу по алгоритмам взаимного исключения.) Хотя разработка решений с активным ожиданием вначале была чисто академическим упражнением (поскольку активное ожидание неэффективно в однопроцессорной системе), появление мультипроцессо­ров подстегнуло новую волну интереса к этой теме. В действительности все современные муль­типроцессоры имеют команды, поддерживающие как минимум одно решение с активным ожи­данием. Большинство этих команд описаны в упражнениях в конце главы.

В работе Дейкстры [1965] было представлено первое программное решение для п процес­сов. Это было расширение решения для двух процессов, разработанного голландским мате­матиком Т. Деккером (см. упражнения). Однако в исходной формулировке Дейкстры не тре­бовалось свойство возможности входа (3.5). Дональд Кнут [Knuth, 1966] стал первым, кто опубликовал решение, гарантирующее возможность входа.

Алгоритм разрыва узла был изобретен Г. Питерсоном [Peterson, 1981]; теперь его часто на­зывают алгоритмом Питерсона. В отличие от ранних решений Дейкстры, Деккера и других авторов, этот алгоритм очень прост для двух процессов. Алгоритм Питерсона также легко обобщается для n-процессного решения (см. листинг 3.7). Это решение требует, чтобы про­цесс прошел через все п-1 уровней, даже если ни один другой процесс не делает попыток войти в критическую секцию. Блок и By [Block and Woo, 1990] представили вариант этого ал­горитма, в котором необходимо только m уровней, если m процессов пытаются войти в крити­ческую секцию (см. упражнения).

Алгоритм поликлиники был изобретен Лампортом [Lamport, 1974]. (В листинге 3.11 пред­ставлена его улучшенная версия из работы [Lamport, 1979].) Кроме того, что этот алгоритм нагляднее, чем предыдущие решения задачи критической секции, он позволяет процессам входить, по существу, в порядке FIFO (first in — first out, первым вошел — первым вышел).

В середине 1960-х годов Эдсгер Дейкстра (Edsger Dijkstra) и пять его коллег из Техниче­ского университета Эйндховена (Нидерланды) разработали одну из первых мультипрограмм­ных операционных систем. (Разработчики назвали ее просто мультипрограммной системой "THE" — по первым буквам названия института на голландском языке.) Эта система имеет элегантную структуру, состоящую из ядра и уровней виртуальных машин, реализованных процессами [Dijkstra, 1968a]. В ней были представлены семафоры, которые Дейкстра изобрел как полезное средство реализации взаимного исключения и выработки сигналов о таких со­бытиях, как прерывания. Дейкстра также ввел термин частный семафор.

Поскольку Дейкстра голландец, названия операций р и V происходят от голландских слов. Р — это первая буква голландского слова passeren (пропустить), а V — первая буква слова \rijgeven (освободить). (Отметим аналогию с железнодорожными семафорами.) Дейкстра и его группа позже решили связать букву Р со словом prolagen, составленного из нидерландских сяовргоЬегеп (попытаться) и verlagen (уменьшить), а букву V — со словом verhogen (увеличить).

Примерно в это же время Дейкстра написал важную работу [Dijkstra, 1968b] по взаимодей­ствию последовательных процессов. В этой работе было показано, как использовать семафо­ры для решения различных задач синхронизации, и представлены задачи об обедающих фи­лософах и о спящем парикмахере (см. раздел 5.2).

В своей основополагающей работе по мониторам (обсуждаемым в главе 5) Тони Хоар [Ноаге, 1974] представил идею разделенного двоичного семафора и показал, как его использо­вать для реализации мониторов. Однако именно Дейкстра позже дал этому методу название и доказал его практичность. Дейкстра [Dijkstra, 1979] описал использование разделенных двоич­ных семафоров для решения задачи о читателях и писателях. Он также показал, как реализовать обычные семафоры, используя только разделенные двоичные семафоры [Dijkstra, 1980].

Автор этой книги, вдохновленный работами Дейкстры о разделенных двоичных семафо­рах, разработал метод передачи эстафеты [Andrews, 1989].

Понятие инкапсуляции данных происходит от конструкции class языка Simula-67. Эдс-гер Дейкстра [Dijkstra, 1971] считается первым, кто начал использовать инкапсуляцию дан­ных для управления доступом к разделяемым переменным в параллельной программе. Он на-

Глава 5. Мониторы                                                                                                                         203

звал такой модуль "секретарем", но не предложил синтаксического механизма для програм­мирования секретарей. Бринч Хансен [Brinch Hansen, 1972] выступил с той же идеей, а в своей работе [Brinch Hansen, 1973] предложил особую языковую конструкцию shared class.

Хоар в своей замечательной статье [Ноаге, 1974] дал название мониторам и популяризи­ровал их с помощью интересных примеров, включавших кольцевой буфер, интервальный таймер и диспетчер доступа к диску (с использованием алгоритма лифта). Условная синхро­низация в варианте Хоара поддерживала порядок сигнализации "сигнализировать и срочно ожидать". Полезно сравнить решения Хоара с решениями из этой главы, в которых использо­ван порядок SC. Хоар также представил понятие разделенного двоичного семафора и пока­зал, как его использовать для реализации мониторов.

Язык Concurrent Pascal [Brinch Hansen, 1975] стал первым языком параллельного про­граммирования, в который были включены мониторы. В нем есть три структурных компо­нента: процессы, мониторы и классы. Классы похожи на мониторы, но не могут совместно использоваться процессами и, следовательно, не нуждаются в условной синхронизации или взаимном исключении. Язык Concurrent Pascal был использован для написания нескольких операционных систем [Brinch Hansen, 1977]. Устройства ввода-вывода в нем рассматриваются как особые мониторы, реализованные с помощью системы времени выполнения (run-time system) этого языка, скрывавшей понятие прерывания.

Мониторы были включены еще в несколько языков программирования. Язык Modula был разработан создателем языка Pascal Никлаусом Виртом (Nicklaus Wirth) как системный язык для задач программирования, связанных с компьютерными системами, включая приложения для управления процессами [Wirth, 1977]. (Первый вариант языка Modula весьма отличается от своих преемников, Modula-2 и Modula-З.) В Xerox PARC был разработан язык Mesa [Mitchell et al., 1979].

Примитивы fork, join и quit впервые были представлены Деннисом и Ван Хорном [Dennis and Van Horn, 1966]. Различные варианты этих примитивов есть в большинстве опе­рационных систем. Например, в операционной системе UNIX [Ritchie and Thompson, 1974] обеспечены соответствующие системные вызовы fork, wait и exit. Похожие примитивы были включены в такие языки программирования, как PL/I, Mesa и Modula-3.

Реализация однопроцессорного ядра особенно хорошо описана в книгах [Bic and Shaw, 1988] и [Holt, 1983]. В них рассмотрены и другие функции, которые должна обеспечи­вать операционная система (файловая система и управление памятью), и их взаимосвязь с ядром. В [Thompson, 1978] описана реализация ядра системы UNIX, а в [Holt, 1983] -UNIX-совместимая система Tunis.

К сожалению, в работах по операционным системам недостаточно подробно рассмотрена тема многопроцессорного ядра. Однако прекрасный отчет о ранних мультипроцессорах, раз­работанных в университете Карнеги-Меллон (Carnegie-Mellon University), представлен в об­зорной статье [Jones and Schwartz, 1980]. Из этой же работы взят принцип блокировки муль­типроцессора (6.1). Несколько многопроцессорных операционных систем описаны в работах [Hwang, 1993] и [Almasi and Gottlieb, 1994]. В [Tucker and Gupta, 1989] рассмотрены вопросы управления процессами и планирования для мультипроцессоров с разделяемой памятью и равномерным распределением времени доступа к памяти, в [Scott et al., 1990] — вопросы ядра для мультипроцессоров с неравномерным временем доступа к памяти, включая исполь­зование нескольких списков готовых к работе процессов.

Хорошими источниками информации по последним работам в области языков програм­мирования и программного обеспечения, связанной с мультипроцессорами, являются докла­ды следующих трех конференций: "Архитектурная поддержка языков программирования и операционных систем" (Architectural Support for Programming Languages and Operating Sys­tems, ASPLOS), "Симпозиум по принципам операционных систем" (Symposium on Operating Systems Principles— SOSP) и "Принципы и практика параллельного программирования" (Principles and Practice of Parallel Programming — PPoPP).

Все парадигмы, описанные в этой главе, были разработаны между серединой 1970-х годов и серединой 1980-х. В течение этих десяти лет интенсивно исследовались многие модели, а затем больше внимания стало уделяться их применению. Многие задачи можно решить не­сколькими способами, используя разные парадигмы. Некоторые из них описаны ниже; до­полнительные примеры приводятся в упражнениях и в главе 11.

Парадигма "управляющий-рабочие" была представлена в статье [Gentleman, 1981] и на­звана парадигмой "администратор-рабочий". В других работах (fCarriero et al., 1986], [Carriero and Gelernter, 1989]) эта же идея называлась распределенным портфелем задач. В них были представлены решения нескольких задач, запрограммированные с помощью примитивов Linda (см. раздел 7.7). В статье [Finkel and Manber, 1987] использовался распределенный портфель задач для реализации алгоритмов с возвратом (backtracking). Модель "управляющий-рабочие" широко используется в параллельных вычислениях, где эту технику иногда называют рабочим пулом, процессорной или рабочей фермой. Независимо от назва­ния идея всегда одна и та же: несколько рабочих процессов динамически делят набор задач.

Алгоритмы пульсации широко используются в распределенных параллельных вычисле­ниях, а особенно часто — в сеточных вычислениях (см. раздел 11.1). Автор этой книги ввел гермин алгоритм пульсации в конце 1980-х; это словосочетание показалось ему точно характе­ризующим действия процессов: закачка (передача), сокращение (прием), подготовка к сле­дующему циклу (вычисления) и повторение этого цикла. Бринч Хансен [Bnnch Hansen, 1995] назвал это парадигмой клеточных автоматов, хотя этот термин больше подходит для описания гипа приложения, а не стиля программирования. В любом случае ставший каноническим стиль программирования "передать-принять-вычислить" многие никак не называют, а про­сто говорят, что процессы обмениваются информацией.

В разделе 9.2 были представлены алгоритмы пульсации для задачи выделения областей в изображении и для игры "Жизнь", которую придумал математик Джон Конвей (John Conway)

История научных вычислений тесно связана с общей историей вычислений. Первые вы­числительные машины разрабатывались для решения научных проблем, а Фортран — первый язык высокого уровня — был создан специально для программирования численных методов. Научные вычисления также стали синонимом высокопроизводительных вычислений, застав­ляя увеличивать предельные возможности самых быстрых машин.

Математические основы научных вычислений представлены в учебниках по численному анализу, а методы решения дифференциальных и матричных уравнений — по вычислительной математике. Книга [Forsythe and Moler, 1967] является классической; в ней содержатся очень ясные описания линейных алгебраических систем и алгоритмов их решения. Она послужила основным источником для материала раздела 11.2. Книга [Van Loan, 1997] представляет собой введение в (непараллельные) научные вычисления, включая линейные и нелинейные системы уравнений. В учебнике [Mathews and Fink, 1999] описываются численные методы для целого ряда приложений, включая интегрирование, системы уравнений и дифференциальные урав­нения. В последних двух книгах для иллюстрации алгоритмов используется пакет MATLAB.

Некоторые книги по параллельным вычислениям дают более подробные описания мето­дов данной главы, представляют родственные алгоритмы и дополнительные темы. В книге [Fox et al., 1998] рассматриваются методы конечных разностей и конечных элементов для ре­шения дифференциальных уравнений в частных производных, матричных и точечных вычис­лений, а также методы Монте-Карло (рандомизированные). Особое внимание уделяется ал­горитмам с передачей сообщений, которые предназначены для работы на гиперкубах, но мо­гут быть адаптированы к другим архитектурам с распределенной памятью. В книге [Bertsekas and Tsitsiklis, 1989] рассматриваются прямые и итерационные методы для ряда линейных и нелинейных задач, динамическое программирование, проблемы потоков в сетях и асин-

444                                                      Часть 3.

Библиотеки параллельного программирования долгое время разрабатывались производи­телями параллельных машин. Однако, за редкими исключениями, все эти библиотеки были несовместимыми. В 1990-х годах стали появляться стандартные библиотеки, облегчавшие разработку переносимых кодов. Библиотека Pthreads рассматривалась в главе 4; там же в справке есть ссылки на другие источники информации о ней. Библиотека MPI была пред­ставлена в главе 7; реализации MPI и ее "близкой родственницы" библиотеки PVM описаны в исторической справке главы 7. Информацию по ОрепМР, включая онлайновые обучающие программы, можно найти в Internet по адресу: www. openmp. org.

Основополагающая работа по анализу зависимости была проведена под руководством Д. Кука (David Kuck) сотрудниками Иллинойского университета У. Банерджи (Utpal Banerjee) и М. Вольфом (Michael Wolfe) и представлена в книге [Wolfe, 1989]. В работе [Bacon, Graham, Sharp, 1994] дан прекрасный обзор анализа зависимости и преобразований компилятора для бы­стродействующих вычислений; работа содержит множество ссылок. В статье [McKinley, Carr, Tseng, 1996] описаны эксперименты, использующие различные преобразования для улучшения распределения данных, и даются рекомендации по очередности выполнения оптимизаций.

Некоторые из языков, перечисленных на рис. 12.3, были объектами учебных примеров в предыдущих главах: Ada в главе 8, Java в главах 5, 7 и 8, SR в главе 8, CSP/Occam и Linda в главе 7. Другие источники информации по этим языкам указаны в исторических справках соответствующих глав.

Из объектно-ориентированных языков на рис. 12.3 указаны только Java и Огса. Для па­раллельного программирования разработано также много других объектно-ориентированных языков. Например, в книге [Wilson and Lu, 1996] представлено более дюжины языков и сис­тем, основанных на C++. Отличное описание одного из этих языков — Compositional C++, а также Фортрана М, HPF и библиотеки MPI содержится в [Foster, 1995]. Обзор языков про­граммирования для распределенных вычислений, включая объектно-ориентированные и функциональные языки, можно найти в статье [Bal, Steiner, Tanenbaum, 1989].

Итеративный параллелизм: умножение матриц

Итеративная последовательная программа использует для обработки данных и вычисле­ния результатов циклы типа for и while. Итеративная параллельная программа содержит несколько итеративных процессов. Каждый процесс вычисляет результаты для подмножества данных, а затем эти результаты собираются вместе.

В качестве простого примера рассмотрим задачу из области научных вычислений. Предпо­ложим, даны матрицы а и Ь, у каждой по п строк и столбцов, и обе инициализированы. Цель — вычислить произведение матриц, поместив результат в матрицу с размером пхп. Для этого нужно вычислить п2 промежуточных произведений, по одному для каждой пары строк и столбцов.

Матрицы являются разделяемыми переменными, объявленными следующим образом. double a[n,n],   b[n,n],   c[n,n];

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

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

for   [i  =  0  to n-1]   { for   [j   =  0  to n-1]   {

28                                                                   Глава 1. Обзор области параллельных вычислений

#  вычислить  произведение  а[i,*]   и b[*,j]

c[i,j]   =   0.0;

for   [k =  0  to n-1]

c[i,j]   = c[i,j]   + a[i,k]*b[k,j]; } }

Внешние циклы (с индексами i и j) повторяются для каждой строки и столбца. Во внутрен­нем цикле (с индексом k) вычисляется промежуточное произведение строки i матрицы а и столбца j матрицы Ь; результат сохраняется в ячейке с [ i, j ]. Строка с символом # в нача­ле является комментарием.

Умножение матриц — это пример приложения с массовым параллелизмом, поскольку про­грамма содержит большое число операций, которые могут выполняться параллельно. Две опе­рации могут выполняться параллельно, если они независимы. Предположим, что множество чтения операции содержит переменные, которые она читает, но не изменяет, а множество запи­си — переменные, которые она изменяет (и, возможно, читает).
Две операции являются незави­симыми, если их множества записи не пересекаются. Говоря неформально, процессы всегда могут безопасно читать переменные, которые не изменяются. Однако двум процессам в общем случае небезопасно выполнять запись в одну и ту же переменную или одному процессу читать переменную, которая записывается другим. (Эта тема рассматривается подробно в главе 2.)

При умножении матриц вычисления промежуточных произведений являются независи­мыми операциями. В частности, строки с 4 по 6 приведенной выше программы выполняют инициализацию и последующее вычисление элемента матрицы с. Внутренний цикл про­граммы читает строку матрицы а и столбец матрицы Ь, а затем читает и записывает один эле­мент матрицы с. Следовательно, множество чтения для внутреннего произведения — это строка матрицы а и столбец матрицы Ь, а множество записи — элемент матрицы с.

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

Сначала рассмотрим параллельное вычисление строк матрицы с. Его можно запрограм­мировать с помощью оператора со (от "concurrent" — "параллельный"):

со   [i=0  to n-1]   {  #  параллельное вычисление строк for   [j   =  0  to n-1]   { c[i,j]   =   0.0; for   [k =  0  to n-1]

c[i,j]   =  c[i,j]   + a[i,k]*b[k,j]; } }

Между этой программой и ее последовательным вариантом есть лишь одно синтаксическое различие — во внешнем цикле оператор for заменен оператором со. Но семантическая раз­ница велика: оператор со определяет, что его тело для каждого значения индекса i будет вы­полняться параллельно (если не в действительности, то, по крайней мере, теоретически, что зависит от числа процессоров).

Другой способ выполнения параллельного умножения матриц состоит в параллельном вычислении столбцов матрицы с.


Его можно запрограммировать следующим образом.

со   [j   =  0  to n-1]   {   #параллельное  вычисление  столбцов for   [i  =  0  to n-1]   { c[i,j]   =  0.0; for   [k =  0  to n-1]

c[i,j]   =  c[i,j]   + a[i,k]*b[k,j]; } }

1.4. Итеративный параллелизм: умножение матриц                                                               29

Здесь два внешних цикла (по i и по j) поменялись местами. Если тела двух циклов незави­симы и приводят к вычислению одинаковых результатов, их можно безопасно менять мес­тами, как это было сделано здесь. (Это и другие аналогичные преобразования программ рассматриваются в главе 12.)

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

со   [i  =  0  to n-1,   j   =  0  to n-1]   {   #  все  строки и с[i,j]   =  0.О;                                 #все  столбцы

for   [k =  0  to n-1]

c[i,j]   =  c[i,j]   + a[i,k]*b[k,j]; }

}

Тело оператора со выполняется параллельно для каждой комбинации значений индексов i и j, поэтому программа задает п2 процессов. (Будут ли они выполняться параллельно, зави­сит от конкретной реализации.) Другой способ параллельного вычисления промежуточных произведений состоит в использовании вложенных операторов со.

со   [i  =  0  to n-1]   {       #  строки параллельно,   затем со   [j   =  0  to n-1]   {   #  столбцы параллельно c[i,j]   =  0.0; for   [k =  0  to n-1]

c[i,j]   =  c[i,j]   + a[i,k]*b[k,j]; } }

Здесь для каждой строки (внешний оператор со) и затем для каждого столбца (внутренний оператор со) задается по одному процессу. Третий способ написать эту программу — поме­нять местами две строки последней программы. Результат всех трех программ будет одинако­вым: выполнение внутреннего цикла для всех п2 комбинаций значений i и j. Разница между ними — в задании процессов, а значит, и во времени их создания.

Заметим, что все параллельные программы, приведенные выше, были получены заменой оператора for на со.


Но мы сделали это только для индексов i и j. А как быть с внутренним циклом по индексу k? Нельзя ли и этот оператор заменить оператором со? Ответ — "нет", по­скольку тело внутреннего цикла как читает, так и записывает переменную с [ i, j ]. Промежу­точное произведение — цикл for с переменной k — можно вычислить, используя двоичный па­раллелизм, но для большинства машин это непрактично (см. упражнения в конце главы).

Другой способ определить параллельные вычисления, показанные выше, — использовать дек­ларацию (объявление) process вместо оператора со. В сущности, process — это оператор со, выполняемый как "фоновый". Например, первая параллельная программа из показанных выше — та, что параллельно вычисляет строки результата, — может быть записана следующим образом. process  row[i  =  0  to n-1]   {  #  строки параллельно for   [j   =  0  to n-1]   { c[i,j]   =  0.0; for   [k =  0  to n-1]

c[i,j]   =  c[i,j]   + a[i,k]*b[k,j]; } }

Здесь определен массив процессов — row [ 1 ], row [ 2 ] и т.д. — по одному для каждого значения индекса i. Эти п процессов создаются и начинают выполняться, когда встречается данная строка описания. Если за декларацией процесса следуют операторы, то они выполняются параллельно с процессом, тогда как операторы, записанные после оператора со, не выполняются до его заверше­ния. Декларации процесса, в отличие от операторов со, не могут быть вложены в другие декла­рации или операторы. Декларации процессов и операторы со подробно описаны в разделе 1.9.

30                                                                  Глава 1 Обзор области параллельных вычислений

В программах, приведенных выше, для каждого элемента, строки или столбца результи­рующей матрицы использовано по одному процессу. Предположим, что число процессоров в системе меньше п (так обычно и бывает, особенно когда п велико). Остается еще очевид­ный способ полного использования всех процессоров: разделить матрицу на полосы (строк или столбцов) и для каждой полосы создать рабочий процесс.


В частности, каждый рабочий процесс вычисляет результаты для элементов своей полосы. Предположим, что есть Р про­цессоров и п кратно р (т.е. п делится на Р без остатка). Тогда при использовании полос строк оабочие пооиессы можно запоогоаммивовать слелуюшим обоазом.

Отличие этой программы от предыдущей состоит в том, что п строк делятся на Р полос, по п/Р строк каждая. Для этого в программу добавлены операторы, необходимые для определе­ния первой и последней строки каждой полосы. Затем строки полосы указываются в цикле (по индексу i), чтобы вычислить промежуточные произведения для этих строк.

Итак, существенным условием распараллеливания программы является наличие незави­симых вычислений, т.е. вычислений с непересекающимися множествами записи. Для произ­ведения матриц независимыми вычислениями являются промежуточные произведения, по­скольку каждое из них записывает (и читает) свой элемент с [ i, j ] результирующей матри­цы. Поэтому можно параллельно вычислять все промежуточные произведения, строки, столбцы или полосы строк. И, наконец, параллельные программы можно записывать, ис­пользуя операторы со или объявления process.

1.5. Рекурсивный параллелизм: адаптивная квадратура

Программа считается рекурсивной, если она содержит процедуры, которые вызывают сами себя — прямо или косвенно. Рекурсия дуальна итерации в том смысле, что рекурсив­ные программы можно преобразовать в итеративные и наоборот. Однако каждый стиль программирования имеет свое применение, поскольку одни задачи по своей природе ре­курсивны, а другие — итеративны.

В теле многих рекурсивных процедур обращение к самой себе встречается больше одного раза. Например, алгоритм quicksort часто используется для сортировки. Он разбивает массив на две части, а затем дважды вызывает себя: первый раз для сортировки левой части, а второй — для правой. Многие алгоритмы для работы с деревьями и графами имеют подобную структуру.

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


Два вызова процедуры (или функции) явля­ ются независимыми, если их множества записи не пересекаются. Это условие выполняется, если: 1) процедура не обращается к глобальным переменным или только читает их; 2) аргументы и результирующие переменные (если есть) являются различными переменны­ми. Например, если процедура не обращается к глобальным переменным и имеет только па­раметры-значения, то любой ее вызов будет независимым. (Хорошо, если процедура читает и записывает только локальные переменные, тогда каждый экземпляр процедур имеет ло­кальную копию переменных.) В соответствии с этими требованиями можно запрограммиро­вать и алгоритм быстрой сортировки. Рассмотрим еще один интересный пример.



Каждая итерация вычисляет площадь малой фигуры по правилу трапеций и добавляет ее к общему значению площади. Переменная width — ширина каждой трапеции. Отрезки пе­ребираются слева направо, поэтому правое значение каждой итерации становится левым зна­чением следующей итерации.

Второй способ аппроксимации интеграла— использовать парадигму "разделяй и властвуй" и переменное число интервалов. В частности, сначала вычисляют значение m — се­редину отрезка между а и Ь. Затем аппроксимируют площадь трех областей под кривой, опре­деленной функцией f (): от а до т, от m до b и от а до Ь. Если сумма меньших площадей равна большей площади с некоторой заданной точностью EPSILON, то аппроксимацию можно счи­тать достаточной. Если нет, то большая задача — от а до Ь — делится на две подзадачи — от а до m и от m до Ь, и процесс повторяется. Этот способ называется адаптивной квадратурой, по­скольку алгоритм адаптируется к форме кривой. Его можно запрограммировать так.



Интеграл функции f (х) от а до Ь аппроксимируется таким вызовом функции:

area  = quad(a,   b,   f(a),   f(b),    (f(a)+f(b))*(b-a)/2);

В функции снова используется правило трапеции. Значения функции f () в крайних точках отрезка и приближенная площадь этого интервала передаются в каждый вызов функции quad, чтобы не вычислять их больше одного раза.



Итеративную программу нельзя распараллелить, поскольку тело цикла и считывает, и за­писывает значение переменной area. Тем не менее в рекурсивной программе вызовы функ­ции quad независимы при условии, что вычисление функции f (х) не дает побочных эффек­тов. В частности, аргументы функции quad передаются по значению, и в ее теле нет присваи-

32                                                                   Глава 1. Обзор области параллельных вычислений

вания глобальным переменным. Таким образом, для задания параллельного выполнения ре­курсивных вызовов функции можно использовать оператор со.

со  larea  = quad(left,   mid,   fleft,   fmid,   larea); //  rarea = quad(mid,   right,   fmid,   fright,   rarea); oc

Это единственное изменение, необходимое для того, чтобы сделать данную программу рекур­сивной. Поскольку оператор со не заканчивается до тех пор, пока не будут завершены оба вызова функций, значения переменных larea и rarea вычисляются до того, как функция quad возвратит их сумму.

В операторах со программ умножения матриц содержатся списки инструкций, выпол­няемых для каждого значения счетчиков (i и j). В операторе со, приведенном выше, содер­жатся два вызова функций, разделенных знаками //. Первая форма оператора со использу­ется для выражения итеративного параллелизма, вторая — рекурсивного.

Итак, программу с несколькими рекурсивными вызовами функций можно легко преобра­зовать в параллельную рекурсивную программу, если вызовы независимы. Однако существу­ет чисто практическая проблема: параллельно выполняемых операций может стать слишком много. Каждый оператор со в приведенной выше программе создает два процесса, по одному для каждого вызова функции. Если глубина рекурсии велика, то появится большое число процессов, возможно, слишком большое для параллельного выполнения. Решение этой про­блемы состоит в сокращении, или отсечении, дерева рекурсии при достаточном количестве процессов, т.е. переключении'с параллельных рекурсивных вызовов на последовательные.Эта тема рассматривается в упражнениях и далее в этой книге.

Языки и модели

Большинство эффективных параллельных программ написаны с помощью последова­тельного языка (как правило, С или Фортран) и библиотеки. Для этого есть несколько при­чин. Во-первых, программисты хорошо знают какой-нибудь последовательный язык и имеют опыт написания научных программ. Во-вторых, библиотеки совместимы с обычно исполь­зуемыми параллельными вычислительными платформами. В-третьих, высокая производи­тельность — основная цель быстродействующих вычислений, а библиотеки создаются под кон­кретное аппаратное обеспечение, предоставляя программисту управление на низком уровне.

Однако использование языка высокого уровня, содержащего механизмы как последователь­ного, так и параллельного программирования, тоже имеет ряд преимуществ. Во-первых, язык обеспечивает более высокий уровень абстракции, что может помочь программисту ориентиро­ваться в решении задачи. Во-вторых, последовательные и параллельные механизмы можно объ­единять, чтобы они работали вместе, а аналогичные алгоритмы имели сходное выражение. Эти два свойства облегчают создание и понимание программ (как правило, относительно коротких). В-третьих, язык высокого уровня обеспечивает контроль типов, освобождая программиста от необходимости проверять соответствие типов данных (об этом можно даже и не вспоминать). Это оберегает программиста от многих ошибок, позволяет создавать более короткие и устой­чивые программы. Основные проблемы разработчиков языка — разработать хороший набор абстракций, мощный и ясный набор механизмов, а также эффективную реализацию.

Для параллельного программирования разработаны различные языки. На рис. 12.3 перечисле­ны языки, которые часто используются или воплощают важные идеи. Языки на рисунке сгруппи­рованы в классы в соответствии с лежащей в их основе моделью программирования: разделяемые переменные, передача сообщений, координация, параллельность по данным и функциональ­ность. Языки первых трех классов используются для создания императивных программ, в кото­рых процессы, взаимодействие и синхронизация программируются явно.
Языки с параллельно­ стью по данным имеют неявную синхронизацию, а функциональные — неявные параллель­ность и синхронизацию. Последняя группа языков на рис. 12.3 содержит три абстрактные модели, которые можно использовать для сравнения алгоритмов и оценки производительности.

Некоторые языки, перечисленные на рис. 12.3, были описаны в предыдущих главах кни­ги. В данном разделе представлен краткий обзор новых, не рассмотренных до сих пор, аспек­тов языков и моделей и дается более подробное описание быстродействующего Фортрана (HPF). В исторической справке в конце главы содержатся ссылки на источники дальнейшей информации по конкретным языкам, а также описываются книги и обзорные статьи, дающие общее представление о языках и моделях.

12.3.1. Императивные языки

Языки первых трех классов на рис. 12.3 используются для создания императивных про­грамм, в которых явно обновляется и синхронизируется доступ к состоянию программы, т.е. к значениям переменных. Все эти языки имеют средства для определения процессов, задач или потоков, которые отличаются способом программирования взаимодействия и синхрони­зации. По первому способу для взаимодействия применяются разделяемые переменные, а для синхронизации— разделяемые блокировки, флаги, семафоры или мониторы. По вто­рому — и для взаимодействия, и для синхронизации используются сообщения. Некоторые языки поддерживают один из этих способов, некоторые — оба, предоставляя программисту выбор в зависимости от решаемой задачи или архитектуры машины, на которой будет рабо­тать программа. Третий способ заключается в обеспечении области разделяемых данных и операций над ними, подобных сообщениям (см. обсуждение языков с координацией ниже).

Учебные примеры многих языков, поддерживающих явное параллельное программиро­вание, уже рассматривались. Три из них (Ada, Java и SR) на рис. 12.3 указаны дважды, по-

468                                                      Часть 3. Синхронное параллельное программирование



Cilk

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

Новшеством в Cilk является то, что если из Cilk-программы убрать специфические для Cilk конструкции, то оставшийся код будет синтаксически и семантически корректной С-программой. Пять механизмов Cilk обозначаются ключевыми словами cilk, spawn, synch, inlet и abort. Ключевое слово с ilk добавляется в начало декларации С-функции и указы­вает, что функция является Cilk-процедурой. В такой процедуре при выполнении оператора spawn происходит разделение процессов. Порожденные потоки выполняются параллельно с родительским, вызывающим потоком. Для ожидания, пока все порожденные потоки завер­шат вычисления и возвратят результаты, в родительском потоке используется оператор synch. Таким образом, последовательность операторов spawn, за которой следует оператор synch, в сущности, является оператором со/ос.

Следующий пример иллюстрирует реализацию (неэффективную) рекурсивной парал­лельной программы для вычисления n-го числа Фибоначчи.



Глава 12. Языки, компиляторы, библиотеки и инструментальные средства                       469

Последний механизм Cilk, abort, используется внутри входов; он уничтожает потоки, порожденные одним и тем же родителем, которые еще выполняются. Одним из применений механизма abort может служить программа рекурсивного поиска, в которой многие пути ис­следуются параллельно; программист может уничтожить поток, исследующий путь, если уже найдено лучшее решение.

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


При порождении процедуры выполняется быстрая версия. Если некоторому рабочему процессу (который выполняет Cilk-потоки) нужна работа, он захватывает процедуру от какого-либо другого рабочего процесса. В этот момент процедура преобразуется в медленную версию.

Фортран М

Этот язык является небольшим набором расширений Фортрана, поддерживающим мо­дульную разработку программ с обменом сообщениями. Механизмы обмена сообщениями аналогичны механизмам, описанным в главе 7. Хотя этот язык больше не поддерживается, его возможности включены в MPI-связывание для языка HPF.

Процесс в Фортране М похож на процедуру с параметрами, но имеет ключевое слово process вместо procedure. Оператор processcall используется для создания нового процесса. Такие вызовы встречаются в частях программы, отмеченных операторами ргос-esses/endprocesses, которые подобны оператору со/ос.

Процессы в Фортране М взаимодействуют друг с другом с помощью портов и каналов; они не могут разделять переменные. Канал представляет собой очередь сообщений. Он соз­дается с помощью оператора channel, который определяет пару портов— вывода и ввода. Оператор send добавляет сообщение в порт вывода. Оператор endchannel добавляет в порт вывода сообщение, отмечающее конец канала. Оба оператора являются неблокирующими (асинхронными). Оператор receive ожидает сообщения в порту ввода, затем удаляет сооб­щение (таким образом, receive является блокирующим).

Каналы можно создавать и уничтожать динамически, передавать в качестве аргументов процессам и отправлять в сообщениях как значения. Например, чтобы позволить двум про­цессам взаимодействовать друг с другом, программисту сначала нужно создать два канала, за­тем — два процесса и передать им каналы как аргументы. Первый процесс использует порт вывода одного канала и порт ввода другого; второй — другие порты этих двух каналов.

Фортран М главным образом предназначен для программирования параллельности по за­дачам, в котором процессы выполняют, вообще говоря, разные задачи.


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

12.3.2. Языки с координацией

Язык с координацией является расширением какого-либо основного языка с разделяемой областью данных и примитивами, подобными сообщениям, для обработки области данных. Идея таких языков происходит от набора примитивов Linda (раздел 7.7). Напомним, что Linda расширяет основной язык, например С, с помощью абстракции ассоциативной памяти, называемой пространством кортежей (ПК). ПК концептуально разделяется всеми процесса­ми. Новый кортеж помещается в ПК при выполнении примитива out, извлекается оттуда с помощью in и проверяется при выполнении rd. Наконец, с помощью примитива eval процессы создаются; завершая работу, процесс помещает возвращаемое им значение в ПК. Таким образом, в Linda комбинируются аспекты разделяемых переменных и асинхронного обмена сообщениями — пространство кортежей разделяется всеми процессами, кортежи по­мещаются и извлекаются неделимым образом, как будто они — сообщения.

470                                                      Часть 3. Синхронное параллельное программирование

Огса

Это более современный пример языка с координацией. Подобно Linda, он основан на структурах данных, которые концептуально разделяются, хотя физически могут быть распре­деленными. Объединяющим понятием в Огса является не разделяемый кортеж, а разделяе­мый объект данных. Процессы на разных процессорах могут совместно использовать пассив­ные объекты — экземпляры абстрактных типов. Процессы получают доступ к разделяемому объекту, вызывая операцию, которая определена объектом. Операции реализуются с помо­щью механизма, сочетающего аспекты RPC и рандеву.

С помощью примитива fork процесс в Огса создает еще один процесс. Параметры про­цесса могут быть значениями (value) или разделяемыми (shared).


Для параметра- значения родительский процесс создает копию аргумента и передает ее процессу-сыну. Для разделяе­мого параметра аргумент должен быть переменной, которая является объектом типа, опреде­ляемого пользователем. После создания процесса-сына он и родитель разделяют этот объект.

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

В первоначальной версии Огса поддерживалась только параллельность по задачам, в со­временной — также и по данным. Это реализовано с помощью разбиения на части объектов данных, основанных на массивах, распределения этих частей по разным процессорам и их обработки с использованием параллельных операций, определенных пользователем.

12.3.3. Языки с параллельностью по данным

Языки с параллельностью по данным непосредственно поддерживают стиль программи­рования, в котором все процессы выполняют одни и те же операции на разных частях разде­ляемых данных. Таким образом, языки с параллельностью по данным являются императив­ными. Однако, несмотря на явное взаимодействие в этих языках, синхронизация выражается неявно — после каждого оператора есть неявный барьер.

Понятие параллельность по данным появилось в середине 1980-х с появлением первой Con­nection Machine, CM-1, с архитектурой типа SIMD.29

СМ-1 состояла из обычного управляющего процессора и специального мультипроцессора, состоявшего из тысяч небольших (серверных) процессоров. Управляющий процессор выполнял последовательные команды и рассылал па­раллельные команды всем серверным.процессорам; там эти команды выполнялись синхронно.

Чтобы упростить программирование СМ-1, сотрудники корпорации Thinking Machines разработали язык С* (С Star) — вариант языка С, параллельный по данным.


И хотя SIMD-машины, подобные СМ-1, больше не производятся, стиль программирования, параллельного по данным, остался, поскольку многие приложения легче всего программируются именно в этом стиле. Ниже мы дадим обзор основных черт языков С* и ZPL — нового интересного языка. В следующем разделе описан NESL — еще один новый язык, параллельный по дан­ным и функциональный. Затем представлен учебный пример по HPF, наиболее широко ис­пользуемому языку с параллельностью по данным. Поскольку в этих языках синхронизация (в основном) неявна, их компиляторы генерируют код, необходимый для синхронизации. Таким образом, не программист, а компилятор использует базовую библиотеку.

с*

Структура языка С* тесно связана с архитектурой СМ-1. Он дополняет С свойствами, по­зволяющими выражать топологию данных и параллельные вычисления. Например, в С* есть

29 Сам стиль архитектуры SIMD появился гораздо раньше — в 1960-х.

Глава 12. Языки, компиляторы, библиотеки и инструментальные средства                       471

конструкция shape для задания формы параллельных структур данных, например матриц. Параллельное выполнение задается с помощью оператора wi th, который состоит из после­довательности операторов, параллельно обрабатывающих данные. Оператор where поддер­живает условное выполнение параллельных операторов. С* также определяет количество операторов редукции, которые комбинируют значения неделимым образом. Рассмотрим следующий несложный фрагмент программы.



В первой строке определяется квадратная форма (shape) с именем grid, во второй — две матрицы действительных чисел, имеющие эту форму. В теле оператора with матрица Ь копи­руется в а, затем следуют оператор where и оператор редукции для накопления суммы всех положительных элементов матрицы а. Оба операторы присваивания внутри оператора where выполняются параллельно по всем элементам а и Ь.

Сопрограмма начинает работу на управляющем процессоре, где выполняются все последо­вательные операторы. Параллельные операторы компилируются в команды, рассылаемые по одной серверным процессорам.


Connection Machine обеспечивала аппаратную поддержку опе­раторов редукции и параллельного перемещения данных между обрабатывающими элементами.

ZPL

Этот новый язык поддерживает и параллельность по данным, и обработку массивов. Та­ким образом, выражения вроде А+В обозначают сложение целых массивов, которое может выполняться параллельно и заканчивается неявным барьером. ZPL является законченным языком, а не расширением какого-то базового. Однако он компилируется в ANSI С, согласо­вывается с кодами на Фортране или С и обеспечивает доступ к научным библиотекам.

Новые аспекты ZPL — области и направления. Вместе с выражениями обработки масси­вов они значительно упрощают программирование обработки матриц. Для иллюстрации объ­явления и использования областей и направлений используем метод итераций Якоби. Отме­тим, насколько проще выглядит программа по сравнению с явно параллельной программой влистинге 11.2 и особенно — с программами на C/Pthreads и C/MPI (см. листинги 12.1 и 12.2).

Область (region) — это просто набор индексов. Направление используется для модифика­ции областей или выражений с индексами массивов. Объявляются они следующим образом.



472                                                      Часть 3. Синхронное параллельное программирование

Префиксы областей указывают на то, что операторы применяются к целым массивам. Таким образом, в первой строке совершается п2

присваиваний. В каждой из остальных четырех строк выполняется п присваиваний и неявно увеличиваются размеры А, чтобы включить граничные векторы (это означает, что память, выделенная для А, в действительности содержит (п+2)2 значений). Каждый оператор может быть реализован параллельно и завершает свою работу до того, как начинает выполняться следующий оператор. Операторы независимы, поэтому по­сле каждого из них барьер не нужен.

Главный цикл для метода итераций Якоби можно записать на ZPL следующим образом. [R]     repeat

Temp   :=   (   A@north  + Aieast  + Aiwest  +



A@south   )   /   4; error   := max«  abs (A-Temp) ; A   :=  Temp; until  error  <  EPSILON;

Префикс региона [R] вновь указывает, что операторы в цикле обрабатывают целые массивы. Первый оператор присваивает каждому элементу Temp среднее арифметическое значений че­тырех его ближайших соседей в А; заметьте, как для выражения индексов этих соседей ис­пользуются направления. Второй оператор присваивает переменной error максимальное значение разностей пар значений в А и Temp; кодтах« является оператором редукции.

12.3.4. Функциональные языки

В императивных языках процессы, взаимодействие и синхронизация выражаются явно. Языки с параллельностью по данным имеют неявную синхронизацию. В функциональных языках неявно все!

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

В языках с одиночным присваиванием нет побочных эффектов, поэтому все аргументы в вызове функции могут вычисляться параллельно. Кроме того, вызываемую функцию можно вычислять, как только будут вычислены все ее аргументы. Таким образом, параллельность явно задавать не нужно; она присутствует автоматически. Процессы взаимодействуют неявно с по­мощью аргументов и возвращаемых значений. Наконец, синхронизация следует непосредст­венно из семантики вызова и возврата функции — тело функции не может выполняться, пока не будут вычислены ее аргументы, а результат функции не доступен до возврата из функции.

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


Таким образом, компилятор должен решать, в каких ситуациях безопасно обновлять массив на месте, а не созда­вать копию. Чтобы определить, перекрываются ли ссылки в массив, нужен анализ зависимости.

Обладая простыми, но мощными свойствами, функциональные языки давно популяр­ны в последовательном программировании. Основанные на функциях, они особенно хо­роши в рекурсивном программировании. Одним из первых функциональных языков был Lisp; два других языка, Haskell и ML, популярны в настоящее время. В их реализации мож­но использовать параллельность. В их версиях программисту позволяется решать, где и в какой степени нужна параллельность. Например, Multilisp является версией Lisp, a Concurrent ML — стандартного ML (Standard ML).

Ниже описываются два функциональных языка, NESL и Sisal, разработанные специально для параллельного программирования.

Глава 12. Языки, компиляторы, библиотеки и инструментальные средства                       473

NESL

NESL — функциональный язык с параллельностью по данным. Наиболее важными но­выми идеями NESL являются: 1) вложенная параллельность по данным и 2) модель произво­дительности, основанная на языке. NESL допускает применение функции параллельно к ка­ждому элементу набора данных и вложенные параллельные вызовы. Модель производитель­ности основана на концепциях работы и глубины, а не на времени работы. Неформально работа в вычислении — это общее число выполняемых операций, а глубина — самая длинная цепочка последовательных зависимостей.

Последовательные аспекты NESL основаны на ML, функциональном языке, и SETL, ла­коничном языке программирования со множествами. Для иллюстрации языка рассмотрим функцию, которая реализует алгоритм быстрой сортировки.



Последовательности являются базовым типом данных в NESL, поэтому аргументом функции является последовательность S. Оператор if возвращает S, если длина S не больше 1. В про­тивном случае в теле функции выполняется пять присваиваний: 1) переменной а присваива­ется случайный элемент S, 2) в последовательность S1 записываются все значения из S, кото­рые меньше а, 3) в S2 — все значения из S, равные а, 4) в S3 — все значения из S больше а и 5) последовательности R присваивается результат рекурсивного вызова функции Quicksort.



В четырех последних операторах присваивания для параллельного вычисления значений используется оператор "применить ко всем" { ... }. Например, выражение в присваива­нии 51 означает "параллельно найти все элементы е из S, которые меньше а". Выражение в присваивании R означает "параллельно вызвать Quicksort (v) для v, равного SI и v, рав­ного S3"; приведенный код является примером вложенной параллельности по данным. Ре­зультатами рекурсивных вызовов являются последовательности. В последней строке к перво­му результату к [ 0 ] дописываются последовательность S2 и второй результат R [ 1 ].

Sisal

Sisal (Streams and Iteration in a Single Assignment Language — потоки и итерация в языке с одиночным присваиванием) стал первым функциональным языком, разработанным специ­ально для создания научных программ. Его основные понятия — функции, массивы, итера­ция и потоки. Функции используются, как обычно, для рекурсии и структурирования про­граммы; итерация и массивы — для итеративного параллелизма (они будут рассмотрены ни­же). Потоки — это последовательности значений, доступных по порядку; они используются в конвейерном параллелизме и в операциях ввода-вывода. Sisal больше не поддерживается его создателями из лаборатории Lawrence Livermore, однако он внес в программирование важные идеи и используется до сих пор.

Цикл for в языке Sisal является первичным механизмом для выражения итеративного па­раллелизма. Его можно применять, если итерации независимы. Например, в следующем коде для вычисления матрицы с как произведения матриц айв используются два цикла.



474                                                      Часть 3 Синхронное параллельное программирование

Слово cross указывает, что внешний цикл выполняется параллельно для всех пар (cross-product), или комбинаций, образуемых n значениями i и п значениями j. Тело внешнего цикла образовано еще одним циклом, который возвращает скалярное произведение А [ i, * ] и В [ *, j ]; ключевое слово sum является оператором редукции.


Внешний цикл возвращает массив элементов, вычисленных п2 экземплярами внутреннего цикла. Отметим, что циклы расположены в правых частях двух операторов присваивания; этот синтаксис отражает семан­тику одиночного присваивания в функциональном языке.

В Sisal поддерживается еще одна циклическая конструкция, for initial. Ее использу­ют, когда есть зависимость, создаваемая циклом. Она позволяет написать императивный цикл в функциональном стиле. Например, следующий цикл создает вектор х[1:п], содер­жащий все частичные суммы вектора у [ 1:n]. (Эта параллельная префиксная проблема рас­сматривалась в разделе 3.5.)



В первой части инициализируются две новые переменные и выполняется первая итерация. В части while к предыдущему значению i каждый раз добавляется 1 и вычисляется новое значение х, которое равно сумме у [ i ] и предыдущего значения х. Данный цикл возвращает массив, содержащий заново вычисленные значения х.

Реализация Sisal основана на модели потоков данных. Выражение можно вычислить, как только будут вычислены его операнды. В цикле умножения матриц, приведенном выше, мат­рицы А и в даны и зафиксированы, поэтому можно вычислить все произведения. Суммы произведений определяются по мере вычисления произведений. Наконец, массив элементов можно строить по мере того, как вычисляются все скалярные произведения. Таким образом, каждое значение переходит к тем операторам, которым оно нужно, а операторы порождают выходные значения, только получив все свои входные значения. Модель выполнения, осно­ванная на потоках данных, применяется и в вызовах функций: аргументы независимы, поэтому их можно вычислить параллельно, а тело функции — после определения всех аргументов.

12.3.5. Абстрактные модели

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


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

Модель параллельных вычислений обеспечивает высокоуровневый подход к характеризации и сравнению времени выполнения различных программ. Это делается с помощью абстракции аппаратного обеспечения и деталей выполнения. Первой важной моделью параллельных вы­числений стала машина с параллельным случайным доступом (Parallel Random Access Ma­chine — PRAM). Она обеспечивает абстракцию машины с разделяемой памятью. Модель BSP (Bulk Synchronous Parallel — массовая синхронная параллельная) объединяет абстракции и раз­деленной, и распределенной памяти. В LogP моделируются машины с распределенной памятью и специальным способом оценивается стоимость сетей и взаимодействия. Упоминавшаяся мо­дель работы и глубины NESL основана на структуре программы и не связана с аппаратным обеспе­чением, на котором выполняется программа. Ниже дается обзор моделей PRAM, BSP и LogP.

Глава 12. Языки, компиляторы, библиотеки и инструментальные средства                       475

PRAM

PRAM является идеализированной моделью синхронной машины с разделяемой памя­тью. Все процессоры выполняют команды синхронно. Если они выполняют одну и ту же ко­манду, PRAM является абстрактной SIMD-машиной; однако процессоры могут выполнять и разные команды. Основными командами являются считывание из памяти, запись в память и обычные логические и арифметические операции.

Модель PRAM идеализирована в том смысле, что каждый процессор в любой момент времени может иметь доступ к любой ячейке памяти. Например, каждый процессор в PRAM может счи­тывать данные из ячейки памяти или записывать данные в эту же ячейку. Очевидно, что на ре­альных параллельных машинах такого не бывает, поскольку модули памяти упорядочивают дос­туп к одной и той же ячейке памяти.


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

Базовая модель PRAM поддерживает параллельные считывание и запись (Concurrent Read, Concurrent Write — CRCW). Существуют две более реалистические версии модели PRAM.

•    Исключительное  считывание,   исключительная  запись   (Exclusive   Read,   Exclusive Write — EREW). Каждая ячейка памяти в любой момент времени доступна только одному процессору.

•    Параллельное считывание, исключительная запись (Concurrent Read, Exclusive Write — CREW). Из каждой ячейки памяти в любой момент времени данные могут считываться параллельно, но записываться только одним процессором.

Эти модели более ограничены и, следовательно, более реалистичны, однако и их нельзя реа­лизовать на практике. Несмотря на это, модель PRAM и ее подмодели полезны для анализа и сравнения параллельных алгоритмов.

BSP   х

В модели массового синхронного параллелизма (BSP) синхронизация отделена от взаимо­действия и учтены влияние иерархии памяти и обмена сообщениями. Модель BSP состоит из трех компонентов:

•    процессоры, которые имеют локальную память и работают с одинаковой скоростью;

•    коммуникационная сеть, позволяющая процессорам взаимодействовать друг с другом;

•    механизм синхронизации всех процессоров через регулярные отрезки времени.

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

Вычисление в BSP состоит из последовательности сверхшагов. На каждом отдельном сверхшаге процессор выполняет вычисления, которые обращаются к локальной памяти, и отправляет сообщения другим процессорам. Сообщения являются запросами на получение копии (чтение) или на обновление (запись) удаленных данных. В конце сверхшага процессо­ры выполняют барьерную синхронизацию и затем обрабатывают запросы, полученные в те­чение данного сверхшага. Далее процессоры начинают выполнять следующий сверхшаг.

Будучи интересной абстрактной моделью, BSP также стала моделью программирова­ния.


В частности, в Oxford Parallel Application Center реализованы библиотека взаимодей­ствия и набор протоколирующих инструментов, основанные на модели BSP. Библиотека состоит примерно из 20 функций, в которых поддерживается BSP-стиль обмена сообще­ниями и удаленный доступ к памяти.

LogP

Модель LogP является более современной. Она учитывает характеристики машин с рас­пределенной памятью и содержит больше деталей, связанных со свойствами выполнения в коммуникационных сетях, чем модель BSP. Процессоры в LogP асинхронные, а не син-

476                                                      Часть 3. Синхронное параллельное программирование

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

•    L — верхняя граница задержки (Latency) при передаче сообщения, состоящего из од­ного слова, от одного процессора к другому;

•    о — накладные расходы (overhead), которые несет процессор, передавая сообщение (в течение этого времени процессор не может выполнять другие операции);

•    g — минимальный временной интервал (gap) между последовательными отправками или получениями сообщений в процессоре;

•    Р — число пар процессор-память.

Единицей измерения времени является длительность основного цикла процессоров. Предпо­лагается, что длина сообщений невелика, а сеть имеет конечную пропускную способность, т.е. одновременно между процессорами передаются не более Г L/gl сообщений.

Модель LogP описывает свойства выполнения в коммуникационной сети, но не ее струк­туру. Таким образом, она позволяет моделировать взаимодействие в алгоритме. Однако про­моделировать время локальных вычислений нельзя. Такой выбор был сделан, поскольку, во-первых, при этом сохраняется простота модели, и, во-вторых, локальное (последовательное) время выполнения алгоритмов в процессорах легко устанавливается и без этой модели.

12.3.6. Учебные примеры: быстродействующий Фортран (НРБ)



Быстродействующий Фортран (High-Performance Fortran — HPF) — это самый новый пред­ ставитель семейства языков, основанных на Фортране. Первая версия HPF была создана мно­гими разработчиками из университетских, промышленных и правительственных лабораторий в 1992 г. Вторая версия была опубликована в начале 1997 г. Несколько компиляторов существу­ют и сейчас, а HPF-программы могут работать на основных типах быстродействующих машин.

HPF — это язык, параллельный по данным. Он является расширением Фортрана 90, по­следовательного языка, поддерживающего ряд операций с массивами и их частями. На про­ект HPF повлиял Фортран D, более ранний диалект Фортрана, параллельный по данным. Основные компоненты HPF: параллельное по данным присваивание массивов, директивы компилятора для управления распределением данных-и операторы для записи и синхрониза­ции параллельных циклов. Ниже рассматривается каждый из этих компонентов языка и при­водится законченная программа для метода итераций Якоби.



Оба присваивания массивов имеют семантику параллельности по данным: сначала вычисля­ется правая часть, затем все значения присваиваются левой части. В первом присваивании значение в каждой внутренней точке new устанавливается равным среднему арифметическо­му значений ее четырех соседей в grid. Во втором присваивании массив new копируется об­ратно в grid. В действительности тело этого цикла можно было бы запрограммировать так.

Глава 12. Языки, компиляторы, библиотеки и инструментальные средства                       477

grid(2:n-l,2:n-l)   =

(grid(l:n-2,2:n-l)   +  grid(3:n, 2:n-l)   + grid(2:n-l,l:n-2)   +  grid(2:n-l,3:n))   /   4

Один и тот же массив может появляться в обеих частях — это обусловлено параллельностью по данным семантики присваивания массивов. Однако в коде, сгенерированном компилятором для этого оператора, все равно придется использовать временную матрицу, например new.

Перед присваиванием массивов может стоять выражение WHERE, задающее условные опера­ции с массивами, например приращение только положительных элементов.


В языке HPF есть также операторы редукции, которые неделимым образом применяют какую-либо операцию ко всем элементам массива и возвращают скалярное значение. Наконец, HPF обеспечивает ряд так называемых встроенных (intrinsic) функций, которые работают с целыми массивами. Например, функция TRANSPOSE (а) вычисляет транспозицию массива а. Другая функция, CSHIFT, обыч­но применяется для выполнения циклического смещения данных в массиве; в последнем при­мере правая часть в присваивании grid представляет собой набор смещенных версий grid.

Отображение данных

В языке HPF директивы отображения данных позволяют программисту управлять распо­ложением данных, в частности, их локализацией, особенно на машинах с распределенной памятью. Директивы являются рекомендациями компилятору HPF, т.е. не императивами, которым необходимо следовать, а советами, которые, по мнению программиста, улучшают производительность. В действительности удаление из программы всех директив отображения данных никак не повлияет на результат вычислений; просто программа, возможно, не будет работать столь эффективно.

Основные директивы — processors, align и distribute. Директива processors определяет форму и размер виртуальной машины процессоров Директива выравнивания align определяет взаимно однозначное соответствие между элементами двух массивов, ука­зывая на то, что они должны быть выровнены и одинаково распределены. Директива DISTRIBUTE определяет, каким способом массив (и все выровненные с ним) должен ото­бражаться в памяти виртуальной машины, определенной ранее директивой PROCESSORS; эти два способа обозначаются с помощью BLOCK (блоки) и CYCLIC (полосы).

В качестве примера предположим, что position и force— векторы, скажем, в задаче имитации п тел, и рассмотрим следующий код.

!HPF$   PROCESSORS  pr(8)

!HPF$  ALIGN position   (:)   WITH   force   (:)

!HPF$   DISTRIBUTE position(CYCLIC)   ONTO  pr

Первая директива определяет абстрактную машину с восемью процессорами, вторая — задает выравнивание position относительно force.


В третьей директиве указано, что вектор po­sition должен отображаться на процессоры циклически (по полосам); соответственно, век­тор force будет точно так же поделен на полосы между процессорами.

HPF поддерживает дополнительные директивы отображения данных. TEMPLATE — абст­рактная область индексов, которую можно использовать в качестве целевой для директив вы­равнивания и источника для директивы распределения. Директива DYNAMIC указывает, что выравнивание или распределение массива может изменяться во время! работы программы

С ПОМОЩЬЮ директивы REALIGN ИЛИ REDISTRIBUTE.

Параллельные циклы

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

478                                                      Часть 3. Синхронное параллельное программирование

Оператор FORALL указывает, что тело цикла должно выполняться параллельно. Напри­мер, в следующем цикле параллельно вычисляются все новые значения в grid.

FORALL   (i=2:n-l,   j=2:n-l)

new(i,j)   =   (grid(i-l,j)   + grid(i+l,j)   +

grid(i,j-l)   + grid(i,j+l))   /   4

Результат здесь такой же, как и при присваивании массивов. Однако тело цикла в операторе FORALL может состоять более, чем из одного оператора. Индексы цикла могут также иметь маску для задания предиката, которому должны удовлетворять индексные значения; это обеспечивает возможности, подобные тем, которые предоставляет оператор WHERE, но при этом отпадает необходимость окружать тело цикла операторами if.

Вторым механизмом написания параллельных циклов является директива INDEPENDENT. Программист, помещая ее перед циклом do, утверждает, что тела циклов независимы и, сле­довательно, могут выполняться параллельно. Например, в коде

!HPF$ INDEPENDENT do i = l,n

A(lndex(i)) = B(i) end

программист утверждает, что все элементы Index (i) различны (не имеют псевдонимов) и А и В не перекрываются в памяти.


Если В — функция, а не массив, программист может также использовать директиву pure, чтобы объявить об отсутствии побочных эффектов в в.

Пример: метод итераций Якоби

В листинге 12.5 представлена законченная HPF-подпрограмма для метода итераций Яко­би. В ней используется несколько механизмов, описанных выше. Первые три директивы оп­ределяют, что матрицы grid и new должны быть выровнены по отношению друг к другу и располагаться на PR процессорах блоками. Значение PR должно быть статической констан­той. В теле вычислительного цикла параллельно обновляются все точки матрицы, затем new также параллельно копируется в grid. Когда главный цикл завершается, в последнем при­сваивании вычисляется максимальная разница между соответствующими друг другу значе­ниями в grid и new. Неявные барьеры установлены после оператора FORALL, оператора ко­пирования массива и оператора редукции массива.



Глава 12. Языки, компиляторы, библиотеки и инструментальные средства                       479

Сравните эту программу с явно параллельной программой в листинге 11.2 и программе использующей библиотеку ОрепМР (см. листинг 12.4). Данный код намного короче благод! ря семантике параллельности по данным языка HPF. С другой стороны, явно параллельны код, подобный кодам в листингах 11.2 и 12.4, должен генерировать компилятор HPF. Это ь слишком трудно для данного приложения и машин с разделенной памятью. Но для машины распределенной памятью создать хороший код гораздо сложнее. Например, программа с яв ным обменом сообщениями для метода итераций Якоби (см. листинг 11.4) полностью отли чается от приведенной выше программы. Компилятор HPF должен распределить данные ме жду процессорами и сгенерировать код с обменом сообщениями. Директивы ALIG, и DISTRIBUTE дают ему указания, как это делать.

Языки, компиляторы, библиотеки и инструментальные средства

Языки, компиляторы, библиотеки и инструментальные средства

До сих пор основное внимание в данной книге уделялось созданию императивных про­грамм с явно заданными процессами, взаимодействием и синхронизацией. Эти программы наиболее распространены и являются тем, что выполняет аппаратура. Для ясности и ком­пактности программы записывались с помощью нотации высокого уровня. Способы описа­ния параллельности в ней похожи на механизмы языка SR, а нотация последовательных про­цессов аналогична языку С. В данной главе рассматриваются дополнительные подходы и ин­струментальные средства для организации высокопроизводительных вычислений.

При написании параллельных программ чаще всего берется какой-нибудь последователь­ный язык и соответствующая библиотека подпрограмм. Тела процессов записываются на по­следовательном языке, например, С или Фортране. Затем с помощью вызовов библиотечных функций программируется создание процессов, их взаимодействие и синхронизация. Нам уже знакомы библиотека Pthread, предназначенная для машин с разделяемой памятью, и библиотека MPI для обмена сообщениями. В разделе 12.1 показано, как с помощью этих библиотек запрограммировать метод итераций Якоби. Затем рассматривается технология ОрепМР — новый стандарт программирования с разделяемыми переменными. Использова­ние ОрепМР проиллюстрировано также на примере итераций Якоби.

Совершенно другой подход к разработке параллельных программ состоит в использова­нии распараллеливающего компилятора. Такой компилятор сам находит параллельность в последовательной программе и создает корректно синхронизированную параллельную программу, которая содержит последовательный код и библиотечные вызовы. В разделе 12.2 приводится обзор распараллеливающих компиляторов. Там описан анализ зависимостей, на основе которого определяется, какие части программы могут выполняться параллельно. За­тем рассмотрены различные преобразования программ, наиболее часто применяемые для конвертирования последовательных циклов в параллельные.
Преимущество распараллели­вающих компиляторов состоит в том, что они освобождают программиста от изучения правил написания параллельных программ и могут быть использованы для распараллеливания уже имеющихся приложений. Однако с их помощью часто невозможно распараллелить сложные алгоритмы и, как правило, трудно добиться оптимальной производительности.

Третий способ разработки параллельных программ — использовать языки высокого уров­ня, в которых параллельность (вся или ее часть), взаимодействие и синхронизация неявны. В разделе 12.3 описано несколько классов языков высокого уровня и проанализированы ос­новные языки из каждого класса. Для иллюстрации использования каждого из языков и их сравнения в качестве примеров используются метод итераций Якоби и другие приложения из предыдущих глав. Также описаны три абстрактные модели, которые можно использовать для характеристики времени работы параллельных алгоритмов. Раздел заканчивается учебным примером по быстродействующему Фортрану (High Performance Fortran — HPF), самому по­следнему в семействе языков на основе Фортрана, предназначенных для научных вычисле­ний. Компиляторы языков, подобных HPF, опираются на методы распараллеливания и соз­дают программы, содержащие последовательный код и библиотечные вызовы.

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

450                                                      Часть 3. Синхронное параллельное программирование

вычислениями. Затем описаны метавычисления — новый подход, позволяющий объединять вычислительную мощность разнотипных машин, соединенных высокоскоростными сетями. Например, моделирующая часть научных вычислений может выполняться на удаленном су­перкомпьютере, а управляющая и графическая части — на локальной графической рабочей станции. В качестве конкретного примера в конце раздела 12.4 описан новый инфраструк­турный набор программных инструментов Globus для поддержки метавычислений.

Клиенты и серверы: файловые системы

Между производителем и потребителем существует однонаправленный поток информа­ции. Этот вид межпроцессного взаимодействия часто встречается в параллельных программах и не имеет аналогов в последовательных, поскольку в последовательной программе только один поток управления, тогда как производители и потребители — независимые процессы с собственными потоками управления и собственными скоростями выполнения.

Еще одной типичной схемой в параллельных программах является взаимосвязь типа клиент-сервер. Процесс-/ошеи/п запрашивает сервис, затем ожидает обработки запроса. Процесс-сервер многократно ожидает запрос, обрабатывает его, затем посылает ответ. Как показано на рис. 1.6, существует двунаправленный поток информации: от клиента к серверу и обратно. Отношения между клиентом и сервером в параллельном программирова­нии аналогичны отношениям между программой, вызы­вающей подпрограмму, и самой подпрограммой в последо­вательном программировании. Более того, как подпро­грамма может быть вызвана из нескольких мест программы, так и у сервера обычно есть много клиентов. Запросы каж­дого клиента должны обрабатываться независимо, однако параллельно может обрабатываться несколько запросов, подобно тому, как одновременно могут быть активны не­сколько вызовов одной и той же процедуры.

34                                                                 Глава 1. Обзор области параллельных вычислений

'Взаимодействие типа клиент-сервер встречается в операционных системах, объектно-ориентированных системах, сетях, базах данных и многих других программах. Типичный пример — чтение и запись файла. Для определенности предположим, что есть модуль файло­вого сервера, обеспечивающий две операции с файлом: read (читать) и write (писать). Ко­гда процесс-клиент хочет получить доступ к файлу, он вызывает операцию чтения или записи в соответствующем модуле файлового сервера.

На однопроцессорной машине или в другой системе с разделяемой памятью файловый сервер обычно реализуется набором подпрограмм (для операций read, write и т.д.) и струк­турами данных, представляющими файлы (например, дескрипторами файлов).
Следователь­но, взаимодействие между процессом-клиентом и файлом обычно реализуется вызовом соот­ветствующей процедуры. Однако, если файл разделяемый, важно, чтобы запись в него велась одновременно только одним процессом, а читаться он может одновременно несколькими. Эта разновидность задачи — пример так называемой задачи о "читателях и писателях", клас­сической задачи параллельного программирования, которая ставится и решается в главе 4, а также упоминается в последующих главах.

В распределенной системе клиенты и серверы обычно расположены на различных машинах. Например, рассмотрим запрос по World Wide Web, который возникает, когда пользователь откры­вает новый адрес URL в окне программы-броузера. Web-броузер является клиентским процессом, выполняемым на машине пользователя. Адрес URL косвенно указывает на другую машину, на ко­торой расположена Web-страница. Сама Web-страница доступна для процесса-сервера, выпол­няемого на другой машине. Этот процесс-сервер может уже существовать или может быть соз­дан; в любом случае он читает Web-страницу, определяемую адресом URL, и возвращает ее на машину клиента. В действительности при преобразовании адреса URL могут использоваться или создаваться дополнительные процессы на промежуточных машинах по пути следования.

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

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

---

---