Алгоритмы, параллельные по данным
В алгоритмах, параллельных по данным, несколько процессов выполняют один и тот же код и работают с разными частями разделяемых данных. Для синхронизации выполнения отдельных фаз процессов используются барьеры. Этот тип алгоритмов теснее всего связан с синхронными мультипроцессорами, или 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, а показана схема рабочего процесса. После инициализации локальных переменных рабочий процесс обменивается значениями на границе своей части матрицы image с соседями. Сначала он отправляет граничные значения соседу сверху и соседу снизу, затем получает значения от соседа снизу и от соседа сверху. Для обмена используются два массива каналов 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 с параметром, указывающим размер массива. Примитив createChan возвращает имя (индекс или адрес) дескриптора.
376 Часть 2. Распределенное программирование
Оператор send реализован с помощью примитива sendChan. Сначала процесс-отправитель вычисляет выражения и собирает значения в единое сообщение, которое обычно записывает в стек выполнения процесса, передающего сообщение. Затем вызывается примитив sendChan; его аргументами являются имя канала (возвращенное из вызова createChan) и само сообщение. Примитив sendChan сначала находит дескриптор канала. Если в списке заблокированных процессов есть хотя бы один процесс, то оттуда удаляется самый старый процесс, а сообщение копируется в его адресное пространство.
После этого дескриптор процесса помещается в список готовых к работе. Если заблокированных процессов нет, сообщение необходимо сохранить в списке сообщений дескриптора, поскольку передача является неблокирующей операцией, и, следовательно, отправителю нужно позволить продолжать выполнение.
Пространство для сохраненного сообщения можно выделять динамически из единого буферного пула, или с каждым каналом может быть связан отдельный коммуникационный буфер. Однако асинхронная передача сообщений поднимает важный вопрос реализации: что, если пространство ядра исчерпано? У ядра есть два выхода: либо остановить выполнение программы из-за переполнения буфера, либо заблокировать передающий процесс, пока не появится достаточно места.
Остановка программы — это решительный шаг, поскольку свободное пространство может вскоре и появиться, но программист сразу получает сигнал о том, что сообщения производятся быстрее, чем потребляются (это обычно говорит об ошибке). С другой стороны, блокировка передающего процесса нарушает неблокирующую семантику оператора send и усложняет ядро, создавая дополнительный источник блокировок. И здесь автор параллельной программы не может ничего предполагать о скорости и порядке выполнения процессов. Ядра операционных систем блокируют отправителей сообщений и при необходимости выгружают заблокированные процессы из памяти в файл подкачки, поскольку должны избегать отказов системы. Однако для языков программирования высокого уровня приемлемым выбором является остановка программы.
Оператор receive реализуется с помощью примитива receiveChan. Его аргументами являются имя канала и адрес буфера сообщений. Действия примитива receiveChan дуальны действиям примитива sendChan. Сначала ядро находит дескриптор, соответствующий выбранному каналу, затем проверяет его список сообщений. Если список не пуст, первое сообщение из него удаляется и копируется в буфер сообщений получателя. Если список сообщений пуст, процесс-получатель добавляется в список заблокированных процессов.
Получив сообщение, процесс- адресат распаковывает сообщение из буфера в соответствующие переменные.
Четвертый примитив, emptyChan, используется для реализации функции empty (ch). Он просто находит дескриптор и проверяет, не пуст ли список сообщений. В действительности структуры данных ядра находятся не в защищенной области, и выполняемый процесс может сам проверять свой список сообщений. Критическая секция не нужна, поскольку процессу нужно просмотреть только заголовок списка сообщений.
В листинге 10.1 показаны схемы всех четырех примитивов. Эти примитивы добавлены к однопроцессорному ядру (см. листинг 6.1). Значением executing является адрес дескриптора процесса, выполняемого в данный момент, a dispatcher — это процедура, планирующая работу процессов на данном процессоре. Действия примитивов sendChan и receiveChan очень похожи на действия примитивов Р и 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, поскольку каждый из них ссылается только на одну разделяемую переменную. В процессе Coordinator для ожидания установки всех элементов arrive можно использовать оператор for. Поскольку для продолжения процессов Worker должны быть установлены все элементы arrive, процесс Coordinator может проверять их в любом порядке. Конфликтов обращения к памяти теперь не будет, поскольку процессы ожидают изменения различных переменных, каждая из которых может храниться в своей строке кэш-памяти.
106 Часть 1 Программирование с разделяемыми переменными
Переменные arrive и continue в программах (3.12) и (3.13) являются примерами так называемого флага (флажка). Его устанавливает (поднимает) один процесс, чтобы сообщить другому о выполнении условия синхронизации. Дополним программы (3.12) и (3.13) кодом, который сбрасывает флаги (присваивая им значение 0) для подготовки к следующей итерации. При этом используются два основных правила.
(3.14) Правила синхронизации с помощью флагов: а) флаг синхронизации сбрасывается только процессом, ожидающим его установки; б) флаг нельзя устанавливать до тех пор, пока не известно точно, что он сброшен.
Первое правило гарантирует, что флаг не будет сброшен, пока процесс не определит, что он установлен. В соответствии с этим правилом в (3.12) флаг continue [ i] должен сбрасываться процессом Worker [ i], а обнулять все элементы массива arrive в (3.13) должен Coordinator. В соответствии со вторым правилом один процесс не устанавливает флаг, пока он не сброшен другим. В противном случае, если другой синхронизируемый процесс в дальнейшем ожидает повторной установки флага, возможна взаимная блокировка.
В (3.13) это означает, что Coordinator должен сбросить arrive [i] перед установкой continue [i]. Coordinator может сделать это, выполнив еще один оператор for после первого for в (3.13). Coordinator может также сбросить arrive [i] сразу после того, как дождался его установки. Добавив код сброса флагов, получим барьер с управляющим (листинг 3.12).
Хотя в программе 3.12 барьерная синхронизация реализована так, что конфликты обращения к памяти исключаются, у данного решения есть два нежелательных свойства Во-первых, нужен дополнительный процесс. Синхронизация с активным ожиданием эффективна, если только каждый процесс выполняется на отдельном процессоре, так что процессу Coordinator нужен свой собственный процессор. Но, возможно, было бы лучше использовать этот процессор для другого рабочего процесса.
Второй недостаток использования управляющего процесса состоит в том, что время выполнения каждой итерации процесса Coordinator, и, следовательно, каждого экземпляра барьерной синхронизации пропорционально числу процессов Worker. В итерационных алгоритмах часто все рабочие процессы имеют идентичный код. Это значит, что если каждый
Глава 3. Блокировки и барьеры 187
рабочий процесс выполняется на отдельном процессоре, то все они подойдут к барьеру примерно в одно время. Таким образом, все флаги arrive будут установлены практически одновременно. Однако процесс Coordinator проверяет флаги в цикле, по очереди ожидая, когда каждый из них будет установлен.
Обе проблемы можно преодолеть, объединив действия управляющего и рабочих процессов так, чтобы каждый рабочий процесс был одновременно и управляющим. Организуем рабочие процессы вдерево (рис. 3.1). Сигнал о том, что процесс подошел к барьеру (флаг arrive[i]), отсылается вверх по дереву, а сигнал о разрешении продолжения выполнения (флаг continue [i])— вниз. Узел рабочего процесса ждет, когда к барьеру подойдут его сыновья, после чего сообщает родительскому узлу о том, что он тоже подошел к барьеру.
Когда все сыновья корневого узла подошли к барьеру, это значит, что все остальные рабочие узлы тоже подошли к барьеру. Тогда корневой узел может сообщить сыновьям, что они могут продолжить выполнение. Те, в свою очередь, разрешают продолжить выполнение своим сыновьям, и так далее. Специфические действия, которые должен выполнить узел каждого вида, описаны в листинге 3.13. Операторы await в данном случае можно реализовать в виде циклов активного ожидания.
Реализация, приведенная в листинге 3.13, называется барьером с объединяющим деревом, поскольку каждый процесс объединяет результаты работы своих сыновних процессов и отправляет родительскому. Этот барьер использует столько же переменных, сколько и "централизованная" версия с управляющим процессом, но он намного эффективнее при больших п, поскольку высота дерева пропорциональна Iog2n.
Объединяющее дерево можно сделать еще эффективнее, если корневой узел будет отправлять единственное сообщение, которое разрешает продолжать работу всем остальным узлам. Например, узлы могут ждать, пока корневой узел не установит флаг continue. Сбрасывать флаг continue можно двумя способами. Первый способ — применить двойную буферизацию, т.е. использовать два флага продолжения и переключаться между ними. Второй способ — изменять смысл флага продолжения, т.е. на четных циклах ждать, когда его значением станет 1, а на нечетных — 0.
108 Часть 1. Программирование с разделяемыми переменными
3.4.3. Симметричные барьеры
В барьере с объединяющим деревом процессы играют разные роли. Промежуточные узлы дерева выполняют больше действий, чем листья или корень. Кроме того, корневой узел должен ждать, пока сигналы о прибытии пройдут через все дерево. Если все процессы работают по одному алгоритму и выполняются на отдельных процессорах, то к барьеру они подойдут примерно одновременно. Таким образом, если все процессы по пути к барьеру выполняют одну и ту же последовательность действий, то они могут пройти барьер с одинаковой скоростью.
В этом разделе представлены симметричные барьеры, особенно удобные на многопроцессорных машинах с разделенной памятью и неоднородным временем доступа к памяти.
Симметричный барьер для n процессов строится из пар простых двухпроцессных барьеров. Чтобы создать двухпроцессный барьер, можно использовать метод "управляющий-рабочий", но тогда действия двух процессов будут различаться. Вместо этого можно создать полностью симметричный барьер. Пусть каждый процесс при достижении им барьера устанавливает собственный флаг. Если w [ i ] и w [ j ] — два процесса, то симметричный барьер для них реализуется следующим образом.
Последние три строки каждого процесса исполняют роли, о которых было сказано выше. Первая же строка на первый взгляд может показаться лишней, поскольку в ней задано просто ожидание сброса собственного флага процесса. Однако она необходима, чтобы не допустить ситуацию, когда процесс успеет вернуться к барьеру и установить собственный флаг до того, как другой процесс сбросит флаг на предыдущем использовании барьера. Итак, чтобы программа соответствовала правилам синхронизации флагами (3.14), необходимы все четыре строки программы.
Теперь необходимо решить вопрос, как объединить экземпляры двухпроцессных барьеров, чтобы получить барьер для п процессов. В частности, нужно построить схему связей так, чтобы каждый процесс в конце концов знал о том, что остальные процессы достигли барьера. Лучше всего для этого подойдет некоторая бинарная схема соединений, размер которой пропорционален числу Iog2n.
Пусть Worker [I :n] — массив процессов. Если n является степенью 2, то процессы можно объединить по схеме, показанной на рис. 3.2. Этот тип барьеров называется барьером-бабочкой (butterfly barrier) из-за схемы связей, аналогичной схеме соединений в преобразовании Фурье, которая похожа на бабочку. Как видно из рисунка, барьер-бабочка состоит из Iog2n уровней. На разных уровнях процесс синхронизируется с разными процессами.
На уровне s процесс синхронизируется с процессом на расстоянии 2"\ Когда каждый процесс прошел через все уровни, до барьера дошли все процессы и могут быть продолжены. Дело в том, что каждый процесс прямо или косвенно синхронизируется со всеми остальными. (Если число n не является степенью 2, то барьер-бабочку можно построить, используя наименьшую степень 2, которая больше п. Отсутствующие процессы заменяются существующими, хотя это и не очень эффективно.)
Другая схема соединений показана на рис. 3.3. Она лучше, Поскольку может быть использована при любых n (не только степенях 2). Здесь также несколько уровней, и на уровне s рабочий процесс синхронизируется с процессом на расстоянии 2*~'. На каждом двухпроцессном барьере
В реализации барьера для п процессов, независимо от используемой схемы соединений, важно избежать состояния гонок, которое может возникнуть при использовании нескольких экземпляров базового двухпроцессного барьера. Рассмотрим барьер-бабочку (см. рис. 3.2). Предположим, что есть только один массив переменных-флагов и они используются, как указано в(3.15). Пусть процесс1 приходит к первому уровню и устанавливает флаг arrive [1]. Пусть процесс 2 — медленный, и еще не достиг первого уровня, а процессы 3 и 4 дошли до первого уровня барьера, установили флаги, сбросили их друг у друга и прошли на второй уровень. На втором уровне процесс 3 должен синхронизироваться с процессом 1, поэтому он ожидает установки флага arrive [1]. Флаг уже установлен, поэтому процесс 3 сбрасывает флаг arrive [1] и переходит на уровень 3, хотя этот флаг был установлен для процесса 2. Таким образом, в результате работы сети некоторые процессы пройдут барьер раньше, чем должны, а другие будут вечно ожидать перехода на следующий уровень. Та же проблема может возникнуть и при использовании барьера с распространением (см. рис. 3.3).
Описанные ошибки синхронизации являются следствием того, что используется только один набор флагов для каждого процесса.
Для решения этой проблемы можно воспользоваться своим собственным набором флагов для каждого уровня барьера для п процессов, но лучше присваивать флагам больше значений.
Если флаги целочисленные, их можно использовать как возрастающие счетчики, которые
запоминают количество уровней барьера, пройденных каждым процессом. Начальное значе-
каждого флага— 0. Каждый раз, когда рабочий процесс i приходит на новый уровень
ьера, он увеличивает значение счетчика arrive [i]. Затем рабочий процесс i определяет
мер процесса-партнера j на текущем уровне и ожидает, пока значение arrive [ j ] не станет, как минимум, таким же, как значение arrive [ i ]. Это описывается следующим кодом.
# код барьера для рабочего процесса i for [s = 1 to num_stages] {
arrive[i] = arrive[i] + 1;
определить соседа j на уровне s
while (arrivefj] < arrive[i]) skip; }
Таким способом рабочий процесс i убеждается, что процесс j зашел, как минимум, так же далеко. Описанный подход к использованию возрастающих счетчиков и уровней позволяет избе-жагь состояния гонок, избавляет от необходимости для процесса ожидать переустановку соб-юнного флага (первая строка кода (3.15)) и переустанавливать флаг другого процесса последняя строка кода(3.15)). Таким образом, каждый уровень каждого барьера— это всего и строки кода. Единственный недостаток этого способа — счетчики все время возрастают, поэтому теоретически возможно их переполнение. Однако на практике это крайне маловероятно.
110 Часть 1. Программирование с разделяемыми переменными
Подведем итог темы барьеров. Наиболее прост и удобен для небольшого числа процессов барьер-счетчик, но при условии, что существует неделимая инструкция "извлечь и сложить". Симметричный барьер наиболее эффективен для машин с разделяемой памятью, поскольку все процессы выполняют один и тот же код, а в идеальном случае — с одинаковой скоростью. (На машинах с распределенной памятью часто более эффективным является барьер с древовидной структурой, сокращающий взаимодействие между процессами.) При любой структуре барьера основная задача — избежать состояния гонок.Это достигается с помощью либо множества флагов (по одному на каждый уровень), либо возрастающих счетчиков.
Библиотеки параллельного программирования
Библиотеки параллельного программирования представляют собой набор подпрограмм, обеспечивающих создание процессов, управление ими, взаимодействие и синхронизацию. Эти подпрограммы, и особенно их реализация, зависят от того, какой вид параллельности поддерживает библиотека — с разделяемыми переменными или с обменом сообщениями.
При создании программ с разделяемыми переменными на языке С обычно используют стандартную библиотеку 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 в jacobi. Это позволяет 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 National Labs и Карл Кессельман (Carl Kesselman) из USC's Information Sciences Institute. Их совместные разработки буквально охватывают весь земной шар.
Цель проекта Globus — обеспечить базовый набор инструментов для разработки переносимых высокопроизводительных сервисов, поддерживающих метавычислительные приложения.
30 Список представлен руководителями проекта Globus Фостером и Кессельманом в [Foster and Kesselman, 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 представила Connection 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 Systems, 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-х с появлением первой Connection 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 Machine — 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.
В третьей директиве указано, что вектор position должен отображаться на процессоры циклически (по полосам); соответственно, вектор 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 — как реализовать серверы в виде процессов, взаимодействующих с клиентами с помощью пересылки сообщений, удаленных вызовов процедур или рандеву.