close

Вход

Забыли?

вход по аккаунту

?

ВВС Лабораторная работа №3

код для вставкиСкачать
А.В. Филатов
Лабораторная работа №3
по курсу:
"Высокопроизводительные вычислительные системы"
Решение систем линейных уравнений.
Содержание:
"ВЫСОКОПРОИЗВОДИТЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ"1
1. ВВЕДЕНИЕ.1
Цель лабораторной работы1
Основные характеристики лабораторной работы1
2. МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ЛАБОРАТОРНОЙ РАБОТЕ.2
МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ2
Метод исключения (метод Гаусса)2
Итерационный метод Гаусса-Зейделя5
Итерационный метод Якоби6
Блочный метод7
АЛГОРИТМ ВЫДЕЛЕНИЯ ВЕТВЕЙ НЕЗАВИСИМЫХ ОПЕРАЦИЙ В ПОСЛЕДОВАТЕЛЬНОЙ ПРОГРАММЕ ДЛЯ ЕЁ РАСПАРАЛЛЕЛИВАНИЯ.8
Критерий выделения параллельных ветвей для машин класса МКМД (MIMD)8
3. ЗАДАНИЕ.10
Домашняя подготовка10
Задание в лаборатории10
4. ЛИТЕРАТУРА11
ПРИЛОЖЕНИЕ 1. ВАРИАНТЫ ЗАДАНИЯ11
ПРИЛОЖЕНИЕ 2. СОДЕРЖАНИЕ ОТЧЁТА О ВЫПОЛНЕНИИ ЛАБОРАТОРНОЙ РАБОТЫ.11
ПРИЛОЖЕНИЕ 3. ОСНОВНЫЕ ФУНКЦИИ БИБЛИОТЕКИ MPI.11
1. Введение.
Цель лабораторной работы
Приобретение навыков распараллеливания алгоритмов численных математических методов, широко применяемых при решении научно-технических задач, а, так же приобретение навыков их реализации на высокопроизводительной ВС. Основные характеристики лабораторной работы
В ходе выполнения ЛР, студенты знакомятся с одним из численных методов решения системы линейных уравнений. Дальнейшая работа предусматривает выполнение нескольких этапов подготовки параллельной программы. Сюда входят: 1) Отладка последовательного алгоритма указанного в задании численного метода; 2) Выявление независимых операций и создание параллельного алгоритма этого метода; 3) Написание параллельной программы с использованием библиотеки MPI реализующий данный алгоритм; 4) Подготовка тестовой задачи. Далее, в ходе лабораторной работы, происходит отладка и выполнение программы на кластерной параллельной ВС.
2. Методические указания к лабораторной работе.
Методы решения систем линейных уравнений
Метод исключения (метод Гаусса)
Метод исключения или метод Гаусса является одним из наиболее часто применяемых прямых (не итерационных) методов решения систем линейных уравнений.
Чтобы проиллюстрировать этот метод, рассмотрим сначала систему из трёх уравнений с тремя неизвестными:
{a11x1+a12x2+a13x3
a21x1+a22x2+a23x3
a31x1+a32x2+a33x3=b1,
=b2,
=b3.(3.1)
(3.2)
(3.3) В такой системе по крайней мере один из коэффициентов a11,a22,a33 должен быть отличен от нуля, иначе мы имели бы дело в этих трёх уравнениях только с двумя неизвестными. Если a11=0, то можно переставить уравнения так, чтобы коэффициент при x1 в первом уравнении был отличен от нуля. Очевидно, что перестановка уравнений оставляет систему неизменной: её решение остаётся прежним.
Теперь введём множитель
m2=a21/a11.
Умножим первое уравнение системы (3.1) на m2 и вычтем его из уравнения (3.2). ("Первое" и "второе" уравнения мы берём уже после перестановки, если она была необходима.) Результат вычитания равен:
(a21 - m2a11)x1+(a22 - m2a12)x2+(a23 - m2a13)x3=b2 - m2b1. (3.4)
Но ведь при этом
a21 - m2a11= a21 - (a21/a11)a11=0,
так что x1 исключено из второго уравнения (конечно именно для достижения такого результата и было выбрано значение m2). Определим теперь новые коэффициенты
a'22
a'23
b'2=a22 - m2a12,
=a23 - m2a13,
=b2 - m2b1.Тогда уравнение (3.2) приобретает вид
a'22x2+ a'23x3= b'2.(3.5)
Заменим второе из первоначальных уравнений (3.2) уравнением (3.5) и введём множитель для третьего уравнения
m3=a31/a11.
Умножим первое уравнение на это множитель и вычтем его из третьего. Коэффициент при x1 снова становится нулевым, и третье уравнение приобретает вид
a'32x2+ a'33x3= b'3.(3.6)
Где
a'32
a'33
b'3=a32 - m3a12,
=a33 - m3a13,
=b3 - m3b1. Если теперь в исходной системе уравнений заменить (3.3) на (3.6), то новая система выглядит так:
{a11x1+a12x2+a13x3
a'22x2+ a'23x3
a'32x2+ a'33x3=b1,
=b'2,
=b'3.(3.1)
(3.5)
(3.6) Полученная система уравнений ((3.1)(3.5)(3.6)) полностью эквивалентна исходной системе уравнений ((3.1)(3.2)(3.3)). Нетрудно заметить, что проведённые нами действия позволили исключить из второго и третьего уравнений системы член с переменной x1. Таким образом, два последних уравнения представляют собой систему из двух уравнений с двумя неизвестными; если теперь найти решение этой системы, т.е. определить x2 и x3, то результат можно подставить в первое уравнение и найти x1.
Попытаемся теперь исключить x2 из двух последних уравнений. Если a'22=0, то снова мы переставим уравнения так, чтобы a'22 было отлично от нуля. (Если же a'22=0 и a'32=0, то система вырождена и либо вовсе не имеет решения, либо имеет бесчисленное множество решений.)
Введём новый множитель
m'3=a'32/a'22.
Умножим уравнение (3.5) на m'3 и вычтем его из (3.6). Результат вычитания равен (a'32 - m'3a'22)x2+(a'33 - m'3a'23)x3=b'3 - m'3b'2.
В силу выбора m'3
a'32 - a'3a'22=0.
Полагая
a"33
b"3=a'33 - m'3a'23,
=b'3 - m'3b'2.окончательно получаем
a"33x3=b"3.(3.7)
Уравнение (3.6) можно заменить уравнением (3.7), после чего система уравнений приобретает следующий вид:
{a11x1+a12x2+a13x3
a'22x2+ a'23x3
a"33x3=b1,
=b'2,
=b"3.(3.1)
(3.5)
(3.7)
Такая система уравнений иногда называется треугольной из-за своего внешнего вида.
Теперь, для решения системы уравнений надо определить x3 из (3.7), подставить этот результат в (3.5), определить x2 из (3.5), подставить x2 и x3 в (3.1) и определить x1. Этот процесс, который обычно называется обратной подстановкой, определяется в нашем случае формулами
x3
x2
x1= b"3/a"33,
= (b'2 - a'23x3)/ a'22,
= (b1 - a12x2 - a13x3)/ a11. Таким образом решается система состоящая из трёх линейных уравнений.
Теперь рассмотрим общий случай, когда имеется система из n уравнений с n неизвестными. Обозначим неизвестные через x1, x2, ..., xn и запишем систему уравнений в следующем виде: {
a11x1+a12x2+...+a1nxn
a21x1+a22x2+...+a2nxn
........................................
an1x1+an2x2+...+annxn
=b1,
=b2,
....
=bn.(3.8) Для системы из n уравнений мы должны будем провести n-1 этапов исключения. На каком-то k -м этапе исключения m, a и b подсчитываются по следующим формулам:
m(k-1)i=
a(k)ij=
b(k)i=a(k-1)ik/a(k-1)kk,
a(k-1)ij - m(k-1)ia(k-1)kj,
b(k-1)i - m(k-1)ib(k-1)k.i=k+1,...,n,
j=k,...,n. - где верхний индекс у каждого параметра означает номер этапа, на котором этот параметр подсчитывается.
Необходимо четко представлять себе смысл индексов i, j, и k.
k означает номер того уравнения, которое вычитается из остальных, а так же номер того неизвестного, которое исключается из оставшихся n-k уравнений.
i означает номер уравнения, из которого в данный момент исключается неизвестное.
j означает номер столбца.
При k=n-1 происходит исключение xn-1 из последнего уравнения.
Окончательная треугольная система уравнений записывается следующим образом:
{
a11x1+a12x2+...+a1nxn
a'22x2+...+a'2nxn
........................................
an-1nnxn
=b1,
=b'2,
....
=bn-1n.(3.9) Обратная подстановка для нахождения значений неизвестных задаётся формулами:
xn=
xn-1=
......
xj=b(n-1)n/a(n-1)nn,
(b(n-2)n-1 - a(n-2)n-1,nxn)/ a(n-2)n-1,n-1,
................................
(b(j-1)j - a(j-1)j,nxn- ...- a(j-1)j,j+1xj+1 /a(j-1)j,j. Для j=n-2,n-3,...,1. Итерационный метод Гаусса-Зейделя
В отличие от рассмотренного ранее конечного метода (метода исключения Гаусса), существуют и применяются при расчётах итерационные методы, т.е. методы в которых решение получается путём постепенного итерационного (пошагового) приближения к нему и уточнения результата. Предположим, что у нас есть система, состоящая из трёх линейных уравнений с тремя неизвестными.
{a11x1+a12x2+a13x3
a21x1+a22x2+a23x3
a31x1+a32x2+a33x3=b1,
=b2,
=b3. Предположим a110, a220, a330, и перепишем систему в следующем виде:
x1=
x2=
x3=(b1-a12x2-a13x3)/a11,
(b2-a21x1-a23x3)/a22,
(b3-a31x1-a32x2)/a33.(3.10)
(3.11)
(3.12) Теперь возьмём некоторое первое приближение к решению этой системы, обозначив его через x01, x02, x03. Подставим это решение в (3.10) и вычислим новое значение x1:
x(1)1=(b1-a12x02-a13x03)/a11.
Используя только что вычисленное значение x(1)1 и начальное значение x03, вмчислим из уравнения (3.11) новое значение x2:
x(1)2=(b2-a21x11-a23x03)/a22.
Наконец, используя только что вычисленные значения x(1)1 и x(1)2, найдём из (3.12) новое значение x3:
x(1)3=(b3-a31x11-a32x12)/a33.
Этим заканчивается первая итерация. Теперь можно заменить исходные значения x01, x02, и x03 на x(1)1, x(1)2, x(1)3 и вычислить следующее приближение. В общем случае k-е приближение определяется формулами
{x(k)1=
x(k)2=
x(k)3=(b1-a12x(k-1)2-a13x(k-1)3)/a11,
(b2-a21x(k)1-a23x(k-1)3)/a22,
(b3-a31x(k)1-a32x(k)2)/a33.(3.13) Заметим, что текущие значения неизвестных сразу же используются для последующих вычислений и что, например, нельзя вычислять x(k)2, пока не получено x(k)1. Аналогично этому для вычисления x(k)3 необходимо сначала определить x(k)1 и x(k)2.
Рассмотрим теперь систему (3.14) с n уравнениями и n неизвестными.
{
a11x1+a12x2+...+a1nxn
a21x1+a22x2+...+a2nxn
........................................
an1x1+an2x2+...+annxn
=b1,
=b2,
....
=bn.(3.14) Мы по прежнему полагаем, что диагональные коэффициенты aij отличны от нуля для всех i. Тогда k-е приближение к решению будет задаватся формулой
x(k)i=(bi-ai1x(k)1-...-ai,i-1x(k)i-1 - ai,i+1x(k-1)i+1-...-ainx(k-1)n)/aii, i=1,2,...,n.
Итерационный процесс продолжается до тех пор, пока все x(k)i не станут достаточно близки к x(k-1)i. Критерий близости можно, например, задать в следующем виде:
M(k)=max| x(k)i - x(k-1)i |<,
где определяется максимальное значение разности для всех i, а  -некоторое положительное число. При выполнении критерия итерационный процесс следует остановить. Можно заменить этот критерий близости, сравнивая с  не абсолютные, а относительные разности
max|(x(k)i - x(k-1)i)/ x(k)i|<,
Итерационный метод Якоби
Метод Якоби - метод, в котором решение получается путём постепенного итерационного (пошагового) приближения к нему и уточнения результата. Предположим, что у нас есть система, состоящая из трёх линейных уравнений с тремя неизвестными.
{a11x1+a12x2+a13x3
a21x1+a22x2+a23x3
a31x1+a32x2+a33x3=b1,
=b2,
=b3.(3.15) Предположим a110, a220, a330, и перепишем систему в следующем виде:
x1=
x2=
x3=(b1-a12x2-a13x3)/a11,
(b2-a21x1-a23x3)/a22,
(b3-a31x1-a32x2)/a33.(3.16)
(3.17)
(3.18) Теперь возьмём некоторое первое приближение к решению этой системы, обозначив его через x01, x02, x03. Подставим это решение в (3.16, 3.17,3.18) и вычислим новые значения x1, , x2, x3:
x(1)1=(b1-a12x02-a13x03)/a11;
x(1)2=(b2-a21x01-a23x03)/a22;
x(1)3=(b3-a31x01-a32x02)/a33.
Этим заканчивается первая итерация.
Теперь можно заменить исходные значения x01, x02, и x03 на x(1)1, x(1)2, x(1)3 и вычислить следующее приближение. В общем случае k-е приближение определяется формулами
{x(k)1=
x(k)2=
x(k)3=(b1-a12x(k-1)2-a13x(k-1)3)/a11,
(b2-a21x(k-1)1-a23x(k-1)3)/a22,
(b3-a31x(k-1)1-a32x(k-1)2)/a33.(3.19) Заметим, что текущие значения неизвестных не сразу используются для последующих вычислений и что, например, нельзя вычислять x(k)i, пока не получены все x(k-1). Рассмотрим теперь систему (3.20) с n уравнениями и n неизвестными.
{
a11x1+a12x2+...+a1nxn
a21x1+a22x2+...+a2nxn
........................................
an1x1+an2x2+...+annxn
=b1,
=b2,
....
=bn.(3.20) Мы по прежнему полагаем, что диагональные коэффициенты aij отличны от нуля для всех i. Тогда k-е приближение к решению будет задаваться формулой
x(k)i=(bi-ai1x(k-1)1-...-ai,i-1x(k-1)i-1 - ai,i+1x(k-1)i+1-...-ainx(k-1)n)/aii, i=1,2,...,n.
Итерационный процесс продолжается до тех пор, пока все x(k)i не станут достаточно близки к x(k-1)i. Критерий близости можно, например задать в следующем виде:
M(k)=max| x(k)i - x(k-1)i |<,
где определяется максимальное значение разности для всех i, а  -некоторое положительное число. При выполнении критерия итерационный процесс следует остановить. Можно заменить этот критерий близости, сравнивая с  не абсолютные, а относительные разности
max|(x(k)i - x(k-1)i)/ x(k)i|<,
Блочный метод
Обращение матрицы путём разбиения на клетки.
Пусть имеем матрицу S порядка T, которая разбита на четыре клетки. Будем искать обратную к ней матрицу S-1 также виде клеточной матрицы S =(AB);CD
S-1 =(KL);MN
где A,K,D и N - квадратные матрицы порядков P и Q; P + Q= T.
Согласно требованию SS-1=E и правилу умножения клеточных матриц, должны иметь место следующие матричные равенства:
AK + BM = E; AL + BN = O; CK + DM = O; CL + DN = E;
Разрешая эту систему относительно K,L,M,N, можно получить следующие три набора 3 набора формул для вычисления искомых клеток:
IIIIIIK =(A - BD-1C)-1N =(D - CA-1B)-1K =(A - BD-1C)-1M = -D-1CKL = -A-1BNM = -D-1CKN = (D - CA-1B)-1M = NCA-1L = KBD-1L = -A-1BNK = A-1 - A-1BMN = D-1 - D-1CL Решение систем линейных уравнений методом разбиения на блоки
Пусть имеем систему линейных уравнений, решение которой необходимо свести к последовательности решений подсистем более низкого порядка.
Представим систему линейных уравнений в виде
(A11A12)(X1) = (B1)=>A11X1 + A12X2 = B1}A21A22X2B2A21X1 + A22X2 = B2 где A11, A22 - квадратные матрицы, и хотя бы одна из них невырожденная, X1, X2 -векторы искомых неизвестных для подсистем, B1, B2 - векторы свободных членов.
Решая систему линейных уравнений относительно X1 и X2 получим
{X1 = A11-1 (B1 - A12X2)X2 =( A22 - A21 A11-1 A12)(B2 - A21 A11-1 B1). Алгоритм выделения ветвей независимых операций в последовательной программе для её распараллеливания.
Критерий выделения параллельных ветвей для машин класса МКМД (MIMD)
При распараллеливании последовательного алгоритма, основным критерием при выделении в задаче параллельных является взаимная независимость операций входящих в алгоритм по входным и выходным данным.
Для того, чтобы проиллюстрировать вышесказанное рассмотрим небольшой пример:
Пусть имеется фрагмент текста исходной, последовательной программы.
№ операцийОператоры1
2
3
4
5
6
7A=1;
B=3;
C=8;
D=A+B*5;
X=6/(D*C-2*A);
Y=8*X/B;
Z=4+A+D; Сразу необходимо обратить ваше внимание на то, что в правой колонке написаны операторы, а в левой колонке номера операций. В действительности, при распараллеливании, всегда распараллеливаются операции, а не операторы. В нашем случае, ввиду отсутствия циклов и других управляющих операторов, номера операторов и операций совпадают. Определим теперь исходя из критерия взаимонезависимости по данным, какие из операций могут выполнятся параллельно, а какие нет. Для этого просто составим таблицу использования данных.
Таблица 3.1
ПеременнаяНомера операций1234567AOIIIBOIICOIDOIIXOIYOZO -где I-означает что переменная является входной, а O-выходной в данной операции.
Для того чтобы выделить параллельные ветви в нашем фрагменте программы, надо определить взаимозависимость операций по данным. Во первых, параллельно не могут выполнятся операции где одни и те же переменные создаются (являются выходными) и используются (являются входными). Например: операции 2 и 4. Во вторых, при любом раскладе, данные не могут быть использованы до того, как они были инициализированы. Последнее условие влияет на распределение операций по ярусам графа ЯПФ. Все эти условия можно учесть, используя таблицу 3.1. Например: операция 5 может идти только после операции 2 из-за использования переменной B в операции 4 при вычислении D.
Ниже представлен получившийся граф ЯПФ фрагмента нашей программы (см. рис 3.1).
Рис. 3.1. Граф ЯПФ В действительности, дело с выявлением параллельных ветвей обстоит не так уж просто. Достаточно вспомнить "многокилометровые" программные тексты с множеством условных операторов, циклов и многомерных структур данных. Далее, в следующем пункте, приведено более подробное описание критерия выделения параллельных ветвей в программе и описание алгоритма автоматизации этого процесса. 3. Задание.
Домашняя подготовка
1) Каждой бригаде, по варианту (журнал ЛР по курсу ВВС), необходимо получить один из численных методов решения системы линейных уравнений (см. приложение 1) для дальнейшей реализации в параллельном режиме на MPI. 2) Написать последовательную программу, реализующую данный метод. 3) Полученная программа должна удовлетворять следующим условиям:
* Программы должна быть написана на языке Си.
* Программы должна чётко реализовывать алгоритм указанного метода.
* Программа должна позволять обсчитывать системы различной размерности (любое число, но не более 200 уравнений в системе). * Все входные данные должны считываться программой только из файла входных данных, а все выходные данные должны выводиться только в файл выходных данных.
* В программе должны быть предусмотрены возможности аварийного выхода с оповещением в случае, если нет возможности получения решения в виду вырожденности системы уравнений, отсутствии корней уравнений или достижения предельно заданного числа итераций.
4) Отладить программу на ПЭВМ. Создать набор тестовых задач с различным числом уравнений в системе и различным набором коэффициентов. Для этого необходимо создать несколько файлов входных данных.
5) Выявить в алгоритме независимые (по данным) операции и составить граф задачи в ярусно-параллельной форме (ЯПФ).
6) Продумать и составить алгоритм параллельной реализации решения системы линейных уравнений при различном числе процессоров. 7) Используя библиотеку функций MPI (для Си), написать программу реализующую разработанный параллельный алгоритм.
8) Параллельная программа должна удовлетворять следующим условиям:
* Программа должна быть масштабируемой (для различного числа параллельных процессов).
* В текст программы необходимо включить вызовы функции MPI_Wtime (см. приложение 2), для замера времени выполнения расчётов.
9) Составить отчёт о выполнении ЛР (см. приложение 2).
10) Подготовить исходные тексты последовательной и параллельной программ, а, так же файлы входных данных тестовых задач для выполнения задания в лаборатории.
Задание в лаборатории
1) Выполнить на ПК последовательную программу (без функций MPI) реализующую вариант задания.
2) Выполнить на ПК программу (с функциями MPI), с запуском одного процесса и с различным размером системы уравнений.
3) Выполнить на ПК программу (с функциями MPI), с запуском нескольких процессов и с различным размером системы уравнений. 4) Показать работающие программы преподавателю.
5) Выполнить пункты 2) и 3) на кластерной системе с замером времени выполнения.
Содержание отчёта смотрите в приложении 2.
4. Литература
1) Д. Мак-Кракен, У. Дорн. Численные методы и программирование на Фортране. -М.: Изд-во "МИР", 1977. г. -585 с..
2) Коношенко М.П. Параллельные вычисления. -М.: Изд-во МЭИ, 1995. г. -82 с..
3) Илья Евсеев. MPI для начинающих http://www.csa.ru/ 4) Илья Евсеев. MPI программный инструмент для параллельных вычислений http://www.csa.ru/
5) Воеводин Вл.В. Курс лекций: "Параллельная обработка данных" http://parallel.ru/vvv/index.html
6) Ортега
7) Шамаева
Приложение 1. Варианты задания
№№ бригадМетоды1,5,9Блочный.2,6,10Исключения (Гауса).3,7,11Якоби4,8,12Гауса-Зейделя Приложение 2. Содержание отчёта о выполнении лабораторной работы.
1) Титульный лист, Ф.И.О. студентов, номер группы и номер бригады.
2) Текст задания.
3) Блок-схема последовательного алгоритма.
4) Текст последовательной программы с комментариями. 5) Спецификация данных.
6) Набор тестовых заданий.
7) Результат выполнения на ПК (без библиотеки MPI).
8) Граф ЯПФ параллельного решения задачи.
9) Блок-схема параллельного алгоритма.
10) Текст параллельной MPI программы с комментариями.
11) Таблицы результатов эксперимента (зависимости , ).
12) Зависимости времени вычисления от размерности системы уравнений и числа задействованных процессоров кластерной ВС. 13) Относительные и абсолютные коэффициенты ускорения. 14) Выводы. Приложение 3. Основные функции библиотеки MPI.
В данном приложении описаны некоторые из основных функций библиотеки MPI. Описания функций и комментарии взяты из [5].
При описании процедур MPI будем пользоваться словом OUT для обозначения "выходных" параметров, т.е. таких параметров, через которые процедура возвращает результаты. Общие процедуры MPI
int MPI_Init( int* argc, char*** argv) MPI_Init - инициализация параллельной части приложения. Реальная инициализация для каждого приложения выполняется не более одного раза, а если MPI уже был инициализирован, то никакие действия не выполняются и происходит немедленный возврат из подпрограммы. Все оставшиеся MPI-процедуры могут быть вызваны только после вызова MPI_Init. Возвращает: в случае успешного выполнения - MPI_SUCCESS, иначе - код ошибки. (То же самое возвращают и все остальные функции, рассматриваемые в данном руководстве.) int MPI_Finalize( void ) MPI_Finalize - завершение параллельной части приложения. Все последующие обращения к любым MPI-процедурам, в том числе к MPI_Init, запрещены. К моменту вызова MPI_Finalize некоторым процессом все действия, требующие его участия в обмене сообщениями, должны быть завершены. Сложный тип аргументов MPI_Init предусмотрен для того, чтобы передавать всем процессам аргументы main:
int main(int argc, char** argv)
{
MPI_Init(&argc, &argv);
...
MPI_Finalize();
}
int MPI_Comm_size( MPI_Comm comm, int* size) Определение общего числа параллельных процессов в группе comm. comm - идентификатор группы OUT size - размер группы int MPI_Comm_rank( MPI_comm comm, int* rank) Определение номера процесса в группе comm. Значение, возвращаемое по адресу &rank, лежит в диапазоне от 0 до size_of_group-1. comm - идентификатор группы OUT rank - номер вызывающего процесса в группе comm double MPI_Wtime(void) Функция возвращает астрономическое время в секундах (вещественное число), прошедшее с некоторого момента в прошлом. Гарантируется, что этот момент не будет изменен за время существования процесса. Прием/передача сообщений между отдельными процессами
Прием/передача сообщений с блокировкой
int MPI_Send(void* buf, int count, MPI_Datatype datatype, int dest, int msgtag, MPI_Comm comm) buf - адрес начала буфера посылки сообщения count - число передаваемых элементов в сообщении datatype - тип передаваемых элементов dest - номер процесса-получателя msgtag - идентификатор сообщения comm - идентификатор группы Блокирующая посылка сообщения с идентификатором msgtag, состоящего из count элементов типа datatype, процессу с номером dest. Все элементы сообщения расположены подряд в буфере buf. Значение count может быть нулем. Тип передаваемых элементов datatype должен указываться с помощью предопределенных констант типа. Разрешается передавать сообщение самому себе. Блокировка гарантирует корректность повторного использования всех параметров после возврата из подпрограммы. Выбор способа осуществления этой гарантии: копирование в промежуточный буфер или непосредственная передача процессу dest, остается за MPI. Следует специально отметить, что возврат из подпрограммы MPI_Send не означает ни того, что сообщение уже передано процессу dest, ни того, что сообщение покинуло процессорный элемент, на котором выполняется процесс, выполнивший MPI_Send. int MPI_Recv(void* buf, int count, MPI_Datatype datatype, int source, int msgtag, MPI_comm comm, MPI_Status *status) OUT buf - адрес начала буфера приема сообщения count - максимальное число элементов в принимаемом сообщении datatype - тип элементов принимаемого сообщения source - номер процесса-отправителя msgtag - идентификатор принимаемого сообщения comm - идентификатор группы OUT status - параметры принятого сообщения Прием сообщения с идентификатором msgtag от процесса source с блокировкой. Число элементов в принимаемом сообщении не должно превосходить значения count. Если число принятых элементов меньше значения count, то гарантируется, что в буфере buf изменятся только элементы, соответствующие элементам принятого сообщения. Если нужно узнать точное число элементов в сообщении, то можно воспользоваться подпрограммой MPI_Probe. Блокировка гарантирует, что после возврата из подпрограммы все элементы сообщения приняты и расположены в буфере buf. В качестве номера процесса-отправителя можно указать предопределенную константу MPI_ANY_SOURCE - признак того, что подходит сообщение от любого процесса. В качестве идентификатора принимаемого сообщения можно указать константу MPI_ANY_TAG - признак того, что подходит сообщение с любым идентификатором. Если процесс посылает два сообщения другому процессу и оба эти сообщения соответствуют одному и тому же вызову MPI_Recv, то первым будет принято то сообщение, которое было отправлено раньше. int MPI_Get_Count( MPI_Status *status, MPI_Datatype datatype, int *count) status - параметры принятого сообщения datatype - тип элементов принятого сообщения OUT count - число элементов сообщения По значению параметра status данная подпрограмма определяет число уже принятых (после обращения к MPI_Recv) или принимаемых (после обращения к MPI_Probe или MPI_IProbe) элементов сообщения типа datatype. int MPI_Probe( int source, int msgtag, MPI_Comm comm, MPI_Status *status) source - номер процесса-отправителя или MPI_ANY_SOURCE msgtag - идентификатор ожидаемого сообщения или MPI_ANY_TAG comm - идентификатор группы OUT status - параметры обнаруженного сообщения Получение информации о структуре ожидаемого сообщения с блокировкой. Возврата из подпрограммы не произойдет до тех пор, пока сообщение с подходящим идентификатором и номером процесса-отправителя не будет доступно для получения. Атрибуты доступного сообщения можно определить обычным образом с помощью параметра status. Следует обратить внимание, что подпрограмма определяет только факт прихода сообщения, но реально его не принимает. Прием/передача сообщений без блокировки
int MPI_Isend(void *buf, int count, MPI_Datatype datatype, int dest, int msgtag, MPI_Comm comm, MPI_Request *request) buf - адрес начала буфера посылки сообщения count - число передаваемых элементов в сообщении datatype - тип передаваемых элементов dest - номер процесса-получателя msgtag - идентификатор сообщения comm - идентификатор группы OUT request - идентификатор асинхронной передачи Передача сообщения, аналогичная MPI_Send, однако возврат из подпрограммы происходит сразу после инициализации процесса передачи без ожидания обработки всего сообщения, находящегося в буфере buf. Это означает, что нельзя повторно использовать данный буфер для других целей без получения дополнительной информации о завершении данной посылки. Окончание процесса передачи (т.е. того момента, когда можно переиспользовать буфер buf без опасения испортить передаваемое сообщение) можно определить с помощью параметра request и процедур MPI_Wait и MPI_Test. Сообщение, отправленное любой из процедур MPI_Send и MPI_ISend, может быть принято любой из процедур MPI_Recv и MPI_IRecv. int MPI_Irecv(void *buf, int count, MPI_Datatype datatype, int source, int msgtag, MPI_comm comm, MPI_Request *request) OUT buf - адрес начала буфера приема сообщения count - максимальное число элементов в принимаемом сообщении datatype - тип элементов принимаемого сообщения source - номер процесса-отправителя msgtag - идентификатор принимаемого сообщения comm - идентификатор группы OUT request - идентификатор асинхронного приема сообщения Прием сообщения, аналогичный MPI_Recv, однако возврат из подпрограммы происходит сразу после инициализации процесса приема без ожидания получения сообщения в буфере buf. Окончание процесса приема можно определить с помощью параметра request и процедур MPI_Wait и MPI_Test. int MPI_Wait( MPI_Request *request, MPI_Status *status) request - идентификатор асинхронного приема или передачи OUT status - параметры сообщения Ожидание завершения асинхронных процедур MPI_ISend или MPI_IRecv, ассоциированных с идентификатором request. В случае приема, атрибуты и длину полученного сообщения можно определить обычным образом с помощью параметра status. int MPI_WaitAll( int count, MPI_Request *requests, MPI_Status *statuses) count - число идентификаторов requests - массив идентификаторов асинхронного приема или передачи OUT statuses - параметры сообщений Выполнение процесса блокируется до тех пор, пока все операции обмена, ассоциированные с указанными идентификаторами, не будут завершены. Если во время одной или нескольких операций обмена возникли ошибки, то поле ошибки в элементах массива statuses будет установлено в соответствующее значение. int MPI_WaitAny( int count, MPI_Request *requests, int *index, MPI_Status *status) count - число идентификаторов requests - массив идентификаторов асинхронного приема или передачи OUT index - номер завершенной операции обмена OUT status - параметры сообщений Выполнение процесса блокируется до тех пор, пока какая-либо операция обмена, ассоциированная с указанными идентификаторами, не будет завершена. Если несколько операций могут быть завершены, то случайным образом выбирается одна из них. Параметр index содержит номер элемента в массиве requests, содержащего идентификатор завершенной операции. int MPI_WaitSome( int incount, MPI_Request *requests, int *outcount, int *indexes, MPI_Status *statuses) incount - число идентификаторов requests - массив идентификаторов асинхронного приема или передачи OUT outcount - число идентификаторов завершившихся операций обмена OUT indexes - массив номеров завершившихся операции обмена OUT statuses - параметры завершившихся сообщений Выполнение процесса блокируется до тех пор, пока по крайней мере одна из операций обмена, ассоциированных с указанными идентификаторами, не будет завершена. Параметр outcount содержит число завершенных операций, а первые outcount элементов массива indexes содержат номера элементов массива requests с их идентификаторами. Первые outcount элементов массива statuses содержат параметры завершенных операций. int MPI_Test( MPI_Request *request, int *flag, MPI_Status *status) request - идентификатор асинхронного приема или передачи OUT flag - признак завершенности операции обмена OUT status - параметры сообщения Проверка завершенности асинхронных процедур MPI_ISend или MPI_IRecv, ассоциированных с идентификатором request. В параметре flag возвращает значение 1, если соответствующая операция завершена, и значение 0 в противном случае. Если завершена процедура приема, то атрибуты и длину полученного сообщения можно определить обычным образом с помощью параметра status. int MPI_TestAll( int count, MPI_Request *requests, int *flag, MPI_STatus *statuses) count - число идентификаторов requests - массив идентификаторов асинхронного приема или передачи OUT flag - признак завершенности операций обмена OUT statuses - параметры сообщений
В параметре flag возвращает значение 1, если все операции, ассоциированные с указанными идентификаторами, завершены (с указанием параметров сообщений в массиве statuses). В противном случае возвращается 0, а элементы массива statuses неопределены. int MPI_TestAny(int count, MPI_Request *requests, int *index, int *flag, MPI_Status *status) count - число идентификаторов requests - массив идентификаторов асинхронного приема или передачи OUT index - номер завершенной операции обмена OUT flag - признак завершенности операции обмена OUT status - параметры сообщения Если к моменту вызова подпрограммы хотя бы одна из операций обмена завершилась, то в параметре flag возвращается значение 1, index содержит номер соответствующего элемента в массиве requests, а status - параметры сообщения. int MPI_TestSome( int incount, MPI_Request *requests, int *outcount, int *indexes, MPI_Status *statuses) incount - число идентификаторов requests - массив идентификаторов асинхронного приема или передачи OUT outcount - число идентификаторов завершившихся операций обмена OUT indexes - массив номеров завершившихся операции обмена OUT statuses - параметры завершившихся операций Данная подпрограмма работает так же, как и MPI_WaitSome, за исключением того, что возврат происходит немедленно. Если ни одна из указанных операций не завершилась, то значение outcount будет равно нулю. int MPI_Iprobe( int source, int msgtag, MPI_Comm comm, int *flag, MPI_Status *status) source - номер процесса-отправителя или MPI_ANY_SOURCE msgtag - идентификатор ожидаемого сообщения или MPI_ANY_TAG comm - идентификатор группы OUT flag - признак завершенности операции обмена OUT status - параметры обнаруженного сообщения Получение информации о поступлении и структуре ожидаемого сообщения без блокировки. В параметре flag возвращает значение 1, если сообщение с подходящими атрибутами уже может быть принято (в этом случае ее действие полностью аналогично MPI_Probe), и значение 0, если сообщения с указанными атрибутами еще нет. Объединение запросов на взаимодействие
Процедуры данной группы позволяют снизить накладные расходы, возникающие в рамках одного процессора при обработке приема/передачи и перемещении необходимой информации между процессом и сетевым контроллером. Несколько запросов на прием и/или передачу могут объединяться вместе для того, чтобы далее их можно было бы запустить одной командой. Способ приема сообщения никак не зависит от способа его посылки: сообщение, отправленное с помощью объединения запросов либо обычным способом, может быть принято как обычным способом, так и с помощью объединения запросов. int MPI_Send_Init( void *buf, int count, MPI_Datatype datatype, int dest, int msgtag, MPI_Comm comm, MPI_Request *request) buf - адрес начала буфера посылки сообщения count - число передаваемых элементов в сообщении datatype - тип передаваемых элементов dest - номер процесса-получателя msgtag - идентификатор сообщения comm - идентификатор группы OUT request - идентификатор асинхронной передачи Формирование запроса на выполнение пересылки данных. Все параметры точно такие же, как и у подпрограммы MPI_Isend, однако в отличие от нее пересылка не начинается до вызова подпрограммы MPI_StartAll. int MPI_Recv_Init( void *buf, int count, MPI_Datatype datatype, int source, int msgtag, MPI_Comm comm, MPI_Request *request) OUT buf - адрес начала буфера приема сообщения count - число принимаемых элементов в сообщении datatype - тип принимаемых элементов source - номер процесса-отправителя msgtag - идентификатор сообщения comm - идентификатор группы OUT request - идентификатор асинхронного приема Формирование запроса на выполнение приема данных. Все параметры точно такие же, как и у подпрограммы MPI_Irecv, однако в отличие от нее реальный прием не начинается до вызова подпрограммы MPI_StartAll. MPI_Start_All( int count, MPI_Request *requests) count - число запросов на взаимодействие OUT requests - массив идентификаторов приема/передачи Запуск всех отложенных взаимодействий, ассоциированных вызовами подпрограмм MPI_Send_Init и MPI_Recv_Init с элементами массива запросов requests. Все взаимодействия запускаются в режиме без блокировки, а их завершение можно определить обычным образом с помощью процедур MPI_Wait и MPI_Test. Совмещенные прием/передача сообщений
int MPI_Sendrecv( void *sbuf, int scount, MPI_Datatype stype, int dest, int stag, void *rbuf, int rcount, MPI_Datatype rtype, int source, MPI_Datatype rtag, MPI_Comm comm, MPI_Status *status) sbuf - адрес начала буфера посылки сообщения scount - число передаваемых элементов в сообщении stype - тип передаваемых элементов dest - номер процесса-получателя stag - идентификатор посылаемого сообщения OUT rbuf - адрес начала буфера приема сообщения rcount - число принимаемых элементов сообщения rtype - тип принимаемых элементов source - номер процесса-отправителя rtag - идентификатор принимаемого сообщения comm - идентификатор группы OUT status - параметры принятого сообщения Данная операция объединяет в едином запросе посылку и прием сообщений. Принимающий и отправляющий процессы могут являться одним и тем же процессом. Сообщение, отправленное операцией MPI_Sendrecv, может быть принято обычным образом, и точно также операция MPI_Sendrecv может принять сообщение, отправленное обычной операцией MPI_Send. Буфера приема и посылки обязательно должны быть различными. Коллективные взаимодействия процессов
В операциях коллективного взаимодействия процессов участвуют все процессы коммуникатора. Соответствующая процедура должна быть вызвана каждым процессом, быть может, со своим набором параметров. Возврат из процедуры коллективного взаимодействия может произойти в тот момент, когда участие процесса в данной операции уже закончено. Как и для блокирующих процедур, возврат означает то, что разрешен свободный доступ к буферу приема или посылки, но не означает ни того, что операция завершена другими процессами, ни даже того, что она ими начата (если это возможно по смыслу операции). int MPI_Bcast(void *buf, int count, MPI_Datatype datatype, int source, MPI_Comm comm) OUT buf - адрес начала буфера посылки сообщения count - число передаваемых элементов в сообщении datatype - тип передаваемых элементов source - номер рассылающего процесса comm - идентификатор группы Рассылка сообщения от процесса source всем процессам, включая рассылающий процесс. При возврате из процедуры содержимое буфера buf процесса source будет скопировано в локальный буфер процесса. Значения параметров count, datatype и source должны быть одинаковыми у всех процессов. int MPI_Gather( void *sbuf, int scount, MPI_Datatype stype, void *rbuf, int rcount, MPI_Datatype rtype, int dest, MPI_Comm comm) sbuf - адрес начала буфера посылки scount - число элементов в посылаемом сообщении stype - тип элементов отсылаемого сообщения OUT rbuf - адрес начала буфера сборки данных rcount - число элементов в принимаемом сообщении rtype - тип элементов принимаемого сообщения dest - номер процесса, на котором происходит сборка данных comm - идентификатор группы OUT ierror - код ошибки Сборка данных со всех процессов в буфере rbuf процесса dest. Каждый процесс, включая dest, посылает содержимое своего буфера sbuf процессу dest. Собирающий процесс сохраняет данные в буфере rbuf, располагая их в порядке возрастания номеров процессов. Параметр rbuf имеет значение только на собирающем процессе и на остальных игнорируется, значения параметров count, datatype и dest должны быть одинаковыми у всех процессов. int MPI_AllReduce( void *sbuf, void *rbuf, int count, MPI_Datatype datatype, MPI_Op op, MPI_Comm comm) sbuf - адрес начала буфера для аргументов OUT rbuf - адрес начала буфера для результата count - число аргументов у каждого процесса datatype - тип аргументов op - идентификатор глобальной операции comm - идентификатор группы Выполнение count глобальных операций op с возвратом count результатов во всех процессах в буфере rbuf. Операция выполняется независимо над соответствующими аргументами всех процессов. Значения параметров count и datatype у всех процессов должны быть одинаковыми. Из соображений эффективности реализации предполагается, что операция op обладает свойствами ассоциативности и коммутативности. int MPI_Reduce( void *sbuf, void *rbuf, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm) sbuf - адрес начала буфера для аргументов OUT rbuf - адрес начала буфера для результата count - число аргументов у каждого процесса datatype - тип аргументов op - идентификатор глобальной операции root - процесс-получатель результата comm - идентификатор группы Функция аналогична предыдущей, но результат будет записан в буфер rbuf только у процесса root. Синхронизация процессов
int MPI_Barrier( MPI_Comm comm) comm - идентификатор группы Блокирует работу процессов, вызвавших данную процедуру, до тех пор, пока все оставшиеся процессы группы comm также не выполнят эту процедуру. Работа с группами процессов
int MPI_Comm_Split( MPI_Comm comm, int color, int key, MPI_Comm *newcomm) comm - идентификатор группы color - признак разделения на группы key - параметр, определяющий нумерацию в новых группах OUT newcomm - идентификатор новой группы Данная процедура разбивает все множество процессов, входящих в группу comm, на непересекающиеся подгруппы - одну подгруппу на каждое значение параметра color (неотрицательное число). Каждая новая подгруппа содержит все процессы одного цвета. Если в качестве color указано значение MPI_UNDEFINED, то в newcomm будет возвращено значение MPI_COMM_NULL. int MPI_Comm_Free( MPI_Comm comm) OUT comm - идентификатор группы Уничтожает группу, ассоциированную с идентификатором comm, который после возвращения устанавливается в MPI_COMM_NULL. Предопределенные константы
Предопределенные константы типа элементов сообщений
Константы MPI Тип в C MPI_CHAR signed char MPI_SHORT signed int MPI_INT signed int MPI_LONG signed long int MPI_UNSIGNED_CHAR unsigned char MPI_UNSIGNED_SHORT unsigned int MPI_UNSIGNED unsigned int MPI_UNSIGNED_LONG unsigned long int MPI_FLOAT float MPI_DOUBLE double MPI_LONG_DOUBLE long double Другие предопределенные типы MPI_Status - структура; атрибуты сообщений; содержит три обязательных поля: MPI_Source (номер процесса отправителя) MPI_Tag (идентификатор сообщения) MPI_Error (код ошибки) MPI_Request - системный тип; идентификатор операции посылки-приема сообщения MPI_Comm - системный тип; идентификатор группы (коммуникатора) MPI_COMM_WORLD - зарезервированный идентификатор группы, состоящей их всех процессов приложения Константы-пустышки MPI_COMM_NULL MPI_DATATYPE_NULL MPI_REQUEST_NULL Константа неопределенного значения MPI_UNDEFINED Глобальные операции MPI_MAX MPI_MIN MPI_SUM MPI_PROD Любой процесс/идентификатор MPI_ANY_SOURCE MPI_ANY_TAG Код успешного завершения процедуры MPI_SUCCESS 1
Документ
Категория
Рефераты
Просмотров
19
Размер файла
195 Кб
Теги
ввс, работа, лабораторная
1/--страниц
Пожаловаться на содержимое документа