«В.П. Гергель, Р.Г. Стронгин ОСНОВЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ ДЛЯ МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ Учебное пособие Издание 2-е, дополненное Издательство Нижегородского госуниверситета Нижний Новгород 2003 УДК ...»

Достижение максимально возможного быстродействия ( p = n 2 ) 1. Выбор параллельного способа вычислений. Выполним анализ информационных зависимостей в алгоритме умножения матрицы на вектор для выбора возможных способов распараллеливания. Как можно заметить выполняемые при проведении вычислений операции умножения отдельных строк матрицы на вектор являются независимыми и могут быть выполнены параллельно;

умножение каждой строки на вектор включает независимые операции поэлементного умножения и тоже могут быть выполнены параллельно;

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

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

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

Для иллюстрации на рис. 4.5 приведена вычислительная схема для процессоров группы Qi при размерности матрицы n = 4.

Рис. 4.5. Вычислительная схема операции умножения строки матрицы на вектор 2. Оценка показателей эффективности алгоритма. Время выполнения параллельного алгоритма при использовании p = n процессоров определяется временем выполнения параллельной операции умножения и временем выполнения каскадной схемы Как результат, показатели эффективности алгоритма определяются следующими соотношениями:

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

Применение вычислительной системы с топологией в виде прямоугольной двумерной решетки размера n n приводит к простой и наглядной интерпретации выполняемых вычислений (структура сети соответствует структуре обрабатываемых данных). Для такой топологии строки матрицы A наиболее целесообразно разместить по горизонталям решетки; в этом случае элементы вектора x должны быть разосланы по вертикалям вычислительной системы. Выполнение вычислений при таком размещении данных может осуществляться параллельно по строкам решетки; как результат, общее количество передач данных совпадает с результатами для линейки ( Lпд = n 1 ).

Коммуникационные действия, выполняемые при решении поставленной задачи, состоят в передаче данных между парами процессоров МВС. Подробный анализ длительности реализации таких операций проведен в п. 3.3.

4. Рекомендации по реализации параллельного алгоритма. При реализации параллельного алгоритма целесообразно выделить начальный этап по загрузке используемых процессоров исходными данными. Наиболее просто такая инициализация обеспечивается при топологии вычислительной системы с топологией в виде полного графа (загрузка обеспечивается при помощи одной параллельной операции пересылки данных). При организации множества процессоров в виде гиперкуба может оказаться полезной двухуровневое управление процессом начальной загрузки, при которой центральный управляющий процессор обеспечивает рассылку строк матрицы и вектора к управляющим процессорам процессорных групп Qi, 1 i n, которые, в свою очередь, рассылают элементы строк матрицы и вектора по исполнительным процессорам. Для топологий в виде линейки или кольца требуется n последовательных операций передачи данных с последовательно убывающим объемом пересылаемых данных от n( n + 1) до 2 элементов.

Использование параллелизма среднего уровня ( n < p < n 2 ) 1. Выбор параллельного способа вычислений. При уменьшении доступного количества используемых процессоров ( p < n ) обычная каскадная схема суммирования при выполнении операций умножения строк матрицы на вектор становится не применимой. Для простоты изложения материала положим p = nk и воспользуется модифицированной каскадной схемой. Начальная нагрузка каждого процессора в этом случае увеличивается и процессор загружается ( n / k ) частями строк матрицы A и вектора x. Время выполнения операции умножения матрицы на вектор может быть оценено как величина При использовании количества процессоров, необходимого для реализации модифицированной каскадной схемы, т.е. при p = 2n(n / log 2 n), данное выражение дает оценку времени исполнения При количестве процессоров T p = n + 1, может быть предложена новая схема параллельного выполнения вычислений, при которой для каждой итерации каскадного суммирования используются неперекрывающиеся наборы процессоров.

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

множество процессоров Q разбивается на непересекающиеся процессорные группы при этом группа Qi, 1 i k, состоит из n / итерации каскадного алгоритма (группа Q0 применяется для реализации поэлементного умножения);

общее количество процессоров p = 2n 1 ;

инициализация вычислений состоит в поэлементной загрузке процессоров группы Q значениями 1 строки матрицы и вектора x ; после начальной загрузки выполняется параллельная операция поэлементного умножения и последующей реализации обычной каскадной схемы суммирования;

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

В результате применения описанного алгоритма множество процессоров Q реализует конвейер для выполнения операции умножения строки матрицы на вектор. На подобном конвейере одновременно могут находиться несколько отдельных строк матрицы на разных стадиях обработки. Так, например, после поэлементного умножения элементов первой строки и вектора x процессоры группы Q1 будут выполнять первую итерацию каскадного алгоритма для первой строки матрицы, а процессоры группы Q0 будут исполнять поэлементное умножение значений второй строки матрицы и т.д. Для иллюстрации на рис. 4.6 приведена ситуация процесса вычислений после 2 итераций конвейера при n = 4.

Рис. 4.6. Состояние конвейера для операции умножения строки матрицы на вектор после 2. Оценка показателей эффективности алгоритма. Умножение первой строки на вектор в соответствии с каскадной схемой будет завершено, как и обычно, после выполнения ( log 2 n + 1 ) параллельных операций. Для других же строк – в соответствии с конвейерной схемой организации вычислений - появление результатов умножения каждой очередной строки будет происходить после завершения каждой последующей итерации конвейера. Как результат, общее время выполнения операции умножения матрицы на вектор может быть выражено величиной Данная оценка является несколько большей, чем время выполнения параллельного алгоритма, описанного в предыдущем пункте ( T p = n + 1 ), однако вновь предлагаемый способ требует меньшего количества передаваемых данных (вектор x пересылается только однократно). Кроме того, использование конвейерной схемы приводит к более раннему появлению части результатов вычислений (что может быть полезным в ряде ситуаций обработки данных).

Как результат, показатели эффективности алгоритма определяются соотношениями следующего вида:

3. Выбор топологии вычислительной системы. Целесообразная топология вычислительной системы полностью определяется вычислительной схемой – это полное бинарное дерево высотой log 2 n + 1. Количество передач данных при такой топологии сети определяется общим количеством итераций, выполняемых конвейером, т.е.

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

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

Организация параллельных вычислений при p = n 1. Выбор параллельного способа вычислений. При использовании n процессоров для умножения матрицы A на вектор x может быть использован ранее уже рассмотренный в пособии параллельный алгоритм построчного умножения, при котором строки матрицы распределяются по процессорам построчно и каждый процессор реализует операцию умножения какой-либо отдельной строки матрицы A на вектор x. Другой возможный способ организации параллельных вычислений может состоять в построении конвейерной схемы для операции умножения строки матрицы на вектор (скалярного произведения векторов) путем расположения всех имеющихся процессоров в виде линейной последовательности (линейки).

Подобная схема вычислений может быть определена следующим образом. Представим множество процессоров в виде линейной последовательности (см. рис. 4.7):

каждый процессор q j, 1 j n, используется для умножения элементов j столбца матрицы и j элемента вектора x. Выполнение вычислений на каждом процессоре q j, 1 j n, состоит в следующем:

запрашивается очередной элемент j столбца матрицы;

выполняется умножение элементов aij и x j ;

запрашивается результат вычислений S предшествующего процессора;

выполняется сложение значений S S + aij x j ;

полученный результат S пересылается следующему процессору.

Рис. 4.7. Состояние линейного конвейера для операции умножения строки матрицы на вектор после выполнения двух итераций При инициализации описанной схемы необходимо выполнить ряд дополнительных действий:

при выполнении первой итерации каждый процессор дополнительно запрашивает элемент вектора x j ;

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

Кроме того, для однородности описанной схемы для первого процессора q1, у которого нет предшествующего процессора, целесообразно ввести пустую операцию сложения Для иллюстрации на рис. 4.7 показано состояние процесса вычислений после второй итерации конвейера при n = 3.

2. Оценка показателей эффективности алгоритма. Умножение первой строки на вектор в соответствии с описанной конвейерной схемой будет завершено после выполнения ( n + 1 ) параллельных операций. Результат умножения следующих строк будет происходить после завершения каждой очередной итерации конвейера (напомним, итерация каждого процессора включает выполнение операций умножения и сложения). Как результат, общее время выполнения операции умножения матрицы на вектор может быть выражено соотношением:

Данная оценка также является большей, чем минимально возможное время T p = 2n выполнения параллельного алгоритма при p = n. Полезность использования конвейерной вычислительной схемы состоит, как отмечалось в предыдущем пункте, в уменьшении количества передаваемых данных и в более раннем появлении части результатов вычислений.

Показатели эффективности данной вычислительной схемы определяются соотношениями:

3. Выбор топологии вычислительной системы. Необходимая топология вычислительной системы для выполнения описанного алгоритма однозначно определяется предлагаемой вычислительной схемой – это линейно упорядоченное множество процессоров (линейка).

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

на каждый из имеющихся процессоров пересылается вектор x и k = n / p строк матрицы;

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

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

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

2. Оценка показателей эффективности алгоритма. Время выполнения параллельного алгоритма определяется оценкой где величина n / p есть наибольшее количество строк, загружаемых на один процессор. С учетом данной оценки показатели эффективности предлагаемой вычислительной схемы имеют вид:

При кратности размера матрицы и количества процессоров показатели ускорения и эффективности алгоритма приводятся к виду:

и принимают, тем самым, максимально возможные значения.

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

4.3. Матричное умножение Задача умножения матрицы на матрицу определяется соотношениями (для простоты изложения материала будем предполагать, что перемножаемые матрицы A и B являются квадратными и имеют порядок n n ).

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

Макрооперационный анализ алгоритмов решения задач Задача матричного умножения требует для своего решения выполнение большого количества операций ( n скалярных умножений и сложений). Информационный граф алгоритма при большом размере матриц становится достаточно объемным и, как результат, непосредственный анализ этого графа затруднен. После выявления информационной независимости выполняемых вычислений могут быть предложены многочисленные способы распараллеливания алгоритма.

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

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

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

Пусть количество процессоров составляет p = k, а количество строк и столбцов матрицы является кратным величине k = p, т.е. n = mk. Представим исходные матрицы A, B и результирующую матрицу C в виде наборов прямоугольных блоков размера m m. Тогда операцию матричного умножения матриц A и B в блочном виде можно представить следующим образом:

где каждый блок C ij матрицы C определяется в соответствии с выражением Информационный граф алгоритма умножения при подобном представлении матриц показан на рис. 4. (на рисунке представлен фрагмент графа для вычисления только одного блока матрицы C ). При анализе этого графа можно обратить внимание на взаимную независимость вычислений блоков C ij матрицы C.

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

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

Рис. 4.9. Информационный граф матричного умножения при блочном представлении матриц Для организации параллельных вычислений предположим, что процессоры образуют логическую прямоугольную решетку размером k k (обозначим через pij процессор, располагаемый на пересечении i строки и j столбца решетки). Основные положения параллельного метода, известного как алгоритм Фокса (Fox) [15], состоят в следующем:

• каждый из процессоров решетки отвечает за вычисление одного блока матрицы C ;

• в ходе вычислений на каждом из процессоров p ij располагается четыре матричных блока:

блок C ij матрицы C, вычисляемый процессором;

блок Aij матрицы A, размещенный в процессоре перед началом вычислений;

блоки Aij, Bij матриц A и B, получаемые процессором в ходе выполнения вычислений;

Выполнение параллельного метода включает:

этап инициализации, на котором на каждый процессор p ij передаются блоки Aij, Bij и обнуляются блоки C ij на всех процессорах;

• этап вычислений, на каждой итерации l, 1 l k, которого выполняется:

для каждой строки i, 1 i k, процессорной решетки блок Aij процессора p ij пересылается на все процессоры той же строки i ; индекс j, определяющий положение процессора p ij в строке, вычисляется по соотношению ( mod есть операция получения остатка от целого деления);

- полученные в результаты пересылок блоки Aij, Bij каждого процессора p ij перемножаются и прибавляются к блоку C ij блоки Bij каждого процессора p ij пересылаются процессорам p ij, являющимися соседями сверху в столбцах процессорной решетки (блоки процессоров из первой строки решетки пересылаются процессорам последней строки решетки).

Для пояснения приведенных правил параллельного метода на рис. 4.10 приведено состояние блоков на каждом процессоре в ходе выполнения итераций этапа вычислений (для процессорной решетки Приведенный параллельный метод матричного умножения приводит к равномерному распределению вычислительной нагрузки между процессорами Вместе с тем, блочное представление матриц приводит к некоторому повышению объема пересылаемых между процессорами данных - на этапе инициализации и на каждой итерации этапа вычислений на каждый процессор передается 2 блока данных общим объемом 2m. Учитывая выполняемое количество итераций метода, объем пересылаемых данных для каждого процессора составляет величину Рис. 4.10. Состояние блоков на каждом процессоре в ходе выполнения итераций этапа вычислений Объем пересылаемых данных может быть снижен, например, при использовании строкового (для A ) и столбцового (для B ) разбиения матриц, при котором справедлива оценка Данные оценки показывают, что различие объемов пересылаемых данных является не столь существенным и данное различие уменьшается при увеличении числа используемых процессоров.

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

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

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

Возможные способы решения этой задачи широко обсуждаются в литературе; один из наиболее полных обзоров алгоритмов сортировки содержится в работе [7]. Вычислительная трудоемкость процедуры упорядочивания является достаточно высокой. Так, для ряда известных простых методов (пузырьковая сортировка, сортировка включением и др.) количество необходимых операций определяется квадратичной зависимостью от числа упорядочиваемых данных Для более эффективных алгоритмов (сортировка слиянием, сортировка Шелла, быстрая сортировка) трудоемкость определяется величиной Данное выражение дает также нижнюю оценку необходимого количества операций для упорядочивания набора из n значений; алгоритмы с меньшей трудоемкостью могут быть получены только для частных вариантов задачи.

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

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

Параллельное обобщение базовой операции сортировки 1. При детальном рассмотрении способов упорядочивания данных, применяемых в алгоритмах сортировки, можно обратить внимание, что многие методы основаны на применении одной и той же базовой операции "сравнить и переставить" (compare-exchange), состоящей в сравнении той или иной пары значений из сортируемого набора данных и перестановки этих значений, если их порядок не соответствует условиям сортировки // операция "сравнить и переставить" Целенаправленное применение данной операции позволяет упорядочить данные; в способах выбора пар значений для сравнения собственно и проявляется различие алгоритмов сортировки. Так, например, в пузырьковой сортировке [7] осуществляется последовательное сравнение всех соседних элементов; в результате прохода по упорядочиваемому набору данных в последнем (верхнем) элементе оказывается максимальное значение ("всплывание пузырька"); далее для продолжения сортировки этот уже упорядоченный элемент отбрасывается и действия алгоритма повторяются // пузырьковая сортировка // передача права доступа к ресурсу процессу ProcessNum = 1;

Реализованный в программе способ гарантирует взаимоисключение, однако такому решению присущи два существенных недостатка:

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

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

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

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

int ResourceProc1 = 0; // =1 – ресурс занят процессом int ResourceProc2 = 0; // =1 – ресурс занят процессом Process_1() { while (1) { // повторять, пока ресурс используется процессом while ( ResourceProc2 == 1 );

ResourceProc1 = 1;

< Использование общего ресурса > ResourceProc1 = 0;

Process_2() { while (1) { // повторять, пока ресурс используется процессом while ( ResourceProc1 == 1 );

ResourceProc2 = 1;

< Использование общего ресурса > ResourceProc2 = 0;

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

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

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

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

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

int ResourceProc1 = 0; // =1 – ресурс занят процессом int ResourceProc2 = 0; // =1 – ресурс занят процессом Process_1() { while (1) { // установить, что процесс 1 пытается занять ресурс ResourceProc1 = 1;

// повторять, пока ресурс занят процессом while ( ResourceProc2 == 1 );

< Использование общего ресурса > ResourceProc1 = 0;

Process_2() { while (1) { // установить, что процесс 2 пытается занять ресурс ResourceProc2 = 1;

// повторять, пока ресурс используется процессом while ( ResourceProc1 == 1 );

< Использование общего ресурса > ResourceProc2 = 0;

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

5.5 и 5.6; дополнительная информация по проблеме может быть получена в [6,13].

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

int ResourceProc1 = 0; // =1 – ресурс занят процессом int ResourceProc2 = 0; // =1 – ресурс занят процессом Process_1() { while (1) { ResourceProc1=1; // процесс 1 пытается занять ресурс // повторять, пока ресурс занят процессом while ( ResourceProc2 == 1 ) { ResourceProc1 = 0; // снятие занятости ресурса ResourceProc1 = 1;

< Использование общего ресурса > ResourceProc1 = 0;

Process_2() { while (1) { ResourceProc2=1; // процесс 2 пытается занять ресурс // повторять, пока ресурс используется процессом while ( ResourceProc1 == 1 ) { ResourceProc2 = 0; // снятие занятости ресурса ResourceProc2 = 1;

< Использование общего ресурса > ResourceProc2 = 0;

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

Алгоритм Деккера В алгоритме Деккера предлагается объединение предложений вариантов 1 и 4 решения проблемы взаимоисключения.

int ProcessNum=1; // номер процесса для доступа к ресурсу int ResourceProc1 = 0; // =1 – ресурс занят процессом int ResourceProc2 = 0; // =1 – ресурс занят процессом Process_1() { while (1) { ResourceProc1=1; // процесс 1 пытается занять ресурс /* цикл ожидания доступа к ресурсу */ while ( ResourceProc2 == 1 ) { // повторять, пока ресурс занят процессом < Использование общего ресурса > ResourceProc1 = 0;

Process_2() { while (1) { ResourceProc2=1; // процесс 2 пытается занять ресурс /* цикл ожидания доступа к ресурсу */ while ( ResourceProc1 == 1 ) { // повторять, пока ресурс используется процессом < Использование общего ресурса > ResourceProc2 = 0;

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

Алгоритм Деккера может быть обобщен на случай произвольного количества процессов (см. [16]), однако, такое обобщение приводит к заметному усложнению выполняемых действий. Кроме того, программное решение проблемы взаимоисключения процессов приводит к нерациональному использованию процессорного времени ЭВМ (процессу, ожидающему освобождения ресурса, постоянно требуется процессор для проверки возможности продолжения – активное ожидание (busy wait)).

Семафоры Дейкстры Под семафором S обычно понимается [16] переменная особого типа, значение которой может опрашиваться и изменяться только при помощи специальных операций P(S) и V(S), реализуемых в соответствии со следующими алгоритмами:

• операция P(S) • операция V(S) если < один или несколько процессов ожидают S > то < снять ожидание у одного из ожидающих Принципиальным в понимании семафоров является то, что операции P(S) и V(S) предполагаются неделимыми, что гарантирует взаимоисключение при использование общих семафоров (для обеспечения неделимости операции обслуживания семафоров обычно реализуются средствами операционной системы).

Различают два основных типа семафоров. Двоичные семафоры принимают только значения 0 и 1, область значений общих семафоров – неотрицательные целые значения. В момент создания семафоры инициализируются некоторым целым значением.

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

Semaphore Mutex=1; // семафор взаимоисключения процессов Process_1() { while (1) { // проверить семафор и ждать, если ресурс занят P(Mutex);

< Использование общего ресурса > // освободить один из ожидающих ресурса процессов // увеличить семафор, если нет ожидающих процессов V(Mutex);

Process_2() { while (1) { // проверить семафор и ждать, если ресурс занят P(Mutex);

< Использование общего ресурса > // освободить один из ожидающих ресурса процессов // увеличить семафор, если нет ожидающих процессов V(Mutex);

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

5.5. Модель программы в виде дискретной системы В самом общем виде тупик может быть определен [6] как ситуация, в которой один или несколько процессов ожидают какого-либо события, которое никогда не произойдет. Важно отметить, что состояние тупика может наступить не только вследствие логических ошибок, допущенных при разработке параллельных программ, но и в результате возникновения тех или иных событий в вычислительной системе (выход из строя отдельных устройств, нехватка ресурсов и т.п.). Простой пример тупика может состоять в следующем. Пусть имеется два процесса, каждый из которых в монопольном режиме обрабатывает собственный файл данных. Ситуация тупика возникнет, например, если первому процессу для продолжения работы потребуются файл второго процесса и одновременно второму процессу окажется необходимым файл первого процесса (см. рис. 5.3).

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

В данном разделе будет рассмотрен один из аспектов проблемы тупика – анализ причин возникновения тупиковых ситуаций при использовании разделяемых ресурсов и разработка на этой основе методов предотвращения тупиков. Дополнительная информация по теме может быть получена в [6,13].

Могут быть выделены следующие необходимые условия тупика [13]:

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

процессы удерживают за собой ресурсы, уже выделенные им, ожидая в то же время выделения дополнительных ресурсов (условие ожидания ресурсов);

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

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

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

Определение состояния программы Состояние программы может быть представлено в виде ориентированного графа (V,E) со следующей интерпретацией и условиями [13]:

1. Множество V разделено на два взаимно пересекающихся подмножества P и R, представляющие процессы и ресурсы программы.

2. Граф является "двудольным" по отношению к подмножествам вершин P и R, т.е. каждое ребро e E соединяет вершину P с вершиной R. Если ребро e имеет вид e = ( pi, R j ), то e есть ребро запроса и интерпретируется как запрос от процесса pi на единицу ресурса R j. Если ребро e имеет вид e = (R j, pi ), то e есть ребро назначения и выражает назначение единицы ресурса R j процессу pi.

3. Для каждого ресурса R j R существует целое k j 0, обозначающее количество единиц ресурса R j.

4. Пусть ( a, b) - число ребер, направленных от вершины a к вершине b. Тогда при принятых обозначениях для ребер графа должны выполняться условия:

Может быть сделано не более k j назначений (распределений) для ресурса R j, т.е.

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

Граф, построенный с соблюдением всех перечисленных правил, именуется в литературе как граф "процесс-ресурс". Для примера, на рис. 5.3 приведен граф программы, в которой ресурс 1 (файл 1) выделен процессу 1, который, в свою очередь, выдал запрос на ресурс 2 (файл 2). Процесс 2 владеет ресурсом 2 и нуждается для своего продолжения в ресурсе 1.

Состояние программы, представленное в виде графа "процесс-ресурс", изменяется только в результате запросов, освобождений или приобретений ресурсов каким-либо из процессов программы.

Запрос. Если программа находится в состоянии S и процесс pi не имеет невыполненных запросов, то pi может запросить любое число ресурсов (в пределах ограничения 4). Тогда программа переходит в состояние T Состояние T отличается от S только дополнительными ребрами запроса от pi к затребованным ресурсам.

Приобретение. Операционная система может изменить состояние программы S на состояние T в результате операции приобретения ресурсов процессом pi тогда и только тогда, когда pi имеет запросы на выделение ресурсов и все такие запросы могут быть удовлетворены, т.е. если Граф T идентичен S за исключением того, что все ребра запроса ( pi, R j ) для pi обратны ребрам ( R j, pi ), что отражает выполненное распределение ресурсов.

Рис. 5.4. Пример переходов программы из состояния в состояние Освобождение. Процесс pi может вызвать переход из состояния S в состояние T с помощью освобождения ресурсов тогда и только тогда, когда pi не имеет запросов, а имеет некоторые распределенные ресурсы, т.е.

В этой операции pi может освободить любое непустое подмножество своих ресурсов. Результирующее состояние T идентично исходному состоянию S за исключением того, что в T отсутствуют некоторые ребра приобретения из S (из S удаляются ребра ( R j, p i ) каждой освобожденной единицы ресурса R j ).

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

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

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

Под программой будем понимать систему где есть множество состояний программы (S, T, U,…), а P представляет множество процессов ( p1, p 2,L, p n ). Процесс pi P есть частичная функция, отображающая состояния программы в непустые подмножества состояний где {} есть множество всех подмножеств. Обозначим множество состояний, в которые может перейти программа при помощи процесса pi (область значений процесса pi ) при нахождении программы в состоянии S через p i (S ). Возможность перехода программы из состояния S в состояние T в результате некоторой операции над ресурсами в процессе pi (т.е. T pi (S ) ) будем пояснять при помощи записи Обобщим данное обозначение для указания достижимости состояния T из состояния S в результате выполнения некоторого произвольного количества переходов в программе Обнаружение и исключение тупиков С учетом построенной модели и введенных обозначений можно выделить ряд ситуаций, возникающих при выполнении программы и представляющих интерес при рассмотрении проблемы тупика:

• процесс pi заблокирован в состоянии S, если программа не может изменить свое состояние при помощи этого процесса, т.е. если pi (S ) = ;

• процесс pi находится в тупике в состоянии S, если этот процесс является заблокированным в любом состоянии T, достижимом из состояния S, т.е.

• состояние S называется тупиковым, если существует процесс pi, находящийся в тупике в этом состоянии;

• состояние S есть безопасное состояние, если любое состояние T, достижимое из S, не является тупиковым.

Для примера на рис. 5.5 приведен граф переходов программы, в котором состояния U и V являются безопасными, состояния S и T и W не являются безопасными, а состояние W есть состояние тупика.

Рассмотренная модель программы может быть использована для определения возможных состояний программы, обнаружения и недопущения тупиков. В качестве возможных теоретических результатов такого анализа может быть приведена теорема [13].

Теорема. Граф "процесс-ресурс" для состояния программы с ресурсами единичной емкости указывает на состояние тупика тогда и только тогда, когда он содержит цикл.

Дополнительный материал по исследованию данной модели может быть получен в [13].

5.6. Модель программы в виде сети Петри Другим возможным способом моделирования состояний и функционирования параллельной программы является использование математических моделей и методов исследования дискретных систем, разработанных в рамках теории сетей Петри [13]. При таком подходе в качестве модели программы может быть использована сеть Петри, представляемая размеченным ориентированным графом (V, E, M 0 ) (изложение материала осуществляется в соответствии с работой [13] за исключением приведения системы обозначений к виду, принятому в данном пособии):

1. Множество вершин сети V разделено на два взаимно пересекающихся подмножества вершинпереходов P и вершин-мест R Вершины-места обычно изображаются кружками, вершины-переходы представляются в виде прямоугольников или линий-барьеров.

2. Граф сети является "двудольным" по отношению к подмножествам вершин P и R, т.е. каждое ребро e E соединяет вершину P с вершиной R. Задание ребер графа может быть выполнено, например, при помощи функций инцидентности ненулевые значения которых задают множество ребер E (при H ( pi, R j ) = 1 сеть содержит ребро вида e = ( pi, R j ), при F ( R j, pi ) = 1 сеть содержит ребро вида e = ( R j, pi ) ).

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

Рис. 5.6. Пример сети Петри Для пояснения введенных понятий на рис. 5.6 показан пример сети Петри с тремя переходами и четырьмя вершинами мест.

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

Разметка мест в этом случае интерпретируется как количество имеющихся (нераспределенных) единиц ресурса.

Сеть Петри может функционировать (изменять свое состояние), переходя от разметки к разметке.

Обозначим через F ( R j ) множество переходов, к которым имеются ребра из вершины-места R j по аналогии, H ( R j ) есть множество переходов, из которых имеются ребра в вершину-место R j С учетом введенных обозначений правила функционирования сети состоят в следующем:

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

В результате срабатывания перехода pi разметка сети M сменяется разметкой M' по правилу:

Рис. 5.7. Состояние сети после срабатывания перехода p Другими словами, переход pi изымает по одной фишке своего входного места и добавляет по одной в каждое свое выходное место. Будем говорить далее, что разметка M' следует за разметкой M, а M предшествует M', и обозначать этот факт Так, в сети на рис. 5.6 могут сработать переходы p1 и p3 ; состояние сети после срабатывания перехода p3 показано на рис. 5.7.

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

При исследовании процессов функционирования сетей Петри широко используется следующий ряд дополнительных понятий и обозначений:

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

• разметка M' достижима в сети от разметки M если разметка M' может быть получена в результате некоторого количества срабатываний сети, начиная от разметки M;

• разметка M достижима в сети, если M 0 M ; множество всех достижимых разметок обозначим через M;

• переход pi достижим от разметки M, если существует достижимая от M разметка M', в которой переход pi может сработать;

• переход pi достижим в сети, если он достижим от M 0 ;

• переход pi называется живым, если он достижим от любой разметки из M; сеть является живой, если все ее переходы живы;

• место R j называется ограниченным, если существует такое число k, что M ( p ) k для любой разметки из M; сеть является ограниченной, если все ее места ограничены.

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

6. Учебно-практическая задача: Решение дифференциальных уравнений в частных производных Дифференциальные уравнения в частных производных представляют собой широко применяемый математический аппарат при разработке моделей в самых разных областях науки и техники. К сожалению, явное решение этих уравнений в аналитическом виде оказывается возможным только в частных простых случаях, и, как результат, возможность анализа математических моделей, построенных на основе дифференциальных уравнений, обеспечивается при помощи приближенных численных методов решения. Объем выполняемых при этом вычислений обычно является значительным и использование высокопроизводительных вычислительных систем является традиционным для данной области вычислительной математики. Проблематика численного решения дифференциальных уравнений в частных производных является областью интенсивных исследований (см., например, [5,11,19]).

Рассмотрим в качестве учебного примера проблему численного решения задачи Дирихле для уравнения Пуассона, определяемую как задачу нахождения функции u = u ( x, y ), удовлетворяющей в области определения D уравнению и принимающей значения g ( x, y ) на границе D 0 области D ( f и g являются функциями, задаваемыми при постановке задачи). Подобная модель может быть использована для описания установившегося течения жидкости, стационарных тепловых полей, процессов теплопередачи с внутренними источниками тепла и деформации упругих пластин и др. Данный пример часто используется в качестве учебно-практической задачи при изложении возможных способов организации эффективных параллельных вычислений [4, 10, 27].

Для простоты изложения материала в качестве области задания D функции u ( x, y ) далее будет использоваться единичный квадрат 6.1. Последовательные методы решения задачи Дирихле Одним из наиболее распространенных подходов численного решения дифференциальных уравнений является метод конечных разностей (метод сеток) [5,11]. Следуя этому подходу, область решения D представляется в виде дискретного (как правило, равномерного) набора (сетки) точек (узлов). Так, например, прямоугольная сетка в области D может быть задана в виде (рис. 6.1) где величина N задает количество узлов по каждой из координат области D.

Обозначим оцениваемую при подобном дискретном представлении аппроксимацию функции u ( x, y ) в точках ( xi, y j ) через uij. Тогда, используя пятиточечный шаблон (см. рис. 6.1) для вычисления значений производных, уравнение Пуассона может быть представлено в конечноразностной форме Данное уравнение может быть разрешено относительно uij Разностное уравнение, записанное в подобной форме, позволяет определять значение uij по известным значениям функции u ( x, y ) в соседних узлах используемого шаблона. Данный результат служит основой для построения различных итерационных схем решения задачи Дирихле, в которых в начале вычислений формируется некоторое приближение для значений uij, а затем эти значения последовательно уточняются в соответствии с приведенным соотношением. Так, например, метод Гаусса-Зейделя для проведения итераций уточнения использует правило по которому очередное k-ое приближение значения uij вычисляется по последнему k-ому приближению значений u i 1, j и u i, j 1 и предпоследнему (k-1)-ому приближению значений u i +1, j и u i, j +1. Выполнение итераций обычно продолжается до тех пор, пока получаемые в результате итераций изменения значений uij не станут меньше некоторой заданной величины (требуемой точности вычислений). Сходимость описанной процедуры (получение решения с любой желаемой точностью) является предметом всестороннего математического анализа (см., например, [5,11]), здесь же отметим, что последовательность решений, получаемых методом сеток, равномерно сходится к решению задачи Дирихле, а погрешность решения имеет порядок h 2.

Рис. 6.1. Прямоугольная сетка в области D (темные точки представляют внутренние узлы сетки, нумерация узлов в строках слева направо, а в столбцах - сверху вниз).

алгоритмическому языку С++, может быть представлен в виде:

dmax = 0; // максимальное изменение значений u for ( i=1; i eps ); // eps - точность решения Для конкретизации представленных в алгоритме действий введем обозначения:

- ProcNum – номер процессора, на котором выполняются описываемые действия, - PrevProc, NextProc – номера соседних процессоров, содержащих предшествующую и следующую - NP – количество процессоров, - M – количество строк в полосе (без учета продублированных граничных строк), - N – количество внутренних узлов в строке сетки (т.е. всего в строке N+2 узла).

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

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

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

// передача нижней граничной строки следующему // процессору и прием передаваемой строки от // предыдущего процессора if ( ProcNum != NP-1 )Send(u[M][*],N+2,NextProc);

if ( ProcNum != 0 )Receive(u[0][*],N+2,PrevProc);

(для записи процедур приема-передачи используется близкий к стандарту MPI [20] формат, где первый и второй параметры представляют пересылаемые данные и их объем, а третий параметр определяет адресат (для операции Send) или источник (для операции Receive) пересылки данных).

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

Синхронные процедуры передачи, как правило, более просты для использования и более надежны;

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

Приведенная выше последовательность блокирующих операций приема-передачи данных (вначале Send, затем Receive) приводит к строго последовательной схеме выполнения процесса пересылок строк, т.к. все процессоры одновременно обращаются к операции Send и переходят в режим ожидания. Первым процессором, который окажется готовым к приему пересылаемых данных, окажется сервер с номером NP-1. В результате процессор NP-2 выполнит операцию передачи своей граничной строки и перейдет к приему строки от процессора NP-3 и т.д. Общее количество повторений таких операций равно NP-1.

Аналогично происходит выполнение и второй части процедуры пересылки граничных строк перед началом обработки строк (см. рис. 6.11).

Последовательный характер рассмотренных операций пересылок данных определяется выбранным способом очередности выполнения. Изменим этот порядок очередности при помощи чередования приема и передачи для процессоров с четными и нечетными номерами:

// передача нижней граничной строки следующему // процессору и прием передаваемой строки от // предыдущего процессора if ( ProcNum % 2 == 1 ) { // нечетный процессор if ( ProcNum != NP-1 )Send(u[M][*],N+2,NextProc);

if ( ProcNum != 0 )Receive(u[0][*],N+2,PrevProc);

else { // процессор с четным номером if ( ProcNum != 0 )Receive(u[0][*],N+2,PrevProc);

if ( ProcNum != NP-1 )Send(u[M][*],N+2,NextProc);

Данный прием позволяет выполнить все необходимые операции передачи всего за два последовательных шага. На первом шаге все процессоры с нечетными номерами отправляют данные, а процессоры с четными номерами осуществляют прием этих данных. На втором шаге роли процессоров меняются – четные процессоры выполняют Send, нечетные процессоры исполняют операцию приема Receive.

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

Так, в стандарте MPI [21] предусмотрена операция Sendrecv, с использованием которой предыдущий фрагмент программного кода может быть записан более кратко:

// передача нижней граничной строки следующему // процессору и прием передаваемой строки от // предыдущего процессора Sendrecv(u[M][*],N+2,NextProc,u[0][*],N+2,PrevProc);

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

Коллективные операции обмена информацией Для завершения круга вопросов, связанных с параллельной реализацией метода сеток на системах с распределенной памятью, осталось рассмотреть способы вычисления общей для всех процессоров погрешности вычислений. Возможный очевидный подход состоит в передаче всех локальных оценок погрешности, полученный на отдельных полосах сетки, на один какой-либо процессор, вычисления на нем максимального значения и рассылки полученного значения всем процессорам системы. Однако такая схема является крайне неэффективной – количество необходимых операций передачи данных определяется числом процессоров и выполнение этих операций может происходить только в последовательном режиме. Между тем, как показывает анализ требуемых коммуникационных действий, выполнение операций сборки и рассылки данных может быть реализовано с использованием рассмотренной в п. 4.1 пособия каскадной схемы обработки данных. На самом деле, получение максимального значения локальных погрешностей, вычисленных на каждом процессоре, может быть обеспечено, например, путем предварительного нахождения максимальных значений для отдельных пар процессоров (данные вычисления могут выполняться параллельно), затем может быть снова осуществлен попарный поиск максимума среди полученных результатов и т.д. Всего, как полагается по каскадной схеме, необходимо выполнить log2NP параллельных итераций для получения конечного значения (NP – количество процессоров).

Учитывая большую эффективность каскадной схемы для выполнения коллективных операций передачи данных, большинство базовых библиотек параллельных программ содержит процедуры для поддержки подобных действий. Так, в стандарте MPI [21] предусмотрены операции:

- Reduce(dm,dmax,op,proc) – процедура сборки на процессоре proc итогового результата dmax среди локальных на каждом процессоре значений dm с применением операции op, - Broadcast(dmax,proc) – процедура рассылки с процессора proc значения dmax всем имеющимся процессорам системы.

С учетом перечисленных процедур общая схема вычислений на каждом процессоре может быть представлена в следующем виде:

// Алгоритм 6.8 – уточненный вариант // схема Гаусса-Зейделя, ленточное разделение данных // действия, выполняемые на каждом процессоре // обмен граничных строк полос с соседями Sendrecv(u[M][*],N+2,NextProc,u[0][*],N+2,PrevProc);

Sendrecv(u[1][*],N+2,PrevProc,u[M+1][*],N+2,NextProc);

// вычисление общей погрешности вычислений dmax Reduce(dm,dmax,MAX,0);

Broadcast(dmax,0);

} while ( dmax > eps ); // eps - точность решения (в приведенном алгоритме переменная dm представляет локальную погрешность вычислений на отдельном процессоре, параметр MAX задает операцию поиска максимального значения для операции сборки). Следует отметить, что в составе MPI имеется процедура Allreduce, которая совмещает действия редукции и рассылки данных. Результаты экспериментов для данного варианта параллельных вычислений для метода Гаусса-Зейделя приведены в табл. 6.4.

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

Таблица 6.4. Результаты экспериментов для систем с распределенной памятью, ленточная схема разделения данных (p=4) сетки (k – количество итераций, t – время в сек., S – ускорение) В завершение рассмотрим возможность организации параллельных вычислений, при которых обеспечивалось бы нахождение таких же решений задачи Дирихле, что и при использовании исходного последовательного метода Гаусса-Зейделя. Как отмечалось ранее, такой результат может быть получен за счет организации волновой схемы расчетов. Для образования волны вычислений представим логически каждую полосу узлов области расчетов в виде набора блоков (размер блоков можно положить, в частности, равным ширине полосы) и организуем обработку полос поблочно в последовательном порядке (см. рис. 6.12). Тогда для полного повторения действий последовательного алгоритма вычисления могут быть начаты только для первого блока первой полосы узлов; после того, как этот блок будет обработан, для вычислений будут готовы уже два блока – блок 2 первой полосы и блок 1 второй полосы (для обработки блока полосы 2 необходимо передать граничную строку узлов первого блока полосы 1). После обработки указанных блоков к вычислениям будут готовы уже 3 блока и мы получаем знакомый уже процесс волновой обработки данных (результаты экспериментов см. в табл. 6.4).

Рис. 6.12. Организация волны вычислений при ленточной схеме разделения данных Интересной момент при организации подобный схемы параллельных вычислений может состоять в попытке совмещения операций пересылки граничных строк и действий по обработке блоков данных.

Блочная схема разделения данных Ленточная схема разделения данных может быть естественным образом обобщена на блочный способ представления сетки области расчетов (см. рис. 6.9). При этом столь радикальное изменение способа разбиения сетки практически не потребует каких-либо существенных корректировок рассмотренной схемы параллельных вычислений. Основной новый момент при блочном представлении данных состоит в увеличении количества граничных строк на каждом процессоре (для блока их количество становится равным 4), что приводит, соответственно, к большему числу операций передачи данных при обмене граничных строк. Сравнивая затраты на организацию передачи граничных строк, можно отметить, что при ленточной схеме для каждого процессора выполняется 4 операции приемапередачи данных, в каждой из которых пересылается (N+2) значения; для блочного же способа происходит 8 операций пересылки и объем каждого сообщения равен ( N / NP + 2 ) (N – количество внутренних узлов сетки, NP – число процессоров, размер всех блоков предполагается одинаковым). Тем самым, блочная схема представления области расчетов становится оправданной при большом количество узлов сетки области расчетов, когда увеличение количества коммуникационных операций приводит к снижению затрат на пересылку данных в силу сокращения размеров передаваемых сообщений.

Результаты экспериментов при блочной схеме разделения данных приведены в табл. 6.5.

Таблица 6.5. Результаты экспериментов для систем с распределенной памятью, блочная схема разделения данных (p=4) Последовательный Параллельный алгоритм сетки (k – количество итераций, t – время в сек., S – ускорение) При блочном представлении сетки может быть реализован также и волновой метод выполнения расчетов (см. рис. 6.13). Пусть процессоры образуют прямоугольную решетку размером NBxNB ( NB = NP ) и процессоры пронумерованы от 0 слева направо по строкам решетки.

Общая схема параллельных вычислений в этом случае имеет вид:

// схема Гаусса-Зейделя, блочное разделение данных // действия, выполняемые на каждом процессоре // получение граничных узлов if ( ProcNum / NB != 0 ) { // строка не нулевая // получение данных от верхнего процессора Receive(u[0][*],M+2,TopProc); // верхняя строка Receive(dmax,1,TopProc); // погрешность if ( ProcNum % NB != 0 ) { // столбец не нулевой // получение данных от левого процессора Receive(u[*][0],M+2,LeftProc); // левый столбец Receive(dm,1,LeftProc); // погрешность // пересылка граничных узлов if ( ProcNum / NB != NB-1 ) { // строка решетки не // пересылка данных нижнему процессору Send(u[M+1][*],M+2,DownProc); // нижняя строка Send(dmax,1,DownProc); // погрешность if ( ProcNum % NB != NB-1 ) { // столбец решетки // пересылка данных правому процессору Send(u[*][M+1],M+2,RightProc); // правый столбец Send(dmax,1, RightProc); // погрешность // синхронизация и рассылка погрешности dmax Broadcast(dmax,NP-1);

} while ( dmax > eps ); // eps - точность решения (в приведенном алгоритме функция Barrier() представляет операцию коллективной синхронизации, которая завершает свое выполнение только в тот момент, когда все процессоры осуществят вызов этой процедуры).

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

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

рис. 6.13), передав после обработки своего блока граничные данные и запустив, тем самым, вычисления на процессорах 1 и 4, оказывается готовым к исполнению следующей итерации метода Гаусса-Зейделя.

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

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

Пропускная способность наиболее распространенной на данный момент сети Fast Ethernet – Mбит/с, для более современной сети Gigabit Ethernet – 1000 Мбит/с. В то же время, скорость передачи данных в системах с общей памятью обычно составляет сотни и тысячи миллионов байт в секунду. Тем самым, использование систем с распределенной памятью приводит к снижению скорости передачи данных не менее чем в 100 раз.

Еще хуже дело обстоит с латентностью. Для сети Fast Ethernet эта характеристика имеет значений порядка 150 мкс, для сети Gigabit Ethernet – около 100 мкс. Для современных компьютеров с тактовой частотой свыше 2 ГГц/с различие в производительности достигает не менее, чем 10000-100000 раз. При указанных характеристиках вычислительной системы для достижения 90% эффективности в рассматриваемом примере решения задачи Дирихле (т.е. чтобы в ходе расчетов обработка данных занимала не менее 90% времени от общей длительности вычислений и только 10% времени тратилось бы на операции передачи данных) размер блоков вычислительной сетки должен быть не менее N= узлов по вертикали и горизонтали (объем вычислений в блоке составляет 5N2 операций с плавающей запятой).

Как результат, можно заключить, что эффективность параллельных вычислений при использовании распределенной памяти определяется в основном интенсивностью и видом выполняемых коммуникационных операций при взаимодействии процессоров. Необходимый при этом анализ параллельных методов и программ может быть выполнен значительно быстрее за счет выделения типовых операций передачи данных – см. раздел 3 пособия. Так, например, в рассматриваемой учебной задаче решения задачи Дирихле практически все пересылки значений сводятся к стандартным коммуникационным действиям, имеющим адекватную поддержку в стандарте MPI (см. рис. 6.14):

- рассылка количества узлов сетки всем процессорам – типовая операция передачи данных от одного процессора всем процессорам сети (функция MPI_Bcast);

- рассылка полос или блоков узлов сетки всем процессорам – типовая операция передачи разных данных от одного процессора всем процессорам сети (функция MPI_Scatter);

- обмен граничных строк или столбцов сетки между соседними процессорами – типовая операция передачи данных между соседними процессорами сети (функция MPI_Sendrecv);

сетки узлов сетки полос или блоков погрешности вычислений узлов сетки Рис. 6.14. Операции передачи данных при выполнении метода сеток в системе с распределенной памятью - сборка и рассылка погрешности вычислений всем процессорам – типовая операция передачи данных от всех процессоров всем процессорам сети (функция MPI_Allreduce);

- сборка на одном процессоре решения задачи (всех полос или блоков сетки) – типовая операция передачи данных от всех процессоров сети одному процессору (функция MPI_Gather).

ЛИТЕРАТУРА

1. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. - Н.Новгород, ННГУ, 2001.

2. Богачев К.Ю. Основы параллельного программирования. - М.: БИНОМ. Лаборатория знаний, 2003.

3. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002.

4. Немнюгин С., Стесик О. Параллельное программирование для многопроцессорных вычислительных систем — СПб.: БХВ-Петербург, 2002.

5. Березин И.С., Жидков И.П. Методы вычислений. - М.: Наука, 1966.

6. Дейтел Г. Введение в операционные системы. Т.1.- М.: Мир, 1987.

7. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. - М.: Мир, 1981.

8. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: МЦНТО, 1999.

9. Корнеев В.В.. Параллельные вычислительные системы. - М.: Нолидж, 1999.

10. Корнеев В.В. Параллельное программирование в MPI. Москва-Ижевск: Институт компьютерных исследований, 2003.

11. П.Тихонов А.Н., Самарский А.А. Уравнения математической физики. -М.:Наука, 1977.

12. Хамахер К., Вранешич З., Заки С. Организация ЭВМ. - СПб: Питер, 2003.

13. Шоу А. Логическое проектирование операционных систем. - М.: Мир, 1981.

14. Andrews G.R. Foundations of Multithreading, Parallel and Distributed Programming. Addison-Wesley, (русский перевод Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования. - М.: Издательский дом "Вильяме", 2003) 15. Barker, M. (Ed.) (2000). Cluster Computing Whitepaper http://www.dcs.port.ac.uk/~mab/tfcc/WhitePaper/.

16. Braeunnl Т. Parallel Programming. An Introduction.- Prentice Hall, 1996.

17. Chandra, R., Menon, R., Dagum, L., Kohr, D., Maydan, D., McDonald, J. Parallel Programming in OpenMP.

- Morgan Kaufinann Publishers, 18. Dimitri P. Bertsekas, John N. Tsitsiklis. Parallel and Distributed Computation. Numerical Methods. Prentice Hall, Englewood Cliffs, New Jersey, 1989.

19. Fox G.C. et al. Solving Problems on Concurrent Processors. - Prentice Hall, Englewood Cliffs, NJ, 1988.

20. Geist G.A., Beguelin A., Dongarra J., Jiang W., Manchek В., Sunderam V. PVM: Parallel Virtual Machine A User's Guide and Tutorial for Network Parallel Computing. MIT Press, 1994.

21. Group W, Lusk E, Skjellum A. Using MPI. Portable Parallel Programming with the Message-Passing Interface. - MIT Press, 1994.(htp://www.mcs.anl.gov/mpi/index.html) 22. Hockney R. W., Jesshope C.R. Parallel Computers 2. Architecture, Programming and Algorithms. - Adam Hilger, Bristol and Philadelphia, 1988. (русский перевод 1 издания: Р.Xокни, К.Джессхоуп.

Параллельные ЭВМ. Архитектура, программирование и алгоритмы. - М.: Радио и связь, 1986) 23. Kumar V., Grama A., Gupta A., Karypis G. Introduction to Parallel Computing. - The Benjamin/Cummings Publishing Company, Inc., 24. Miller R., Boxer L. A Unified Approach to Sequential and Parallel Algorithms. Prentice Hall, Upper Saddle River, NJ. 2000.

25. Pacheco, S. P. Parallel programming with MPI. Morgan Kaufmann Publishers, San Francisco. 1997.

26. Parallel and Distributed Computing Handbook. / Ed. A.Y. Zomaya. -McGraw-Hill, 1996.

27. Pfister, G. P. In Search of Clusters. Prentice Hall PTR, Upper Saddle River, NJ 1995. (2nd edn., 1998).

28. Quinn M. J. Designing Efficient Algorithms for Parallel Computers. - McGraw-Hill, 1987. 29.Rajkumar Buyya. High Performance Cluster Computing. Volume l: Architectures and Systems. Volume 2:

Programming and Applications. Prentice Hall PTR, Prentice-Hall Inc., 1999. 30.Roosta, S.H. Parallel Processing and Parallel Algorithms: Theory and Computation. Springer-Verlag, NY. 2000.

31. Xu, Z., Hwang, K. Scalable Parallel Computing Technology, Architecture, Programming. McGraw-Hill, Boston. 1998.

32. Wilkinson В., Allen M. Parallel programming. - Prentice Hall, 1999.

Информационные ресурсы сети Интернет 33. Информационно-аналитические материалы по параллельным вычислениям (http://www.parallel.ru) 34. Информационные материалы Центра компьютерного моделирования Нижегородского университета (http://www.software.unn.ac.ru/ccam) 35. Информационные материалы рабочей группы IEEE по кластерным вычислениям (http://www.ieeetfcc.org) 36. Introduction to Parallel Computing (Teaching Course) (http://www.ece.nwu.edu/~choudhar/C58/) 1994.(http://www.mcs.anl.gov/dbpp)